汉诺塔问题是使用递归解决问题的经典范例。
汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。
- 如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。
- 如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。
- 如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。
- 代码如下：
-
#include<stdio.h>
拓展：递推公式：f(n)=f(n-1)*2+1;
#include<string.h>
#include<stdlib.h>
#include<limits.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<math.h>
#define maxn 1000005
int step;
void move(int a,int b)
{
printf("move from %d to %d \n",a,b);
}
void hanoi(int n,int a,int b,int c)//a表示起点，b表示过渡的柱子，c表示终点
{
if(n==1)
{
++step;
move(a,c);
}
else
{
++step;
move(a,c);
hanoi(n-1,a,c,b);
hanoi(n-1,b,a,c);
}
}
int main()
{
int T,i,j,n;
scanf("%d",&T);
while(T--)
{
step=0;
scanf("%d",&n);
hanoi(n,1,2,3);
printf("Total steps is %d\n",step);
}
} - 拓展题目如下：
-
汉诺塔（二）
时间限制：3000 ms | 内存限制：65535 KB难度：5- 描述
-
汉诺塔的规则这里就不再多说了，详见题目：汉诺塔（一）
现在假设规定要把所有的金片移动到第三个针上，给你任意一种处于合法状态的汉诺塔，你能计算出从当前状态移动到目标状态所需要的最少步数吗？
- 输入
-
第一行输入一个整数N，表示测试数据的组数(0<N<20)
每组测试数据的第一行是一个整数m表示汉诺塔的层数(0<m<32)，随后的一行有m个整数Ai,表示第i小的金片所在的针的编号。（三根针的编号分别为1，2，3） - 输出
- 输出从当前状态所所有的金片都移动到编号为3的针上所需要的最少总数
- 样例输入
-
2
3
1 1 1
3
1 1 3 - 样例输出
-
7
3 - 代码如下：
-
#include<stdio.h>
#include<string.h>
int step[33],num[33];
void find()
{
step[0]=1;
for(int i=1;i<=33;i++)
step[i]=step[i-1]*2;
}
int main()
{
find();
int t,n,m;
scanf("%d",&t);
while(t--)
{
int t=3,i,sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&num[i]);
for(i=n-1;i>=0;i--)
{
if(num[i]!=t)
{
sum+=step[i];
t=6-num[i]-t;//当n-1时，如果第n-1小的（也就是最大的）不在3号针上，比如在2上，则会把小于第n-1个盘的其他盘移到1号针上去
//然后判断第n-2小的盘在不在1号针上，依次类推......也就是针的总和数6减去num[i]所在的号数，减去n-1个盘所在的位置（自己模拟画画图）
}
}
printf("%d\n",sum);
}
}