题目描述
汉诺塔是一个古老的数学问题：有三根杆子 A，B，C。A 杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
- 每次只能移动一个圆盘
- 大盘不能叠在小盘上面
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。问：如何移？最少要移动多少次？
输入描述
一行，包含 2 个正整数，一个是 N，表示要移动的盘子数；一个是 M，表示最少移动步数的第 M 步。
输出描述
共 2 行。
第一行输出格式为：#No: a->b，表示第 M 步骤具体移动方法，其中 No 表示第 M 步移动的盘子的编号（N个盘子从上到下依次编号为 1 到 n），表示第M步是将 No 号盘子从 a 杆移动到 b 杆（a和 b 的取值均为 {A、B、C}）。
第 2 行输出一个整数，表示最少移动步数。
输入输出样例
示例 1
输入
3 2
输出
1. #2: A->B 2. 7
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
代码：
1. sum=0 #计数 2. def hanoi(x,y,z,n): 3. global sum 4. #边界条件，当只剩最后一个盘子时，把该盘子移动到c盘即可 5. if n==1: 6. sum=sum+1 7. if sum==m: 8. print("#",n,": ",x,"->",z,sep='') 9. else: 10. #进入第一次递归，盘子x转移到y 11. hanoi(x,z,y,n-1) 12. sum=sum+1 13. if sum==m: 14. print("#",n,": ",x,"->",z,sep='') 15. #第二次递归，盘子从y转移到z 16. 17. hanoi(y, x, z, n-1) 18. 19. n,m=map(int,input().split()) 20. hanoi('A','B','C',n) 21. print(sum)
