1、4.3 非数值计算第4单元 计算与问题解决学学 习习 目目 标标（重点）（重点）运行Python编写的“猜数字”游戏，计算机在01000中随机产生一个数，试试看你要多少次才能猜中。假设一本书大约300页，目标信息在第132页。请在下表记录你的翻页过程，和同学们比一比，看谁翻的次数最少。次数次数翻至页码翻至页码下一步决策下一步决策第1次第2次第3次第4次 分治策略分治策略 分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。二分查找二分查找 二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的
2、方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小-半。二分法查找的前提条件是被查找的数据必须是有序的。查找的基本算法有:顺序查找、二分查找、分块查找、哈希查找等 有了翻书的经验，我们尝试完善下面的二分查找程序。x=int(input(请输入要查找的1000以内的整数:)step=0#记录查找次数flag1=1#目标区域左边界flag2=1000#目标区域左边界while（）:#区间数据范围小于1则结束循环
3、mid=（）#中间值 （）#查找次数加1 if midx:（）#右边界前移 elif midx:（）#左边界后移 else:breakprint(查找次数为：,step)#找到目标数据，退出循环input(运行完毕，请按回车键退出.)#输出次数(flag1,t)#将一个盘子从s移动到t else:hanno(n-1,s,t,m)#将前n-1个盘子从s移动到m上 print(s,-,t)#将最底下的最后一个盘子从s移动到t上 hanno(n-1,m,s,t)#将m上的n-1个盘子移动到t上#主程序n=int(input(请输入汉诺塔的层数：)#调用函数，将n个木盘从A借助B移动到Channo(n
4、,A,B,C)input(运行完毕，请按回车键退出.)递归递归输入不同的层数，查看运行结果递归递归计算“汉诺塔”游戏移动的次数。参考答案：def f(n):if n=0:return 0 else:return 2*f(n-1)+1 x=int(input(请输入塔的个数：)print(需要移动,f(x),次)input(运行完毕，请按回车键退出.)递归递归根据提示输入不同的塔数，查看移动的次数递归递归 迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有密切的联系。迭代迭代 重复方式：是重复反馈过程反馈过程的活动，其目的通常是逼迫所需目标或结果。结束方式：通常使用计数器结束循环。递归递归 重复方式是重复调用函数自身调用函数自身。结束方式：遇到满足终止条件的情况时逐层返回。递归与迭代的关系递归与迭代的关系 利用Python调试运行课本P106表4.3.2递归与迭代，查看比较结果。巩固练习巩固练习
