汉诺塔移动规则;
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
- 每次只能移动一个圆盘；
- 大盘不能叠在小盘上面。
可以将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。
解决汉诺塔问题的关键在于找到汉诺塔的规则
我们先从一层汉诺塔来看
只有一层的时候我们只需要直接移动到c上面就可（1步）
当有2层的时候，我们要先将上面的移动到B，再将下面的移动到C，然后再将B上的移动到C上（3步）
当有三层的时候，我们需要先将粉色和蓝色的移动到B上，然后将绿色的移动到C上，然后再将蓝色和粉色移动到C上（7步）
那么以此类推，我们可以找出一定的规律
| 层数 | 步数 | 规律 |
| 1 | 1 | 2^1 - 1 |
| 2 | 2 | 2^2 - 1 |
| 3 | 7 | 2^3 - 1 |
| 4 | 15 | 2^4 - 1 |
我们发现步数是由2^层数减1得到的
代码（非递归）
#includeint main() { int n = 0; scanf("%d", &n); printf("完成%d层hanoi的步数:%d", (int)(pow(2, n) - 1));//注意包含头文件 return 0; }
我们再来研究如何用递归的方式完成这个代码
通过规律我们可以看出
第一步就是先将（n-1）层通过C移动到B上
第二步就是将n（底下最大的一层）移动到C上面
第三步就是将（n-1）通过A移动到C上
所以我们可以得到一个公式F(n-1) + 1+F(n-1)
即2*F（n-1）+ 1
代码（递归）
#includeint Hanio(int n) { if (1 == n) return 1; else return 2 * Hanio(n - 1) + 1; } int main() { int n = 0; scanf("%d", &n);//塔数 int ret = Hanio(n); printf("完成%d层的汉诺塔需要%d步n", n, ret); return 0; }
运行结果:
