非数值计算-课件完整版

教科版（2019版）信息技术（高中）4.3非数值计算第4单元计算与问题解决必修1数据与计算

运行利用python编写的“猜数字”游戏，计算机在1-1000

中随机产生一个数，试试看你要猜多少次才能猜中。猜数字课堂导入程序源代码及执行结果截图：如何猜得又快又准？二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可以将查找区间缩小一半。二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要log2n次。课堂活动1如何实现？请学生思考：利用自然语言如何描述？利用程序如何实现？统计二分查找次数的源代码和程序运行截图：尝试用二分法求x3-x2+x-1=0在[-5,5]区间的解。deff(x): #定义方程returnx**3-x**2+x-1a=float(input("请输入解区间的左边界："))b=float(input("请输入解区间的右边界："))whileabs(b-a)>1e-6:x0=(a+b)/2iff(a)*f(x0)<0:b=x0iff(b)*f(x0)<0:a=x0iff(x0)==0:breakprint("解为:",x0)input("运行完毕，请按回车键退出...")练习1程序源代码和运行界面截图：1.凡治众如治寡，分数是也。（摘自孙子兵法）2.查找的基本算法有：顺序查找、二分查找，分块查找、哈希查找等。拓展知识3.当while循环中执行break语句时，循环会马上终止。4.python中的sort()可以用于数据排序。

例如，以下语句：x=[4,6,2,1,5,9]x.sort()可以将列表x按从小到大的顺序排列。

“汉诺塔”游戏源于一个古老的印度传说。如下图所示，在木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘。且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有的木盘从A杆全部移到C杆上。课堂活动2直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。递归递归函数是只用函数自身来定义该函数的方法。如斐波那契数列“1,1,2,3,5,8,13……”,可以递归定义为：F(n)=1(n=1或n=2)F(n-1)+F(n-2)(n>2)递归函数递归的基本思想递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。递归可用“分”，“治”，“合”三个字概括1）分：将原有问题分解成K个子问题。2）治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进

行下去，直到问题足够小时，就很容易求出子问题的解。3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。汉诺塔游戏源代码和运行界面截图：1.理解递归思想。2.理解递归算法。3.理解二分查找思想，运用二分算法解决实际问题。课堂小结结合4.2的知识，计算“汉诺塔”游戏移动的次数。deff(n):ifn==0:return0else:return2*f(n-1)+1x=int(input("请输入塔的个数："))print("需要移动",f(x),"次")input("运行完毕，请按回车键退出...")练习2汉诺塔移动次数源代码和运行界面截图：迭代程序可以转换成等价的递归程序。以上一节中计算斐波那契数列第N项的值为例，程序间的转换如表所示。迭代与递归算法都需要重复执行某些代码，两者既