第050讲：函数（X）- 汉诺塔

小甲鱼 · 发表于 2026-2-23 14:49:39

购买主题 已有 1 人购买 本主题需向作者支付 5 鱼币 才能浏览

版权声明

作者：小甲鱼

版权：本帖内容著作权归作者所有，禁止商业或非商业转载，仅供个人学习使用，违者必究！

来源：https://fishc.com.cn/thread-256050-1-1.html

某一个“天” · 发表于 2026-2-23 15:02:08

a247863072 · 发表于 2026-6-4 18:49:51

@FishC 下列代码的输出结果是？

def is_even(n):
if n == 0:
      return True
return is_odd(n-1)

def is_odd(n):
if n == 0:
      return False
return is_even(n-1)

print(is_odd(36))

A. True
B. False
C. RecursionError
D. 36
这题我最后数出来的莫非要我点着数36次才能得出答案吗？
@FishC 下列代码打印的数字是多少？

def plan(n, s, m, t):
if n == 0:
      return []
return plan(n-1, s, t, m) + [(s, t)] + plan(n-1, m, s, t)

print(len(plan(3, "左", "中", "右")))

A. 3
B. 6
C. 7
D. 9
为什么不是9，前面调用自己从3到2到1到0最后出来一个空列表，空列表也算一个列表，再返回1，也就是空的，1的，2的，3的，加，【左右】后面一样，只是左忠友顺序不一样，但反正是一个列表，4+1+4

@FishC 如果不用递归，改用迭代去“手动模拟”递归的调用过程，最常用的数据结构是？（这题有点超纲^o^）
A. 队列（Queue）
B. 栈（Stack）
C. 集合（Set）
D. 字典（Dict）
不懂
@FishC “递归反人类”的常见破解心法是：写第 n 层时，先相信第 n-1 层能正确解决（把它当黑盒）。落实到编码上，你在当前层最应该做的是？
A. 只关心如何把问题拆成更小的子问题，以及如何用子问题的结果完成当前这一层任务
B. 每次都把递归展开成几十行 if-else，把所有层手写出来
C. 形参实参随便换，跑得起来就行
D. 让 n 随机变化，这样“总会”碰到基例

@FishC 下列代码的输出结果是？

def steps(n):
if n == 1:
      return 1
return 2 * steps(n-1) + 1

print(steps(4))

A. 7
B. 8
C. 15
D. 16
这个应该是2*step（3）+1然后2*（2*step（2）+1）+1
然后2*{2*【2*（2*step（1）+1）+1】+1}
step（1）=1.算出来15

@FishC 在汉诺塔最优解中，“最大”的那个圆盘（最底下那片）会被移动几次？
A. n 次
B. 1 次
C. 2^(n-1) 次
D. 取决于 n 是奇数还是偶数
没算，不会做，猜了A
@FishC 若某个三柱搬运任务的最少移动次数为1023次（规则同汉诺塔），则圆盘数n最可能是？
A. 9
B. 10
C. 11
D. 1023
不会做，猜了1023

FishC · 发表于 2026-6-4 18:50:03

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

答案如下：

第一题：B. False。递归交替判断奇偶，36是偶数，所以is_odd返回False。
第二题：C. 7。plan函数模拟汉诺塔，3个盘最少移动次数为2^3-1=7。
第三题：B. 栈（Stack）。递归本质是函数调用栈，迭代模拟常用栈。
第四题：A。递归心法：只拆分问题，相信子问题能解决，并用子结果完成当前层。
第五题：C. 15。steps(4)=2*steps(3)+1=2*7+1=15。
第六题：B. 1次。汉诺塔最优解中最大的盘子只移动一次。
第七题：B. 10。最少移动次数2^n-1=1023，解得2^n=1024，n=10。

提示：若递归深度过大可能引发RecursionError，本题深度仅36，未超出默认限制。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

FishC · 发表于 2026-6-4 18:50:26

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

