欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Python学习 - 汉诺塔的实现思想 (递归函数)

程序员文章站 2024-02-12 12:15:04
...

这两天在学习Python的基本知识,学到函数的递归调用时,用汉诺塔来举例子是一个很好的方式,这里把实现思想和代码简单说明一下。

汉诺塔 (hanoi)的由来

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

汉诺塔的原理展示

  • A,B,C三个柱子,盘子在A柱子上按金字塔形状从小到大排列
  • 每次只能移动一个盘子
  • 任何一次移动,必须大盘子在下面,小盘子在上面
  • 最后盘子按顺序从放到C上
    Python学习 - 汉诺塔的实现思想 (递归函数)

###汉诺塔的移动步骤
####前提条件: 有ABC三个柱子,起初所有的盘子在A柱上(最左边),通过不断的移动,把盘子移到最右边的C柱子上。

实现步骤:

1. 只有一个盘子1
    - 把1从A直接挪到C  (A --> C)
2. 俩个盘子1,2
    - 把1从A挪到B    (A --> B)
    - 把2挪到C       (A --> C)
    - 把1从B挪到C    (B --> C)
3. 三个盘子1,2,3
    - 把上面两个借助C先移到B   (2, A-->C-->B):  这里可以不看最底下个盘子,先看上面的两个盘子,借助C先移到B,这里跟两个盘子的移动是一样的。
	- 把1 移到C  (A --> C)
        - 把2 移到B (A --> B)
	- 把1 移到B (C --> B)
    - 把最底下的盘子3移到C               
	- A --> C 
    - 把 1,2 从B借助A移到C  (1,2 在B柱)(2, B-->A-->C)
        - 把 1 移到A
        - 把 2 移到C
        - 把 1 移到C
4. N个盘子 
     - 把上面N-1个先移到B柱 (N-1,A-->C-->B)
     - 把底下第N个移到C柱    (1,A-->C)
     - 把N-1个盘借助A移到C   (N-1, B-->A-->C)

Python代码的汉诺塔实现方式

# 汉诺塔的实现方式
# n: 代表多少个盘子
# A, B, C 代表 起始盘子A,辅助盘子B,目的盘子C

#表示移动位置,从a到b
def move(a,b):
    print(a,"-->",b)
    
# 汉诺塔实现
def hanoi(n, A, B, C):
    if n == 1:
        move(A,C)
        return None
    if n == 2:
        move(A,B)
        move(A,C)
        move(B,C)
        return None
    if n >= 3:
        hanoi(n-1,A, C, B)    #上面的N-1个盘子从A上,借助C,移到B
        move(A,C)             # 把左边最底下的盘子从A移到C
        hanoi(n-1, B, A, C)   # 在B上个N-1个盘子,借助B移到C
        
# 测试
print("1个盘子")
hanoi(1,"A", "B", "C")
print("2个盘子")
hanoi(2,"A", "B", "C")
print("3个盘子")
hanoi(3,"A", "B", "C")        
print("5个盘子 ")
hanoi(5,"A", "B", "C")

思考:其实这里去掉N=2的实现,结果也是一样的,在这里多写一步N=2, 是为了代码的方便阅读。