4.3 非数值计算 第4单元 计算与问题解决 学 习 目 标 3.体验递归算法，并结合具体问题开展编程实践。 2.了解算法设计中的分治思想，并运用二分查找解决实际问题。 1.运用合适的算法形成解决问题的方案。 二分查找法的理解和运用二分法解决实际问题。 （重点） 递归算法的实际应用，并针对具体问题开展编程实践。 （难点） 运行Python编写的“猜数字”游戏，计算机在0～1000中随机产生一个数，试试看你要多少次才能猜中。 假设一本书大约300页，目标信息在第132页。请在下表记录 你的翻页过程，和同学们比一比，看谁翻的次数最少。 {5C22544A-7EE6-4342-B048-85BDC9FD1C3A}次数 翻至页码 下一步决策 第1次 第2次 第3次 第4次 …… 分治策略 分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。 二分查找 二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。 以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小-半。 二分法查找的前提条件是被查找的数据必须是有序的。 查找的基本算法有: 顺序查找、二分查找、 分块查找、哈希查找等 有了翻书的经验，我们尝试完善下面的二分查找程序。 x=int(input("请输入要查找的1000以内的整数:")) step=0 #记录查找次数 flag1=1 #目标区域左边界 flag2=1000 #目标区域左边界 while（ ）: #区间数据范围小于1则结束循环 mid=（ ） #中间值 （ ） #查找次数加1 if mid>x: （ ） #右边界前移 elif mid
~~ 您好，已阅读到文档的结尾了 ~~
