python5.7汉诺塔_Python汉诺塔

小小码 • 2023-07-22 12:30 • 未分类 • 阅读 122

大家好，我是考100分的小小码，祝大家学习进步，加薪顺利呀。今天说一说python5.7汉诺塔_Python汉诺塔,希望您对编程的造诣更进一步.

简介

汉诺塔，又称河内塔，是根据一个传说形成的数学问题：

有三根柱子 A， B， C。A 杆上有 N 个（N > 1）穿圆孔盘，盘的尺寸又下到上依次变小。要按照下列规则将所有圆盘移至 C 杆：

1.每次只能移动一个圆盘；

2.大盘不能叠在小盘上面。

问：如何移？最少需要移动多少字？

—— 摘自维基百科（自备梯子）

汉诺塔Python代码

先亮代码：

def hanoi(n, a, b, c): if n == 1:
        print a, '-->', c
        return
    hanoi(n-1, a, c, b)
    print a, '-->', c
    hanoi(n-1, b, a, c)
    hanoi(4, 'A', 'B', 'C')

解析

解法的基本思想是递归。

现有 A，B，C 三塔，A 塔有 x 个圆盘，目标是把这这些圆盘全部移到 C 塔。要求小盘必须在大盘之上，故而必然会有一步使一大坨（x – 1）个盘子在 B 塔上，以便 A 塔最大的盘子移到 C 塔。

至此，第一步完成。

为方便理解，让我们从头开始，把 B 塔（x – 1）个盘子看成 y 个，即：

现有 B， A， C 三塔，B 塔有 y 个圆盘，目标是把这些圆盘全部移到 C 塔。要求小盘必须在大盘之上，故而必然会有一步使一大坨（y – 1）个盘子在 A 塔上，以便 B 塔最大的盘子移到 C 塔。

至此，第二步完成。

第三步，还是从头开始，把 A 塔上（y – 1）个盘子看成 z 个，即：

现有 A，B， C 三塔，A 塔有 z 个圆盘，目标是把这些圆盘全部移到 C 塔。要求小盘必须在大盘之上，故而必然会有一步使一大坨（z – 1）个盘子在 A 塔上，以便 A 塔最大的盘子移到 C 塔。

至此，第三步完成。相信聪明的小伙伴已经看出来了，只要不断重复第一第二步，周而复始，即可解出此题。

详解 Python 算法

故，可以以此规律设计出 Python 程序算法：

首先定义一个汉诺塔移动函数，hanoi(n, a, b, c)， n代表 A 塔上盘子个数，a代表 A 塔（初始塔）， b带表 B 塔（缓存塔）， c代表 C 塔（目标塔）。

递归总是要有终止条件的，显而易见，就是当初始塔上只有一个最大盘子的时候即终止本次递归并返回，并把初始塔最后一个盘子移到目标塔，即打印print(a, '-->', c)。

首先来移动开始的（n – 1）个圆盘，为什么要这样移呢？玩多了就知道了，归纳总结出来的经验。怎么移呢？通过目标塔暂时存放到缓存塔，抽象出来的代码为hanoi(n-1, a, c, b)，此函数进入递归。

不好理解？好吧，换一种方式写：hanoi(n-1, a, c, b)===hanoi(n-1, 初始塔，缓存塔，目标塔)，清楚了吧，就像上面说的，把这（n-1）个盘子看成一局新游戏，切不可把 a c b 这几个形参当成实参，网上其他解析让人看的云里雾里的原因就在这。此时 A 塔为初始塔，B 塔为目标塔，C 塔为缓存塔，套用初始塔上盘子通过目标塔暂存到缓存塔，以便最大盘移至目标塔 这句话。

接下来打印每次移动：print(a, '-->', c) ,换一种方式写：print(初始塔, '-->', 目标塔)，同样不要被形参带飞咯。。。

这不，A 塔上（n-1）个盘子已经移到 B 塔上了，接下来当然要把 B 塔上的盘子移到 C 塔，这样才能完成汉诺塔这个游戏啊。想想此时初始塔、缓存塔、目标塔分别是 A、 B、 C 的哪一个？

此时 B 塔是初始塔，A 塔是缓存塔， C 塔是目标塔，代码为：hanoi(n-1, b, a, c) 。

def hanoi(盘子个数, 初始塔, 缓存塔, 目标塔)
    if 盘子个数 == 1:
        print 初始塔,'移到', 目标塔
        return
    hanoi(盘子个数-1, 初始塔, 缓存塔, 目标塔)
    print 初始塔,'移到', 目标塔
    hanoi(盘子个数-1, 初始塔, 缓存塔, 目标塔)

    def hanoi(n, a='A', b='B', c='C'): 
    if n == 1:
        print a, '-->', c
        return
    hanoi(n-1, a, c, b)
    print  a, '-->', c
    hanoi(n-1, b, a, c)
    hanoi(4)