资源简介

(共24张PPT)
粤教版普通高中教科书
信息技术 必修1
数据与计算
第三章 算法基础
数据在信息社会中具有重要价值，掌握数据处理的基本方法与技能具有重要意义。随着数据的快速增长，掌握利用计算机和算法更高效地分析和解决海量数据问题的方法对人类社会发展具有重要作用。
项目范例
设计从A市到B市耗时最少的旅行路线方案
第三章 算法基础
设计从A市到B市耗时最少的旅行路线方案
当从A市到B市没有直达的交通工具时（不考虑水上交通工具），人们可以利用铁路公司、汽车客运公司和航空公司公布的信息，设计出耗时最少的旅行路线（中转且等待时间和行驶时间最少）。
3.1.1
人工解决问题的过程
如何设计从A市到B市耗时最少(中转且等待时间和行驶时间最少)的旅行路线方案呢？假如我们从铁路公司和汽车客运公司网站得知以下信息：
1、交通工具有汽车、火车和飞机；
2、从A到B没有直达，只能中转。
3、每一种交通工具有不同的班次，从A到转城市B1有M1种班次、到转城市B2有M2种班次、到转城市B3有M3种班次……
4、同样，从中转城市B1，B2，B3·……到B市也有不同的交通工具，每一种交通工具有不同的班次，因此从B1到转城市B有N1种班次、从中转城市B2到转城市B有N2种班次、从中转城市B3到转城市B有N3种班次……
B1
A
B2
B3
…….
B
M1
M2
M3
M……
N1
N2
N3
N……
于是从A市经B1，B2，B3……到B市的交通班车(班机)数共有： S=M1×N1+M2×N2+…+
探究活动一
3.1.1
人工解决问题的过程
我们先简化一下问题：假设从A市到B市的中转城市只有B1、B2市，从A市经B1、B2市的交通情况如表3-2和3-3所示
A
B1
B
M1
M2
N1
N2
B2
探究活动一
从A 到B1 出发时间 到达时间 耗时 从B1 到B 出发时间 到达时间 耗时
飞机 09:00 12:00 3 飞机 无 无 无
12:00 14:30 2.5 16:00 18:00 2 火车 08:00 20:00 12 火车 09:00 10:30 1.5
10:00 20:00 10 11:00 12:18 1.3
12:00 21:36 9.6 15:00 16:00 1
13:00 22:36 9.6 18:00 20:00 2
汽车 无 无 无 汽车 08:00 09:48 1.8
09:00 11:00 2
13:00 15:12 2.2
15:00 17:12 2.2
18:00 19:42 1.7
从A 到B2 出发时间 到达时间 耗时 从B1 到B 出发时间 到达时间 耗时
飞机 09:00 12:00 3 飞机 无 无 无
11:00 14:30 2.5 15:00 18:00 2 火车 08:30 20:00 12 火车 08:00 09:30 1.5
11:20 20:00 10 10:00 11:18 1.3
14:00 21:36 9.6 14:00 15:00 1
16:00 22:36 9.6 19:00 21:00 2
汽车 08:30 21:06 22.6 汽车 08:00 09:48 1.8
11:20 8:20 21 09:00 11:06 2.1
14:00 9:36 19.6 13:00 15:30 2.5
16:00 11.36 19.6 16:00 18:12 2.2
18:00 20 19:00 20:42 1.7
表3-2
表3-3
3.1.1
人工解决问题的过程
学生活动一：各小组结合活动记录表中提供的表3-2和表3-3，找出从A市到B市耗时最少(中转且等待时间和行驶时间最少)的旅行路线
探究活动一
从A 到B1 出发时间 到达时间 耗时 从B1 到B 出发时间 到达时间 耗时
飞机 09:00 12:00 3 飞机 无 无 无
12:00 14:30 2.5 16:00 18:00 2 火车 08:00 20:00 12 火车 09:00 10:30 1.5
10:00 20:00 10 11:00 12:18 1.3
12:00 21:36 9.6 15:00 16:00 1
13:00 22:36 9.6 18:00 20:00 2
汽车 无 无 无 汽车 08:00 09:48 1.8
09:00 11:00 2
13:00 15:12 2.2
15:00 17:12 2.2
18:00 19:42 1.7
从A 到B2 出发时间 到达时间 耗时 从B1 到B 出发时间 到达时间 耗时
飞机 09:00 12:00 3 飞机 无 无 无
11:00 14:30 2.5 15:00 18:00 2 火车 08:30 20:00 12 火车 08:00 09:30 1.5
11:20 20:00 10 10:00 11:18 1.3
14:00 21:36 9.6 14:00 15:00 1
16:00 22:36 9.6 19:00 21:00 2
汽车 08:30 21:06 22.6 汽车 08:00 09:48 1.8
11:20 8:20 21 09:00 11:06 2.1
14:00 9:36 19.6 13:00 15:30 2.5
16:00 11.36 19.6 16:00 18:12 2.2
18:00 20 19:00 20:42 1.7
表3-2
表3-3
3.1.1
人工解决问题的过程
同学们，你们找到了结果了吗？
探究活动一
从A 到B1 出发时间 到达时间 耗时 从B1 到B 出发时间 到达时间 耗时
飞机 09:00 12:00 3 飞机 无 无 无
12:00 14:30 2.5 16:00 18:00 2 火车 08:00 20:00 12 火车 09:00 10:30 1.5
10:00 20:00 10 11:00 12:18 1.3
12:00 21:36 9.6 15:00 16:00 1
13:00 22:36 9.6 18:00 20:00 2
汽车 无 无 无 汽车 08:00 09:48 1.8
09:00 11:00 2
13:00 15:12 2.2
15:00 17:12 2.2
18:00 19:42 1.7
从A 到B2 出发时间 到达时间 耗时 从B1 到B 出发时间 到达时间 耗时
飞机 09:00 12:00 3 飞机 无 无 无
11:00 14:30 2.5 15:00 18:00 2 火车 08:30 20:00 12 火车 08:00 09:30 1.5
11:20 20:00 10 10:00 11:18 1.3
14:00 21:36 9.6 14:00 15:00 1
16:00 22:36 9.6 19:00 21:00 2
汽车 08:30 21:06 22.6 汽车 08:00 09:48 1.8
11:20 8:20 21 09:00 11:06 2.1
14:00 9:36 19.6 13:00 15:30 2.5
16:00 11.36 19.6 16:00 18:12 2.2
18:00 20 19:00 20:42 1.7
表3-2
表3-3
……..
时间短了，找不到！
数据多了，找不到！
数据太杂乱了，找不到！
明确要解决的问题
给出的条件
行驶时间最少
A市到B市，不能直达，只能中转，交通工具只有火车、汽车和飞机三种，中转城市有B1、B2
等待时间最短
目标：耗时最少
采用人工方法来解决问题，首先需要明确所要解决的问题和给出的条件，然后再根据已有的经验和知识确定解决问题的方法(算法），从而解决问题。
分析总结：人工解决问题的过程
A
B1
B
M1
M2
N1
N2
B2
设计从A市到B市耗时最少的旅行路线
解决问题的方法(算法)
分析总结：人工解决问题的过程
穷举法
A
B1
B
M1
M2
N1
N2
B2
能到
(1)找出能够中转的从A市经B1市到达B市的联运班次，并计算所用的时间。
能到且耗时最少
(2)找到能够中转的从A市经B1市到达B市的联运班次中耗时最少的联运班次。
能到
(3)找出能够中转的从A市经B2市到达B市的联运班次，并计算所用的时间。
能到且耗时最少
(4)找到能够中转的从A市经B2市到达B市的联运班次中耗时最少的联运班次。
(2)和（4）中耗时最少
(5)取两条线路中耗时最少的联运班次为最佳旅行路线。
3.1.1
人工解决问题的过程
探究活动一
……..
A
B1
B
M1=7
M2=12
N1=9
N2=9
B2
从A市经B1市到B市的联运班次有7×9=63班；从A市经B2市到B市的联运班次有12×9=108班，合计为S=63+108=171班
从A 到B1 出发时间 到达时间 耗时 从B1 到B 出发时间 到达时间 耗时
飞机 09:00 12:00 3 飞机 无 无 无
12:00 14:30 2.5 16:00 18:00 2 火车 08:00 20:00 12 火车 09:00 10:30 1.5
10:00 20:00 10 11:00 12:18 1.3
12:00 21:36 9.6 15:00 16:00 1
13:00 22:36 9.6 18:00 20:00 2
汽车 无 无 无 汽车 08:00 09:48 1.8
09:00 11:00 2
13:00 15:12 2.2
15:00 17:12 2.2
18:00 19:42 1.7
从A 到B2 出发时间 到达时间 耗时 从B1 到B 出发时间 到达时间 耗时
飞机 09:00 12:00 3 飞机 无 无 无
11:00 14:30 2.5 15:00 18:00 2 火车 08:30 20:00 12 火车 08:00 09:30 1.5
11:20 20:00 10 10:00 11:18 1.3
14:00 21:36 9.6 14:00 15:00 1
16:00 22:36 9.6 19:00 21:00 2
汽车 08:30 21:06 22.6 汽车 08:00 09:48 1.8
11:20 8:20 21 09:00 11:06 2.1
14:00 9:36 19.6 13:00 15:30 2.5
16:00 11.36 19.6 16:00 18:12 2.2
18:00 20 19:00 20:42 1.7
表3-2
表3-3
3.1.1
人工解决问题的过程
同学们，你们找到了结果了吗？
探究活动一
时间短了，找不到！
数据多了，找不到！
数据太杂乱了，找不到！
难
效率低
准确度低
事实上，从A市到B市中转的城市有很多个，且分别有不同的交通工具及班次：
组合班次有S=M1 ×N1+M2 ×N2+…… +Mk ×Nk
在现实生活中，我们经常需要对数据进行统计、分析。当数据量不多时，我们可以采用人工方法来处理；然而，当数据量变多时，人工处理效率很低时我们运用计算机来解决问题将是一种更高效、更便捷的方法，如通过编制计算机程序来解决问题。
A
B2
B3
…….
B
M1
M2
M3
M……
N1
N2
N3
N……
B1
人工解决问题的过程
探究活动一
3.1.1
探究活动二
第三章 算法基础
3.1.2
计算机解决问题的过程
3.1体验计算机解决问题的过程
体验：计算机程序解决从A市到B市耗时最少(中转且等待时间和行驶时间最少)的旅行路线问题
操作步骤：
1、找到老师提供的 “素材\程序3.1.py”
2、右击，选择Edit with IDLE 的 Edit with IDLE 3.8（32-bit）
3、运行程序
4：观察程序运行结果并结合教材数据进行检验
请同学们说说你利用计算机程序解决上述问题的感受：
计算机解决问题的一般过程
问
题
那么计算机是如何解决问题的呢？
分析问题
在从A市到B市耗时最少的旅行路线问题中，在不知道有多少个中转城市和每个城市有多少班车（或飞机）的情况下，我们可以利用大数据挖掘技术中的爬虫程序到铁路网站、各航空公司和汽车客运公司网站获取从A市经中转城市B1，B2，…，Bk市到达B市的交通班次信息，再经过数据清洗后，形成结构化的数据存储为Excel文件。
在利用计算机解决问题之前，我们首先要分析问题的需求情况、已知条件和需要解决的问题。
拓展
网络爬虫
网络爬虫(又被称为网页蜘蛛，网络机器人），是一种按照一定的规则，自动的抓取互联网信息的程序或者脚本。
网络爬虫的基本过程
分析问题
在从A市到B市耗时最少的旅行路线问题中，在不知道有多少个中转城市和每个城市有多少班车（或飞机）的情况下，我们可以利用大数据挖掘技术中的爬虫程序到铁路网站、各航空公司和汽车客运公司网站获取从A市经中转城市B1，B2，…，Bk市到达B市的交通班次信息，再经过数据清洗后，形成结构化的数据存储为Excel文件。
在利用计算机解决问题之前，我们首先要分析问题的需求情况、已知条件和需要解决的问题。
设计算法
问题分析清楚后，需要给出解决问题的详细方法和步骤，这一过程称为设计算法。
（1）分别找出能够中转的从A市经B1，B2，…，Bk市到达B市的联运班次，并计算所用的时间。
（2）分别找到能够中转的从A市经B1，B2，…，Bk市到达B市的联运班次中耗时最少的联运班次，共k条线路。
（3）取k条线路中耗时最少的联运班次为最佳旅行路线。
有了清晰可操作的算法描述，就可以选择t种计算机语言工具来编写程序，实现算法。一般来说，只要算法确定，对计算机程序设计语言的选择没有特别的限定，通常根据问题的特性和编程人员对语言的熟悉程度来选定编写程序。
编写程序
用Python语言编写从A市到B市耗时最少的旅行路线问题的算法的程序
‘’’查询数据表2的行数，取出c*列的时间，选择中转时间大于1小时的，并计算A到B1 +中转时间 + B1 所有总时间 ‘’’
‘’’查询数据表1的行数，取 出c*、e*列的时间，并计算A市到中转地B1 的时间’’’
m= 99
for i in range(1,rs1):
t14 = table_1.cell(i,4).value
t12 = t14-table_1.cell(i,2).value
for j in range(1,rs2):
t22 = table_2.cell(j,2).value
if t22-t14>=1/24 :
m1=t12+(t22-t14)+(table_2.cell(j,4).value-t22)
if m>m1:
m=m1
r1=i
r2=j
调试运行程序
程序编写完成以后，再通过键盘把程序输入计算机中运行，检查程序能否按预想的效果执行，这一过程称为程序的调试运行。
计算机只能识别程序设计语言中所规定的语法规则，如果编写程序时与规则不一致，哪怕是一个标点符号出错，也会因程序出错而中断运行。此时，我们可以根据计算机提示的出错信息修改程序，重新调试运行。
由于Python是解释程序，因此它的调试是在运行过程中逐行进行的。
人工求解与计算机求解问题的方式的异同
探究活动三
第三章 算法基础
讨
论
求解问题的方式 相同点 不同点
人工求解问题
用计算机求解问题
3.1体验计算机解决问题的过程
人工求解与计算机求解问题的方式的异同
探究活动
第三章 算法基础
讨
论
求解问题的方式 相同点 不同点
人工求解问题 分析问题、设计算法、得出结果、验算结果 每次只能对特定的问题进行解答，运算速度慢，不需要借助计算机工具。
用计算机求解问题 编写程序、调试程序、运行速度快，通用性强。
3.1体验计算机解决问题的过程
总结
1、人工解决问题的过程
采用人工方法来解决问题，首先需要明确所要解决的问题和给出的条件，然后再根据已有的经验和知识确定解决问题的方法，从而解决问题。
2、计算机解决问题的过程
当数据量很大，人工处理效率很低时，我们可以借助计算机，通过编写计算机程序解决问题提。编写计算机程序解决问题要经过分析问题、设计算法、编写程序、调试运行程序等若干个步骤。
第三章 算法基础
同学们以4人组成一个小组，
围绕本章项目学习活动的大主题“设计从A市到B市的最优旅行路线方案”，根据自己感兴趣的问题，小组头脑风暴后确定项目选题，以小组为单位，填写《项目学习活动记录表》“项目选题”栏目。
项目选题
教材参考选题
1.设计从A 市到B 市耗时最少的旅行路线方案；
2.设计从A 市到B 市交通费最少的旅行路线方案；
3.设计从A 市到B 市路程最短的旅行路线方案；
4.在不超预算的情况下，设计从A市到B市耗时最少的旅行路线方案；
5.自拟...
调整后的选题
1.鸡兔同笼问题
例如鸡兔同笼，头共46，足共128，鸡兔各几只
2.韩信点兵
原有士兵约1500，死伤四五百，现点兵，3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名，士兵约一千多，具体多少人

展开更多......

收起↑