人工智能通识 题目一

汉诺塔问题

题目描述

有 3 根柱子（记为 A、B、C）和 n 个大小互不相同的圆盘，所有圆盘初始时都套在柱子 A 上，且圆盘按 “上小下大” 的顺序叠放（大圆盘不能放在小圆盘上方）。要求将所有圆盘从柱子 A 移动到柱子 C，期间可借助柱子 B 作为辅助，每次只能移动 1 个圆盘。请编写程序，输出移动圆盘的每一步操作步骤。

输入要求

输入一个正整数 n（表示圆盘的数量，1≤n≤10，避免递归深度过大）。

输出要求

每行输出一步移动操作，格式为：移动圆盘x从柱子X到柱子Y（其中 x 为圆盘编号，按 “上小下大” 编号为 1~n；X、Y 为柱子编号 A/B/C）。

用例输入1

n=1

用例输出1

移动圆盘1从柱子A到柱子C

用例输入2

n=2

用例输出2

移动圆盘1从柱子A到柱子B

移动圆盘2从柱子A到柱子C

移动圆盘1从柱子B到柱子C

用例输入3

n=3

用例输出3

移动圆盘1从柱子A到柱子C

移动圆盘2从柱子A到柱子B

移动圆盘1从柱子C到柱子B

移动圆盘3从柱子A到柱子C

移动圆盘1从柱子B到柱子A

移动圆盘2从柱子B到柱子C

移动圆盘1从柱子A到柱子C

def hanoi(n, source, auxiliary, target): """ 递归实现汉诺塔移动逻辑 :param n: 当前需要移动的圆盘数量 :param source: 起始柱子（如'A'） :param auxiliary: 辅助柱子（如'B'） :param target: 目标柱子（如'C'） """ if n == 1: # 递归终止条件：只有1个圆盘时，直接从起始柱移到目标柱 print(f"移动圆盘1从柱子{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) # 处理用户输入并调用函数 if __name__ == "__main__": # 获取用户输入的圆盘数量，确保输入是1~10的正整数 while True: try: n = int(input("请输入圆盘数量n（1≤n≤10）：")) if 1 <= n <= 10: break else: print("输入错误！请输入1到10之间的正整数。") except ValueError: print("输入错误！请输入有效的整数。") # 调用汉诺塔函数，起始柱A，辅助柱B，目标柱C hanoi(n, 'A', 'B', 'C')