汉诺塔递归函数,农夫抓牛问题,数字金字塔最大路径和问题

def hanoi(n, source, target, auxiliary): """ 汉诺塔递归函数 :param n: 当前要移动的圆盘数量 :param source: 起始柱子 :param target: 目标柱子 :param auxiliary: 辅助柱子 """ if n == 1: # 最小情况：直接将圆盘1从源移动到目标 print(f"移动圆盘1从柱子{source}到柱子{target}") else: # 步骤1：将上面n-1个圆盘从source -> auxiliary（借助target） hanoi(n - 1, source, auxiliary, target) # 步骤2：将第n个圆盘（最大的）从source -> target print(f"移动圆盘{n}从柱子{source}到柱子{target}") # 步骤3：将n-1个圆盘从auxiliary -> target（借助source） hanoi(n - 1, auxiliary, target, source) # 主程序 if __name__ == "__main__": try: n = int(input("请输入圆盘数量n（1≤n≤10）：")) if not (1 <= n <= 10): print("n必须在1到10之间！") else: hanoi(n, 'A', 'C', 'B') except ValueError: print("请输入一个有效的整数！")

...........................................................................................................................................................

from collections import deque def min_time_to_catch_cow(N, K): """ 使用 BFS 求农夫抓牛的最短时间 农夫可以在数轴上通过三种方式移动：X-1, X+1, 2*X，每步耗时 1 分钟 目标是找到从 N 到 K 的最少时间（步数） :param N: 农夫起始位置 :param K: 牛的位置（目标） :return: 最少花费的时间（分钟） """ if N >= K: # 如果农夫在牛的右边或正好在牛的位置，只能一步步往左走 return abs(N - K) # BFS 初始化 queue = deque([(N, 0)]) # (位置, 时间) visited = set() visited.add(N) # 设定搜索范围，避免无限扩张 max_bound = 2 * K if K < 100000 else 100000 while queue: pos, time = queue.popleft() # 如果到达目标位置 if pos == K: return time # 生成下一步可能的位置：X-1, X+1, 2*X next_positions = [pos - 1, pos + 1, 2 * pos] for next_pos in next_positions: # 只处理有效且未访问过的位置 if 0 <= next_pos <= max_bound and next_pos not in visited: visited.add(next_pos) queue.append((next_pos, time + 1)) # 主程序 if __name__ == "__main__": try: # 增加清晰的用户提示 print("🐄 农夫抓牛问题") print("请输入农夫和牛的位置（两个整数，空格分隔）：") print("说明：") print(" - 农夫起始位置 N (0 ≤ N ≤ 100000)") print(" - 牛的位置 K (0 ≤ K ≤ 100000)") print(" - 移动方式：X-1、X+1 或 2*X，每次耗时 1 分钟\n") N, K = map(int, input("请输入 N 和 K：").strip().split()) if not (0 <= N <= 100000) or not (0 <= K <= 100000): print("❌ 输入错误：N 和 K 必须在 0 到 100000 之间！") else: result = min_time_to_catch_cow(N, K) print(f"\n✅ 成功！农夫最少需要 {result} 分钟抓住牛。") except ValueError: print("❌ 输入格式错误！请确保输入两个有效的整数，例如：5 17") except Exception as e: print(f"⚠️ 程序发生未知错误：{e}")

.......................................................................................................................................................

def solve_pyramid(): print("📐 数字金字塔最大路径和问题") print("=" * 40) print("规则说明：") print("• 从顶部出发，每步可走向下一行的左下方或右下方") print("• 目标是找到一条路径，使得经过的数字之和最大") print("• 所有数字为非负整数且 ≤ 100\n") try: # 第一步：输入行数 while True: R_str = input("请输入金字塔的行数 R (1≤R≤1000)：").strip() if not R_str: print("⚠️ 输入不能为空，请重新输入。") continue try: R = int(R_str) if 1 <= R <= 1000: break else: print("❌ R 必须在 1 到 1000 之间，请重新输入。") except ValueError: print("❌ 请输入一个有效的整数！") print(f"\n✅ 开始输入 {R} 行金字塔数据（第 i 行应有 i+1 个数字）：") pyramid = [] for i in range(R): while True: row_input = input(f"第 {i + 1} 行 ({i + 1} 个数字): ").strip() if not row_input: print(" ⚠️ 这一行不能为空，请重新输入。") continue try: row = list(map(int, row_input.split())) if len(row) != i + 1: print(f" ❌ 错误：这一行需要 {i + 1} 个数字，但你输入了 {len(row)} 个。请重试。") continue # 检查每个数是否合法 valid = all(0 <= x <= 100 for x in row) if not valid: print(" ❌ 所有数字必须是非负且不超过 100，请重新输入。") continue pyramid.append(row) break except ValueError: print(" ❌ 包含无效字符，请只输入用空格分隔的整数！") # 动态规划求解（自底向上） # 创建 dp 表，最后一行初始化为原值 dp = [row[:] for row in pyramid] # 深拷贝 # 从倒数第二行开始向上更新 for i in range(R - 2, -1, -1): for j in range(i + 1): dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]) max_sum = dp[0][0] print("\n🎉 计算完成！") return max_sum except KeyboardInterrupt: print("\n\n👋 程序被用户中断。") exit(0) except Exception as e: print(f"\n❌ 程序发生未预期错误：{e}") return None # 主程序入口 if __name__ == "__main__": result = solve_pyramid() if result is not None: print(f"\n🏆 最大路径和为：{result}")