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

| 6页
| 4062人阅读
| 1179人下载
普通

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亿次。page number 0


师:还有没有其他方法?(提示:可以利用异或运算)

异或应用于逻辑运算,其运算法则为:0^0=0,1^0=1,0^1=1,1^1=0。

由于两个相同数异或结果为0,而任何数异或0的结果等于数据本身。因此,可以把两文件中所有ID号直接进行异或,只出现一次的数据就能被找出,并且最后出现的异或结果就是这个数。

(学生可能会提出将中心服务器的ID号全部加起来,然后减去备份服务器的ID号,得到的数就是被删除的ID号,可以让学生比较它和异或的方法)

请重新思考该问题解决的算法,并用流程图表示出来。(可以用^表示异或)

生:

4.1教案流程图.bmp

                                  图1

师:请思考下面的问题。

1.计算备份库ID号异或结果的循环结构和计算中心库ID号异或结果的循环结构能不能交换顺序?page number 1


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题的解决方法:“房间里有三盏灯,房间外有三个开关,page number 2


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。