资源简介

(共17张PPT)
第四单元 非数值计算
4.3 非数值计算
---探寻“汉诺塔”中的奥秘
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
二分查找/折半查找 p112
二分思想：将数列有序排列，采用跳跃的方式查找数据。
左边界
flag1
右边界
flag2
目标数x
中间数
mid
！！！若中间数mid比目标数x大，则区间变为左半区间，右边界更新
左边界
flag1
右边界
flag2
目标数x
中间数
mid
！！！若中间数mid比目标数x小，则区间变为右半区间，左边界更新
在有n个元素的有序序列中，利用二分查找大约需要log2n次。
n = 1000
需要10次
方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都能将查找区间缩小一半。
找一半
按照顺序找一半，
一比较，舍一半。
继续找一半，
一半又一半，
快速找答案！
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
分治策略：
其设计思想为，将一个难以直接解决的大问题，分割成较小的同类问题，各个击破，最终达到解决问题的目的。
A B C D E F G H I
需要解决的问题
第一次分割
第二次分割
第三次分割
二分查找
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
有了实际操作经验，我们来尝试完善下面的二分查找程序。
填充代码，调试程序
优势：明显减少比较次数，提高查找效率；
局限：被查找数据必须是有序的。
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
如果输入的数据不在范围内，会出现什么结果呢？程序还需要在哪些地方进行完善？大家一起来试试吧。
x=int(input(“请输入要查找的数据：＂））
step=0 ＃记录查找次数
flagl=l ＃目标区域左边界
flag2=400 ＃目标区域右边界
if x>flag2 or xwhile(flag2-flag1>1) ＃区间数据范围小于1则结束循环
mid=（flag1+flag2)/2 ＃中间值
step=step+1 ＃查找次数加1
if mid>x:
flag2=mid #有边界前移
elif midflag1=mid #左边界后移
else:
break ＃恰好找到目标数据， 退出循环
print(“查询次数为：”，step) #输出次数
else:
print(“查询超出范围。”)
循环结构：计算机程序周而复始地重复同样的步骤，称为循环。
知识点回顾
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片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
解决移动3个木盘的问题。
第1步：A→C
第2步：A→B
第3步：C→B
第4步：A→C
第5步：B→A
第6步：B→C
第7步：A→C
A
B
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程序
想一想什么时候需要计数呢？
课堂小结
递归：直接或间接地调用自己的方法。
递：分解调用
有限次数
归： 求解返回
分
治
合
参考代码：

展开更多......

收起↑