1、4.3 非数值计算非数值计算 在数值计算中，我们更多考虑的是“数”，但计算应该是一个更广泛的领域。计算的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话,那么非数值计算更多探讨“算法”问题。数据是普遍存在的，甚至可以说对象即数据;对数据的分析、处理;都属于计算的范畴。选择一个合适的算法，设计出平实、易读、易懂的程序，正确、高效地解决实际需求，是计算的本质。学习目标 运用合适的算法形成解决问题的方案。了解算法设计中的分治思想，运用二分查找解决问题。体验递归算法，并结合具体问题开
2、展编程实践。学习重点学习难点 运行Python编写的“猜数字”游戏，计算机在01000中随机产生一个数，试试看你要多少次才能猜中。想一想 假设一本书大约300页，目标信息在第132页。请在下表记录你的翻页过程，和同学们比一比，看谁翻的次数最少。次数次数翻至页码翻至页码下一步决策下一步决策第1次第2次第3次第4次 巧翻字典 许多程序设计问题的解决，要依靠标准算法和现成的模型，更需要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些独特的数据结构来支撑和实现算法。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。本节我们将围绕“生活中的算法”项目，尝试用“算法的眼睛
3、”看待生活，用“算法的思维”去解决实际问题。活动：统计查字典次数 查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的一部分。假设一本字典一千页，目标页数在328页。在下表填写翻页过程。有的同学翻得特别快，他们用了什么方法呢?原来看似普通的翻字典，不仅是一门技术，更是一种能力，是算法思想的体现。分治策略 分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。凡治众如治寡，分数是也。孙子兵法任务一、生活中的分治问题任务二、巧查监控寻找失主生活中的算法活动1：查找漏扫图书活动2：查找英文单词活动3
4、：查找假币 生活中的分治问题 为了更好地学习英语，小为了更好地学习英语，小I I和小和小T T去阅览室借去阅览室借了了2020本英文原著，由于扫码时有一本漏扫引起了本英文原著，由于扫码时有一本漏扫引起了警报声。警报声。活动：查找漏扫图书如果你是管理员，如何快速找到漏扫的图书？方法一：一本本的查找显然效率低下。方法一：一本本的查找显然效率低下。方法二：将方法二：将2020本书分成了两份，第一份经过警报器没响，又本书分成了两份，第一份经过警报器没响，又把剩下的一份分成两份，拿出一份接着测试把剩下的一份分成两份，拿出一份接着测试这样就可以这样就可以快速找到漏扫图书。快速找到漏扫图书。活动：查找漏扫图
5、书活动2：查找英文单词小小I I和小和小T T在阅读在阅读老人与海老人与海小小I I：“A A man can be destroyed but not man can be destroyed but not defeateddefeated”你知道你知道defeatdefeat是什么意思吗？是什么意思吗？小小T T：我刚买了一本新字典有：我刚买了一本新字典有23462346页呢，我来帮页呢，我来帮你查一下。你查一下。如果你是小T，如何快速找到单词？方法：根据首字母D大概确定第一次先翻到字典的六分之一处，再根据看到的首字母确定下一个位置，如果首字母相同，则查看第二个字母，依此类推，直到查出单
6、词。活动：查找英文单词如果你是数学家，如何按要求找到假币？活动：查找假币 小小I I在阅览室读到了有趣的故事：国王有在阅览室读到了有趣的故事：国王有1818枚金币，枚金币，其中掺进去一枚较轻的假币，要求数学家使用一个没有其中掺进去一枚较轻的假币，要求数学家使用一个没有砝码的天平三次找到假币。砝码的天平三次找到假币。方法：先将18枚金币分成三组，标记好编号A123456、B123456、C123456.选出其中ab两组进行第一次称量。称量结果有三种情况：a组重、一样重、b组重。如果两组一般重，则假币在c组中，如果a组重，则假币在b组，反之则在a组。总之经过第一次称量我们就可以确定假币所在的分组。
7、假设是c组，第二次称量可以将c1c2c3和c4c5c6分别放在天平的两边。假币在轻的一侧。第三次称量在三枚重选择任意两枚放置在天平两侧，一样重则剩余的是假币，不一样重则较轻的是假币。活动：查找假币第二次：3 3第三次：1 1 118第一次：6 6 6 二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可以将查找区间缩小一半。二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。二分法二分查找 二分查找是一种高效的查找方法。它可以明显减
8、少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要log2 2n次。但是，二分法查找的前提条件是被查找的数据必须是有序的有序的。查找的基本算法有:顺序查找、二分查找、分块查找、哈希查找等二分查找程序 在翻页过程中借助两个书签，划定目标所属范围，然后翻到两个书签的中间位置。每次目标区域都更新为原来的“二分之一”，当数据范围缩小到只有1个数的时候肯定能得到问题的解。1000 以内的页码，最多翻10次肯定能找到解。有了翻字典的实际操作经验，我们来尝试完善下面的二分查找程序。x=int(input(请输入要查找的1000以内的整数:)step=0#记录查找次数flag1=1#
9、目标区域左边界flag2=1000#目标区域右边界while(flag1x:flag2=mid-1#左边界前移 elif midx:flag1=mid+1#左边界后移 else:break#恰好找到目标数据，退出循环print(“查找次数为：”,step)#输出次数input(运行完毕，请按回车键退出.)查找的1000以内的整数的代码凡治众如治寡，分数是也凡治众如治寡，分数是也孙子兵法孙子兵法 分治策略快递送达过程、营销策略、快递送达过程、营销策略、上传下载中的断点续传、通上传下载中的断点续传、通信原理中的分组交换信原理中的分组交换 小小I I和小和小T T在阅览室角落里捡到了一本无名的在阅览
10、室角落里捡到了一本无名的读书笔记，如何在一个小时读书笔记，如何在一个小时36003600秒的监控录像中秒的监控录像中快速找到失主？快速找到失主？任务二、巧查监控寻找失主 二分查找（折半查找）区间13600，假设目标值是1866，二分查找的次数?边界值的变化规律？次数次数左边界左边界右边界右边界中间值中间值比较结果比较结果1136001800180018663180126992250225018664180122492025202518665180120241912191218666180119111856185618668185718831870187018669185718691863186
11、31866101864186918661866=18661、分析问题数据量大、有序数列0101次数：log2n0202 二分查找（折半查找）2、完成二分法流程图请根据数据分析补充二分法流程图次数次数左边界左边界右边界右边界中间值中间值比较结果比较结果113600180018001866318012699225022501866418012249202520251866518012024191219121866618011911185618561866818571883187018701866918571869186318631e-6:x0=(a+b)/2 if f(a)*f(x0)0:b=x0
12、 if f(b)*f(x0),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(请输入汉诺塔的层数：)hanno(n,A,B,C)input(运行完毕，请按回车键退出.)调试运行将一个难以直接解决的大问题，分割成一些规模较小的同类问题，以便各个击破，分而治之，此为分治。分治与递归就像一对孪生兄弟，经常同时应用在算法设计中，并由此产生了许多高效的算法。迭代算法与递归算法都需要重复执
13、行某些代码，两者既有区别又有密切的联系。迭代迭代 重复方式：是重复反馈过程反馈过程的活动，其目的通常是逼迫所需目标或结果。结束方式：通常使用计数器结束循环。递归递归 重复方式是重复调用函数自身调用函数自身。结束方式：遇到满足终止条件的情况时逐层返回。递归与迭代的关系递归与迭代的关系迭代程序可以转换成等价的递归程序。迭代程序可以转换成等价的递归程序。如：计算斐波那契数列第N项的值。计算“汉诺塔”游戏移动的次数。参考答案：def f(n):if n=0:return 0 else:return 2*f(n-1)+1 x=int(input(请输入塔的个数：)print(需要移动,f(x),次)input(运行完毕，请按回车键退出.)迭代与递归迭代与递归根据提示输入不同的塔数，查看移动的次数迭代与递归迭代与递归THANK YOU2020