第一题： 代码是递归判断奇偶，is_odd(36) 会调用 is_even(35) -> is_odd(34) -> ... 最终到 is_odd(0) 返回 False。所以输出 False，选 B。
第二题： 函数 plan(n, s, m, t) 是汉诺塔移动步骤的递归实现，返回列表长度即移动次数。当 n=3 时，移动次数为 2^3 - 1 = 7，所以输出 7，选 C。
第三题： 手动模拟递归调用过程，常用数据结构是 栈（Stack），因为递归本质上是深度优先的后进先出，故选 B。
第四题： 递归心法：当前层最应该做的是 只关心如何把问题拆成更小的子问题，以及如何用子问题的结果完成当前这一层任务，即选 A。
第五题： steps(4) 计算：steps(1)=1，steps(2)=2*1+1=3，steps(3)=2*3+1=7，steps(4)=2*7+1=15，输出 15，选 C。
第六题： 汉诺塔最优解中，最大圆盘（最底下）只被移动 1 次，即从起始柱直接移到目标柱，故选 B。
第七题： 三柱汉诺塔最少移动次数公式为 2^n - 1 = 1023，则 2^n = 1024，n=10。故选 B。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

FishC · 发表于 2026-6-4 18:50:48

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

第一题答案：B. False。递归交替调用，偶数返回False，奇数返回True，36是偶数，所以False。
第二题答案：C. 7。汉诺塔移动次数为2^n-1，n=3时是7。递归过程：plan(3) = plan(2) + [(左,右)] + plan(2)，而plan(2)=3步，总和7。
第三题答案：B. 栈（Stack）。递归本质是函数调用栈，用栈后进先出可模拟递归。
第四题答案：A. 只关心如何把问题拆成更小的子问题，以及如何用子问题的结果完成当前这一层任务。递归心法就是信任子问题，只处理当前层。
第五题答案：C. 15。逐层计算：steps(1)=1，steps(2)=3，steps(3)=7，steps(4)=2*7+1=15。
第六题答案：B. 1次。最大圆盘在最优解中只需从起始柱直接移到目标柱一次。
第七题答案：B. 10。最少移动次数2^n-1=1023，解得2^n=1024，n=10。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

FishC · 发表于 2026-6-4 18:51:01

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

问题1： 代码输出是 False（选项B）。
因为 is_odd(36) 会交替调用 is_even 和 is_odd，每次 n 减1，一直减到 n=0 时 is_odd(0) 返回 False。你不需要手动数36次，理解“偶数调用 is_odd 最终落在 is_odd(0)”即可。

问题2： len(plan(3, "左", "中", "右")) 输出是 7（选项C）。
这是汉诺塔递归，移动次数公式为 2^n - 1，n=3 时是7步。你的“4+1+4”是错误理解，递归分解结果是 [(左→右), (左→中), (右→中), (左→右), (中→左), (中→右), (左→右)]，共7个。

问题3： 迭代手动模拟递归最常用的数据结构是栈（Stack）（选项B）。
因为递归本质就是函数调用栈，后进先出。

问题4： 写递归时当前层最应该做的是 A：只关心如何拆分子问题及用子问题结果完成当前任务。
相信底层函数正确，把子问题当黑盒。

问题5： steps(4) 输出 15（选项C）。
你推导正确：steps(4)=2*steps(3)+1，逐步计算得15，即 2^4 - 1。

问题6： 汉诺塔中最大圆盘只移动 1 次（选项B）。
因为只需从起始柱直接搬到目标柱，中间过程它的位置一直没变。

问题7： 最少步数1023次对应圆盘数 10（选项B）。
公式 2^n - 1 = 1023，解得 2^n = 1024，n=10。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

FishC · 发表于 2026-6-4 18:51:19

a247863072 发表于 2026-06-04 18:49
@FishC 下列代码的输出结果是？

def is_even(n):
...

