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

前一种方法的/*原理：
 如果把三个柱子围成一个环，盘子总数为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;
}
}

本文地址：http://com.8s8s.com/it/it37259.htm