《【课件】非数值计算（课件）-高一信息技术课件（教科版2019必修1）.pptx》由会员分享，可在线阅读，更多相关《【课件】非数值计算（课件）-高一信息技术课件（教科版2019必修1）.pptx（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.3 4.3 非数值计算非数值计算2019教科版高中信息技术学学习目标习目标运用合适的算法形成解决问题的方案。了解算法设计中的分治思想，并运用二分查找解决实际问题。体验递归算法，并结合具体问题开展编程实践。三维三维目标目标知识与技能：能够理解分治思想和递归方法；能够利用递归方法设计相应程序；能够基于不同场景分析编写程序。过程与方法通过在练习活动中不断将问题与大概念相结合，促进和提升问题解决能力。情感态度价值观通过在游戏中体验程序设计的乐趣和逻辑思维的严谨。学科核心素养能够分析问题时将其理解为数学问题，并通过合理、严谨的算法进行程序设计，提升问题解决能力和计算思维。一、游戏导入一、游戏导入【寻
2、找假币游寻找假币游戏戏】有100个硬币，其中有1个伪币，它除了质量比真币轻一点之外，没有别的区别，如何通过天平快速找到这个伪币。大家自己查找资料并讨论1、如何判断假币2、如何找到假币？【在100个硬币中找出伪币】如何判断假币？厚薄不均匀色泽不光滑重量不一致如何找到假币？分治思想【寻找假币游寻找假币游戏戏】一、游戏导入一、游戏导入首先是将100个硬币分成两个50，使用天平进行衡量，然后确定伪币在比较轻的那50个里，接着再将50分成2个25，将25分成两个12和1个1，将12分成2个6，将6分成2个3，将3分成3个1，这样6次就可以找到伪币，比50次少很多。以重量判断为例重量轻的是假币【寻找假币游
3、寻找假币游戏戏】一、游戏导入一、游戏导入二二、活动探究、活动探究请总结说出如何查找单词“book”的算法。1、从字典本的中间开始翻找，找到字母b的所在页码区域；2、从字母b的区域中间翻找，找到o的所在页码区域；3、重复上述翻找，直到查找到字母k。【查找单词游查找单词游戏戏】【二二分查找分查找】（1）数据排序将数据有序排列：先将一个数据集进行有序排列（2）数据分半：就是将排序好的数据集切分成大致相等的两份数据集；（3）查找数据：查找的时候直接和拆分数据集中的第一个或最后一个元素进行大小比较，不满足则表示数据不存在于该数据集中，满足则说明要查找的元素存在于当前数据集中。二二、活动探究、活动探究【二
4、二分查找分查找】将查找下面数组中的10数组1:1、5、6、9、10、20、21数字2:9、10、33、45、76、90、100【练习】二二、活动探究、活动探究【二二分查找分查找】数组1:1、5、6、9、10、20、21leftright01234561569102021mid=(left+right)/2第一次查找查找结果为：索引号3，数值9二二、活动探究、活动探究【二二分查找分查找】leftright01234561569102021mid第二次查找查找结果为：索引号5，数值20910，因此，mid要向右移动1个单位，即left=mid+1left=mid+1二二、活动探究、活动探究【二二分
5、查找分查找】leftright01234561569102021mid第三次查找查找结果为：索引号4，数值102010，因此，mid要向左移动1个单位，即right=mid-1right=mid-1二二、活动探究、活动探究【二二分查找分查找】012345691033457690100自主练习数组2:9、10、33、45、76、90、100二二、活动探究、活动探究【二二分查找分查找】012345691033457690100自主练习数字2:9、10、33、45、76、90、100第一次leftright06911结果mid=3号，45.right=mid-1第二次 leftright02933结
6、果mid=1号，10二二、活动探究、活动探究【二二分查找分查找】deferfen(array,key):left=0right=len(array)-1whileleft=right:mid=(left+right)/2ifarraymidkey:right=mid-1else:returnmid核心程序：array=9,10,33,45,76,90,100key=10array_index=erfen(array,key)print(array_index)主程序：二二、活动探究、活动探究二二、活动探究、活动探究【二二分查找分查找】【分分治与二分治与二分】1分治策略分治的设计思想，是将一个难
7、以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。2二分法二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。二二、活动探究、活动探究补充程序代码【二分查找二分查找】while(flag1x:flag2=mid-1elifmidx:flag1=mid+1else:break二二、活动探究、活动探究1、有三根相邻的柱子，标号为A,B,C。2、A
8、柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。3、现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。【什么是汉诺塔游戏？】【玩转汉诺塔玩转汉诺塔】二二、活动探究、活动探究https:/zhangxiaoleiwk.gitee.io/h.html同学们登录网址自己玩一玩汉诺塔游戏吧。核心思想是：不断重复前面移动规则。当摆3层时，则需要重新摆2层。当摆4层时，则需要重新摆3层。二二、活动探究、活动探究【玩转汉诺塔玩转汉诺塔】【递归勾股树】递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。直接或间接地调用自
9、身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。二二、活动探究、活动探究【递归递归】二二、活动探究、活动探究【递归递归】在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1，1，2，3，5，8，13，”，可以递归定义为二二、活动探究、活动探究【递归递归】【递归的分治】结合分治策略，递归也可用“分”“治”“合”三个字概括。（1）分：将原问题分解成k个子问题。（2）治：对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。（3）合：将求出的小规模问题的解合并为一个更大规
10、模问题的解，自下而上逐步求出原问题的解。二二、活动探究、活动探究【递归递归】【练习】常见递归方法有：阶乘、等比数列、等差数列。1、请你设计阶乘底数为5的递归程序设计，并能正确打印结果。2、请你设计递归形式的斐波那契数列，使其输入索引号时，能够打印出对应数值。二二、活动探究、活动探究【递归递归】deffbnq(n):ifn=2:return1n=fbnq(n-1)+fbnq(n-2)returnnm=fbnq(int(input(请输入索引号)print(m)【斐波那契数列】二二、活动探究、活动探究【递归递归】【等差数列】defdengcha(n):#定义一个函数名是dengcha，参数为n的函
11、数ifn=1:#当参数n为1时，返回n的值returnn#结束函数，并返回一个值n给函数n=dengcha(n-1)+10returnnm=dengcha(int(input(请输入等差项目)print(m)二二、活动探究、活动探究【递归递归】【阶乘】defjiecheng(n):#定义一个函数名是jiecheng，参数为n的函数ifn=1:#当参数n为1时，返回n的值returnn#结束函数，并返回一个值n给函数n=n*jiecheng(n-1)#当不满足n=1时，进行递推，nl=n*（n-1）！returnn#结束函数，并返回一个值n给函数m=jiecheng(int(input(输入阶乘底数)print(m)#打印出m的值二二、活动探究、活动探究【递归递归】观察程序设计，发现递归的本质是，函数对自身的调用函数a函数b调用函数a调用函数b函数a自调用函数a递归【总结递归】二二、活动探究、活动探究【递归递归】三三、课后作业、课后作业查找迭代和递归的相关资料，并写一份报告，报告内容为：你认为用迭代方法和递归方法分别实现斐波那契数列时的区别，并在下节课交流你的发现和结论。