第一个问题：代码输出结果是 B. False。这是互递归判断奇偶性，is_odd(36) 表示 36 是偶数，故返回 False。无需手动数 36 次，理解原理即可。
第二个问题：代码输出结果是 C. 7。函数 plan 实现汉诺塔最优移动序列，n=3 时总步数为 2^3 - 1 = 7。len(plan(3,...)) 即为 7。
第三个问题：最常用的数据结构是 B. 栈（Stack）。递归调用本质是函数栈，手动模拟递归常用栈保存状态。
第四个问题：在当前层最应该做的是 A。只关心如何拆分子问题并用子问题结果完成当前层任务，信任下一层能正确解决。
第五个问题：代码输出结果是 C. 15。steps(4)=2*steps(3)+1=2*(2*steps(2)+1)+1=...=15，你算得正确。
第六个问题：最大圆盘移动次数是 B. 1 次。最优解中最大盘只需从起始柱移动到目标柱一次。
第七个问题：圆盘数 n 最可能是 B. 10。因为 2^10 - 1 = 1023。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

a247863072 · 发表于 2026-6-4 18:53:08

第五个问题：代码输出结果是 C. 15。steps(4)=2*steps(3)+1=2*(2*steps(2)+1)+1=...=15，碰到这种我非要用手算一遍吗

@FishC

FishC · 发表于 2026-6-4 18:53:16

a247863072 发表于 2026-06-04 18:53
第五个问题：代码输出结果是 C. 15。steps(4)=2*steps ...

第五个问题：代码输出结果是 C. 15。steps(4)=2*steps(3)+1=2*(2*steps(2)+1)+1=...=15，碰到这种我非要用手算一遍吗@FishC

哈哈，别慌～其实手算一遍递归恰恰是理解递归本质最直观的方法，就像看魔术揭秘一样。但是，如果代码已经写好了，你完全不需要每次都自己手算，计算机会帮你一步步展开的。

对于这个steps(n)函数，它的递推关系是：

steps(1) = 1
steps(n) = 2 * steps(n-1) + 1

复制代码

其实它有一个通项公式：

steps(n) = 2^n - 1

复制代码

验证一下：n=4时，2^4-1=16-1=15，完美匹配！所以以后遇到这种“2倍加1”的规律，直接套公式秒出答案，不用再手算递推了{:10_227:}。

当然，如果你在写代码调试时，手动模拟前几次调用还是很有用的，能帮你快速发现逻辑bug。记住：手算是理解，公式是捷径，电脑是苦力，你只需要聪明地选择方法就行～

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

a247863072 · 发表于 2026-6-4 18:54:51

问题2： len(plan(3, "左", "中", "右")) 输出是 7（选项C）。
这是汉诺塔递归，移动次数公式为 2^n - 1，n=3 时是7步。你的“4+1+4”是错误理解，递归分解结果是 [(左→右), (左→中), (右→中), (左→右), (中→左), (中→右), (左→右)]，共7个。@FishC
这个你把它一步步写出来，我不懂

FishC · 发表于 2026-6-4 18:55:05

a247863072 发表于 2026-06-04 18:54
问题2： len(plan(3, "左", "中", "右")) 输出是 7（ ...

鱼油你好，我来一步步给你拆解 plan(3, "左", "中", "右") 的递归过程。先记住汉诺塔的规则：要把 n 个盘子从源柱移到目标柱，可以借助辅助柱。移动次数确实是 2^n - 1，n=3 时就是 7 步。下面我用递归树的方式把每一步写清楚。

定义：
plan(n, source, auxiliary, target) 表示把 n 个盘子从 source 移到 target，辅助柱为 auxiliary。

递归基：
当 n=1 时，直接移动：source → target。

递归步骤：
对于 n≥2：
1. 先把上面 n-1 个盘子从 source 移到 auxiliary（利用 target 做辅助）。
2. 然后把最底下的大盘子从 source 移到 target。
3. 最后把 n-1 个盘子从 auxiliary 移到 target（利用 source 做辅助）。

