第三章 算法基础 从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 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
