(
课件网) 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
