资源简介

第三章 算法基础
从A市到B市耗时最少的旅行路线方案设计报告
—— 以从广州市到长春市为例
一、引言
随着科学技术的快速发展，我国铁路、航空、桥梁建设得到了快速发 展，这给我们的交通出行提供了多种选择，如铁路运输、航空运输、汽车 客运等给我们的出行带了许多的便利。
二、设计目的
(一)项目情景
小张是广州市某中学高三的学生，国庆节到了，小张要去探访在长春 市就读的好友，为了节约成本而且更多地欣赏沿途风光，并且能够一睹北 京市容，小张决定以北京作为中转站，乘高铁前往长春。现请你帮他设计 一个以高铁为交通工具、以北京为中转站的从广州市到长春市耗时最少的 旅行方案。
(二)设计目的
通过对“耗时最少的旅行方案”设计，体验计算机解决问题的过程， 理解和概述算法的概念与特征，学会运用恰当的描述方法和控制结构表示 简单算法，懂得描述程序设计语言产生与发展的过程，了解不同种类程序 设计语言的特点。
三、需求分析
要设计一个以高铁为交通工具，以北京为中转站的从广州市到长春市 耗时最少的旅行方案，首先必须知道广州市到北京市的高铁有哪些班次、
· 1 ·
北京市到长春市的高铁有哪些班次。
然后分析从广州市到长春市高铁的可行旅行方案有哪些？在可行的旅 行方案中，找出从广州市到长春市耗时最少的旅行方案。
四、需要的工具与方法
在设计广州市到长春市耗时最少的旅行方案时，可以编写计算机程序 来解决问题。编写计算机程序解决问题的基本过程是：分析问题、设计算 法、编写程序、程序调试与运行。
算法描述常用的方法有：自然语言描述法、流程图描述法、伪代码描 述法。
算法描述过程中用到的三种基本结构是：顺序结构、分支结构、循环 结构。
本项目中，用到的工具有：Python程序设计语言、思维导图等；用到的 方法有：自然语言描述法，用顺序结构、分支结构、循环结构三种基本结 构描述算法的方法等。
五、设计方案
1．问题分析
本项目要求设计一个以高铁为交通工具，以北京为中转站的从广州市 到长春市耗时最少的旅行方案。首先我们通过网络获取广州市到北京市、 北京市到长春市的高铁班次信息。(本章所展示的高铁班次信息仅为项目 分析提供数据支持，查询时间不同，高铁班次信息或有差异，请以实际查 询为准。)
(1)广州市到北京市的高铁班次信息如图3-1所示。
·2 ·
图 3-1 广州市到北京市的高铁班次信息
(2)北京市到长春市的高铁班次信息如图3-2所示。
图 3-2 北京市到长春市的高铁班次信息
·3 ·
然后，我们将获取的信息经过数据清洗后，形成结构化的数据存储为 Excel文件，广州至北京高铁班次查询结果如图3-3所示。
图 3-3 广州市至北京市高铁班次查询结果图
北京市至长春市高铁班次查询结果如图3-4所示。
图 3-4 北京市至长春市高铁班次查询结果图
2．设计算法
以北京市为中转站从广州市到长春市耗时最少的旅行方案问题，根据 获取的广州市到北京市、北京市到长春市的高铁班次信息，采用以下的方 法找出耗时最少的联运班次方案，算法如下：
·4 ·
分别算出从广州市至北京市各班次所用的时间。
分别算出从北京市到长春市各班次所用的时间。
(2)找到能够从广州市经北京市到达长春市的联运班次，共 k 条
线路。
(3)从 k 条联运班次线路中找出耗时最少的为最佳旅行路线。
3．编写程序
根据所设计的算法，编写程序，程序的核心代码如下。
(
#
导入xlrd 模块
#
以下3行初始化列表
)import xlrd ms=[] ra=[] rb=[] data = xlrd.open_workbook("B1.xls") # Excel文件名 B1.xls table_1 = data.sheet_by_name("Sheet1") # 取出 Excel 文件中的数据表 Sheet1 table_2 = data.sheet_by_name("Sheet2") # 取出 Excel 文件中的数据表 Sheet2 (
#
读
取数据表Sheet1 的每一行记录数据,记为rs1
#
读
取数据表Sheet2 的每一行记录数据,记为rs2
#旅行
方
案耗时最小值初始化
#枚
举
rs
1(即数据表
Sheet
1)中每一行记录
)rs1 = table_1.nrows rs2 = table_2.nrows m= 99 for i in range(1,rs1): t14 = table_1.cell(i,4).value #读取数据表第4列的数据(由广州出发到达北京的时间) t15 = table_1.cell(i,5).value #读取数据表第5列的数据(由广州出发到达北京的时间) if t15=="第二天": t14=t14+24 t12 = t14-table_1.cell(i,2).value #计算由广州出发到达北京所用的时间(到达时间-出发时间) for j in range(1,rs2):
·5 ·
#枚举rs2(即数据表sheet2)中的每一行记录 t22 = table_2.cell(j,2).value #读取从北京出发的时间 if t22>t14 : #如果从北京出发的时间大于到达北京的时间 m1=t12+(t22-t14)+(table_2.cell(j,4).value-t22) #算出到达长春所用的时间 if m>m1: #如果当前值比最小值还小 m=m1 # 则更新最小值 r1=i #记录这时从广州出发到达北京的数据 r2=j #记录从北京出发到达长春的数据 ms.append(m) #将最小值添加到列表中 ra.append(r1) #将取得最小值时从A出发到达中间地的记录添加到列表ra中 rb.append(r2) #将取得最小值时从中间地出发到达B市的记录添加到列表rb中 ms0=min(ms) #取出列表ms中的取最小值 ms1=ms.index(ms0) #找出中间城市编号 print("从广州出发经北京到达长春，最少耗时为：",ms0*24,"小时。 具体行程请查看文件ZHXC.XLS。") #输出结果 data = xlrd.open_workbook("B1"+".xls") #找出取最小值时中间城市对应的数据文件 table_1 = data.sheet_by_name("Sheet1") #找数据文件的数据表Sheet1 table_2 = data.sheet_by_name("Sheet2") #找数据文件的数据表Sheet2
·6 ·
(
import
xlwt
wbk
=
xlwt.Workbook()
sheet
=
wbk.add_sheet("Sheet
1")
)#导入模块 xlwt #创建一个工作簿文件 #创建数据表Sheet1 (
style
=
xlwt.XFStyle() #创建单元格格式对象
for
l
in
range
(5
): #枚举要写出结果的列 l(1--4)
sheet
.
write
(
0
,l, table_1.cell(0,l).value)
#将
数
据文件的数据表Sheet1的表头第l列数据写入数据表Sheet1
if
l in (2,4):
)#对于开始时间和到达时间，指定时间格式 style.num_format_str = "hh:mm" else: #其他单元格不设置格式 style.num_format_str = "" #写入数据时指定格式(最后一个参数) sheet.write(1,l, table_1.cell(ra[ms1],l).value,style) #将最优值时到达对应经过中间城市数据文件的数据表Sheet1的第 #l列数据写入数据表Sheet1 sheet.write(2,l, table_2.cell(rb[ms1],l).value,style) #将最优值时对应从中间城市出发数据文件的数据表Sheet1的第l #列数据写入数据表Sheet1 wbk.save("zjxc.xls") # 将结果保存到数据簿文件zjxc.xls
4．调试运行程序
扫描封底的二维码，打开配套资源中的“项目范例程序.py”，运行程 序，输入数据以图3-3、图3-4的数据为例，可以快速地找出从广州市到长 春市耗时最少的高铁旅行方案，如表3-1所示。
·7 ·
表 3-1 耗时最少的高铁旅行方案
交通工具 出发地 出发时间 到达地 到达时间
高铁 广州 8:25 北京 16:27
高铁 北京 16:37 长春 21:33
在本项目的算法描述中，用到了自然语言描述法，而在程序实现过程 中，程序是由上而下执行，属于顺序结构，在枚举rs1(即数据表Sheet1)中 每一行记录、以及枚举rs2(即数据表Sheet2)中的每一行记录时用到了循 环结构，在判断从北京市出发的时间是否大于到达北京市的时间、以及判 断当前值是否比最小值还小时用到了分支结构。
六、结语
通过参与并完成本项目，我们深刻体会到：
1．设计算法是用计算机解决问题的关键。
算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。 通俗地说，算法就是用计算机求解某一问题的方法，是能被机械地执行的 动作或指令的有穷集合。一个问题能否用计算机来解决，很大程度取决于 能否设计出解决问题的算法。
2．根据具体问题用恰当的描述方法描述算法。
描述算法的常用方法有自然语言描述算法、流程图描述算法和伪代码 描述算法。每一种描述方法各有优点与不足，要根据具体问题选用恰当的 描述方法描述算法。
3．计算机解决问题更高效。
通过本项目问题可以明显体会到用计算机解决问题的优势，当数据量 不多时，我们可以采用人工方法来处理；然而，当数据量较多时，运用计 算机解决问题可以更高效、更便捷。
在开展本项目的过程中，我们进行了自主、协作、探究学习，体验 了计算机解决问题的过程，理解了算法的概念与特征，学会了运用恰当 的描述方法和控制结构表示简单算法，了解了程序设计语言产生与发展的 过程、不同种类程序设计语言的特点，促进了信息技术学科核心素养的达 成，达成了项目学习的目的。
·8 ·

展开更多......

收起↑