高一信息技术教科版必修1教案43非数值计算

教学单元计算与问题解决教学主题非数值计算

教学目标

知识与技能

•能够理解分治思想和递归方法；

•能够利用递归方法设计相应程序；

•能够基于不同场景分析编写程序。

过程与方法

•通过在练习活动中不断将问题与大概念相结合，促进和提升问题解决能力。

情感态度价值观

•通过在游戏中体验程序设计的乐趣和逻辑思维的严谨。

核心素养培养

能够分析问题时将其理解为数学问题，并通过合理、严谨的算法进行程序设计，提升问题解决

能力和计算思维。

教学内容

二分查找；分治思想：递归思想

教学媒体

电子白板、PPT

教学过程

教学环节教师活动学生活动设计意图

游戏导入【寻找假币游戏一一在学生讨论并说明寻找假币的关键通过游戏让学

100个硬币中找出伪币】点：生从问题解决

有100个硬币，其中有11、如何判断假币；中学会如何抓

个伪币，它除了质量比真2、如何找到假币,住问题的关键

币轻一点之外，没有别的问题，解决关

区别，如何通过天平快速如何判断假币？键问题便是解

找到这个伪币。•厚薄不均匀决问题。

大家自己查找资料并讨•色泽不光滑在教师的引导

论。•重要不一致下了解引入二

如何找到假币？分查找方法。

引入二分查找•分治思想激发学习兴

趣。

100个硬币，1个籁的

以重量判断为例，重量轻回S

就是假币。a固

回回日

首先是将100个硬币分成两个

ES

50,使用天平进行衡量，然后SS

确定伪币在比较轻的那50个LLJLULLI

里，接着再将50分成2个25,

将25分成两个12和1个1,

将12分成2个6,赧6分成2

个3,将3分成3个1,这样6

次就可以找到伪币，比50次少

很多。

活动探究【知识点一、二分查找】

请总结说出如何查找单词学生尝试说明如何去查找单词，在前述寻找假

“book”的算法。并在教师引导下总结步骤：币游戏的导入

1、从字典本的中间开始翻找，（1）数据排序下，充分激发

找到字母b的所在贝码区域：•将数据有序排列：先将一个数学生对课堂的

2、从字母b的区域中间翻找，据集进行有序排列好奇心，但是

找到。的所在页码区域：（2）数据分半：假币并不足以

3、重复上述翻找，直到查找到・就是将排序好的数据集切分完全作为二分

字母ko成大致相等的两份数据集；法内容的案

（3）查找数据：例，利用寻找

・查找的时候直接和拆分数据单词游戏来让

集中的第一个或最后一个元学生总结步

素进行大小比较，不满足则表骤，并让学生

示数据不存在于该数据集中，体会二分法步

满足则说明要查找的元素存骤。

在于当前数据集中。

【练习】学生按照二分的方法，自己尝试

将查找下面数组中的10寻找各数组的10。

数组1:1、5、6、9、10、

20、21

数字2:9、10、33、45、

76、90、100通过数组练习

数组1:1、5、6、9、10、法，再次实践

20、211I1理论知识，深

■[left][ed.Mt.rtghWZ]

分别引导学生进行第一次、第化和巩固二分

n次的排序方法和结果。让学法的实际操作

a”.■«,fBoraaiEQ.4mm*1

生模仿并对照，激发思维活力。方法，并在探

IIII究学习中不断

■熟练掌握二分

方法，为后续

二分算法和程

Im序设计打下知

识基础。

自主练习教组2:9、10、—一次leftright

33、45、76、90、10006

911

结聚md=3号，45

nghl=mid-1

篦二次leftrtflht

02

933

结果mMT号，10

由学生讨论教师引导，分析并核心程序：

经过两轮数组

设计出二分法的核心程序和主

deferfen(array,key):二分查找的练

程序。left=O

right=len(array)l习后，学生己

whileleft<=right:经能够完全进

mid=(left+right)//2入程序设计阶

ifarray[mid]<key:段，跟随教师

left=mid+l的引导自主总

elifarray[mid]>key:结算法结构和

播放【数组二分】的结果演示right=midl代码内容。

视频。else:

returnmid

主程序:array=[9,10,33,45,76,90,100]

key=10

array_index=erfen(2rray,key)

print(array_index)

【知识点二、分治】

1、分治策略认真听讲并记笔记。学生在二分基

分治的设计思想，是将一础上更容易理

个难以直接解决的大问解分治策略。

题，分割成一些较小的同在前述的游戏

类问题，各个击破，最终探究和问题解

达到解决问题的目的。二决中，已经理

