递归:汉诺塔问题

时间:2023-01-23 16:04:15

问题背景

汉诺塔问题源自印度一个古老的传说,印度教的“创造之神”梵天创造世界时做了 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