python实现递归的汉诺塔

发表于 | 分类于

python实现递归的汉诺塔

汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

此处输入图片的描述

编程思想：

step 1: 将第一个柱子的第n个盘子上的（n-1）的盘子，通过第三个柱子的迁移存放，放到第二个柱子上。

step 2: 然后将第二个柱子上的（n-1）的盘子，通过第一个柱子的迁移存放，放入到第三个柱子上。

step 3: 通过递归的方式一层一层的迁移。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#coding: utf-8
def hanota(n, x, y, z):
        if n == 1:
                print(x+"---->"+z) #当 n=1 则直接将盘子从x移到z上
        else:
                hanota(n-1, x, z, y) # 当 n!=1 时，需要先将x的第n个盘子上的（n-1）个盘子，从x通过z放到y上
                print(x+"---->"+z)   # 然后将第n个盘子放入到z上
                hanota(n-1, y, x, z) # 让后将y上的（n-1）个盘子，通过x放入到z上
num = input("please input the hanota layer number: ")
n = int(num)
hanota(n, 'x', 'y', 'z')
'''
[root@24902b4429c6 lab1]# python hanota.py
please input the hanota layer number: 3
x---->z
x---->y
z---->y
x---->z
y---->x
y---->z
x---->z
'''
def hanota(n):
        step1xtoz = 1
        if n == 1:
                return step1xtoz
        else:
                stepcount = hanota(n-1) + hanota(n-1) + step1xtoz
                return stepcount
num = input("please input the hanota layer number: ")
n = int(num)
count = hanota(n)
print("The step count: ",count)
'''
[root@24902b4429c6 lab1]# python hanota1.py
please input the hanota layer number: 3
('The step count: ', 7)
'''