教学单元 计算与问题解决 教学主题 非数值计算
教学目标
知识与技能 能够理解分治思想和递归方法； 能够利用递归方法设计相应程序； 能够基于不同场景分析编写程序。 过程与方法 通过在练习活动中不断将问题与大概念相结合，促进和提升问题解决能力。 情感态度价值观 通过在游戏中体验程序设计的乐趣和逻辑思维的严谨。
核心素养培养
能够分析问题时将其理解为数学问题，并通过合理、严谨的算法进行程序设计，提升问题解决能力和计算思维。
教学内容
二分查找；分治思想；递归思想
教学媒体
电子白板、PPT
教学过程
教学环节 教师活动 学生活动 设计意图
游戏导入 【寻找假币游戏——在100个硬币中找出伪币】 有100个硬币，其中有1个伪币，它除了质量比真币轻一点之外，没有别的区别，如何通过天平快速找到这个伪币。 大家自己查找资料并讨论。 引入二分查找 以重量判断为例，重量轻就是假币。 首先是将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 学生按照二分的方法，自己尝试寻找各数组的10。
数组1: 1、5、6、9、10、20、21 分别引导学生进行第一次、第n次的排序方法和结果。让学生模仿并对照，激发思维活力。
自主练习数组2: 9、10、33、45、76、90、100
由学生讨论教师引导，分析并设计出二分法的核心程序和主程序。 播放【数组二分】的结果演示视频。 核心程序： def erfen(array,key): left=0 right=len(array)-1 while left<=right: mid=(left+right)//2 if 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)
【知识点二、分治】
1、分治策略 分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破，最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。 2、二分法 二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。 认真听讲并记笔记。 补充教材上的代码并运行结果，调适bug。 学生在二分基础上更容易理解分治策略。在前述的游戏探究和问题解决中，已经理解了二分法，因此从特殊向一般进行抽象理解分治策略，有利于问题解决能力提升和抽象思维的发展。
补充教材中的程序代码 while(flag1<=flag2): mid=（flag1+flag2）/2 if mid>x: flag2=mid-1 elif mid活动2 用Python绘制斐波那契数列图象 查找资料，小组合作完成利用Python实现递归方法下的斐波那契数列图象绘制。 并解释核心代码实现过程。 【播放视频】 播放运行程序结果并给学生讲解过程。
【知识点三、递归】
【什么是汉诺塔游戏】 1、有三根相邻的柱子，标号为A,B,C。 2、A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。 3、现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。 播放【汉诺塔玩法】视频，让学生和教师一起总结汉诺塔游戏的核心思想。 学生观看视频，理解游戏规则，并进入汉诺塔游戏网站，自行体验游戏玩法。 核心思想是： 不断重复前面移动规则。 当摆3层时，则需要重新摆2层。 当摆4层时，则需要重新摆3层。 在游戏中体会汉诺塔游戏的核心原理，让学生自己总结结论，提升归纳结论的能力。
【递归——勾股树】 递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。 直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。 播放【递归树】的视频，并由教师递归树的构成。 在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1，1，2，3，5，8，13，…”，可以递归定义为 【递归的分治】 结合分治策略，递归也可用“分”“治”“合”三个字概括。 （1）分：将原问题分解成k个子问题。 （2）治：对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。 （3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。 【练习】 常见递归方法有：阶乘、等比数列、等差数列。 1、请你设计阶乘底数为5的递归程序设计，并能正确打印结果。 2、请你设计递归形式的斐波那契数列，使其输入索引号时，能够打印出对应数值。 【总结递归】 观察程序设计，发现递归的本质是，函数对自身的调用 汉诺塔就是利用了递归的思想。 学生理解递归的概念。 递归树是由勾股定理组合成的一种美丽数学图案。 记笔记并认真听讲。 讨论并练习设计函数，自主运行结果，调适bug。 【斐波那契数列】 def fbnq(n): if n<=2: return 1 n=fbnq(n-1)+fbnq(n-2) return n m=fbnq(int(input('请输入索引号'))) print(m) 【等差数列】 def dengcha(n):#定义一个函数名是dengcha，参数为n的函数 if n==1:#当参数n为1时，返回n的值 return n#结束函数，并返回一个值n给函数 n=dengcha(n-1)+10 return n m=dengcha(int(input('请输入等差项目'))) print(m) 【阶乘】 def jiecheng(n):#定义一个函数名是jiecheng，参数为n的函数 if n==1:#当参数n为1时，返回n的值 return n#结束函数，并返回一个值n给函数 n=n*jiecheng(n-1)#当不满足n==1时，进行递推，nl=n*（n-1）！ return n#结束函数，并返回一个值n给函数 m=jiecheng(int(input('输入阶乘底数'))) print(m)#打印出m的值 勾股树是典型的递归结果，通过让学生观看勾股树的形式过程，结合汉诺塔游戏，理解递归的思想。 在探究基础上讲解内容更能让学生理解知识并且提升知识的理论程度。 由学生在知识讲解完后，让学生自主设计函数，虽然有难度，但是锻炼了学生整体的综合程序设计能力，具有挑战性。
课后作业 查找迭代和递归的相关资料，并写一份报告，报告内容为：你认为用迭代方法和递归方法分别实现斐波那契数列时的区别，并在下节课交流你的发现和结论。 学生完成学习报告。 巩固、加强学习，并解决开放性问题。(共30张PPT)
4.3 非数值计算
2019教科版
高中信息技术
学习目标
运用合适的算法形成解决问题的方案。
了解算法设计中的分治思想，并运用二分查找解决实际问题。
体验递归算法，并结合具体问题开展编程实践。
三维目标
一、游戏导入
【寻找假币游戏】
有100个硬币，其中有1个伪币，它除了质量比真币轻一点之外，没有别的区别，如何通过天平快速找到这个伪币。
【在100个硬币中找出伪币】
【寻找假币游戏】
一、游戏导入
首先是将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] 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)
主程序：
二、活动探究
二、活动探究
【二分查找】
【分治与二分】
二、活动探究
补充程序代码
【二分查找】
while(flag1<=flag2):
mid=（flag1+flag2）/2
if mid>x:
flag2=mid-1
elif midflag1=mid+1
else:
break
二、活动探究
1、有三根相邻的柱子，标号为A,B,C。
2、A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。
3、现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。
【什么是汉诺塔游戏？】
【玩转汉诺塔】
二、活动探究
https://zhangxiaoleiwk.gitee.io/h.html同学们登录网址自己玩一玩汉诺塔游戏吧。
核心思想是：
不断重复前面移动规则。
当摆3层时，则需要重新摆2层。
当摆4层时，则需要重新摆3层。
二、活动探究
【玩转汉诺塔】
【递归——勾股树】
递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。
直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。
二、活动探究
【递归】
二、活动探究
【递归】
在数学与计算机领域中，递归函数是指用函数自身来定义该函数的方法。如著名的斐波那契数列“1，1，2，3，5，8，13，…”，可以递归定义为
二、活动探究
【递归】
【递归的分治】
结合分治策略，递归也可用“分”“治”“合”三个字概括。
（1）分：将原问题分解成k个子问题。
（2）治：对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。
（3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
二、活动探究
【递归】
【练习】
常见递归方法有：阶乘、等比数列、等差数列。
1、请你设计阶乘底数为5的递归程序设计，并能正确打印结果。
2、请你设计递归形式的斐波那契数列，使其输入索引号时，能够打印出对应数值。
二、活动探究
【递归】
def fbnq(n):
if n<=2:
return 1
n=fbnq(n-1)+fbnq(n-2)
return n
m=fbnq(int(input('请输入索引号')))
print(m)
【斐波那契数列】
二、活动探究
【递归】
【等差数列】
def dengcha(n):#定义一个函数名是dengcha，参数为n的函数
if n==1:#当参数n为1时，返回n的值
return n#结束函数，并返回一个值n给函数
n=dengcha(n-1)+10
return n
m=dengcha(int(input('请输入等差项目')))
print(m)
二、活动探究
【递归】
【阶乘】
def jiecheng(n):#定义一个函数名是jiecheng，参数为n的函数
if n==1:#当参数n为1时，返回n的值
return n#结束函数，并返回一个值n给函数
n=n*jiecheng(n-1)#当不满足n==1时，进行递推，nl=n*（n-1）！
return n#结束函数，并返回一个值n给函数
m=jiecheng(int(input('输入阶乘底数')))
print(m)#打印出m的值
二、活动探究
【递归】
观察程序设计，发现递归的本质是，函数对自身的调用
函数a
函数b
调用
函数a调用函数b
函数a
自调用
函数a递归
【总结递归】
二、活动探究
【递归】
三、课后作业
查找迭代和递归的相关资料，并写一份报告，报告内容为：你认为用迭代方法和递归方法分别实现斐波那契数列时的区别，并在下节课交流你的发现和结论。
