项目范例成果报告 第三章 算法基础 设计从A市到B市耗时最少的旅行路线方案.docxVIP

·1·

第三章算法基础

从A市到B市耗时最少的旅行路线方案设计报告

——以从广州市到长春市为例

一、引言

随着科学技术的快速发展，我国铁路、航空、桥梁建设得到了快速发展，这给我们的交通出行提供了多种选择，如铁路运输、航空运输、汽车客运等给我们的出行带了许多的便利。

二、设计目的

(一)项目情景

小张是广州市某中学高三的学生，国庆节到了，小张要去探访在长春市就读的好友，为了节约成本而且更多地欣赏沿途风光，并且能够一睹北京市容，小张决定以北京作为中转站，乘高铁前往长春。现请你帮他设计一个以高铁为交通工具、以北京为中转站的从广州市到长春市耗时最少的旅行方案。

(二)设计目的

通过对“耗时最少的旅行方案”设计，体验计算机解决问题的过程，理解和概述算法的概念与特征，学会运用恰当的描述方法和控制结构表示简单算法，懂得描述程序设计语言产生与发展的过程，了解不同种类程序设计语言的特点。

三、需求分析

要设计一个以高铁为交通工具，以北京为中转站的从广州市到长春市耗时最少的旅行方案，首先必须知道广州市到北京市的高铁有哪些班次、

·2·

北京市到长春市的高铁有哪些班次。

然后分析从广州市到长春市高铁的可行旅行方案有哪些？在可行的旅行方案中，找出从广州市到长春市耗时最少的旅行方案。

四、需要的工具与方法

在设计广州市到长春市耗时最少的旅行方案时，可以编写计算机程序来解决问题。编写计算机程序解决问题的基本过程是：分析问题、设计算法、编写程序、程序调试与运行。

算法描述常用的方法有：自然语言描述法、流程图描述法、伪代码描述法。

算法描述过程中用到的三种基本结构是：顺序结构、分支结构、循环结构。

本项目中，用到的工具有：Python程序设计语言、思维导图等；用到的方法有：自然语言描述法，用顺序结构、分支结构、循环结构三种基本结构描述算法的方法等。

五、设计方案

1．问题分析

本项目要求设计一个以高铁为交通工具，以北京为中转站的从广州市到长春市耗时最少的旅行方案。首先我们通过网络获取广州市到北京市、北京市到长春市的高铁班次信息。(本章所展示的高铁班次信息仅为项目分析提供数据支持，查询时间不同，高铁班次信息或有差异，请以实际查询为准。)

(1)广州市到北京市的高铁班次信息如图3-1所示。

·3·

图3-1广州市到北京市的高铁班次信息

(2)北京市到长春市的高铁班次信息如图3-2所示。

图3-2北京市到长春市的高铁班次信息

·4·

然后，我们将获取的信息经过数据清洗后，形成结构化的数据存储为Excel文件，广州至北京高铁班次查询结果如图3-3所示。

图3-3广州市至北京市高铁班次查询结果图

北京市至长春市高铁班次查询结果如图3-4所示。

图3-4北京市至长春市高铁班次查询结果图

2．设计算法

以北京市为中转站从广州市到长春市耗时最少的旅行方案问题，根据获取的广州市到北京市、北京市到长春市的高铁班次信息，采用以下的方法找出耗时最少的联运班次方案，算法如下：

·5·

分别算出从广州市至北京市各班次所用的时间。

分别算出从北京市到长春市各班次所用的时间。

(2)找到能够从广州市经北京市到达长春市的联运班次，共k条

线路。

(3)从k条联运班次线路中找出耗时最少的为最佳旅行路线。

3．编写程序

根据所设计的算法，编写程序，程序的核心代码如下。

#导入xlrd模块#以下3行初始化列表

#导入xlrd模块

#以下3行初始化列表

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#读

#读取数据表Sheet1的每一行记录数据,记为rs1#读取数据表Sheet2的每一行记录数据,记为rs2#旅行方案耗时最小值初始化

#枚举rs1(即数据表Sheet1)中每一行记录

rs2=table_2.nrows

m=99

foriinrange(1,rs1):

t14=table_1.cell(i,4).value

#读取数据表第4列的数据(由广州出发到达北京的时间)

t15=table_1.cell(i,5).value

#读取数据表第5列的数据(由广州出发到达北京的时间)ift15==第二天:

t14=t14+24

t12=t14-table_