Python 实现递归算法之汉诺塔

如图的小游戏,汉诺塔:

Python 实现递归算法之汉诺塔

 游戏的目的是将最左边的三块移动到最右边,游戏即为成功。

下面按照代码的步骤进行移动,三根柱子分别代表了x,y,z:

Python 实现递归算法之汉诺塔

发现可以实现游戏目的!

 Python 实现递归算法之汉诺塔

当然,三个对于很多人来说并不难实现目标,但是当块变成了5个甚至8个呢

下面,我们来试试7个方块,同样是三根柱子,人的计算就很难实现游戏目标了

Python 实现递归算法之汉诺塔

 所以我们用代码来试试:

Python 实现递归算法之汉诺塔

 可以看到非常长,所以我来按照他的指示来进行游戏

Python 实现递归算法之汉诺塔

 游戏成功!

总共有128步操作,如果人为的来进行游戏的话,很有可能会出错。

所以在此运用了递归算法,编写递归函数来教我们如何进行下一步。

以下是汉诺塔的源代码:

def hanoi(n ,x ,y ,z):
    if n == 1:
        print(x, ‘-->‘ ,z)

    else:

        hanoi(n-1,x,z,y)
        print(x ,‘-->‘ ,z)
        hanoi(n-1,y,x,z)

n = int(input("请输入层数:"))

hanoi(n,‘x‘,‘y‘,‘z‘)

相关推荐