/*汉诺塔的递归算法*
#include<iostream.h>
void hanio(int n,char A,char B,char C)
{
if(n==1)
{
cout<<"将第"<<n<<"片金片从"<<A
<<"柱搬到"<<C<<"柱上"<<endl;
}
else
{
hanio(n-1,A,C,B);
cout<<"将第"<<n<<"片金片从"<<A
<<"柱搬到"<<C<<"柱上"<<endl;
hanio(n-1,B,A,C);
}
}
void main()
{
char A=''A'',B=''B'',C=''C'';
int n=3;
hanio(n,A,B,C);
}
*/
/****关于汉诺塔问题的另类解*****
汉诺塔问题归于中序遍历，采用递归算法或分治算法也许的最简单的求解方法。
递归是设计和描述算法的一种有力的工具。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题（1<k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
当然，有时我们并不需要求解出问题的全解。如我们只想知道６４片金片要从A柱上移动到C柱上（B柱为桥），第一百亿步应该是哪片金片的第几次移动，且是从哪根柱上移动到哪根柱上呢？在计算机上是否能用递归算法或分治算法求解我不知道，但在只有一支笔一张纸的情况呢？我想用递归法或分治法是不现实的！那有没有方法求解呢，答案是肯定的。我通过递推法（利用问题本身所具有的一种递推关系求问题解的一种方法）找到了解决这个问题的数学表达式：
(2^i)*(2^j-1)=M；k=j%3； N； 条件：N金片数，第M步为已知。（金片1为最小，金片64最大）那么解就是：N片金片的第M步为金片i+1的第j次移动，当(i+1)%2=N%2时，k=0：从B柱上移动到A柱上；k=1：从A柱上移动到C柱上；k=2：从C柱上移动到B柱上；当(i+1)%2≠N%2时，k=0：从C柱上移动到A柱上；k=1：从A柱上移动到B柱上；k=2：从B柱上移动到C柱上；
如果此时想知道各柱上的金片是如何排列的却只有使用另一种方法了。那就是先用N位二进制数来表示M，余下的工作就是随手画出各柱上的金片的排列！再画出第M-1步各柱上的金片的排列，那么就可以不用计算而得到答案！这正是我为大家推荐的方法。
请仔细阅读程序中蓝色字体部分，我想信你也能随手画出答案！(提示：用N位二进制数来表示M，最高位代表最大的金片，最低位为最小。先从最高位开始，为1则最大的金片用N表示画在C柱上，否则在A柱上；次高位如果同上一位相同则画在同一柱上，否则画在B柱上；下一次高位如果同次高位同则画在同一柱上，否则画在A柱上；依此循环。并遵守在同一柱上相邻的两片金片编号不能同时为奇或偶。从低位往高位看，第一位为1的金片就是本次移动的金片，且在大多数情况下不用画出第M-1步各柱上的的排列就能知道该金片的如何移动的。例：4张金片第10步，10=（1010）2 显然A柱上有2，B柱上是3，C柱上有1和4。第一位为1在第2位上，因此是金片2，
1+（1010）2>>2 =1+(0010)2 =3,显然 4张金片第10步为金片2的第3次移动，且是从B柱移动到A柱。）
*********************************************/
/*********************************************
* 文件名称：hanio.cpp
* 摘 要：汉诺塔的终极经典的算法。
* 可以随手画出答案的方法。
* 本例没考虑程序本身的可读性和效率。
* 当前版本：1.0
* 作 者：赵智强
* 完成日期：2005年10月12日
* 电子邮箱：wwwindowsxp@163.com
* 腾讯 QQ : 191580647
* 测试环境：Turbo C++ 3.0
*********************************************/
#include<iostream.h>
void divtwo(int d[],int n)
{
int temp=0,cy=0;
int i;
for(i=n;i>=0;i--)
{
cy=d[i]%2;
d[i]=(d[i]+temp*10)/2;
temp=cy;
}
}//十进制数组除2
void multwo(int d[],int m,int n)
{
int temp=0,cy=0;
int i,j;
for(j=0;j<n;j++)
{
for(i=0;i<m;i++)
{
cy=(d[i]*2)/10;
d[i]=(d[i]*2)%10+temp;
temp=cy;
}
}
}//十进制数组=2^m
void decaddone(int d[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(d[i]==9) d[i]=0;
else {d[i]+=1;break;}
}
}//十进制数组加1
void main()
{
int i,j,k, n;
int m=52;
char a[52]="1";
int b[52]={0};
int d[52]={1};
int e[52]={0};
cout<<"Input :disk(1~100) " //输入金片数：整型
<<"step(2^disk-1)"<<endl;//输入第M步：字符数组
cin>>n;
if(n>100){cout<<"disk err! (disk>100)"
<<endl; return;}
int c[100]={0};
int aa[100]={0};
int bb[100]={0};
int cc[100]={0};
for(i=0;i<m;i++)
{
cin>>a[i];
if(a[i]>0x39||a[i]<0x30)
{a[m-1]=i;break;}
}//输入第M步：字符数组以非数字结尾
for(i=0;i<a[m-1];i++)
b[i]=int(a[(a[m-1]-1-i)]-0x30);//转换成十进制整型数组，个位在b[0]
multwo(d,m,n);
cout<<endl;
cout<<"step max: ";
j=0;
for(i=m-1;i>=0;i--)
{
if(d[i]==0&&j==0) continue;
j=1;
cout<<d[i];
}
cout<<"-1"<<endl;
for(i=m-1;i>=0;i--)
{
if(b[i]<d[i]) break;
if(b[i]>d[i]||(b[i]==d[i]&&i==0))
{cout<<"step err! (step>=2^disk)"
<<endl; return;}
}//输入第M步是否<=2^disk-1
for(i=0;i<m;i++)
{
d[i]=b[i];e[i]=b[i];
}
for(i=0;i<n;i++)
{
if(b[0]%2==1) { c[i]=1;b[0]-=1;}
else c[i]=0;
for(j=0;j<m;j++) if(b[j]!=0) break;
if(j==m) break;
divtwo(b,1+n/2);
}
cout<<" ";
for(i=n-1;i>=0;i--)
{
cout<<c[i]<<" ";
}//step的n位二进制数组表示
cout<<endl;
j=0;
int aa1=0,bb1=0,cc1=0,dd1=0;
if(c[n-1]==0) { aa[aa1]=n;aa1++;dd1=1;}
else { cc[cc1]=n;j++;cc1++;dd1=3;}
for(i=n-2;i>=0;i--)
{
if(c[i+1]==c[i])
{
switch(dd1)
{
case 1: { aa[aa1]=i+1;aa1++;
dd1=1;continue;break;}
case 2: { bb[bb1]=i+1;bb1++;
dd1=2;continue;break;}
case 3: { cc[cc1]=i+1;cc1++;
dd1=3;continue;break;}
}
}
else
{
j++;
switch(dd1)
{
case 1: if(j%2==i%2) {cc[cc1]=i+1;
cc1++;dd1=3;continue;break;}
else { bb[bb1]=i+1;bb1++;
dd1=2;continue;break;}
case 2: if(j%2==i%2){aa[aa1]=i+1;
aa1++;dd1=1;continue;break;}
else {cc[cc1]=i+1;cc1++;
dd1=3;continue;break;}
case 3: if(j%2==i%2) {bb[bb1]=i+1;
bb1++;dd1=2;continue;break;}
else { aa[aa1]=i+1;aa1++;
dd1=1;continue;break;}
}
}
}// 根据step的n位二进制数组表示，解出A、B、// C柱上各金片的相对排列。
for(i=0;i<n;i++)
{
if(d[0]%2==1)
{
divtwo(d,1+n/2);
decaddone(d,m);
cout<<"disk: "<<n<<" "<<"step: ";
k=0;
for(j=m-1;j>=0;j--)
{
if(e[j]==0&&k==0) continue;
k=1;
cout<<e[j];
}
cout<<endl;
cout<<"No. "<<i+1<<" "
<<"times: ";
k=0;
for(j=m-1;j>=0;j--)
{
if(d[j]==0&&k==0) continue;
k=1;
cout<<d[j];
}
if(d[0]==0&&k==0) cout<<d[0];
cout<<" ";
k=0;
for(j=0;j<m;j++)
{
k+=d[j];
}
if(n%2==(i+1)%2)
{
switch(k%3)
{
case 0: cout<<"B------>A"
<<endl; break;
case 1: cout<<"A------>C"
<<endl; break;
case 2: cout<<"C------>B"
<<endl; break;
}
}
else
{
switch(k%3)
{
case 0: cout<<"C------>A"
<<endl; break;
case 1: cout<<"A------>B"
<<endl; break;
case 2: cout<<"B------>C"
<<endl; break;
}
}
break;
}
else divtwo(d,1+n/2);
}//根据上文提到的数学表达式(2^i)*(2^j-1)=M计算
cout<<"A ";
for(i=n-1;i>=0;i--)
{
if(n%2==1&&c[n-1]==1)
cout<<bb[i]<<" ";
else cout<<aa[i]<<" ";
}
cout<<endl;
cout<<"B ";
for(i=n-1;i>=0;i--)
{
if(n%2==1)
if(c[n-1]==1) cout<<aa[i]<<" ";
else cout<<cc[i]<<" ";
else cout<<bb[i]<<" ";
}
cout<<endl;
cout<<"C ";
for(i=n-1;i>=0;i--)
{
if(n%2==1&&c[n-1]==0)cout<<bb[i]<<" ";
else cout<<cc[i]<<" ";
}
cout<<endl;
//求解出A、B、C柱上各金片的最终排列。
}
/*****************非递归算法******************
* 本例输入：disk为金片数（1～100）。
* step为移动的第xxxx步。
* xxxx应小于2^disk。
* 本例输出：第xxxx步为第xx金片第xxxx次移动。
* 且是从x柱移动到x柱。
* 注： A源柱，B桥柱，C目的柱。
* 另注： 例共1张金片，其移动步骤可能是：第
* 1步从A—>B,第2步从B-->C。但这不是我们
* 要的答案！正确方法是：第1步从A—>C。
*****************程序运进结果*****************
输入：4 10p（非数字结尾）
输出：step max: 16-1
1 0 1 0(10的4位二进制表示)
disk：4 step：10
No. 2 times：3 B--àA
A 0 0 0 2
B 0 0 0 3
C 0 0 1 4
解析：共4张金片的第10步为：
第2张金片第3次移动，且是从B柱上移动到A柱上。
*********************************************/
，看上去挺吓人的，其实更简单～
