算法分析_贪心算法解汽车加油问题_实验报告

格#不够，可自行拉伸。) 1) 确定求解汽车加油问题的贪心选择策略。 2) 给出使用贪心算法求解汽车加油问题的算法，用C++语言描述。 要求:求解汽车加油问题时，不仅要求出所需的最小加油次数(即最优值)，而且还要求出应在哪 些加油站加油(即最优解)。 3) 证明上述算法的正确性。(可选) 需证明:汽车加油问题始终存在以贪心选择开始的最优解，以及汽车加油问题具有最优子结构性质。 贪心算法正确性证明: , 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。根据贪心选择，在该题中，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。 , 最优子结构性质: 当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于(b[1],b[2],……b[n])是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1,则(b[2],b[3],……b[n])是从 a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为(a[2],a[3],……a[n])的最优解，再者，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。 5(实验数据处理方法: ?数据输入 由文件input.txt给出输入数据。第一行有2 个正整数n和k，表示汽车加满油后可行驶 n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第 k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示 目的地。 ?结果输出 将编程计算出的最少加油次数以及应在哪些加油站加油输出到文件output.txt。如果无法到达目的地，则输出”No Solution”。 6(参考文献: 《计算机算法设计与分析,第3版,》 王晓东著 电子工业出版社 《算法设计与实验题解》王晓东著 电子工业出版社 指导老师对实验设计方案的意见: 指导老师签名:吕兰兰 2011年 11 月 10 日 二、实验报告 1、实验目的、设备与材料、实验内容、实验方法步骤见实验设计方案 2、实验现象、数据及结果(请自行填写真实结果) 序号 输入文件(input.txt) 输出文件(output.txt) 7 7 0. 4 1 2 3 4 5 1 6 6 3708 6 1. 0 33 20 83 77 26 59 67 630 37 46 43 94 77 45 98 11 60 15 42 7 69 61 2. 3 54 51 65 50 16 28 60 91 17 44 54 93 52 32 54 41 80 88 54 55 27 58 59 92 73 181 46 54 94 61 51 51 57 73 96 32 45 97 73 44 3. 88 25 14 53 59 79 41 63 100 25 57 35 18 55 61 88 54 40 77 1 53 86 67 59 13 56 96 56 75 45 37 76 99 41 94 3、对实验现象、数据及观察结果的分析与讨论: 对输入数据和相应输出结果按照你所设计的算法进行分析，举1~2个例子即可。要求分析出一个输入的最( 优解。) 例: 输入:7 8 1 3 5 1 5 4 1 6 7 输出:5 4、结论: (包括:使用的算法设计方法是否正确，是否也可以用其他方法解决，算法效率如何, 程序的编译是否通过，程序的输出结果是否正确等) 该实验使用的算法基本正确，程序编译通过。程序结果正确。时间复杂度为O(n)。 5、实验总结 1)、本次实验成败之处及其原因分析: 注:从技术角度来分析实验的成功或失败，分析实验过程中出现了哪些问题，程序出现了什么错误，出现错误的具体原因是什么，以及是如何解决的。 本次实验基本成功。只是最后输出加油的次数的数据覆盖了之前写入output文件中的在第1次在哪个加油站加油的数据。不知道应该在文件打开的语句中修改，使它可以在已经存在的文件中追加数据，而不是覆盖。 2)、本实验的关键环节及改进措施: ?做好本实验需要把握的关键环节: 在greed函数中，判断sum>n后，i的次数要减1。因为在距离大于可行驶的距离之前就应该 之前的加油站加油了。 (如实填写，忌文不对题) ?若重做本实验，为实现预期效果，仪器操作和实验步骤应如何改善: 我认为此贪心算法不需要再改进，够贪心了。 (如实填写，忌文不对题) 3)、对实验的自我评价: 对文件的输入输出的使用还没完全掌握。 (注:自己的体会、感想和收获等) 指导老师评语及得分: 签名: 吕兰兰 2011年 11 月 15 日