非数值计算ppt课件.pptx

《非数值计算ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.3非数值计算淄博市博山区实验中学电教中心制作4.3非数值计算在数值计算中，我们更多考虑的是“数”，但计算应该是一个更广泛的领域。计算的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话,那么非数值计算更多探讨“算法”问题。数据是普遍存在的，甚至可以说对象即数据;对数据的分析、处理;都属于计算的范畴。选择一个合适的算法，设计出平实、易读、易懂的程序，正确、高效地解决实际需求，是计算的本质。学习目标★运用合适的算法形成解决问

2、题的方案。★了解算法设计中的分治思想，并运用二分查找解决实际问题。★体验递归算法，并结合具体问题开展编程实践。任务一巧翻字典许多程序设计问题的解决，要依靠标准算法和现成的模型，更需要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些独特的数据结构来支撑和实现算法。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。本节我们将围绕“生活中的算法”项目，尝试用“算法的眼睛”看待生活，用“算法的思维”去解决实际问题。本项目主要包含“巧翻字典”和“玩转‘汉诺塔’游戏”两个任务。※活动统计查字典次数查汉字、查单词、查成语

3、等查字典的活动，早已成为我们学习生活的一部分。假设一本字典一千页，目标页数在328页。在下表填写翻页过程。有的同学翻得特别快，他们用了什么方法呢?原来看似普通的翻字典，不仅是一门技术，更是一种能力，是算法思想的体现。分治策略分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。凡治众如治寡，分数是也。（摘自《孙子兵法》）二分查找二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，

4、如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要log2n次。但是，二分法查找的前提条件是被查找的数据必须是有序的。查找的基本算法有:顺序查找、二分查找、分块查找、哈希查找等。二分查找程序在翻页过程中借助两个书签，划定目标所属范围，然后翻到两个书签的中间位置。每次目标区域都更新为原来的“二分之一”，当数据范围缩小到只有1个数的时候肯定能得到问题的解。1000以

5、内的页码，最多翻10次肯定能找到解。有了翻字典的实际操作经验，我们来尝试完善下面的二分查找程序。x=int(input("请输入要查找的1000以内的整数:"))step=0记录查找次数flag1=1目标区域左边界flag2=1000目标区域右边界while(flag1<=flag2):区间数据范围小于1则结束循环mid=(flag1+flag2)//2中间值step=step+1查找次数加1ifmid>x:flag2=mid-1左边界前移elifmid

6、int(“查找次数为：”,step)输出次数input("运行完毕，请按回车键退出...")※活动剖析问题，设计游戏策略“汉诺塔”游戏源于一个古老ABC的印度传说。如图4.3.1所示，木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘，且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有木盘图4.3.1汉诺塔从A杆全部移到C杆上任务二玩转“汉诺塔”游戏任务二玩转“汉诺塔”游戏相传在印度的婆罗门神庙内插着三根钻石棒，创世之时，神便在其中一根钻石棒上放了64枚纯金的圆盘。有一个叫婆罗门的门徒，不分日夜地将64枚金盘移

7、到另一根钻石棒上，移动的过程中一次只能移动一个金盘，且大盘不能放在小盘上。神说等到婆罗门完成这项工作，世界将在一声霹雳中毁灭……次数: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●递归

8、递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。