算法设计与分析课程设计--用贪心算法解决汽车加油次数最少问题

《算法设计与分析课程设计--用贪心算法解决汽车加油次数最少问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、时光荏苒，岁月如白驹过隙，不经意间，我们即将从多彩的大学毕业，完成一个从大学生到社会人的转变。四年的大学生涯，让我明白了许许多多的科学知识和人生哲理，以及数不尽的感悟和成长。然只有将所学的理论知识付诸于社会的实践，才能检验和实现理论自身的价值，也只有将理论付诸于实践才能使理论得以检验。同样，一个人的价值也是通过实践活动来实现的，也只有通过实践才能锻炼人的品质，彰显人的时代风貌。而毕业实习作为大学的最后一课，也是最后一刻，我倍加珍惜，从而可以较深层次的理解社会，以便为将来能更好的胜任工作打下坚实的基础。算法设计与分析课程设计指

2、导老师：刘锡祥班级：计算机11-1班姓名：刘兵飞学号：21时光荏苒，岁月如白驹过隙，不经意间，我们即将从多彩的大学毕业，完成一个从大学生到社会人的转变。四年的大学生涯，让我明白了许许多多的科学知识和人生哲理，以及数不尽的感悟和成长。然只有将所学的理论知识付诸于社会的实践，才能检验和实现理论自身的价值，也只有将理论付诸于实践才能使理论得以检验。同样，一个人的价值也是通过实践活动来实现的，也只有通过实践才能锻炼人的品质，彰显人的时代风貌。而毕业实习作为大学的最后一课，也是最后一刻，我倍加珍惜，从而可以较深层次的理解社会，以便为将

3、来能更好的胜任工作打下坚实的基础。时光荏苒，岁月如白驹过隙，不经意间，我们即将从多彩的大学毕业，完成一个从大学生到社会人的转变。四年的大学生涯，让我明白了许许多多的科学知识和人生哲理，以及数不尽的感悟和成长。然只有将所学的理论知识付诸于社会的实践，才能检验和实现理论自身的价值，也只有将理论付诸于实践才能使理论得以检验。同样，一个人的价值也是通过实践活动来实现的，也只有通过实践才能锻炼人的品质，彰显人的时代风貌。而毕业实习作为大学的最后一课，也是最后一刻，我倍加珍惜，从而可以较深层次的理解社会，以便为将来能更好的胜任工作打下坚

4、实的基础。实验名称：用贪心算法解决汽车加油次数最少问题。实验目的：（1）使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法；（2）使学生掌握以抽象数据类型为模块的面向对象程序设计方法；（3）使学生提高对实际问题的分析、设计和实现能力；（4）为学生后续课程的学习及课程设计打下坚实实践基础。实验方法：贪心算法实验内容：一、问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，

5、并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。二、问题分析对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3......n1.始点到终点的距离小于Ｎ，则加油次数k=0；2.始点到终点的距离大于N，时光荏苒，岁月如白驹过隙，不经意间，我们即将从多彩的大学毕业，完成一个从大学生到社会人的转变。四年的大学生涯，让我明白了许许多多的科学知识和人生哲理，以及数不尽的感悟和成长。然只有将所学

6、的理论知识付诸于社会的实践，才能检验和实现理论自身的价值，也只有将理论付诸于实践才能使理论得以检验。同样，一个人的价值也是通过实践活动来实现的，也只有通过实践才能锻炼人的品质，彰显人的时代风貌。而毕业实习作为大学的最后一课，也是最后一刻，我倍加珍惜，从而可以较深层次的理解社会，以便为将来能更好的胜任工作打下坚实的基础。时光荏苒，岁月如白驹过隙，不经意间，我们即将从多彩的大学毕业，完成一个从大学生到社会人的转变。四年的大学生涯，让我明白了许许多多的科学知识和人生哲理，以及数不尽的感悟和成长。然只有将所学的理论知识付诸于社会的实

7、践，才能检验和实现理论自身的价值，也只有将理论付诸于实践才能使理论得以检验。同样，一个人的价值也是通过实践活动来实现的，也只有通过实践才能锻炼人的品质，彰显人的时代风貌。而毕业实习作为大学的最后一课，也是最后一刻，我倍加珍惜，从而可以较深层次的理解社会，以便为将来能更好的胜任工作打下坚实的基础。A：加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n；B：加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点；C：加油站间的距离相等，即ａ[i]=a[j]=L

8、0)或k=[n/N]+1(n%N！=0)；D：加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过以下算法求解。三、算法描述1.贪心算法的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心