资源简介

教科版
高一信息技术
必修1
第四单元
4.1
算法及特征
教学设计
4.1
算法及其特征
【学习目标】
1.通过解决开关问题，能够分析出算法的基本特征，感受算法在解决问题中的重要性。
2.通过解决药丸问题，尝试运用恰当的方法描述算法。
3.能够将部分简单算法转换为程序，并调试运行得出结果。
4.通过解决冠军问题，了解枚举法的含义，并能使用枚举法解决相关问题。
【教学重点】
能够分析问题，设计解决问题的算法，并用恰当的方法描述算法；
了解枚举法的含义，并能使用枚举法解决相关问题。
【教学难点】
能够设计出解决问题的算法；能够用枚举法解决相关问题。
【教学过程】
第一课时
一、引入
师：叶达报名参加学校软件开发社团时。面试中有一道IQ题：有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个药罐被污染了。每片被污染的药丸比污染前增重1克。只允许称量一次，判断出哪个罐子的药被污染了。（同座位讨论该问题的解决步骤）
生：用自然语言描述问题解决的步骤。
第一步：
第二步：
师：在生活中很多类似的问题，在解决问题过程中都需要有一定方法。这种问题解决的方法实际就是算法。
二、算法及其表示方法
师：算法的定义在2.1节已经学过了，请大家再回顾一下，算法的表示方法有几种。
生：自然语言、流程图、程序。
师：来看下面这个问题的解决。
学校历届校友的海量数据存储在校网络中心服务器中（共10000条，无重复数据），某管理员因为误操作删除了一位校友的ID号（8位整数）信息，恰好在备份数据库中保存了一份所有人员ID号的文件（无重复数据，无序）。怎样快速找出被误删的ID号以便恢复数据？
例如：
网络中心服务器ID列表
备份服务器ID列表
19750001
19760230
19990002
19990003
……
19990003
19750001
19760230
20010432
19990002
……
请同座位讨论，用自然语言描述问题求解的算法。
生：取出网络中心服务器ID列表中第一条数据；和备份服务器中的ID列表逐条进行对比，如果能够找到相同的ID号，则完成目标，否则取出网络中心服务器ID列表中下一条数据继续比对。
师：最差情况下，按照该算法解决问题需要进行多少次比较？
生：10000
10000，1亿次。
师：还有没有其他方法？（提示：可以利用异或运算）
异或应用于逻辑运算，其运算法则为：0^0=0，1^0=1，0^1=1，1^1=0。
由于两个相同数异或结果为0，而任何数异或0的结果等于数据本身。因此，可以把两文件中所有ID号直接进行异或，只出现一次的数据就能被找出，并且最后出现的异或结果就是这个数。
（学生可能会提出将中心服务器的ID号全部加起来，然后减去备份服务器的ID号，得到的数就是被删除的ID号，可以让学生比较它和异或的方法）
请重新思考该问题解决的算法，并用流程图表示出来。（可以用^表示异或）
生：
图1
师：请思考下面的问题。
1.计算备份库ID号异或结果的循环结构和计算中心库ID号异或结果的循环结构能不能交换顺序？
2.如何存放两个数据库中ID号？
生：1.可以交换；2.列表、文件、数据库。
师：已知备份数据库文件存放在“copy.txt”中，中心服务器文件存放在“trouble.txt”中，用程序实现该问题的解决。
提示：文件的一般使用方法
f1=open(r"copy.txt")
#打开文件
list1=f1.readlines()
#读取每行数据，list1是一个记录了问题所有元素的列表
……
f1.close
#关闭文件
生：
target=0
#设置初始值
f1=open(r"copy.txt")
#打开备份文件
list1=f1.readlines()
#读取每行数据
for
line
in
list1:
#依次处理列表list1中的数据
target=
target^int(line)
#将读取的数据做异或运算
f1.close
#关闭备份文件
f2=open(r"trouble.txt")
#打开故障文件
list2=f2.readlines()
#按行读取故障文件
for
line
in
list2:
#依次处理列表list2中的数据
target=
target^int(line)
#将读取的数据做异或运算
f2.close
#关闭备份文件
print("被删除的ID号是:",
target)
#输出被删除的ID号
三、算法的特征
师：思考解决“被删除的ID号”算法中的一些规律，思考算法应该具有哪些特征。填写下表。
现象（可多选）
算法的特征
输入项：
□0个输入
□1个输入
□多个输入
输出项：
□0个输出
□1个输出
□多个输出
执行的结果：□确定的
□不确定的
□都可以
执行的步骤：□有限
□无限
□都可以
执行的时间：□有限
□无限
□都可以
生：注意对输出的理解。
四、总结
算法的特征：0或多个输入项；1或多个输出项；算法的确定性（确定的执行结果或者运算的确定性）；算法的有穷性；算法的可行性。
第二课时
一、复习
师：回顾上一节课的内容，回答算法具有哪些特征？
生：输入项、输出项、确定性、有穷性、可行性等。
师：算法的常见表达方式有哪些？
生：自然语言、流程图、程序。
练习：任选一种方法表达一道IQ题的解决方法：“房间里有三盏灯，房间外有三个开关，在房外看不见房内的情况下，进门一次确定开关与灯的控制关系。”
生：打开1和2号开关片刻；
关闭2号开关；
进入房间。发现亮的灯对应1号开关；暗且热的灯对应2号开关，剩余的灯对应3号开关。
或者：
师：为什么同学们不用程序来表示呢？
生：不方便。
师：算法的表达方式各有特点。如自然语言表述比较贴近自然方式，表述方便；但容易有二义性，流程图表示比较清晰，但绘制起来比较麻烦；程序功能强大，编写有一定难度。三种方式可以根据实际问题进行选择。只要恰当准确即可。除了已经介绍的三种，其实表达方式还有很多，例如拓展知识中介绍的PAD表示方法，有兴趣的同学可以课后阅读。
二、枚举法
师：每一个问题都要从头开始思考，比较困难，有没有一些“公式”可以套用呢？
在程序设计中常见的算法有解析法，例如：求解二元一次方程，输入方程的系数a，b，c，然后利用求根公式求出方程的解。再比如枚举法，利用了计算机运算速度快、精确度高的特点，把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法也称作“枚举”或“穷举”。
例题：叶达班上有好几位志同道合的软件开发爱好者。听说这次面试的冠军就在叶达班的A、B、C、D四位同学中。消息很快传到了班上，当A、B、C、D四人回到班上，叶达迫不及待地问他们中谁得了冠军。四人相对一笑，A说：“不是我。”B说：“是C。”C说：“是D。”D说：“C说的不对。”原来他们想让叶达猜出答案，而且有一人说了假话。叶达很快就知道了答案，大家都想知道他的方法。你能判断到底谁是冠军吗？
生：利用枚举法，逐一假设A、B、C、D是冠军，判断是否正确。
冠军
A说：“不是我。”
B说：“是C。”
C说：“是D。”
D说：“C说的不对。”
A
×
×
×
√
B
√
×
×
√
C
√
√
×
√
D
√
×
√
×
师：下面将这个问题用计算机程序来解决。
提示：我们需要把每个人说的话转化成计算机能够执行的表达式。如A说：“不是我。”可以表示为“i!='A'”，其中i为枚举的冠军选手编号。
解读下面的程序，尤其理解标注横线的语句含义。
champion=['A','B','C','D']
#设置选手列表
for
i
in
champion:
#______________________________
cond=(i!='A')+(i=='C')
+
(i=='D')+(i!='D')
#___________________
if
cond==3:
print("冠军是:",i)
生：1.枚举每一个选手是冠军。
2.判断每个人说的话是否是真的，如果是真的表达式为1。cond等于几，就表示就几个人说的是真话。
三、练习
任选两题完成。
1.□3×6528=3□×8256，在两个□内填入相同的数字使得等式成立。求这个数。
2.找出三位正整数中能被3整除的整数。
3.在一千多年前的《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”。即一个数除以3余2，除以5余3，除以7余2，求这个数。
参考答案：
1.
for
i
in
range(10):
if
((i
10+3)
6528)==((30+i)
8256):
print("结果是：",i)
2.
for
i
in
range(100,1000):
if
i%3==0:
print(i)
3.
i=0
while
(i%3!=2
or
i%5!=3
or
i%7!=2):
i=i+1
print(i)
/

展开更多......

收起↑