题目
汉诺塔问题：有 3 根柱子 A、B、C，A 柱上有 3 个大小不同的圆盘（小的在上面）。每次只能移动一个圆盘，且大圆盘不能放在小圆盘上面。要将所有圆盘从 A 柱移到 C 柱，最少需要移动多少次？
解法
设 f(n) 表示移动 n 个圆盘所需的最少次数。
要把 n 个圆盘从 A 移到 C，需要：
先把上面 n−1 个圆盘从 A 移到 B（借助 C），需要 f(n−1) 次。
再把最大的圆盘从 A 移到 C，需要 1 次。
最后把 n−1 个圆盘从 B 移到 C（借助 A），需要 f(n−1) 次。
递推公式：f(n) = 2 × f(n−1) + 1。
基础情况：f(1) = 1（直接移动）。
f(1)=1按递推公式计算：
f(2)=2 × f(1) + 1 = 2 × 1 + 1 = 3f(3)=2 × f(2) + 1 = 2 × 3 + 1 = 7移动 3 个圆盘最少需要 7 次。
方法
练一练
汉诺塔问题：有 4 个大小不同的圆盘，每次只能移动一个，大圆盘不能放在小圆盘上面。将所有圆盘从 A 柱移到 C 柱，最少需要移动多少次？