2022.3.17
2022.11.15 增加次数计算

一.抽象为数学问题:

从左到右有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)

在这里插入图片描述
在这里插入图片描述
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)

汉罗塔内部顺序写法,根据的是:

在这里插入图片描述

五 实例 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)
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

六 关于移动次数的计算

  • 用参数每次带入
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)
  • 全局变量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)
Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