汉诺塔递归公式分析

int hanoi(int n) {
    if (n == 1) return 1;
    return 2 * hanoi(n - 1) + 1;
}

递推式： $\( \begin{cases} f(1)=1\\ f(n)=2\cdot f(n-1)+1 \end{cases} \)$

求通项公式

这是标准一阶线性递推。 $\( \begin{aligned} f(n)+1 &= 2\big(f(n-1)+1\big)\\ f(1)+1 &= 2 \end{aligned} \)$

\(\{f(n)+1\}\)是首项为2、公比为2的等比数列：

\[ f(n)+1 = 2^n \]

通项：\(\boldsymbol{f(n)=2^n -1}\)

汉诺塔移动次数：n个盘子，需要 \(2^n-1\) 次。

笔算 hanoi(20)

\[ f(20)=2^{20}-1 \]

先记常用2的幂：

  • \(2^{10}=1024\)
  • \(2^{20}=(2^{10})^2 = 1024\times1024\)

笔算： $\( 1024\times 1024 =1024\times(1000+24) =1\,024\,000 + 24\,576 =1\,048\,576 \)$

\[ 2^{20}-1 = 1\,048\,576 -1 = \boldsymbol{1\,048\,575} \]

所以 hanoi(20) 结果：1048575

做题快速技巧

  1. 看到递归：f(n)=2*f(n\(f(n)=2f(n\(2^n‑1\)1)+2\)1)+1,f(1)=1，直接背结论：\(\boldsymbol{f(n)=2^n-1}\)，不用一层层递归展开算。
  2. 小值验证：
    • \(n=1:2^1-1=1\) ✔
    • \(n=2:2^2-1=3\) ✔（移3次）
    • \(n=3:2^3-1=7\) ✔
  3. 考试笔算：记住 \(2^{10}=1024\)，\(2^{20}=1024^2\)，\(2^{30}=1024^3\)。

注意：C++ int 一般是32位，最大能存到 \(2^{31}-1\)。\(2^{20}-1\) 没问题；n=31的时候int就溢出了。

举一反三

如果递推式变形：

  • \(f(n)=2f(n\(f(n)=2f(n\(2^n‑1\)1)+2\)1)+2\)，就不能直接套\(2^n\(f(n)=2f(n\(2^n‑1\)1)+2\)1\)，要重新构造等比数列。 但标准汉诺塔模板就是 \(f(n)=2^n-1\)。

考试草稿完整演算（纸上直接这么写）

题目递归：

int hanoi(int n) {
    if (n == 1) return 1;
    return 2 * hanoi(n - 1) + 1;
}
hanoi(20)

递推关系： $\( \begin{cases} f(1)=1\ f(n)=2f(n-1)+1 \end{cases} \)$

步骤1：构造等比数列（草稿书写版）

\[ \begin{align*} f(n) &= 2f(n-1)+1 \ f(n)+k &= 2\big(f(n-1)+k\big) \ f(n)+k &=2f(n-1)+2k \ f(n) &=2f(n-1)+k \end{align*} \]

对比原式 \(f(n)=2f(n-1)+1\)，得 \(\boldsymbol{(\boldsymbol{k=1})}\)。

得到： $\( \boldsymbol{f(n)+1 = 2\big(f(n-1)+1\big)} \)$

步骤2：求首项

\[ f(1)+1 =1+1=2 \]

数列 \({f(n)+1}\)：首项 \(2\)，公比 \(2\) 的等比数列。

等比数列通项： $\( f(n)+1 = 2 \cdot 2^{n-1}=2^n \)\( \)\( \boldsymbol{f(n)=2^n-1} \)$

步骤3：代入 (n=2)0，笔算

\[ f(20)=2^{20}-1 \]

已知 $\( 2^{10}=1024 \)\( \)\( 2^{20}= (2^{10})^2 =1024 \times 1024 \)$

笔算乘法草稿： $\( \begin{aligned} 1024 \times 1024 &=1024\times(1000+24)\ &=1024\times1000 ;+; 1024\times24 \ &=1,024,000 + 24,576 \ &=1,048,576 \end{aligned} \)$

\[ f(20)=1,048,576 - 1 = \boldsymbol{1,048,575} \]

步骤4：小样本检验（防止推导错，考试必做）

  • \((n=1)\)：\(2^1-1=1\) ✔
  • \((n=2)\)：\(2^2-1=3\) ✔
  • \((n=3)\)：\(2^3-1=7\) ✔

考场速记

递归形式：f(n)=2*f(n‑1)+1，f(1)=1 \(\Rightarrow \boldsymbol{f(n)=2^n-1}\)，直接套，不要递归一层一层算。

坑点提醒（CSP‑J选择题常考）

32位int范围：\(\boldsymbol{-2^{31} \sim 2^{31}-1}\)

  • \(2^{31}-1=2147483647\)
  • \((n=3)1\)：\(2^{31}-1\) 刚好int上限
  • \((n=3)2\)：\(2^{32}-1\)，int溢出，要使用long long。

拓展小练习（你可以自己算）

求 hanoi(10) 的值？

点击看答案 \(2^{10}-1 =1024-1=\boldsymbol{1023}\)

如果你需要，我可以再给你讲：遇到 f(n)=2f(n‑1)+c 这种通用题型的快速构造套路，不管常数c是几都能秒推通项。