高中信息技术教科版 (2019)必修1 数据与计算4.3 非数值计算课前预习课件ppt

这是一份高中信息技术教科版 (2019)必修1 数据与计算4.3 非数值计算课前预习课件ppt，共23页。PPT课件主要包含了学习目标，新课导入，分治策略，二分查找，递归的基本思想，迭代与递归的关系，巩固提升，练一练等内容，欢迎下载使用。
4.3 非数值计算
★ 运用合适的算法形成解决问题的方案。★ 了解算法设计中的分治思想，并运用二分查找解决实际问题。 ★ 体验递归算法，并结合具体问题开展编程实践。
在数值计算中，我们更多考虑的是“数” ，但计算应该是一个更广泛的领域。计算的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话，那么非数值计算更多探讨＂ 算法” 问题。
许多程序设计问题的解决，要依靠标准算法和现成的模型，更需要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些独特的数据结构来支撑和实现算法。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。
任务一 巧翻字典 — 统计查字典次数
查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的部分。假设一本字典大约500页，目标信息在第269页。请记录你翻页过程，和同学们比比，看谁翻的次数最少。
有的同学翻得特别快，他们用了什么方法呢？原来看似普通的翻字典，不仅是一门技术， 更是一种能力，是算法思想的体现。
凡治众如治寡，分数是也。 ——《孙子兵法》
思考：生活中还有哪些事情可以利用分治策略解决？
快递送达过程、营销策略、上传下载中的断点续传、通信原理中的分组交换……
分治的设计思想，是将个难以直接解决的大问题，分割成些较小的同类问题，各个击破，最终达到解决问题的目的。 二分查找实际上一就是分治策略的种典型运用。
二分思想：将数列有序排列，采用跳跃的方式查找数据。
方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都能将查找区间缩小一半。
找一半按照顺序找一半，一比较，舍一半。继续找一半，一半又一半，快速找答案！
二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要lg2n次。但是，二分法查找的前提条件是被查找的数据必须是有序的。查找的基本算法有:顺序查找、二分查找、分块查找、哈希查找等。
若中间数mid比目标数x大，则区间变为左半区间，右边界更新为high=mid-1, lw不变。
若中间数mid比目标数x小，则区间变为右半区间，左边界更新为lw=mid+1, high不变。
在翻页过程中借助两个书签，划定目标所属范围，然后翻到两个书签的中间位置。每次目标区域都更新为原来的“二分之一”，当数据范围缩小到只有1个数的时候肯定能得到问题的解。1000以内的页码，最多翻10次肯定能找到解。
目标信息在第269页。
有了翻字典的实际操作经验，我们来尝试完善下面的二分查找程序。
x=int(input(“请输入要查找的数据：＂））step=0 ＃记录查找次数flagl=l ＃目标区域左边界flag2=1000 ＃目标区域右边界while(flag1x: flag2=mid-1#有边界前移elif midflag2 r x1)：＃区间数据范围小于1则结束循环mid=（flag1+flag2)/2 ＃中间值step=step+1 ＃查找次数加1if mid>x: flag2=mid#有边界前移elif mid2)
递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。
递归可用“分”，“治”，“合”三个字概括
1）分：将原有问题分解成K个子问题。2）治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进 行下去，直到问题足够小时，就很容易求出子问题的解。3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在有限次的计算后得出结果，而不会产生尤限循环的情况。
移动3个木盘的方法是：根据木盘叠放规则，要使A杆上最大的木盘（记为x)移动到C杆上（子问题1, 如图第4步），必须先把 x上方的所有木盘移动到B杆上（子问题2, 如图4中的前3步），然后再将B杆上所有的木盘移动到C杆上（子问题3, 如图中的后3步）。
3个木盘的移动问题成功解决了，就可以解决更多木盘的移动问题了。
解决移动3个木盘的问题。
解决移动n个木盘的问题。
将n个木盘从A杆移动到C杆，需要借助中间的B杆。只要超过一个木盘，在移动过程中，总会存在起始杆、 过渡杆及目标杆的问题。因此，定义函数时，用到了4个参数：hani(n,A,B,C), n表示需要移动的盘子数量，A表示盘子的起始杆，B表示中间过渡杆，C表示目标杆，如图所示。
活动 代码实现汉诺塔游戏
def hann(n,s,m,t): #定义一个函数,n层塔，将盘子从s借助m移动到t if n==1: print(s,'-->',t) #将一个盘子从s移动到t else: hann(n-1,s,t,m) #将前n-1个盘子从s移动到m上 print(s,'-->',t) #将最底下的最后一个盘子从s移动到t上 hann(n-1,m,s,t) #将m上的n-1个盘子移动到t上#主程序n=int(input('请输入汉诺塔的层数：'))hann(n,'A','B','C')input("运行完毕，请按回车键退出...")
迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有密切的联系。
迭代程序可以转换成等价的递归程序。以上一节中的计算斐波那契数列第n项的值为例，程序间的转换如下：
1、计算“汉诺塔”游戏移动的次数。参考答案： def f(n): if n==0: return 0 else: return 2*f(n-1)+1 x=int(input("请输入塔的个数：")) print("需要移动",f(x),"次") input("运行完毕，请按回车键退出...")
2、尝试用二分法求解x3-x2+x-1=0
操作提示：令f(x)= x3-x2+x-1，针对有解的单调区间(a,b)，取x。=（a+b)/2:若f(a)*f(x。)＜0，则f(x)在(a,x。)内有解；若f(x。）*f（b)< 0，则f(x)在(x。,b)内有解；若|f(x。)|＜10-6，则x。为方程的解。
参考答案：def f(x): #定义方程 return x**3-x**2+x-1a=flat(input("请输入解区间的左边界："))b=flat(input("请输入解区间的右边界："))while abs(b-a)>1e-6: x0=(a+b)/2 if f(a)*f(x0)