C语言递归:汉诺塔问题分析
持续进化中 人气:0问题背景
汉诺塔问题源自印度一个古老的传说,印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱,其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上,移动过程中必须遵守以下规则:
每次只能移动柱子最顶端的一个圆盘;每个柱子上,小圆盘永远要位于大圆盘之上;
游戏体验
点击开始体验游戏:汉诺塔游戏 (gitee.io)
汉诺塔移动次数规律
个数 | 移动次数f(n) | 规律 |
1 | 1 | 2^1-1 |
2 | 3 | 2^2-1 |
3 | 7 | 2^3-164-1 |
4 | 15 | 2 |
... | ... | ... |
n | 2^n-1 | 2^n-1 |
由上述分析可以得到f(n)与f(n-1)的关系:
所以:f(n)=2^n-1 ; f(n-1)=2^(n-1)-1
f(n)=2^n-1=2^1*(2^(n-1)-1)+1=2*f(n-1)+1
移动过程的深层解读
汉诺塔问题的三步过程归纳
(我们是把n-1个圆盘看成一个整体去分析的)
一.把n-1个圆盘从A(经过C)移到B
二. 把A上第n个圆盘移到C
三: 把B上的(n-1)个圆盘(经过A)移到C
重点!!!!
中间的一步是把最大的一个盘子由A移到C上去;A->C
(1)中间一步之前可以看成把A上n-1个盘子通过借助C塔移到了B上,A->B
(2)中间一步之后可以看成把B上n-1个盘子通过借助A塔移到了C上;B->C
图解:
阶数 | 步骤 |
1 | A->C |
2 | A->B,A->C,B->C |
3 | A->C,A->B,C->B,A->C,B->A,B->C,A->C |
4 | A->B,A->C,B->C,A->B,C->A,C->B,A->B,A->C,B->C,B->A,C->A,B->C,A->B,A->C,B->C |
... | ... |
奇数 | 第一步A->C |
偶数 | 第一步A->B |
发现:
奇数个圆盘第一步永远为A–>C
偶数个圆盘第一步永远为A–>B
代码实现1
仅打印移动次数
#include<stdio.h> int Tower(int num) { if(num==1) return 1; else return 2*Tower(num-1)+1; } int main() { int num=0; int ret=0; printf("请输入层数:"); scanf("%d",&num); ret=Tower(num); printf("需要%d次完成\n",ret); return 0; }
关键步骤
if(num==1) return 1; else return 2*Tower(num-1)+1;
代码实现2
打印移动的具体过程
#include <stdio.h> void Move(char A,char C) { printf("%c --> %c\n",A,C); } void tower(int a,char A,char B,char C)//汉诺塔函数实施主体,A为初始柱,B为经由柱,C为目的柱 { if (a==1) { Move(A,C); } else { tower(a-1,A,C,B);//把n-1个圆盘从A(经过C)移到B Move(A,C); tower(a-1,B,A,C);//把B杆上的(n-1)个圆盘(经过A)移到C } } int Tower(int num) { if (num==1) return 1; else return 2*Tower(num-1)+1; } int main() { int a = 0; int Num=0; printf("请输入层数:"); scanf("%d",&a); Num = Tower(a); printf("%d层需要移动%d步\n", a, Num); tower(a, 'A', 'B', 'C');//进入递归 return 0; }
补充
进阶题:移动盘子的过程中只能够相邻柱间移动,结论:移动次数:f(n)=3^n-1
加载全部内容