资源简介

(共16张PPT)
1.斐波那契数列
2.迭代变量及迭代关系表达式
复习回顾
1，1，2，3，5，8，13.......
f1= f2= 1
f1 , f2 = f2 , f1+f2
4.3 非数值计算
教科版必修一
了解分治策略的概念
壹
掌握二分查找的算法思想
贰
在python中用二分法解决问题
叁
学习目标
CONTENTS
计算一定是数吗？
除了数还有什么？
这些属于数值计算吗？
计算的对象可以是自然界和人类社会的一切事物。如数据、文字、语言、图形、知识、事物的运动过程及思维过程。
数值计算——数学问题
非数值计算——”算法”问题，如分治、递归、解析等
【导】猜数字游戏
运行利用python编写的“猜数字”游戏，计算机在1-1000中随机产生一个数，试试看你要猜多少次才能猜中。
思考：怎样才能最快的找到正确答案？
猜数字游戏
每次取中间的数，最多需要10次即可找到答案
第1次猜500，剩余500种可能性；
第2次猜250/750，剩余250种可能性；
第3次猜125/375/625/875，剩余125种可能性；
......，剩余63种可能性；
......，剩余32种可能性；
.......
......，剩余1种可能性；
猜数字游戏
思考：如果是1~100，最多需要几次找到答案？1~10000？1~n
2
7
≈
100
2
10
≈
1000
目标越大，优势越明显
2
14
≈
10000
log2n
分治策略
壹
凡治众如治寡，分数是也。
——《孙子兵法》
分治策略
设计思想：将难以直接解决的大问题，分割成些较小的同类问题，各个击破，最终达到解决问题的目的。
凡治众如治寡，分数是也。
——《孙子兵法》
思考：生活中还有哪些事情可以利用分治策略解决？
快递送达过程、营销策略、上传下载中的断点续传、通信原理中的分组交换……
分治策略
二分查找
利用分治法解决问题的典型案例之一
贰
二分查找
二分查找又叫折半查找。
思想：将数列有序排列，采用跳跃式的方式查找数据。
方法：以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。 每一次比较后可以将查找区域缩小一半。
第一次分割
第二次分割
第三次分割
左边界
low
右边界
high
目标数x
中间数
mid
(low+high)/2
左边界
low
右边界
high
目标数x
中间数
mid
(low+high)/2
区间变为左半区间
low不变
high=mid-1
区间变为右半区间
low=mid+1
high不变
中间数mid>目标数x
中间数mid<目标数x
在python中用二分法解决问题
课堂练习———补全程序
Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor.
x=int(input("请输入要查找的1000以内的整数:"))
step=0 #记录查找次数
flag1=1 #目标区域左边界
flag2=1000 #目标区域右边界
while(__________________): #只要区间存在则执行循环
mid=________________ #计算中间值
______________________ #查找次数加1
if mid>x:
__________________ #右边界前移
elif mid__________________ #左边界前移
else:
break #恰好找到目标数据，退出循环
print("查找次数为：",step)
flag1<=flag2
(flag1+flag2)//2
step=step+1
flag2=mid-1
flag1=mid+1
课堂小结

展开更多......

收起↑