农夫抓牛问题Python解决方案
汉诺塔问题的递归解法遵循以下核心规则：
要将 n 个圆盘从源柱（A） 移动到目标柱（C），需借助辅助柱（B），可拆解为3步：
将 n-1 个圆盘从 A → B（借助 C 作为辅助）；
将第 n 个圆盘（最大的圆盘）从 A → C（直接移动）；
将 n-1 个圆盘从 B → C（借助 A 作为辅助）。
当 n=1 时（递归终止条件），直接将圆盘从 A 移动到 C 即可。
Python 代码实现
python
def hanoi(n, source, auxiliary, target):
"""
递归实现汉诺塔问题
:param n: 圆盘数量
:param source: 源柱子（初始为'A'）
:param auxiliary: 辅助柱子（初始为'B'）
:param target: 目标柱子（初始为'C'）
"""
if n == 1:
# 递归终止条件：直接移动最后一个圆盘到目标柱
print(f"移动圆盘{n}从柱子{source}到柱子{target}")
return
# 步骤1：将n-1个圆盘从源柱→辅助柱（借助目标柱）
hanoi(n-1, source, target, auxiliary)
# 步骤2：将第n个圆盘从源柱→目标柱
print(f"移动圆盘{n}从柱子{source}到柱子{target}")
# 步骤3：将n-1个圆盘从辅助柱→目标柱（借助源柱）
hanoi(n-1, auxiliary, source, target)
# 输入处理
n = int(input("请输入圆盘数量n: "))
# 调用递归函数（初始源柱A，辅助柱B，目标柱C）
hanoi(n, 'A', 'B', 'C')
代码验证（与用例一致）
输入n=1：输出 移动圆盘1从柱子A到柱子C
输入n=2：输出与用例2完全一致
输入n=3：输出与用例3完全一致
关键说明
圆盘编号：按“上小下大”规则，最上方圆盘为 1，最下方（最大）圆盘为 n，符合题目要求。
递归深度：题目限制 n≤10，而Python默认递归深度上限为1000，因此不会出现栈溢出问题。
通用性：函数参数 source、auxiliary、target 可灵活调整柱子顺序，若需改变移动方向（如A→B），只需修改初始调用的参数即可。
汉诺塔问题的递归解法遵循以下核心规则：
要将 n 个圆盘从源柱（A） 移动到目标柱（C），需借助辅助柱（B），可拆解为3步：
将 n-1 个圆盘从 A → B（借助 C 作为辅助）；
将第 n 个圆盘（最大的圆盘）从 A → C（直接移动）；
将 n-1 个圆盘从 B → C（借助 A 作为辅助）。
当 n=1 时（递归终止条件），直接将圆盘从 A 移动到 C 即可。
Python 代码实现
python
def hanoi(n, source, auxiliary, target):
"""
递归实现汉诺塔问题
:param n: 圆盘数量
:param source: 源柱子（初始为'A'）
:param auxiliary: 辅助柱子（初始为'B'）
:param target: 目标柱子（初始为'C'）
"""
if n == 1:
# 递归终止条件：直接移动最后一个圆盘到目标柱
print(f"移动圆盘{n}从柱子{source}到柱子{target}")
return
# 步骤1：将n-1个圆盘从源柱→辅助柱（借助目标柱）
hanoi(n-1, source, target, auxiliary)
# 步骤2：将第n个圆盘从源柱→目标柱
print(f"移动圆盘{n}从柱子{source}到柱子{target}")
# 步骤3：将n-1个圆盘从辅助柱→目标柱（借助源柱）
hanoi(n-1, auxiliary, source, target)
# 输入处理
n = int(input("请输入圆盘数量n: "))
# 调用递归函数（初始源柱A，辅助柱B，目标柱C）
hanoi(n, 'A', 'B', 'C')
代码验证（与用例一致）
输入n=1：输出 移动圆盘1从柱子A到柱子C
输入n=2：输出与用例2完全一致
输入n=3：输出与用例3完全一致
关键说明
圆盘编号：按“上小下大”规则，最上方圆盘为 1，最下方（最大）圆盘为 n，符合题目要求。
递归深度：题目限制 n≤10，而Python默认递归深度上限为1000，因此不会出现栈溢出问题。
通用性：函数参数 source、auxiliary、target 可灵活调整柱子顺序，若需改变移动方向（如A→B），只需修改初始调用的参数即可。
数字金字塔的结构是：第 i 行有 i 个数字，每个数字只能向下或向右下移动。我们需要找到从顶部（第1行）到底部（第R行）的一条路径，使得路径上的数字之和最大。
关键观察：
对于第 i 行第 j 列的数字 pyramid[i][j]，其最大路径和等于自身加上下方两个数字的最大路径和（即 max(pyramid[i+1][j], pyramid[i+1][j+1])）。因此，我们可以从底部开始向上递推，逐步更新每个位置的最大路径和，最终顶部的数字即为答案。
算法思路
输入处理：读取行数 R 和数字金字塔的每一行。
动态规划递推：从倒数第二行开始，向上逐行更新每个位置的最大路径和：
对于第 i 行第 j 列的数字，更新为 pyramid[i][j] + max(pyramid[i+1][j], pyramid[i+1][j+1])。
输出结果：顶部（第0行第0列）的数字即为最大路径和。
代码实现（Python）
python
# 读取输入
R = int(input())
pyramid = []
for _ in range(R):
row = list(map(int, input().split()))
pyramid.append(row)
# 从倒数第二行开始向上递推
for i in range(R-2, -1, -1):
for j in range(len(pyramid[i])):
# 当前位置的最大路径和 = 自身 + 下方两个位置的最大值
pyramid[i][j] += max(pyramid[i+1][j], pyramid[i+1][j+1])
# 顶部即为最大路径和
print(pyramid[0][0])
代码解释
输入处理：
读取行数 R。
逐行读取数字金字塔的每一行，存储为二维列表 pyramid。
动态规划递推：
外层循环从倒数第二行（R-2）向上遍历到第0行（顶部）。
内层循环遍历当前行的每个位置 j，更新其值为自身加上下方两个位置的最大值。
例如，对于样例输入的倒数第二行 [6, 14, 15, 8]，处理后变为：
6 + max(12,7) = 18，14 + max(7,13)=27，15 + max(13,24)=39，8 + max(24,11)=32，即 [18,27,39,32]。
输出结果：
经过递推后，顶部（pyramid[0][0]）的值即为从顶部到底部的最大路径和。
复杂度分析
时间复杂度：O(R²)，其中 R 是行数。需要遍历每一行的每个元素，共 1+2+...+R = R(R+1)/2 次操作。
空间复杂度：O(R²)，用于存储数字金字塔。若直接在输入的二维列表上修改（如代码所示），空间复杂度可优化为 O(1)（不额外占用空间）。
示例验证
以样例输入为例：
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
递推过程如下：
第4行（底部）：[12,7,13,24,11]（不变）。
第3行：6+max(12,7)=18，14+max(7,13)=27，15+max(13,24)=39，8+max(24,11)=32 → [18,27,39,32]。
第2行：12+max(18,27)=39，7+max(27,39)=46，26+max(39,32)=65 → [39,46,65]。
第1行：11+max(39,46)=57，8+max(46,65)=73 → [57,73]。
第0行：13+max(57,73)=86 → 最终结果为 86，与样例输出一致。
该方法高效且易于理解，适用于行数较大的情况（如题目中 R≤1000 时，1000²=1e6 次操作完全可行）。
————————————————
版权声明：本文为CSDN博主「yanghusu」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yanghusu/article/details/156160204
