教科版 高一信息技术 必修1 第四单元 4.1 算法及特征 教学设计

【学习目标】

1.通过解决开关问题，能够分析出算法的基本特征，感受算法在解决问题中的重要性。

2.通过解决药丸问题，尝试运用恰当的方法描述算法。

3.能够将部分简单算法转换为程序，并调试运行得出结果。

4.通过解决冠军问题，了解枚举法的含义，并能使用枚举法解决相关问题。

【教学重点】

能够分析问题，设计解决问题的算法，并用恰当的方法描述算法；

了解枚举法的含义，并能使用枚举法解决相关问题。

【教学难点】

能够设计出解决问题的算法；能够用枚举法解决相关问题。

【教学过程】

第一课时

一、引入

师：叶达报名参加学校软件开发社团时。面试中有一道IQ题：有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个药罐被污染了。每片被污染的药丸比污染前增重1克。只允许称量一次，判断出哪个罐子的药被污染了。（同座位讨论该问题的解决步骤）

生：用自然语言描述问题解决的步骤。

第一步：

第二步：

师：在生活中很多类似的问题，在解决问题过程中都需要有一定方法。这种问题解决的方法实际就是算法。

二、算法及其表示方法

师：算法的定义在2.1节已经学过了，请大家再回顾一下，算法的表示方法有几种。

生：自然语言、流程图、程序。

师：来看下面这个问题的解决。

学校历届校友的海量数据存储在校网络中心服务器中（共10000条，无重复数据），某管理员因为误操作删除了一位校友的ID号（8位整数）信息，恰好在备份数据库中保存了一份所有人员ID号的文件（无重复数据，无序）。怎样快速找出被误删的ID号以便恢复数据？

例如：

生：取出网络中心服务器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或多个输出项；算法的确定性（确定的执行结果或者运算的确定性）；算法的有穷性；算法的可行性。

第二课时

一、复习

师：回顾上一节课的内容，回答算法具有哪些特征？

生：输入项、输出项、确定性、有穷性、可行性等。

师：算法的常见表达方式有哪些？

生：自然语言、流程图、程序。

练习：任选一种方法表达一道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说：“不是我。”可以表示为“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)