另一个家庭作业.将老师的A传给我;)
来源:http://www.soc.napier.ac.uk/~andrew/hanoi/rechelp.html
奖金:一步一步的YouTube视频.
关于河内塔的一点点
这个问题的分析以及(发明的)神话和四个peg版本的讨论可以在rec.puzzles常见问题解答中查找indu/hanoi.s.
河内塔问题有一个很好的递归解决方案.
制定递归解决方案
要解决这些问题,请问自己:"如果我解决了n-1案,我可以解决n案吗？"
如果这个问题的答案是肯定的,你可以在n-1案例已经解决的无耻假设下进行.奇怪的是,只要存在一些基本情况(通常当n为零或一个)时,这可以作为一种特殊情况处理.
如何将N环从极A移动到极点C？
如果您知道如何将n-1环从一个极移动到另一个极,那么只需将n-1个环移动到备用极 - 现在源极上只剩下一个环,只需将其移动到目的地,然后堆放其余的他们从备用杆到目的地杆.
例如,当n为4时......
首先将三个移到备用杆上(担心以后如何做到这一点).
现在将一个环从源极移动到目标极点.
现在将三个环从备用杆移动到目标杆
(再次,我们可以担心以后如何做到这一点).
我们完成了!
更简洁......
使用B作为备用将n个环从A 移动到C:
- 如果n是1
- 去做就对了,
- 除此以外...
- 使用C作为备用,将n-1环从A 移动到B.
- 将一个环从A移动到C.
- 使用A作为备用,将n-1环从B移到C.
与大多数递归解决方案一样,我们必须特别处理一些基本情况 - 这里基本情况发生在我们只有一个环要移动的地方.
如何在C中完成
/* Tower of Hanoi - the answer */
/* How to move four rings from pin 1 to pin 3 using pin 2 as spare */
#include <stdio.h>
void move(n, A, C, B)
/* number to move, source pole, destination pole and
spare pole respectively */
int n, A, B, C; {
if (n == 1) {
printf("Move from %d to %d.\n", A, C);
} else {
move(n - 1, A, B, C);
move(1, A, C, B);
move(n - 1, B, C, A);
}
}
main() {
move(4, 1, 3, 2);
}