4.3-非数值计算

4.3非数值计算淄博市博山区实验中学电教中心制作4.3非数值计算在数值计算中，我们更多考虑的是“数”，但计算应该是一个更广泛的领域。计算的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话,那么非数值计算更多探讨“算法”问题。数据是普遍存在的，甚至可以说对象即数据;对数据的分析、处理;都属于计算的范畴。选择一个合适的算法，设计出平实、易读、易懂的程序，正确、高效地解决实际需求，是计算的本质。学习目标★运用合适的算法形成解决问题的方案。★了解算法设计中的分治思想，并运用二分查找解决实际问题。★体验递归算法，并结合具体问题开展编程实践。任务一巧翻字典许多程序设计问题的解决，要依靠标准算法和现成的模型，更需要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些独特的数据结构来支撑和实现算法。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。本节我们将围绕“生活中的算法”项目，尝试用“算法的眼睛”看待生活，用“算法的思维”去解决实际问题。本项目主要包含“巧翻字典”和“玩转‘汉诺塔’游戏”两个任务。※活动统计查字典次数查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的一部分。假设一本字典一千页，目标页数在328页。在下表填写翻页过程。有的同学翻得特别快，他们用了什么方法呢?原来看似普通的翻字典，不仅是一门技术，更是一种能力，是算法思想的体现。分治策略分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。凡治众如治寡，分数是也。（摘自《孙子兵法》）二分查找二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要log2n次。但是，二分法查找的前提条件是被查找的数据必须是有序的。查找的基本算法有:顺序查找、二分查找、分块查找、哈希查找等。二分查找程序在翻页过程中借助两个书签，划定目标所属范围，然后翻到两个书签的中间位置。每次目标区域都更新为原来的“二分之一”，当数据范围缩小到只有1个数的时候肯定能得到问题的解。1000以内的页码，最多翻10次肯定能找到解。有了翻字典的实际操作经验，我们来尝试完善下面的二分查找程序。x=int(input(请输入要查找的1000以内的整数:))step=0记录查找次数flag1=1目标区域左边界flag2=1000目标区域右边界while(flag1=flag2):区间数据范围小于1则结束循环mid=(flag1+flag2)//2中间值step=step+1查找次数加1ifmidx:flag2=mid-1左边界前移elifmidx:flag1=mid+1左边界后移else:break恰好找到目标数据，退出循环print(“查找次数为：”,step)输出次数input(运行完毕，请按回车键退出...)※活动剖析问题，设计游戏策略“汉诺塔”游戏源于一个古老ABC的印度传说。如图4.3.1所示，木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘，且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有木盘图4.3.1汉诺塔从A杆全部移到C杆上任务二玩转“汉诺塔”游戏任务二玩转“汉诺塔”游戏相传在印度的婆罗门神庙内插着三根钻石棒，创世之时，神便在其中一根钻石棒上放了64枚纯金的圆盘。有一个叫婆罗门的门徒，不分日夜地将64枚金盘移到另一根钻石棒上，移动的过程中一次只能移动一个金盘，且大盘不能放在小盘上。神说等到婆罗门完成这项工作，世界将在一声霹雳中毁灭……次数:18446744073709551615。婆罗门以1秒移动1次的速度，不眠不休要花5849万万年生活中的递归要使移动次数尽可能少，必须排除无效移动。现在有8个木盘，不妨先以3个木盘为例，观察一下移动的过程。请在图4.3.2中记录木盘移动的过程。每层汉诺塔至少需要多少步1层：1次2层：3次3层：7次4层：15次5层：31次6层：63次7层：127次8层：255次9层：511次计算公式：f(x)=2^x-1●递归递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。图4.3.3所示就是递归的一种形象表示。递归一说起递归，我想每个人都不陌生。举个从小就听过的例子：从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山...还有你从两面相对的镜子中看到的画面，其实都是抽象出来的递归现象，但是严格来说并不是递归，因为会一直重复下去，没有终止条件，那就称为死循环了。有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？利用递归的方法，递归分为回推和递推两个阶段。要想知道第五个人岁数，需知道第四人的岁数，以此类推，推到第一人（10岁），再往回推。递归在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1,1,2，3,5，8,13,..”，可以递归定义为递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在有限次的计算后得出结果，而不会产生无限循环的情况。分、治、合面对一个大规模复杂问题的求解，递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。结合分治策略，递归也可用“分”“治”“合”三个字概括。(1)分:将原问题分解成k个子问题。(2)治:对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。(3)合:将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。移动3个木盘的方法是:根据木盘叠放规则，要使A杆上最大的木盘(记为x)移动到C杆上(子问题1,如图4.3.2中的第4步)，必须先把x上方的所有木盘移动到B杆上(子问题2，如图4.3.2中的前3步)，然后再将B杆上所有的木盘移动到C杆上(子问题3，如图4.3.2中的后3步)。3个木盘的移动问题成功解决了，就可以解决更多木盘的移动问题了。将n个木盘从A杆移动到C杆，需要借助中间的B杆。只要超过一个木盘，在移动过程中，总会存在起始杆、过渡杆及目标杆的问题。因此，定义函数时，用到了4个参数:hanoi(n,s,m,t),n表示需要移动的盘子数量，s表示盘子的起始杆，m表示中间过渡杆，t表示目标杆，如图4.3.4所示。defhanno(n,s,m,t):#定义一个函数,n层塔，将盘子从s借助m移动到tifn==1:print(s,'--',t)#将一个盘子从s移动到telse: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(运行完毕，请按回车键退出...)将一个难以直接解决的大问题，分割成一些规模较小的同类问题，以便各个击破，分而治之，此为分治。分治与递归就像一对孪生兄弟，经常同时应用在算法设计中，并由此产生了许多高效的算法。迭代与递归的关系迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有着密切的联系。迭代是重复反馈过程的活动，其目的通常是逼近所需目标或结果。递归是重复调用函数自身。递归中，遇到满足终止条件的情况时逐层返回。迭代则通常使用计数器结束循环。迭代程序可以转换成等价的递归程序。以上一节中计算斐波那契数列第n项的值为例，程序间的转换如表4.3.2所示。