汉诺塔问题的详细讲解（python版）_汉诺塔python

2022.3.17
2022.11.15 增加次数计算
1
2

一．抽象为数学问题：

从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。【图 n=3】

二 条件

1. 最开始A柱有放好的盘子，移到C放好
2. 每次只能移动一个圆盘
3. 任何时刻都不能将一个较大的圆盘压到较小的圆盘纸上

三 讲解

1. 创建个汉罗塔函数hanoi(A,B,C,n)

   n是几个盘子，A,B,C分别表示柱子

2. 当 n=1时，只有一个盘子 那个直接 A柱内容 移到 C柱内容
   我们看函数，四个参数，其实就是第1个参数移到第3个参数（点非常重要,后面会用到）

def hanoi(A, B, C, n):
	if n == 1:
		print(A, '->', C)
1
2
3

3. 当n>1时 ,我们发现A柱初始状态下，上面是n-1的汉罗塔初始状态+最下面的大盘

我们 把上面n-1个汉罗塔看成整体 ，只需做下面三步：

• ① 借助C柱我们先把 n-1汉罗塔 移到B柱子
  
• ② 借助B,把A 移到 C

• ③ 把B柱 n-1汉罗塔 移到 C

四 代码

def hanoi(A, B, C, n):
	if n == 1:
		print(A, '->', C)
	eles:
		#将A柱中n-1汉罗塔 移到B住
		hanoi(A,C,B,n-1)

		# 将A中最大的地盘 移到C,没有移动汉罗塔，所以直接输出
		print(A, '->', C)

		# 将B柱中n-1汉罗塔看成整体 移到C柱
		hanoi(B,A,C,n-1)
1
2
3
4
5
6
7
8
9
10
11
12

汉罗塔内部顺序写法，根据的是：

五 实例 n=4

def hanoi(A, B, C, n):
    if n == 1:
        print(A, '->', C)
    else:
        hanoi(A,C,B,n-1)
        print(A, '->', C)
        hanoi(B,A,C,n-1)
        
hanoi('A','B','C',4)
1
2
3
4
5
6
7
8
9

A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
A -> C
B -> C
B -> A
C -> A
B -> C
A -> B
A -> C
B -> C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

六 关于移动次数的计算

• 用参数每次带入

def hanoi(A, B, C, n):
    time = 0
    if n == 1:
        print(A, '->', C)
        time += 1
    else:
        time +=hanoi(A,C,B,n-1)
        print(A, '->', C)
        time += 1
        time +=hanoi(B,A,C,n-1)
    return(time)

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

• 全局变量global

time = 0
def hanoi(A, B, C, n):
    global time
    if n == 1:
        print(A, '->', C)
        time += 1
    else:
        hanoi(A,C,B,n-1)
        print(A, '->', C)
        time += 1
        hanoi(B,A,C,n-1)
        
hanoi('A','B','C',4)
print(time)
1
2
3
4
5
6
7
8
9
10
11
12
13
14