木块问题(The Blocks Problem,Uva 101)

不定长数组:vector

vector就是一个不定长数组。不仅如此,它把一些常用操作“封装”在了vector类型内部。 例如,若a是一个vector,可以用a.size( )读取它的大小,a.resize( )改变大小,a.push_back( )向 尾部添加元素,a.pop_back( )删除最后一个元素。

vector是一个模板类,所以需要用vectora或者vectorb这样的方式来声明一 个vector。Vector是一个类似于inta[]的整数数组,而vector就是一个类似于 stringa[ ]的字符串数组。vector看上去像是“一等公民”,因为它们可以直接赋值,还可以作为 函数的参数或者返回值,而无须像传递数组那样另外用一个变量指定元素个数。(n=strlen(a);)

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

木块问题(The Blocks Problem,Uva 101)

从左到右有n个木块,编号为0~n-1,要求模拟以下4种操作(下面的a和b都是木块编 号)。

  • move a onto b: 把a和b上方的木块全部放回初始的位置,然后把a放到b上面
  • move a over b: 把a上方的木块全部放回初始的位置,然后把a放在b所在木块堆的最上方
  • pile a onto b: 把b上方的木块部放回初始的位置,然后把a和a上面所有的木块整体放到b上面
  • pile a over b: 把a和a上面所有的木块整体放在b所在木块堆的最上方

一组数据的结束标志为"quit",如果有非法指令(a和b在同一堆),应当忽略。

输出:所有操作输入完毕后,从左到右,从下到上输出每个位置的木块编号。

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;
int n;
vector<int> pile[];
void find_block(int x,int &xp,int &j){
for(int i=;i<n;i++){
for(j=;j<pile[i].size();j++){
if(pile[i][j]==x) {
xp=i;
return;
}
}
}
}
//把第p堆高度为h的木块上方的所有木块移回原位
void clear_above(int p,int h){
for(int i=h+;i<pile[p].size();i++){
int x=pile[p][i];
pile[x].push_back(x);
}
pile[p].resize(h+);
}
//把第p堆高度为h及其上方的木块整体移动到p2 堆的顶部
void pile_onto(int p,int h,int p2){
for(int i=h;i<pile[p].size();i++){
pile[p2].push_back(pile[p][i]);
}
pile[p].resize(h);
}
//print
void print(){
for(int i=;i<n;i++){
printf("%d:",i);
for(int j=;j<pile[i].size();j++) printf(" %d",pile[i][j]);
printf("\n");
}
}
int main(){
int a,b;
string s1,s2;
cin>>n;
for(int i=;i<n;i++) pile[i].push_back(i);
while(){
cin>>s1;
if(!s1.compare("quit")) break;
cin>>a>>s2>>b;
int pa,pb,ha,hb;
find_block(a,pa,ha);
find_block(b,pb,hb);
if(pa==pb) continue;//在同一堆,忽略
if(!s2.compare("onto")) clear_above(pb,hb);
if(!s1.compare("move")) clear_above(pa,ha);
pile_onto(pa,ha,pb);
}
print();
return ;
}

数据结构的核心是vectorpile[maxn],所有操作都是围绕它进行的。vector就像一个 二维数组,只是第一维的大小是固定的(不超过maxn),但第二维的大小不固定。上述代码 还有一个值得学习的技巧:输入一共有4种指令,但如果完全独立地处理各指令,代码就会 变得冗长而且易错。更好的方法是提取出指令之间的共同点,编写函数以减少重复代码。

vector头文件中的vector是一个不定长数组,可以用clear( )清空,resize( ) 改变大小,用push_back( )和pop_back( )在尾部添加和删除元素,用empty( )测试是否为 空。vector之间可以直接赋值或者作为函数的返回值,像是“一等公民”一样。

上一篇:拜占庭将军问题(Byzantine Generals Problem),一个关于分布式系统容错问题故事


下一篇:ios app的版本号