Page 52 - 高中 信息技术 必修1 数据与计算

第三章 算法基础

从中转城市B ，B ，…，B 市到B市也有不
k
1
2
同的交通工具，每一种交通工具有不同的班
次，因此从中转城市B ，B ，…，B 市到B市
k
1
2
就有N ，N ，…，N k 种班次。于是从A市经
2
1
B ，B ，…，B 市到B市的交通班车（班机）
k
2
1
数共有：
S=M ×N +M ×N +…+M k ×N k
2
1
1
2
寻找从A市到B市耗时最少的旅行路线问题
就转化为在S种联运班次中找到一种耗时最少的
联运班次。这样就需要遍历每一个班次进行比
较。若用人工方式找出能够中转且等待时间和
行驶时间最少的班次，工作量将极其浩大！ 图3-4 从A市经B 1 ，B 2 ，…，B k 市到
B市的交通情况
假设从A市到B市的中转城市只有B ，B 2
1
市，从A市经B ，B 市到B市的交通情况如表
2
1
3-2和表3-3所示。

表3-2 从A市经B 市到B市的交通情况
1
行驶时间/时 从B 1 市到B市的交通工具
从A市到B 1 市的交通工具 广东教育出版社 发车时间 行驶时间/时
发车时间
9:00 3

飞机 12:00 2.5 飞机 无 无

16:00 2

8:00 12 9:00 1.5

10:00 11 11:00 1.33
火车 火车
12:00 9.6 15:00 1

13:00 9.5 18:00 2

8:00 1.8

9:00 2

汽车 无 无 汽车 13:00 2.2

15:00 2.66

18:00 1.66

44 44

9 ֻ೘ᅣ JOEE