汉诺塔问题的具体解决办法

1. 汉诺塔问题的具体解决办法

2. 汉诺塔问题用什么方法解决?

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒。
第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。
面对庞大的数字(移动圆片的次数)18446744073709551615(2^64-1)，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

相关信息
法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。
印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。
僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

3. 关于汉诺塔的一个问题。

汉诺塔算法介绍：把三根柱子按顺序排成“品”字型，把所有圆盘按从大到小的顺序放于柱子A上，根据圆盘数量来确定柱子排放的顺序：n若为偶数的话，顺时针方向依次摆放为：ABC；而n若为奇数的话，就按顺时针方向依次摆放为：ACB。这样经过反复多次的测试，最后就可以按照规定完成汉诺塔的移动。因此很简单的，结果就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。

4. 汉诺塔问题!!!

汉诺塔问题的C++实现
#include
using
namespace
std;
char
A,B,C;
int
main()
{
int
n;
void
hano(int,char,char,char);
cout<<"请输入A座上的盘子数目：";
cin>>n;
hano(n,'A','B','C');
return
0;
}
void
print(char
A,char
C)
{cout<<A<<"--"<<C<<endl;}
void
hanoi(int
n,char
A,char
B,char
C)
{
if(n==1)
print(A,C);
else
{hanoi(n-1,A,C,B);
print(A,C);
hanoi(n-1,B,A,C);
}
}
说明：
规模为n的汉诺塔问题可以写成两个规模为n-1的汉诺塔问题的和。也就是说若用H(n)表示规模为n的汉诺塔问题的解的话，则H(n)=
2H(n-1)+1。最后加的1就是printf("%d->%d\n",a,c);的含义。
以上就是汉诺塔问题的数学模型，比较抽象。
就以Hanoi(4,1,2,3)举例来说：1、2、3分别代表可以存放盘子的底座的编号，4表示刚开始时第1个底座有4个盘子，a、b、c分别代表：问题开始时的原来存放盘子的底座、临时底座、问题结束时盘子存放的底座。那么怎么将第1个底座上4个盘子移动到第3个底座上呢？
按照上面的模型，分成三步：
（1）将第1个底座的最上面的3个盘子移动到第2个底座上；
（2）将第1个底座上剩下的1个盘子直接放到第3个底座上；
（3）将第2个底座上的3个盘子移动到第三个底座上；
上面三个过程实际上就对应到你的Hanoi(...)函数的中的三个语句。
第(1)、(3)步就是相当于原来问题的两个变形。可以把第(1)步理解为：将n-1个盘子从第1个底座搬到第2个底座的汉诺塔问题，这样问题有3个变化的地方和1个不变的地方：盘子总数减少了1、要将盘子移动到的目标底座变成了第2个底座了、临时底座变成了第3个底座了、问题的本质上还是汉诺塔问题，这个不变很重要，它是问题可以递归求解的关键，也就是说可以用不同的参数来调用同一个函数来解决。对应到Hanoi(...)函数的4个参数中的3个变化。
完成了前面两步后，显然问题并没有解决，所以才有第(3)步，也就是第二个递归。同样的道理第(3)步可以理解为：将n-1个盘子从第2个底座搬到第三个底座的汉诺塔问题了。只不过与第一个递归不同的是：原来的第2个底座相当于原来的第1个底座、原来的第1个底座相当于现在的第2个底座了。
补充：对于初学者来说，求解汉诺塔问题的方法其实很简单，但是求解的细节却很绕人，1、2、3与a、b、c的关系就不太好理解。个人认为搞清楚形式参数与实际参数的关系会对理解程序代码有帮助。直观的来看，123就是实际参数，abc就是形式参数。由前面内容可以看出，其实123和abc的意义在每一层递归调用中的含义是不同的，但就Hanoi(int
n,int
a,int
b,int
c)而言，每次调用它都是把当前要移动的盘子总数传给n、盘子初始位置传给a、目标位置传给c。进入Hanoi函数内部以后，问题被分解为“三步走”这样abc的具体含义在递归调用时就变化了。

5. 汉诺塔问题

编程时，脑子里不要去思考递归过程（转来转去，会让人很头疼，一会儿就晕了）。
数列我想你是清楚的，所谓的递归，就是把an变成a(n-1)去处理问题，处理一个通项式是相同的方法，只要给出a1(或者还有a2)，这是递归结束的条件。
假设汉诺塔A B C三根针，只考虑移动最底下的盘子时，
如果只有一个盘子，就是直接A->C
如果只有两个盘子，就是A->B  然后A->C
如果只有三个盘子，就是A->C  A->B  C->B  然后A->C
可以发现，
（1）如果想移动最底下的盘子，则，先要上面n-1个移动到B盘，即可。
（2）在移动B盘上的n-1中的最底下的盘子时，则改变一下源针和中间针即可，即：把B看成A A看成B
（3）接下来，在移动A盘上的n-2中的最底下的盘子时，则恢复源针和中间针即可，即：A还是A，B还是B。本步与第一步相同，即1 2两步是在n>1时，的循环。
（4）当只有一个盘子时（n=1），就做“源针”到“目标针”即可，结束本次递归。
因此，递归程序只有以上三步，即可实现汉诺塔的移动。

