1、第2单元 编程计算第1单元 初识数据与计算第3单元 认识数据第4单元 计算与问题解决第5单元 数据分析与人工智能信息技术信息技术（必修（必修1 1）4.3 4.3 非数值计算非数值计算学习目标 运用合适的算法形成解决问题的方案。运用合适的算法形成解决问题的方案。了解算法设计中的分治思想，并运用二分查找解决实际了解算法设计中的分治思想，并运用二分查找解决实际问题。问题。体验递归算法，并结合具体问题开展编程实践。体验递归算法，并结合具体问题开展编程实践。在数值计算中，我们更多考虑的是在数值计算中，我们更多考虑的是“数数”，但计算应该是一个更广泛的领域。计算，但计算应该是一个更广泛的领域。计算的对象
2、可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，的对象可以是自然界和人类社会的一切事物。更确切地说，计算的对象可以是某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要如数据、文字、语言、图形、知识、事物的运动过程及思维过程。如果说数值计算主要探讨数学问题的话，那么非数值计算更多探讨探讨数学问题的话，那么非数值计算更多探讨 算法算法”问题。问题。许多程序设计问题的解决，要依靠标准算法许多程序设计问题的解决，要依靠标准算法和现成的模型，更需要编程者开阔思路，提出一和现成的模型，更需要编程者开阔思路，提出一些新颖、巧妙的算法，或者设计出一些
3、独特的数些新颖、巧妙的算法，或者设计出一些独特的数据结构来支撑和实现算法。在解决非数值类计算据结构来支撑和实现算法。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。递归、解析等。新课导入任务一 巧翻字典 统计查字典次数查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的部分。假设查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的部分。假设一本字典大约一本字典大约500500页，目标信息在第页，目标信息在第269269页。请记录你翻页过程，和同学们比比，看谁翻页。请记录你翻页过程，和同学们比比，看谁翻的次数
4、最少。的次数最少。次数次数翻至页码翻至页码下一步决策下一步决策第一次250第二次第三次第四次第五次 有的同学翻得特别快，他们用了什么方法呢？原来看似普通的翻字典，不仅是一门有的同学翻得特别快，他们用了什么方法呢？原来看似普通的翻字典，不仅是一门技术，技术，更是一种能力，是算法思想的体现。更是一种能力，是算法思想的体现。凡治众如治寡，分数是也。凡治众如治寡，分数是也。孙子兵法孙子兵法 快递送达过程、营销策略、上传下载中的断点续传、通信原理中的快递送达过程、营销策略、上传下载中的断点续传、通信原理中的分组交换分组交换分治策略 分治的设计思想，是将个难以直接解决的大问题，分割成些较小的同类问题，各个
5、分治的设计思想，是将个难以直接解决的大问题，分割成些较小的同类问题，各个击破，最终达到解决问题的目的。击破，最终达到解决问题的目的。二分查找实际上一就是分治策略的种典型运用。二分查找实际上一就是分治策略的种典型运用。二分思想：将数列有序排列，采用跳跃的方式查找数据。二分思想：将数列有序排列，采用跳跃的方式查找数据。方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都能将查找区间
6、缩小一半。能将查找区间缩小一半。找一半找一半按照顺序找一半，一比较，舍一半。继续找一半，一半又一半，快速找答案！二分查找二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有在一个有n n个元素的有序序列中，利用二分查找大约需要个元素的有序序列中，利用二分查找大约需要loglog2 2n n次。次。但是，二分法查但是，二分法查找的前提条件是被查找的数据必须是找的前提条件是被查找的数据必须是有序的有序的。查找的基本算法有查找的基本算法有:顺序查找、二分查找、分块查找、哈希查找等。顺序查找、二分查找、分块
7、查找、哈希查找等。左边界左边界lowlow右边界右边界highhigh目标数目标数x x 中间数中间数 mid mid(low+high)/2(low+high)/2 若中间数若中间数midmid比目标数比目标数x x大，则区间变为左半区间，右边界更新为大，则区间变为左半区间，右边界更新为high=mid-1,high=mid-1,lowlow不变。不变。左边界左边界lowlow右边界右边界highhigh目标数目标数x x中间数中间数M Midid(low+high)/2(low+high)/2 若中间数若中间数midmid比目标数比目标数x x小，则区间变为右半区间，左边界更新为小，则区间
8、变为右半区间，左边界更新为low=mid+1,low=mid+1,highhigh不变。不变。例：例：在翻页过程中借助两个书签，划定目标所属范围，然后翻到两个书签的中间位置。在翻页过程中借助两个书签，划定目标所属范围，然后翻到两个书签的中间位置。每次目标区域都更新为原来的每次目标区域都更新为原来的“二分之一二分之一”，当数据范围缩小到只有，当数据范围缩小到只有1 1个数的时候肯定能个数的时候肯定能得到问题的解。得到问题的解。10001000以内的页码，最多翻以内的页码，最多翻1010次肯定能找到解。次肯定能找到解。有了翻字典的实际操作经验，我们来尝试完善下面的二分查找程序。如果输入的数据不在范
9、围内，会出现什么结果呢？程序还需要在哪些地方进行完如果输入的数据不在范围内，会出现什么结果呢？程序还需要在哪些地方进行完善？大家一起来试试吧。善？大家一起来试试吧。任务二 玩转“汉诺塔”游戏 剖析问题，设计游戏策略 “汉诺塔汉诺塔”游戏源于游戏源于 一个古老的印度传说。一个古老的印度传说。如图所示，木板上有如图所示，木板上有A A、B B、C C三根杆，三根杆，A A杆上杆上有若干木盘，规定每次移动一个木盘，且小的有若干木盘，规定每次移动一个木盘，且小的木盘只能叠在大的木盘上面。木盘只能叠在大的木盘上面。请设计算法，请设计算法，用尽可能少的次数把所有木盘从用尽可能少的次数把所有木盘从A A杆移
10、动到杆移动到C C杆杆上。上。要使移动次数尽可能少，必须排除无效移动。现在让我们来观察一下移动过程。要使移动次数尽可能少，必须排除无效移动。现在让我们来观察一下移动过程。递归 直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。重复的事物。在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列名的斐波那契数列“1,1,2,3,5,8,13,1,1,2,3,5,8,13,”，可以递归定义为：，可以递归定义
11、为：递归递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。也是一种问题求解的重要方法。F(n)=1(n=1或n=2)F(n-1)+F(n-2)(n2)递归的基本思想递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。而言，递推与回归，二者缺一不可。递归可用“分”，“治”，“合”三个字概括1 1）分分：将原有问题分解成：将原有问题分解成K K个子问题。个子问题。
12、2 2）治治：对这：对这K K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K K个个子问题，如此进子问题，如此进 行下去，直到问题足够小时，就很容易求出子问题的解。行下去，直到问题足够小时，就很容易求出子问题的解。3 3）合合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。问题的解。递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能在有限递推关系是递归的重要组成，而边界条件是递归的另一要素，它保证递归能
13、在有限次的计算后得出结果，而不会产生尤限循环的情况。次的计算后得出结果，而不会产生尤限循环的情况。移动移动3 3个木盘的方法是：根据木盘叠放规则，要使个木盘的方法是：根据木盘叠放规则，要使A A杆上最大的木盘（记为杆上最大的木盘（记为x)x)移动到移动到C C杆上（子问题杆上（子问题1,1,如图第如图第4 4步），必须先把步），必须先把 x x上方的所有木盘移动到上方的所有木盘移动到B B杆上（子问题杆上（子问题2,2,如如图图4 4中的前中的前3 3步），然后再将步），然后再将B B杆上所有的木盘移动到杆上所有的木盘移动到C C杆上（子问题杆上（子问题3,3,如图中的后如图中的后3 3步）。
14、步）。第1步：AC第2步：AB第3步：CB第4步：AC第5步：BA第6步：BC第7步：AC3 3个木盘的移动问题成功解决了，就可以解决更多木盘的移动问题了。个木盘的移动问题成功解决了，就可以解决更多木盘的移动问题了。解决移动3个木盘的问题。解决移动n个木盘的问题。将将n n个木盘从个木盘从A A杆移动到杆移动到C C杆，需要借助中间的杆，需要借助中间的B B杆。只要超过一个木盘，在移杆。只要超过一个木盘，在移动过程中，总会存在起始杆、动过程中，总会存在起始杆、过渡杆及目标杆的问题。因此，定义函数时，用过渡杆及目标杆的问题。因此，定义函数时，用到了到了4 4个参数：个参数：hanoi(n,A,B
15、,C),nhanoi(n,A,B,C),n表示需要移动的盘子数量，表示需要移动的盘子数量，A A表示盘子的起始表示盘子的起始杆，杆，B B表示中间过渡杆，表示中间过渡杆，C C表示目标杆，如图所示。表示目标杆，如图所示。活动 代码实现汉诺塔游戏def hanno(n,s,m,t):def hanno(n,s,m,t):#定义一个函数定义一个函数,n,n层塔，将盘子从层塔，将盘子从s s借助借助m m移动到移动到t t if n=1:if n=1:print(s,-,t)#print(s,-,t)#将一个盘子从将一个盘子从s s移动到移动到t t else:else:hanno(n-1,s,t,
16、m)#hanno(n-1,s,t,m)#将前将前n-1n-1个盘子从个盘子从s s移动到移动到m m上上 print(s,-,t)#print(s,-,t)#将最底下的最后一个盘子从将最底下的最后一个盘子从s s移动到移动到t t上上 hanno(n-1,m,s,t)#hanno(n-1,m,s,t)#将将m m上的上的n-1n-1个盘子移动到个盘子移动到t t上上#主程序主程序n=int(input(n=int(input(请输入汉诺塔的层数：请输入汉诺塔的层数：)hanno(n,A,B,C)hanno(n,A,B,C)input(input(运行完毕，请按回车键退出运行完毕，请按回车键退出
17、.).)迭代与递归的关系 迭代迭代算法算法与递归算法都需要重复执行某些代码，两者既有区别又有密切的联系。与递归算法都需要重复执行某些代码，两者既有区别又有密切的联系。递归迭代重复方式是重复调用函数自身。重复方式：是重复反馈过程的活动，其目的通常是逼近所需目标或结果。结束方式：遇到满足终止条件的情况时逐层返回。结束方式：通常使用计数器结束循环。迭代程序可以转换成等价的递归程序。以上一节中的计算斐波那契数列第迭代程序可以转换成等价的递归程序。以上一节中的计算斐波那契数列第n n项的值为例，项的值为例，程序间的转换如下：程序间的转换如下：1 1、计算、计算“汉诺塔汉诺塔”游戏移动的次数。游戏移动的次
18、数。参考答案：参考答案：def f(n):def f(n):if n=0:if n=0:return 0 return 0 else:else:return 2 return 2*f(n-1)+1 f(n-1)+1 x=int(input(x=int(input(请输入塔的个数：请输入塔的个数：)print(print(需要移动需要移动,f(x),f(x),次次)input(input(运行完毕，请按回车键退出运行完毕，请按回车键退出.).)巩固提升练一练操作提示：令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)1e-6:while abs(b-a)1e-6:x0=(a+b)/2 x0=(a+b)/2 if f(a)if f(a)*f(x0)0:f(x0)0:b=x0 b=x0 if f(b)if f(b)*f(x0)0:f(x0)0:a=x0 a=x0 if f(x0)=0:if f(x0)=0:break breakprint(print(解为解为:,x0):,x0)input(input(运行完毕，请按回车键退出运行完毕，请按回车键退出.).)课堂小结非数值计算
