最便宜航空路线求解.docVIP

学 号： 课 程 设 计 题 目 最便宜航空线路求解 学 院 管理学院 专 业 信息管理与信息系统 班 级 姓 名 指导教师 2014 年 07 月 03 日 课程设计任务书 学生姓名： 专业班级： 信管 指导教师： 工作单位： 管理学院 题 目：最便宜航空线路求解 初始条件： 【问题描述】 飞机是远途旅行必不可少的工具，但是高昂的价格也令人颇费思量，因此人们往往宁愿用时间来换金钱而选择较慢的交通工具。不过，当航班线路变得丰富之后，人们也发现很多时候选择直达航班往往并非最省钱的路径，比如飞往美国选择从韩国转机就比直飞要便宜多了（虽然这样有坠机的危险）。这样一来，当采用曲线行进能达到省钱也省时间的目的时，坐飞机还是可以接受的。 为了能够更好地解决路径的选择问题，我们模拟一下通过合适的算法来选出最优航空线路。参考/上的数据，自选至少10个城市和至少20条航线（不含中转），要求任意两城市间都可达（这并不意味着两个城市之间就一定有直飞航班，比如大陆到台湾），且至少有2条可选飞行路线。预先定义每条航线的最高定价，航线票价每季度都有折扣机会，但并非必须。每条线路每季度的折扣率由随机函数产生，范围是0.20～1.0（小数点后取两位）。 要求完成的主要任务: （包括课程设计工作量及其技术要求、说明书撰写等具体要求） 本程序不考虑机场建设费和燃油附加费，只计算机票价格，将其作为路径上的权值处理，耗费矩阵存储结构自行选择。在真实的情形中，同一线路每天可能有许多航班，也可能每周只有一两趟航班，即便同一天的航班早晚价格也可能有所不同。为简便计，假定每条线路每天只有一趟航班，不考虑航空公司的差别。 时间安排： 序号 设计内容 所用时间 1 问题分析和任务定义 0.5天 2 数据类型和系统设计 0.5天 3 编码实现和静态检查 3天 4 上机准备和上机调试 2天 5 总结和整理设计报告 1天 合 计 7天 指导教师签名： 2014年 06月25日 系主任（或责任教师）签名： 2014年06月25日最便宜航空线路求解 需求分析 1.1 基本要求 （1）所有原始数据一律事先用文本文件保存，读入数据时从文件获取。 （2）航班价格可以用随机函数生成，但建议从网上直接复制真实数据。 （3）可输出所有城市名称以及每一城市所有可直飞到达的城市列表。 （4）可输出任一指定直飞线路（若没有则显示无直飞航班）四个季度的全票和折扣价格。 （5）输入月份、起始城市和目的城市名称，程序能显示出最经济 的中转路线选择方案。 1.2 输入 （1）从文件read.txt中读取不同城市之间（共10个城市）不同航线（共24条航线）的最高价格输入，四个季度有相同的最高价格。 （2）每条线路每季度的折扣率由随机函数产生，范围是0.20～1.00（小数点后取两位），四个季度有不同的折扣。 （3）运行程序时需根据要求从键盘输入相应指令，保证程序的正确运行。 1.3输出 （1）输出所有城市名以及每一城市所有可直飞到达的城市列表（按城市名拼音升序排列）：始发地 可直飞目的地北京 长春 广州 杭州 昆明 上海 首尔 武汉 香港……首尔 北京 上海 台北 香港…… （2）输出指定线路四个季度的折扣和全价：输入：北京-台北输出：无直飞航班输入：北京-广州输出：季度 全票价格 折扣 折后价格（不计小数，四舍五入） 1 1240 6.5 806 2 1192 7.0 834 3 1475 4.6 679 4 1230 8.7 1070 （3）输入月份、起始城市和目的城市名称，输出最佳方案：输入：5 北京-台北输出：最佳线路：北京-香港，1503，香港-台北，791，合计2294输入：7 广州-首尔输出：最佳线路：广州-上海，880，上海-首尔，773，合计1653输入：10 武汉-上海输出：最佳线路：武汉-上海，278，合计278…… 1.4测试数据 文本文件re