1、4.3 非数值计算 4.3 非数值计算 在数值计算中，我们更多考虑的是“数”，但计算应该是一个更广泛的领 域。计算的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对 象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思 维过程。如果说数值计算主要探讨数学问题的话,那么非数值计算更多探讨“算 法”问题。 数据是普遍存在的，甚至可以说对象即数据;对数据的分析、处理;都属于 计算的范畴。选择一个合适的算法，设计出平实、易读、易懂的程序，正确、 高效地解决实际需求，是计算的本质。 学习目标 运用合适的算法形成解决问题的方案。 了解算法设计中的分治思想，并运用二分查找解决实际问
2、题。 体验递归算法，并结合具体问题开展编程实践。 任务一 巧翻字典 许多程序设计问题的解决，要依靠标准算法和现成的模型，更需 要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些独 特的数据结构来支撑和实现算法。在解决非数值类计算问题时，一些 基础的思维方式可以借鉴，如分治、递归、解析等。本节我们将围绕 “生活中的算法”项目，尝试用“算法的眼睛”看待生活，用“算法 的思维”去解决实际问题。 本项目主要包含“巧翻字典”和“玩转汉诺塔游戏”两个任务。 活动统计查字典次数 查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的 一部分。假设一本字典一千页，目标页数在328页。在下表填写翻
3、页过程。 有的同学翻得特别快，他们用了什么方法呢?原来看似普通的翻字典， 不仅是一门技术，更是一种能力，是算法思想的体现。 分治策略 分治的设计思想，是将一个难以直接解决的大问题，分割 成一些较小的同类问题，各个击破，最终达到解决问题的目的。 二分查找实际上就是分治策略的一种典型运用。 凡治众如治寡，分数是也。（摘自孙子兵法） 二分查找 二分查找又叫折半查找，该方法主要将数列有序排列，采用跳 跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为 比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小 为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩 小一半。 二分查找是一种
4、高效的查找方法。它可以明显减少比较次数， 提高查找效率。在一个有n个元素的有序序列中，利用二分查找大 约需要log2n次。但是，二分法查找的前提条件是被查找的数据必须 是有序的有序的。 查找的基本算法有:顺序查找、二分查找、分块查找、哈希查 找等。 二分查找程序 在翻页过程中借助两个书签，划定目标所属范围，然后翻 到两个书签的中间位置。每次目标区域都更新为原来的“二分之 一”，当数据范围缩小到只有1个数的时候肯定能得到问题的解。 1000 以内的页码，最多翻10次肯定能找到解。 有了翻字典的实际操作经验，我们来尝试完善下面的二分 查找程序。 x=int(input(请输入要查找的1000以内的
5、整数:) step=0 记录查找次数 flag1=1 目标区域左边界 flag2=1000 目标区域右边界 while(flag1x: flag2=mid-1 左边界前移 elif mid,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(运行完毕，请按回车键退出.) 将一个难以直接解决的大问题，分割成一些规模较小的同类问题，以便各个击 破，分而治之，此为分治。分治与递归就像一对孪生兄弟，经常同时应用在算法设 计中，并由此产生了许多高效的算法。 迭代与递归的迭代与递归的关系关系 迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有着密切的联 系。 迭代是重复反馈过程的活动，其目的通常是逼近所需目标或结果。递归是重复 调用函数自身。递归中，遇到满足终止条件的情况时逐层返回。迭代则通常使用计 数器结束循环。 迭代程序可以转换成等价的递归程序。以上一节中计算斐波那契数列第n项的值 为例，程序间的转换如表4.3.2所示。
