4.3 非数值计算（课件）-高一信息技术同步教材配套教案+课件（教科版2019必修1）

4.3 非数值计算 2019教科版 高中信息技术 学习目标 运用合适的算法形成解决问题的方案。 了解算法设计中的分治思想，并运用二分查找解决实际问题。 体验递归算法，并结合具体问题开展编程实践。 三维目标 3 知识与技能： 能够理解分治思想和递归方法； 能够利用递归方法设计相应程序； 能够基于不同场景分析编写程序。 过程与方法 通过在练习活动中不断将问题与大概念相结合，促进和提升问题解决能力。 情感态度价值观 通过在游戏中体验程序设计的乐趣和逻辑思维的严谨。 学科核心素养 能够分析问题时将其理解为数学问题，并通过合理、严谨的算法进行程序设计，提升问题解决能力和计算思维。 一、游戏导入 【寻找假币游戏】 有100个硬币，其中有1个伪币，它除了质量比真币轻一点之外，没有别的区别，如何通过天平快速找到这个伪币。 【在100个硬币中找出伪币】 大家自己查找资料并讨论 1、如何判断假币 2、如何找到假币？ 【寻找假币游戏】 一、游戏导入 如何判断假币？ 厚薄不均匀 色泽不光滑 重量不一致 如何找到假币？ 分治思想 首先是将100个硬币分成两个50，使用天平进行衡量，然后确定伪币在比较轻的那50个里，接着再将50分成2个25，将25分成两个12和1个1，将12分成2个6，将6分成2个3，将3分成3个1，这样6次就可以找到伪币，比50次少很多。 以重量判断为例 重量轻的是假币 【寻找假币游戏】 一、游戏导入 二、活动探究 请总结说出如何查找单词“book”的算法。 1、从字典本的中间开始翻找，找到字母b的所在页码区域； 2、从字母b的区域中间翻找，找到o的所在页码区域； 3、重复上述翻找，直到查找到字母k。 【查找单词游戏】 【二分查找】 （1）数据排序 将数据有序排列：先将一个数据集进行有序排列 （2）数据分半： 就是将排序好的数据集切分成大致相等的两份数据集； （3）查找数据： 查找的时候直接和拆分数据集中的第一个或最后一个元素进行大小比较，不满足则表示数据不存在于该数据集中，满足则说明要查找的元素存在于当前数据集中。 二、活动探究 【二分查找】 将查找下面数组中的10 数组1: 1、5、6、9、10、20、21 数字2: 9、10、33、45、76、90、100 【练习】 二、活动探究 【二分查找】 数组1: 1、5、6、9、10、20、21 left right 0 1 2 3 4 5 6 1 5 6 9 10 20 21 mid=(left+right)/2 第一次查找 查找结果为：索引号3，数值9 二、活动探究 【二分查找】 left right 0 1 2 3 4 5 6 1 5 6 9 10 20 21 mid 第二次查找 查找结果为：索引号5，数值20 9<10，因此，mid要向右移动1个单位，即left=mid+1 left=mid+1 二、活动探究 【二分查找】 left right 0 1 2 3 4 5 6 1 5 6 9 10 20 21 mid 第三次查找 查找结果为：索引号4，数值10 20＞10，因此，mid要向左移动1个单位，即right=mid-1 right=mid-1 二、活动探究 【二分查找】 0 1 2 3 4 5 6 9 10 33 45 76 90 100 自主练习数组2: 9、10、33、45、76、90、100 二、活动探究 【二分查找】 0 1 2 3 4 5 6 9 10 33 45 76 90 100 自主练习数字2: 9、10、33、45、76、90、100 第一次 left right 0 6 9 11 结果 mid=3号，45. right=mid-1 第二次 left right 0 2 9 33 结果 mid=1号，10 二、活动探究 【二分查找】 def erfen(array,key):     left=0     right=len(array)-1     while left<=right:         mid=(left+right)//2         if array[mid]<key:             left=mid+1         elif array[mid]>key:             right=mid-1         else :             return mid 核心程序： array=[9,10,33,45,76,90,100] key=10 array_index=erfen(array,key) print(array_index) 主程序： 二、活动探究 二、活动探究 【二分查找】 【分治与二分】 二、活