分查找实际上就是分治策解了二分法，

略的一种典型运用。因此从特殊向

2、二分法一般进行抽象

二分查找乂叫折半查找，理解分治策

该方法主要将数列有序排略，有利于问

歹九采用跳跃式的方式查题解决能力提

找数据。以递增数列为例，升和抽象思维

先以中点位置的元素作为的发展。

比较对象，如果要找的元

素值小于该中点元素，则

将待查序列缩小为左半部补充教材上的代码并运行结果，

分，否则为右半部分。每调适bug.

一次比较后都可以将查找

区间缩小一半。

补充教材中的程序代码

while(flagl<=flag2)：

mid=(flagl+flag2)/2

ifmid>x:

flag2=midl

elifmid<x:

flagl=mid+l

else:

break

活动2用Python绘制

斐波那契数列图象

查找资料，小组合作完成

利用Python实现递归方法

下的斐波那契数列图象绘

制。

并解释核心代码实现过

程。

【播放视频】

播放运行程序结果并给学

生讲解过程。

【知识点三、递归】

【什么是汉诺塔游戏】学生观看视频，理解游戏规则，在游戏中体会

1、有三根相邻的柱子，标并进入汉诺塔游戏网站，自行体汉诺塔游戏的

号为A,B,C.验游戏玩法。核心原理，让

2、A柱子上从下到上按金学生自己总结

字塔状叠放着n个不同大核心思想是：结论，提升归

小的圆盘。•不断重复前面移动规则。纳结论的能

3、现在把所有盘子一个•当摆3层时，则需要重新摆2力。

一个移动到柱子B上，并层。

且每次移动同一根柱子上•当摆4层时，则需要重新摆3

都不能出现大盘子在小盘层。

子上方。

播放【汉诺塔玩法】视频，

让学生和教师一起总结汉

诺塔游戏的核心思想。

【递归一一勾股树】汉诺塔就是利用了递归的思想。勾股树是典型

递归是计算科学领域中一学生理解递归的概念。的递归结果，

种重要的计算思维模式。通过让学生观

它既是一种抽象表达的手递归树是由勾股定理组合成的一看勾股树的形

段，也是一种问题求解的种美丽数学图案。式过程，结合

重要方法。汉诺塔游戏，

直接或间接地调用自身的理解递归的思

方法称为递归。可以将递想。

归简单类比为具有自相似在探究基砒上

性重复的事物。讲解内容更能

播放【递归树】的视频，让学生理解知

并由教师递归树的构成。识并且提升知

在数学与计算机领域中,识的理论程

递归函数是指用函数自身度。

来定义该函数的方法。如记笔记并认真听讲。由学生在知识

著名的斐波那契数列“1,讲解完后，让

1,2,3,5,8,13,…”，学生自主设计

可以递归定义为函数，虽然有

fl(R-KH-D

F(n)-<难度，但是锻

[人■-l)♦/(・-2[(n>2)

炼了学生整体

【递归的分治】

的综合程序设

结合分治策略，递归也可

计能力，具有

用“分”，，治，，，，合”三个

挑战性。

字概括。

(1)分：将原问题分解成

k个r问题。

(2)治：对这k个子问题

分别求解。如果子问题的

规模仍然不够小，则将其

再分解为k个子问题，如此

进行下去，直到问题足够

小时，就很容易求出子问

题的解。

(3)合：将求出的小规模

问题的解合并为一个更大

规模问题的解，自下而上

逐步求出原问题的解。

讨论并练习设计函数，自主运行

【练习】

结果，调适bug。

常见递归方法有：阶乘、

【斐波那契数列】

等比数列、等差数列。

deffbnq(n):

1、请你设计阶乘底数为5

ifn<=2:

的递归程序设计，并能正

return1

确打印结果。

n=fbnq(nl)+fbnq(n2)

2、请你设计递归形式的斐

returnn

波那契数列，使其输入索

m=fbnq(int(inputC请输入索引号

引号时，能够打印出对应

数值。')))

print(m)

【总结递归】

观察程序设计，发现递归【等差数列】

的本质是，函数对自身的defdengcha(n):#定义一个函数名

调用是dengcha,参数为n的函数

ifn==l:#当参数n为1时，返

回n的值

returnn#结束函数,并返

函数a调用函数b回一个值n给函数

自调用n=dengcha(nl)+10

areturnn

m=dengcha(int(input('请输入等差

项目》)

print(m)

函数a递归【阶乘】

defjiecheng(n):#定义一1个函数名

是jiecheng,参数为n的函数

ifn==l:#当参数n为1时，返

回n的值

returnn#结束函数，并返回

一个值n给函数