6. 汉诺塔问题，为什么程序这样写，请解释一下

当只有一个盘子的时候，只需要从将A塔上的一个盘子移到C塔上。
            当A塔上有两个盘子是，先将A塔上的1号盘子（编号从上到下）移动到B塔上，再将A塔上的2号盘子移动的C塔上，最后将B塔上的小盘子移动到C塔上。
            当A塔上有3个盘子时，先将A塔上编号1至2的盘子（共2个）移动到B塔上（需借助C塔），然后将A塔上的3号最大的盘子移动到C塔，最后将B塔上的两个盘子借助A塔移动到C塔上。
           当A塔上有n个盘子是，先将A塔上编号1至n-1的盘子（共n-1个）移动到B塔上（借助C塔），然后将A塔上最大的n号盘子移动到C塔上，最后将B塔上的n-1个盘子借助A塔移动到C塔上。
          综上所述，除了只有一个盘子时不需要借助其他塔外，其余情况均一样（只是事件的复杂程度不一样）。
         
#include   
//第一个塔为初始塔，中间的塔为借用塔，最后一个塔为目标塔  
int i=1;//记录步数  
void move(int n,char from,char to) //将编号为n的盘子由from移动到to  
{printf("第%d步:将%d号盘子%c---->%c\n",i++,n,from,to);  
}  
void hanoi(int n,char from,char denpend_on,char to)
//将n个盘子，由初始塔，利用借用塔，移动到目标塔  
{  
    if (n==1)  
    move(1,from,to);//只有一个盘子是直接将初塔上的盘子移动到目的地  
    else  
    {  
      hanoi(n-1,from,to,denpend_on);//先将初始塔的前n-1个盘子借助目的塔移动到借用塔上  
      move(n,from,to);              //将剩下的一个盘子移动到目的塔上  
      hanoi(n-1,denpend_on,from,to);//最后将借用塔上的n-1个盘子移动到目的塔上  
    }  
}  
void main()  
{  
     printf("请输入盘子的个数:\n");  
     int n;  
     scanf("%d",&n);  
     char x='A',y='B',z='C';  
     printf("盘子移动情况如下:\n");  
     hanoi(n,x,y,z);  
}  

7. 汉诺塔问题

汉诺塔问题是典型的递归问题，解题的关键就是将这个问题逐步进行分解，直到最后剩1个盘子的时候一步完成。
基本上，汉诺塔可以可以用下面的方式实现：
void move(char x, char y)  {       cout"<<y<<endl;  }  void hanoi(int n,char one,char two,char three)  {       if (n == 1)       {             move(one,three);       }       else       {           hanoi(n-1,one,three,two);           move(one,three);           hanoi(n-1,two,one,three);       }  } 
  
当只剩下1个盘子的时候，把最后一个盘子从起始柱子移动到目标柱子。就是程序中n==1时候的分支；
当剩下的盘子很多的时候，就将整个过程分解：
1、把N-1个盘子从起点柱子移动到（当前）没有任何盘子的过度柱子；
2、把最后一个盘子从起点柱子移动到目标柱子；
3、把N-1个盘子从过度柱子移动到目标柱子（模仿1和2的操作方法来实现）。
这就是else分支所要进行的操作。
  因此，这里面用到了2次递归，一次是操作1，一次是操作3。

8. 如何解汉诺塔问题

汉诺塔是一个迭代问题，我们先假设x层汉诺塔从第一根柱子移动到最后一根柱子（目标柱子）的最快次数是f(x)次
显然f(1)=1
f(2)=3
然后看3层的，我们可以把整个过程分解为三个部分
一，把第一第二层移动到中间的柱子（过渡柱子），最快f(2)步
二，把第三层移动到最后一根柱子（目标柱子），最快1步
三，把刚才移动到中间柱子的第一第二层移动到最后一根柱子，最快f(2)步
所以f(3)=f(2)+1+f(2)=7
然后以此类推
f(4)=f(3)+1+f(3)=15
f(5)=f(4)+1+f(4)=31
f(6)=f(5)+1+f(5)=63
f(7)=f(6)+1+f(6)=127
f(8)=f(7)+1+f(7)=255
f(9)=f(8)+1+f(8)=511

PS.如果学习过数列的话，这个其实可以得到更为一般的递推公式
f(x+1)=2*f(x)+1
再进一步，可以得到通项公式为
f(x)=2^x-1