汉诺塔问题的非递归非堆栈算法（二）

前一种方法的/*原理：

如果把三个柱子围成一个环，盘子总数为N，其移动的规律是：

如果N为偶数：奇数号盘每次2步；偶数号盘每次1步；

如果N为奇数：奇数号盘每次1步；偶数号盘每次2步；

至于下一步该移动哪个柱子上的盘子，通过大小和顺序即可判断。

以上可以通过数学证明，不赘述！

*/

以下是第二种算法：

#include <iostream.h>

#include <math.h>

void main(){

int tt = 1,ff=1,fff=1,t;

cout<<"请输入（1-64）：";

cin>> t;

cout<<"F：表示盘子的起始柱子既From的意思"<<endl;

cout<<"T：表示盘子的目标柱子既To的意思"<<endl;

cout<<"o：表示在这一步中没有用到的柱子"<<endl<<endl;

for(int i1=1;i1<=t;i1++,ff*=2 );

char **hand;

hand=new char*[ff + 1];

for(int i2=0;i2<ff+1;i2++) hand[i2] = new char[4];

//char **hand=new char[ff + 1][ 4];

hand[0][1] = 'O';

hand[0][2] = 'O';

hand[0][3] = 'O';

hand[1][1] = 'F';

hand[1][2] = 'o';

hand[1][3] = 'T';

for(int i = 2;i<= t;i++){

tt ++;

if(fmod(i,2) == 0){

hand[tt][ 1] = 'F';

hand[tt][ 2] = 'T';

hand[tt][ 3] = 'o';

}

else{

hand[tt][ 1] = 'F';

hand[tt][ 3] = 'T';

hand[tt][ 2] = 'o';

}

fff=1;

for(int h=1;h<=i-1;h++,fff*=2);

for(int ii = 1;ii<= fff - 1;ii++)

{tt ++;

if(fmod(i, 2)== 0){

hand[tt][ 1] = hand[ii][ 2];

hand[tt][ 2] = hand[ii][ 3];

hand[tt][ 3] = hand[ii][ 1];}

else{

hand[tt][ 1] = hand[ii][ 3];

hand[tt][ 2] = hand[ii][ 1];

hand[tt][ 3] = hand[ii][ 2];

}

}

}

if(fmod(t, 2) == 0){//调换位置

for(int i = 1;i<=tt;i++){

hand[i][ 0] = hand[i][ 2];

hand[i][ 2] = hand[i][ 3];

hand[i][ 3] = hand[i][ 0];}

}

for(int u=1;u<ff;u++ )

cout<<u<<": "<<hand[u][1]<<" "<<hand[u][2]<<" "<<hand[u][3]<<" "<<endl;

cin>>fff;

}

}