一、什么是汉诺塔
1、汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。问应该如何操作？
2、汉诺塔游戏在线 点我就可以玩哦
二、代码实现
1、非递归实现打印步数
寻找规律
| 层数 | 步数 |
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| … | … |
| n | 2^n - 1 |
代码
#include <stdio.h> #include <math.h> int main() { int n = 0; while(scanf("%d", &n)!=EOF)//输入汉诺塔层数 { //getchar(); printf("%d层汉诺塔需要移动%d步\n", n, (int)pow(2, n) - 1); } return 0; }
2、递归实现打印步数
通过一个函数f1(),当层数为1时步数为1，即f(1)=1
f(n)可表示为f(n-1)*2+1
代码
#include <stdio.h> #include <math.h> int f1(int n) { if (n == 1) { return 1; } else { return f1(n - 1) * 2 + 1; } } int main() { int n = 0; while (scanf("%d", &n) != EOF)//输入汉诺塔层数 { //getchar(); printf("%d层汉诺塔需要移动%d步\n", n, f1(n)); } return 0; }
3、递归实现打印步骤
- 把1层从左边塔移到右边塔,直接从左边塔到右边塔需要一步
- 把2层从左边塔移到右边塔,需要先把第一个移到中间塔,再把最后一个移到右边塔,然后把中间的移到右边塔
- 把3层从左边塔移到右边塔,需要先借助右边塔把前两个移到中间塔,再把最后一个移到右边塔,然后借助左边塔把中间的移到右边塔
- 把n层从左边塔移到右边塔,需要先借助右边塔把前n-1个移到中间塔,再把最后一个移到右边塔,然后借助左边塔把中间的移到右边塔
- 递归函数hanoi()有四个参数,一个int型层数,三个char型塔
#include <stdio.h> void hanoi(int n, char a, char b, char c) { if (n == 1) { printf("%c->%c\n", a, c);//一层直接从A塔到C塔 } else { hanoi(n - 1, a, c, b);//先借助C塔将n-1层移到B塔 printf("%c->%c\n", a, c);//将剩余一个移到C塔 hanoi(n - 1, b, a, c);//借助A塔将n-1层从B塔移到C塔 } } int main() { int n = 0; scanf("%d", &n); hanoi(n, 'A', 'B', 'C'); return 0; }
可以点开小游戏验证步骤是否正确
三、总结
理解汉诺塔问题,,需要基本掌握递归思想,对n层汉诺塔把n-1层当一个整体移动,对n-1层把n-2层当作整体移动,一直到一层直接移动,对剩下的一个进行单独处理即可。
