【分治算法】Hanoi塔问题Python实现

文章目录

• • @[toc]
  • • 问题描述
    • `Python`实现

个人主页：丷从心·

系列专栏：Python基础

学习指南：Python学习指南

---

问题描述

• 设$a$、$b$、$c$是三个塔座，开始时，在塔座$a$上有一叠共$n$个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为$1$，$2$，$\cdots$，$n$，要求将塔座$a$上的这一叠圆盘移到塔座$b$上，并仍按照同样顺序叠置
• 在移动圆盘时应遵守以下移动规则
  • 每次只能移动一个圆盘
  • 任何时刻都不允许将较大的圆盘压在较小的圆盘之上

---

Python实现

def hanoi(n, source, target, auxiliary):
    if n > 0:
        # 将 n - 1 个盘子从源柱移动到辅助柱
        hanoi(n - 1, source, auxiliary, target)
        # 将第 n 个盘子从源柱移动到目标柱
        print(f'将盘子 {n} 从 {source} 移动到 {target}')
        # 将 n - 1 个盘子从辅助柱移动到目标柱
        hanoi(n - 1, auxiliary, target, source)


n = 3

hanoi(n, 'A', 'B', 'C')
1
2
3
4
5
6
7
8
9
10
11
12
13

将盘子 1 从 A 移动到 B
将盘子 2 从 A 移动到 C
将盘子 1 从 B 移动到 C
将盘子 3 从 A 移动到 B
将盘子 1 从 C 移动到 A
将盘子 2 从 C 移动到 B
将盘子 1 从 A 移动到 B
1
2
3
4
5
6
7

---