资源简介

(共13张PPT)
第四单元 非数值计算
4.3探寻“汉诺塔”中的奥秘
循环结构：计算机程序周而复始地重复同样的步骤，称为循环。
知识点回顾
s=1
for i in range(1,6):
s=s*i
print（s）
如果求5！的结果，你可以用循环实现吗？
如果求任意数的阶乘呢？
while
自定义函数——可以复用的代码
知识点回顾
基本格式
def 函数名(参数)：
语句或语句组
return 返回值
n可以取任意的值，完成调用。
知识点分析
分解：
5*4！
5*4*3！
5*4*3*2！
5*4*3*2*1！
5！可以如何求解呢？
得出：
5！=5*4！
4！=4*3！
3！=3*2！
2！=2*1！
F（n）=
1（n=1）
n*f(n-1) (n>2)
调用本身
递归
递归算法
直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。
递归的基本思想
递归的“分”-“治”-“合”
把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。
1）分：将原有问题分解成K个子问题。
2）治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。
3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
探寻汉诺塔的奥秘
汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
1.汉诺塔——1个圆盘
探寻汉诺塔的奥秘
2.汉诺塔——2个圆盘
A→C
A→B
A→C
B→C
初始状态 第四步
第一步 第五步
第二步 第六步
第三步 第七步
2.汉诺塔——3个圆盘
前4步：？
A→B→C
后3步：？
B→A→C
如果是n个盘子呢？
先把最大圆盘上方的所有圆盘,即n-1个圆盘从起始杆s移动到过渡杆m；
接着把最大圆盘，即第n个圆盘移动到目标杆t；
再把过渡杆m上的圆盘移动到目标杆t。
S m t
当n>1时：
def hanoi(n, ____,_____,_____):
hanoi(n-1, ____,____,____)
print(__ , ‘-->’, ____)
hanoi(n-1, ___,_____,____)
s
m
t
if n==1:
print(__ , ‘-->’, ____)
else:
起始杆
中间杆
目标杆
探寻汉诺塔的奥秘
先把最大盘子上方的所有盘子,即n-1个盘子从起始杆s移动到过渡杆m；
接着把最大盘子，即第n个盘子移动到目标杆t；
再把过渡杆m上的盘子移动到目标杆t。
当n=1时：s→t
s
t
m
s
t
s
t
m
s
t
你能知道圆盘一共移动了多少次吗？
想一想什么时候需要计数呢？自主完善汉诺塔次数.py程序
想一想什么时候需要计数呢？
课堂小结
递归：直接或间接地调用自己的方法。
递：分解调用
有限次数
归： 求解返回
分
治
合

展开更多......

收起↑