汉诺塔 (Tower of Hanoi) 源于印度传说中, 大梵天创造世界时造了三根金钢石柱子, 其中一根柱子自底向上叠着 64 片黄金圆盘. 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上. 并且规定, 在小圆盘上不能放大圆盘, 在三根柱子之间一次只能移动一个圆盘.
伪算法(重点理解):
if( n>1 ){
先把 A 柱子上的前 n-1 个盘子从 A 借助 C 移到 B// 重点
将 A 柱子上的第 n 个盘子直接移到 C// 第 n 个就是最下面的一个
再将 B 柱子上的 n-1 个盘子从 B 借助 A 移到 C// 重点
}
三个盘情况: 移动盘子次数为 7
四个盘情况: 移动盘子次数为 15
假设有 n 片, 移动次数是 f(n). 显然 f(1)=1,f(2)=3,f(3)=7, 且 f(k+1)=2*f(k)+1. 此后不难证明 f(n)=2^n-1.
- #include<stdio.h>
- // 函数的形参 A,B,C 不一定代表的是 A,B,C 柱子, 递归传参的时候会变化!
- void hanoit(int n,char A,char B,char C){
- if(n==1){
- // 如果剩下一个盘子, 直接将 A 柱子上的盘子从 A 移到 C(直接从初始塔移动到目标塔)
- printf("将编号为 %d 的盘子从 %c 柱子移到 %c 柱子",n,A,C);
- }
- else{
- // 否则, 先将 A 柱子上的 n-1 个盘子从 A 借助 C 移到 B(从初始塔移动到介质塔)
- hanoit(n-1,A,C,B);// 注意参数顺序: 从 A 借助 C 移到 B
- printf("将编号为 %d 的盘子从 %c 柱子移到 %c 柱子",n,A,C);
- // 最后将 B 柱子上的 n-1 个盘子从 B 借助 A 移到 C(从介质塔移动到目标塔)
- hanoit(n-1,B,A,C);
- }
- }
- int main(){
- // 三个柱子 A,B,C, 分别的作用是初始柱, 介质柱, 目标柱
- char ch1 = 'A';
- char ch2 = 'B';
- char ch3 = 'C';
- int n;
- printf("移动盘子的个数:");// 也是最后一个盘子的编号, 顶部第一个盘子的编号是 1
- scanf("%d",&n);
- hanoit(n,'A','B','C');
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3157332.html