第一步： plan(3, "左", "中", "右")
因为 n=3>1，所以先做 plan(2, "左", "右", "中")
（把上面2个盘子从左→中，借助右）

第二步： plan(2, "左", "右", "中")
n=2>1，先做 plan(1, "左", "中", "右")
（把上面1个盘子从左→右，借助中）

第三步： plan(1, "左", "中", "右")
n=1，直接移动：左 → 右【第1步】

第四步： plan(2,...) 的第二步：把剩余最大的盘子（左上的那个）从左移到中。
移动：左 → 中【第2步】

第五步： plan(2,...) 的第三步：把刚才移到右的1个盘子再从中移到中。
注意：现在是 plan(1, "右", "左", "中")
n=1，直接移动：右 → 中  【第3步】

现在 plan(2, "左", "右", "中") 已完成，回到最外层。

第六步： plan(3,...) 的第二步：把最底下的大盘子从左移到右。
移动：左 → 右【第4步】

第七步： plan(3,...) 的第三步：把已经在中柱上的2个盘子移到右柱（借助左柱）。
调用 plan(2, "中", "左", "右")

第八步： plan(2, "中", "左", "右")
先做 plan(1, "中", "右", "左")
n=1，直接移动：中 → 左  【第5步】

第九步： plan(2,...) 的第二步：把剩下的一个盘子（中柱上的）移到右。
移动：中 → 右【第6步】

第十步： plan(2,...) 的第三步：把刚才移到左的盘子再从左移到右。
调用 plan(1, "左", "中", "右")
n=1，直接移动：左 → 右  【第7步】

全部结束，共7步。按顺序列出就是：

左 → 右
左 → 中
右 → 中
左 → 右
中 → 左
中 → 右
左 → 右

复制代码

和你给出的列表完全一致。核心就是递归思想：先把上面两块移到中间，再移最底下那块到右，最后把中间两块移到右。希望对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

a247863072 · 发表于 2026-6-4 18:58:51

  不知道为什么
steps(1) = 1
steps(n) = 2 * steps(n-1) + 1
怎么得出这个通项公式的
steps(n) = 2^n - 1
@FishC

FishC · 发表于 2026-6-4 18:58:59

a247863072 发表于 2026-06-04 18:58
不知道为什么
steps(1) = 1
steps(n) = 2 * steps ...

鱼油你好！这个问题其实是经典的“汉诺塔”递推关系。我们一步步推导：

已知：

steps(1) = 1
steps(n) = 2 × steps(n-1) + 1

两边同时加 1，得到：
steps(n) + 1 = 2 × steps(n-1) + 2 = 2 × (steps(n-1) + 1)

令 b(n) = steps(n) + 1 ，则上式变为：
b(n) = 2 × b(n-1)

同时， b(1) = steps(1) + 1 = 1 + 1 = 2 。

于是 b(n) 是首项为 2、公比为 2 的等比数列：
b(n) = 2 × 2^(n-1) = 2^n

最后， steps(n) = b(n) - 1 = 2^n - 1 。

所以通项公式 steps(n) = 2^n - 1 就得出来了。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

账号		自动登录	找回密码
密码			立即注册

小甲鱼小甲鱼当前离线 UID 9 日志相册贡献荣誉积分 97718 狗仔卡	发表于 2026-2-23 14:49:39 \| 显示全部楼层 \|阅读模式购买主题已有 1 人购买本主题需向作者支付 5 鱼币才能浏览版权声明作者：小甲鱼版权：本帖内容著作权归作者所有，禁止商业或非商业转载，仅供个人学习使用，违者必究！来源：https://fishc.com.cn/thread-256050-1-1.html
小甲鱼小甲鱼当前离线 UID 9 日志相册贡献荣誉积分 97718 狗仔卡	小甲鱼最新课程 -> https://ilovefishc.com
	回复使用道具举报置顶卡千斤顶显身卡

[快问快答] 第050讲：函数（X）- 汉诺塔

版权声明

浏览过的版块