汉诺塔问题

汉诺塔问题~

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

　　后来，这个传说就演变为汉诺塔游戏:

　　1.有三根杆子A,B,C。A杆上有若干碟子
　　2.每次移动一块碟子,小的只能叠在大的上面
　　3.把所有碟子从A杆全部移到C杆上

　　经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
　　如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

　　此外，汉诺塔问题也是程序设计中的经典递归问题。

　　算法思路：
　　1.如果只有一个金片，则把该金片从源移动到目标棒，结束。
　　2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒

　　(非专业人士可以忽略以下内容)

　　补充：汉诺塔的算法实现（c++）
　　#include
　　#include
　　using namespace std;

　　ofstream fout("out.txt");

　　void Move(int n,char x,char y)
　　{
　　fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
　　}

　　void Hannoi(int n,char a,char b,char c)
　　{
　　if(n==1)
　　Move(1,a,c);
　　else
　　{
　　Hannoi(n-1,a,c,b);
　　Move(n,a,c);
　　Hannoi(n-1,b,a,c);
　　}
　　}

　　int main()
　　{
　　fout<<"以下是7层汉诺塔的解法:"<<endl;
　　Hannoi(7,'a','b','c');
　　fout.close();
　　cout<<"输出完毕！"<<endl;
　　return 0;
　　}

