C++ 汉诺塔程序实现

2017-01-11 15:23:16来源:oschina作者:元禛慎独人点击

第七城市

首先不看代码,汉诺塔解题步骤有三步(设A->C),先将汉诺塔看成两部分n-1,1(n-1在上面) 第一:将A中的n-1个盘借助C移到B ===>Hanoi(n-1,a,c,b); 第二:将A中的最下面的那一个移到C===>move(a,c); 第三:将B中的盘借助A移到C.===>Hanoi(n-1,b,a,c);


###################################################


yuanzhen@ubuntu:~/C_script$ cat myhanno.cpp #include #include #include #include


using std::vector; using std::cout; using std::endl; using std::cin; using std::map; using std::make_pair;


typedef map CharMap;


vector > vec; CharMap colm;


CharMap init_map()//用于根据字符以确定将移动的 起始列和目的列 { CharMap mymap; mymap.insert(make_pair('A',0)); mymap.insert(make_pair('B',1)); mymap.insert(make_pair('C',2)); return mymap; }


void show(vector > veca) //用于呈现容器vector { cout <<"A" << "/t" << "B" << "/t" << "C" << endl; cout << "---------------------" << endl; vector >::const_iterator vec_it; vector::const_iterator it; for(vec_it=veca.begin(); vec_it!=veca.end();++vec_it) { for (it=(*vec_it).begin();it!=(*vec_it).end();++it) {std::cout << *it << "/t"; } std::cout << std::endl; } }


int start_row_num(vector > tvec, char A)//用于确定移动其实字符所属的行数 { int i=0; int col=colm[A]; vector >::const_iterator cit; for(cit=tvec.begin();cit != tvec.end();++cit) { //cout << (*cit)[0] << endl; if((*cit)[col]!=0)return i; i++; } }


int dest_row_num(vector > tvec, char C) //用于确定移动目标字符所属的行数 { int i=0; int col=colm[C]; vector >::const_iterator cit; for(cit=tvec.begin(); cit!=tvec.end();++cit) { //cout <<"a" << endl; if((*cit)[col]!=0)return i-1; i++; } return i-1; }


void move(char A, char C)//根据算法结果来改变 vector,而在本程序中的改变就是交换A列的


//第一个非零数字和C列的最后一个0数字 { int start_x=start_row_num(vec,A); int start_y=colm[A]; int dest_x=dest_row_num(vec,C); int dest_y=colm[C];


//cout << "(" << start_x << "," << start_y << ")" << "(" << dest_x << "," << dest_y << ")" << endl; int temp=vec[start_x][start_y]; vec[start_x][start_y]=vec[dest_x][dest_y]; vec[dest_x][dest_y]=temp; cout << endl; cout << endl; cout << A << "--------------->" << C << endl; cout << endl; show(vec); }


void hanno(int n, char A, char B, char C)//汉诺塔算法使用递归方法实现的(但是此方法应该不是最快的实现方式,但确实最容易理解的方式) { if(n==1)move(A,C); else { hanno(n-1, A, C, B); move(A,C); hanno(n-1, B, A, C);


} }


vector > init(int n)//根据输入的 n 来初始化vector { vector > veca(n, vector (3,0)); vector >::iterator vec_it; int i=0; for(vec_it=veca.begin(); vec_it!=veca.end();++vec_it) { *(*vec_it).begin()=i; i++; } return veca; }


int main(void) { int n; cin >> n; system("clear"); vec=init(n+1); // n*3 wei vector colm=init_map(); show(vec); hanno(n, 'A','B','C'); } #########################################


运行程序(注意示例n为3):


3


A B C --------------------- 0 0 01 0 02 0 03 0 0


A--------------->C


A B C --------------------- 0 0 00 0 02 0 03 0 1


A--------------->B


A B C --------------------- 0 0 00 0 00 0 03 2 1


C--------------->B


A B C --------------------- 0 0 00 0 00 1 03 2 0


A--------------->C


A B C --------------------- 0 0 00 0 00 1 00 2 3


B--------------->A


A B C --------------------- 0 0 00 0 00 0 01 2 3


B--------------->C


A B C --------------------- 0 0 00 0 00 0 21 0 3


A--------------->C


A B C --------------------- 0 0 00 0 10 0 20 0 3

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台