信息技术必修1 数据与计算4.3 非数值计算教学ppt课件
展开3.体验递归算法,并结合具体问题开展编程实践。
2.了解算法设计中的分治思想,并运用二分查找解决实际问题。
1.运用合适的算法形成解决问题的方案。
二分查找法的理解和运用二分法解决实际问题。 (重点)
递归算法的实际应用,并针对具体问题开展编程实践。 (难点)
运行Pythn编写的“猜数字”游戏,计算机在0~1000中随机产生一个数,试试看你要多少次才能猜中。
假设一本书大约300页,目标信息在第132页。请在下表记录你的翻页过程,和同学们比一比,看谁翻的次数最少。
分治的设计思想,是将一个难以直接解决的大问题,分割成一些较小的同类问题,各个击破,最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。
二分查找又叫折半查找,该方法主要将数列有序排列,采用跳跃式的方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。 以递增数列为例,先以中点位置的元素作为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。每一次比较后都可以将查找区间缩小-半。 二分法查找的前提条件是被查找的数据必须是有序的。
查找的基本算法有: 顺序查找、二分查找、 分块查找、哈希查找等
有了翻书的经验,我们尝试完善下面的二分查找程序。x=int(input("请输入要查找的1000以内的整数:"))step=0 #记录查找次数flag1=1 #目标区域左边界flag2=1000 #目标区域左边界while( ): #区间数据范围小于1则结束循环 mid=( ) #中间值 ( ) #查找次数加1 if mid>x: ( ) #右边界前移 elif mid
(flag1+flag2)//2
step=step+1
flag2=mid-1
flag1=mid+1
“汉诺塔”游戏源于一个古老的印度传说。如图所示,在木板上有A、B、C三根杆,A杆上有若干木盘,规定每次移动一个木盘。且小的木盘只能叠在大的木盘上面。请设计算法,用尽可能少的次数把所有的木盘从A杆全部移到C杆上。完成课本P102图4.3.2汉诺塔的移动过程。
直接或间接地调用自身的方法称为递归。
递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段,也是一种问题求解的重要方法。
以下是一个四叶草的代码及运行结果
图4.3.3 递归图像
在数学与计算机领域中,递归函数是指用函数自身定义该函数的方法。 递归的要素: 1.递推关系的递归的重要组成 2.边界条件。它保证递归能在有限次的计算后得出结果,而不会产生无限循环的情况。
递归的基本思想:把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言,递推与回归,二者缺一不可。结合分治策略,递归也可以用“分”“治”“合”三个字概况
分:将原有问题分解成K个子问题。治:对这K个子问题分别求解。如果子问题的规模仍然不够小,则将其再分解为K个子问题,如此进行下去,直到问题足够小时,就很容易求出子问题的解。合:将求出的小规模问题的解合并为一个更大规模问题的解,自下而上逐步求出原问题的解。
汉诺塔的递归过程:将N个木盘从A杆移动到C杆,需要借助中间的B杆,只要超过一个木盘,在移动过程中,总会存在起始杆、过渡杆及目标杆的问题。因此,定义函数时,用到了4个参数:hai(n,s,m,t),n表示需要移动的盘子数量,S表示盘子的起始杆,m表示中间过渡杆,t表示目标杆。可用下图表示:
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('请输入汉诺塔的层数:'))#调用函数,将n个木盘从A借助B移动到Chann(n,'A','B','C')input("运行完毕,请按回车键退出...")
输入不同的层数,查看运行结果
计算“汉诺塔”游戏移动的次数。参考答案: def f(n): if n==0: return 0 else: return 2*f(n-1)+1 x=int(input("请输入塔的个数:")) print("需要移动",f(x),"次") input("运行完毕,请按回车键退出...")
根据提示输入不同的塔数,查看移动的次数
迭代算法与递归算法都需要重复执行某些代码,两者既有区别又有密切的联系。 迭代 重复方式:是重复反馈过程的活动,其目的通常是逼迫所需目标或结果。 结束方式:通常使用计数器结束循环。 递归 重复方式是重复调用函数自身。 结束方式:遇到满足终止条件的情况时逐层返回。
高中信息技术教科版 (2019)必修1 数据与计算4.3 非数值计算课前预习课件ppt: 这是一份高中信息技术教科版 (2019)必修1 数据与计算4.3 非数值计算课前预习课件ppt,共23页。PPT课件主要包含了学习目标,新课导入,分治策略,二分查找,递归的基本思想,迭代与递归的关系,巩固提升,练一练等内容,欢迎下载使用。
信息技术必修1 数据与计算4.3 非数值计算优质ppt课件: 这是一份信息技术必修1 数据与计算4.3 非数值计算优质ppt课件,共17页。PPT课件主要包含了游戏导入,Part01,本节内容讲解,Part02,二分查找,查找过程演示,二分法查找2的过程,重点难点解读,Part03等内容,欢迎下载使用。
高中信息技术教科版 (2019)必修1 数据与计算4.3 非数值计算完美版课件ppt: 这是一份高中信息技术教科版 (2019)必修1 数据与计算4.3 非数值计算完美版课件ppt,文件包含43非数值计算第二课时ppt、4-3汉诺塔游戏swf等2份课件配套教学资源,其中PPT共20页, 欢迎下载使用。