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