小甲鱼Python学习笔记

汉诺塔的起源与规则

• 起源：法国数学家编写的印度古老故事
  • 场景：贝纳勒斯圣庙的黄铜板，3根宝针，64块由小到大的晶片
  • 预言：所有晶片移到另一根针时，世界将消失
• 核心规则
  • 每次只能移动1个盘子
  • 任何时候，小片必须在大片上方

汉诺塔的递归解题思路

• 核心策略：分三步走（以n个盘子从X移到Z，借助Y为例）
  1. 把前n-1个盘子从 X移到Y，借助Z
  2. 把最底下的第n个盘子从 X移到Z
  3. 把前n-1个盘子从 Y移到Z，借助X
• 递归拆解逻辑：n-1个盘子的移动问题可继续拆分为n-2个，以此类推，直到n=1
• 对比优势：迭代实现汉诺塔难度大，递归思路简洁且贴合问题本质

汉诺塔的Python递归代码实现

• 函数定义：hanoi(n, x, y, z)
  • 参数说明：n=盘子数量；x=起始针；y=辅助针；z=目标针
• 代码逻辑
  1. 边界条件（n=1）：直接打印x --> z
  2. 递归处理（n>1）
     • 调用hanoi(n-1, x, z, y)：实现步骤1
     • 打印x --> z：实现步骤2
     • 调用hanoi(n-1, y, x, z)：实现步骤3
• 调用示例：输入盘子数，执行hanoi(数量, 'X', 'Y', 'Z')，输出移动步骤

代码验证

• n=3：输出清晰的移动步骤，可直接按步骤完成游戏
• n=4：代码可正确输出复杂移动路径，验证递归有效性