　　C语言精简算法
　　/* Copyrighter by SS7E */
　　#include /* Copyrighter by SS7E */
　　void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */
　　{
　　if(n==1)
　　{
　　printf("Move disk %d from %c to %c
",n,A,C);
　　}
　　else
　　{
　　hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
　　printf("Move disk %d from %c to %c
",n,A,C);
　　hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
　　}
　　}
　　main() /* Copyrighter by SS7E */
　　{
　　int n;
　　printf("请输入数字n以解决n阶汉诺塔问题：
");
　　scanf("%d",&n);
　　hanoi(n,'A','B','C');
　　}/* Copyrighter by SS7E */

　　PHP算法：
　　<?php
　　function hanoi($n,$x,$y,$z){
　　if($n==1){
　　move($x,1,$z);
　　}else{
　　hanoi($n-1,$x,$z,$y);
　　move($x,$n,$z);
　　hanoi($n-1,$y,$x,$z);
　　}
　　}
　　function move($x,$n,$z){
　　echo 'move disk '.$n.' from '.$x.' to '.$z.'';
　　}
　　hanoi(10,'x','y','z');
　　?>
　　JAVA算法：
　　public class Haniojava
　　{
　　public static void main(String args[])
　　{
　　byte n=2;
　　char a='A',b='B',c='C';
　　hanio(n,a,b,c);
　　}
　　public static void hanio(byte n,char a,char b,char c)
　　{
　　if(n==1)
　　System.out.println("move "+a+" to "+b);
　　else
　　{
　　hanio((byte)(n-1),a,c,b);
　　System.out.println("move "+a+" to "+b);
　　hanio((byte)(n-1),c,b,a);
　　}
　　}
　　}


　　#include

　　void move(char ch1, char ch2) {
　　cout"<<ch2<<' ';
　　}

　　void hanoi(int n, char a, char b, char c) {
　　if (n==1)
　　move (a,c);
　　else {
　　hanoi (n-1,a,c,b);
　　move (a,c);
　　hanoi (n-1,b,a,c);
　　}
　　}

　　void main() {
　　int m;
　　cout<<"Enter the number of disk to move:
";
　　cin>>m;
　　cout<<"The step to moving "<<m<<" disk:
";
　　hanoi (m,'A','B','C');
　　cin>>m;
　　}

　　用不了这么复杂
　　，设A上有n个盘子。
　　如果n=1，则将圆盘从A直接移动到C。
　　如果n=2，则：
　　1.将A上的n-1(等于1)个圆盘移到B上；
　　2.再将A上的一个圆盘移到C上；
　　3.最后将B上的n-1(等于1)个圆盘移到C上。
　　如果n=3，则：
　　A. 将A上的n-1(等于2，令其为n`)个圆盘移到B(借助于C)，步骤如下：
　　(1)将A上的n`-1(等于1)个圆盘移到C上。
　　(2)将A上的一个圆盘移到B。
　　(3)将C上的n`-1(等于1)个圆盘移到B。
　　B. 将A上的一个圆盘移到C。
　　C. 将B上的n-1(等于2，令其为n`)个圆盘移到C(借助A)，步骤如下：
　　(1)将B上的n`-1(等于1)个圆盘移到A。
　　(2)将B上的一个盘子移到C。
　　(3)将A上的n`-1(等于1)个圆盘移到C。
　　到此，完成了三个圆盘的移动过程。
　　从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：
　　第一步 把A上的n-1个圆盘移到B上；
　　第二步 把A上的一个圆盘移到C上；
　　第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。
　　当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。 显然这是一个递归过程，据此算法可编程如下：
　　move(int n,int x,int y,int z)
　　{
　　if(n==1)
　　printf("%c-->%c
",x,z);
　　else
　　{
　　move(n-1,x,z,y);
　　printf("%c-->%c
",x,z);
　　move(n-1,y,x,z);
　　}
　　}
　　main()
　　{
　　int h;
　　printf("
input number:
");
　　scanf("%d",&h);
　　printf("the step to moving %2d diskes:
",h);
　　move(h,'a','b','c');
　　}

从问题本质说起，这个问题的解题思路是在n大于1时，将n-1个盘子移到第二个柱子上，然后将第n个盘子移到第三个柱子上，再将第二个柱子上的n-1个盘子从第二个柱子上移到第三个柱子上。回到你的代码中：

函数调用“void hanoi(int n,char one,char two ,char three) ”的意思即是将n个盘子借助“two”这个柱子从“one”移到“three”上。

"if(n==1) move(one,three)"的意思是只有一个盘子时直接将这个盘子从1移到3上。

“
if(n>1)
{ hanoi(n-1,one,three,two);
move(one,two);
hanoi(n-1,three,two,one);
}
”
这一段意思即n大于1时，先将n-1个盘子借助3从1移到2上，“move(one,two)"这个调用不对，应该是“move(one, three)”,即将第n个盘子从1移到3。然后“hanoi(n-1, three, two, one)”也不对，应该是“hanoi(n-1, two, one, three)”，即将n-1个盘子借助1从2移到3上。
如果你看得比较糊涂的话，就像你说的，我们看一个实例：调用hanoi(3,one, two ,three)时的情况如下，
hanoi(3, one, two, three)
-> hanoi(2, one, three, two)
-> hanoi(1, one, two, three) = move 1 from "one" to "three"
-> move 2 from "one" to "two"
-> hanoi(1, three, one, two) = move 1 from "three" to "two"
-> move 3 from "one" to "three"
-> hanoi(2, two, one, three)
-> hanoi(1, two, three, one) = move 1 from "two" to "one"
-> move 2 from "two" to "three"
-> hanoi(1, three, two, one) = move 1 from "three" to "one"

已经说得很具体了，不过你要耐心的看看想想就明白了。

亲，这是汊诺塔问题的程序，满意的话就采纳

void hanoi(int n,char one,char two,char three)
{if(n==1)
  printf("%c-->%c
",one,three);
 else
  {hanoi(n-1,one,three,two);
   printf("%c-->%c
",one,three);
   hanoi(n-1,two,one,three);
  }
}
main()
{int n;
scanf("%d",&n);
hanoi(n,'A','B','C');
getch();
}

 

---

曲靖市18751796279： 汉诺塔问题 - ？
巫鲍优力： n=2^t-1(n为次数,t为碟子数) 有四个碟子 所以n=2^4-1=15 选B 汉诺塔(又称河内塔)问题是印度的一个古老的传说.开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个...

曲靖市18751796279： 简单汉诺塔问题汉诺塔问题是指有3根杆子A、B、C. B杆上有若干碟子,把所有碟子从B杆移到A杆上,每次只能移动一个碟子,大的碟子不能叠在小的碟... - ？
巫鲍优力：[答案] 把1,2移到C杆违反了规则:大的碟子2不能叠在小的碟子1上面把1移到A,2移到C,1移到C,3移到A,1移到B,2移到A,1再移到A

曲靖市18751796279： 汉诺塔问题公式是什么? - ？
巫鲍优力： 汉诺塔问题(又称河内塔问题)是根据一个传说形成的一个问题:有三根杆子A,B,C.A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆:1. 每次只能移动一个圆盘; 2. 大盘不能叠在小盘上面. ...

曲靖市18751796279： 谁能解4个圆盘的河内塔问题?认知心理学作业 - ？
巫鲍优力：[答案] 这个问题很简单!书上都是答案的! 河内塔(又称汉诺塔)问题是印度的一个古老的传说.开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不...

曲靖市18751796279： 递归 汉诺塔有些问题只能用递归来解决.一个典型的例子就是汉诺塔问题.问题的提法是:“传说婆罗门庙里有一个塔台,台上有3根标号为A,B,C的用钻石... - ？
巫鲍优力：[答案] void hanoi ( int n, char a, char b, char c ) { if ( n >= 1 ) { hanoi ( n-1, a, c, b ) ; printf(“%c --> %c\n”, a , c) ; hanoi ( n-1, b, a, c ) ; ...

曲靖市18751796279： 如何理解汉诺塔模型? - ？
巫鲍优力： 汉诺谈问题是一个转换盘子问题 汉诺塔(又称河内塔)问题是印度的一个古老的传说.开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧...

曲靖市18751796279： 汉诺塔问题的算法分析及C++实现1.当仅有1个盘子时,把这个盘子从A塔柱移动到C塔柱上2.当圆盘的个数多于1个时,如下解决:(1) 先将A塔柱上的(n - 1... - ？
巫鲍优力：[答案] hanoi函数的目的是解决汉诺塔的移动序列,它有4个参数:1.n表示要移动的盘子的个数2.一开始盘子在哪个柱子上,这个变量叫a,所以可以说,一开始在a柱子上4.最后盘子要移动到哪个柱子上,这个变量叫c,所以可以说,最后要移...

曲靖市18751796279： 汉诺塔问题(编程)？
巫鲍优力： 1个盘子移动1次.2个盘子移动3次. 3个盘子移动7次...... 所以移动次数就是2^n-1. 时间复杂度就是O(2^n); 具体代码如下: #include<iostream> using namespace std;int N=0; void Hanoi( int n, char A, char B, char C) { if(n==1) { cout<<＂第＂<<++...

曲靖市18751796279： 求四根柱子的汉诺塔问题的详细题目描述?就是说这个问题究竟有什么要求啊?否则不过是三根柱子汉诺塔多一根冗余的柱子罢了. - ？
巫鲍优力：[答案] 如何能够用最短的次数呗呗

曲靖市18751796279： 汉诺塔问题,五个盘子具体走法不是编程,就是想知道怎么走,具体一点的.三根柱子1、2、3,五个由小到大的盘子abcde全部在1柱上,要按这个顺序移到3... - ？
巫鲍优力：[答案] 五个柱子!分别为1号 2号 3号 五个盘子 A B C D E 这样走: A-3 B-2 A-2 C-3 A-1 B-3 A-3 D-2 A-2 B-1 A-1 C-2 A-3 B-2 1-2 E-3 A-1 B-3 A-3 C-1 A-2 B-1 A-1 D-3 A-3 B-2 A-2 C-3 A-1 B-3 A-3 得出