[修订]算法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
_综合性设计性实验_贪心算法实例编程_实验报告_2011年下期
姓名 王怡娟 学号200908001219 专业 计算机科学与技术 班级2009级02 班 实验课程名称 算法设计与分析 指导教师及职称 吕兰兰 讲师 开课学期 2011 至 2012 学年 上 学期 上课时间 2011年 10 月 20 日
湖南科技学院教务处编印
一、实验设计
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
实验名称:贪心算法实例编程 实验时间:2011-11-08
小组成员:无 小组合作: 是? 否?
1、实验目的:
1) 理解贪心算法的概念
2) 掌握贪心算法的基本要素
3) 掌握设计贪心算法的一般步骤
4) 针对具体问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
，能应用贪心算法设计有效算法
5) 用C++实现算法，并且分析算法的效率
2、实验设备及材料:(注意:请自行填写，按实际情况写，各位同学的实验报告应有所区别)
硬件设备:笔记本
机器配置:内存1G、硬盘320G、512独显
操作系统:winXP
开发工具:VC++6.0
3、实验
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
:
?问题描述
一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应
在哪些加油站停靠加油，使沿途加油次数最少。并说明算法能产生一个最优解。
?编程任务
对于给定的n和k个加油站位置，编程计算最少加油次数。
?样例
例如，现在汽车加满油之后可跑7公里，途中共有7个加油站，各个加油站之间的距离为1公里、2公里、3公里、4公里、5公里、1公里、6公里、6公里。
那么，汽车可在____3 ____4_______6_____7__________________________(哪几个加油站)加油，使沿途加油次数最少，只需加油 4 次。
(注意:此部分为本实验的关键部分，请自行填写，不得雷同～) 4、实验方法步骤及注意事项:
?实验步骤(请参考教材自行总结归纳之后再认真填写)
1.将原问题分解为若干相互独立的子问题。
2.对于每一个子问题求局部的最优解。
3.将各个子问题的解合并为原问题的解。
?解题思路(注意:以下部分仅为提示，请自行填写;若
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
格不够，可自行拉伸。)
由于汽车加油是由起点向终点方向开的,我们最大的问题就是不知道在哪个加油站加油可以使我们到达终点时加油次数最少。
不到万不得已不加油，即除非油不足以开到下一个加油站，才加一次油。每次在局部找到一个最优的解。
每加一次油可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个子问题的最优解合并为原问题的解得到原问题的求解。
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 3,4,6,7， 0. 1 2 3 4 5 1 6 6 4 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 12,24,34， 2. 54 51 65 50 16 28 60 91 17 44 54 93 52 3 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 2,5,7,10,12,16,18,20,22,26,28,32, 3. 88 25 14 53 59 79 41 63 100 25 57 35 34,37,39,42,44,46， 55 61 88 54 40 77 1 53 86 67 59 13 56 18
96 56 75 45 37 76 99 41 94
3、对实验现象、数据及观察结果的分析与讨论:
(对输入数据和相应输出结果按照你所设计的算法进行分析，举1~2个例子即可。要求分析出一个输入的最优解。)
假设加油站个数为7，每个加油站间距离为a[i];i=1，2，3，4，5，6，7，
a[0]=1，a[1]=2，a[2]=3，a[3]=4，a[4]=5，a[5]=1，a[6]=6，a[7]=6
I Sum k
3 0 < 7
3 4 < 7
4 9 > 7 输出i=4;t加1等于2;把i=4赋值给m;
4、结论:
(包括:使用的算法设计方法是否正确，是否也可以用其他方法解决，算法效率如何, 程序的编译是否通过，程序的输出结果是否正确等)在贪心算法中，每次做出的选择仅在当前的状态下做出的最好的选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。不是每个问题用贪心算法都可以一定得到最优解，除非该问题具有贪心选择性质(所求问题的整体最优解可以通过一系列局部最优的选择而得到)和最优子结构性质。
5、实验总结
1)、本次实验成败之处及其原因分析:
注:从技术角度来分析实验的成功或失败，分析实验过程中出现了哪些问题，程序出现了什么错误，出现错
误的具体原因是什么，以及是如何解决的。
开始没有为* b分配空间。解决方法:在main()函数中
加入b=new int[g+1]; 2)、本实验的关键环节及改进措施:
?做好本实验需要把握的关键环节:
(如实填写，忌文不对题)
理解贪心算法是自顶向下的方式以迭代的方式相继做出贪心选择 ?若重做本实验，为实现预期效果，仪器操作和实验步骤应如何改善: (如实填写，忌文不对题)
本次实验没有用输入和输出文件操作
希望下次改进
3)、对实验的自我评价:
(注:自己的体会、感想和收获等)
开始编写代码时没有为*b分配空间，一直无法运行 指导老师评语及得分:
签名: 吕兰兰
2011年 11 月 15 日
源代码:
#include
int tanxin(int *a,int n,int k) {
int sum,i,t,m;
sum=t=m=0;
for(i=m;i<=n;i++)
{
sum+=a[i];
if(sum>k)
{
printf("%d, ",i);
sum=a[i];
t++;
}
}
return t;
}
int main()
{
int g,s,*b;
printf("请输入加油站个数:\n ");
scanf("%d",&g);
printf("请输入加满油后可跑路程:\n ");
scanf("%d",&s);
printf("请输入各加油站的距离:\n ");
b=new int[g+1];
for(int i=0;i<=g;i++)
scanf("%d",&b[i]);
printf("\n%d\n",tanxin(b,g,s));
delete [] b;
}
![[修订]算法分析_综合性设计性实验_贪心算法实例编程_实验报告_2011年下期](https://swf.iask.com/327B68bSL3X.jpg?ssig=bJ7J%2F4p1zE&Expires=1720936515&KID=sina,ishare&range=0-239309)
浙公网安备 33021202002483