湖南第一师范学院信息科学与工程学院实验报告
课程名称： 算法分析与设计 成绩评定： 实验项目名称： 实验三：贪心算法程序设计 指导教师： 岳珂娟
学生姓名： 李召英 学号：13403090109 专业班级： 13计科班 实验项目类型：设计性 实验地点： 实202 实验时间： 2016 年 5 月 6 日 一、实验目的与要求
1．理解贪心算法的基本要素。
2．掌握利用贪心算法求解问题的基本步骤和设计方法。
3．针对特定问题，可以设计出高效的贪心算法进行求解，并能够上机编程实现，运行程序并得到正确的结果。
二、实验环境
1. 微机一台 2. Windows XP 3. Visual c++ 6.0
三、实验内容
任务1．最优装载问题
已知有n个集装箱，其中第i个集装箱的重量为wi，轮船的载重量是C。求在装载体积不受限制的情况下，如何将尽可能多的集装箱装上轮船。用贪心法求解这个问题，要求如下：
（1）输入：要求可以由用户输入集装箱的个数n和重量wi，以及轮船的载重量C。 （2）输出：可以装载上船的集装箱的编号。 （3）分析程序的时间复杂度。
测试数据（也可由用户选择其他的测试数据）：
（1）集装箱的个数为4，重量w={20，10，26，15}，轮船的载重量为70；
（2）集装箱的个数为10，重量w={1，2，3，4，5，6，1，2，34，5}，轮船的载重量为15； 任务2．汽车加油问题
一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，指出应在那些加油站停靠加油。用贪心法求解这个问题，要求如下：
（1）输入：可以由用户给出N，给出加油站的个数，并以数组的形式给出加油站之间的距离。指出若要使沿途的加油次数
（2）输出：应在那些加油站停靠加油。 （3）分析程序的时间复杂度。
测试数据（也可由用户选择其他的测试数据）：
（1）各个加油站之间的距离为:1,2,3,4,5,1,6,6.汽车加满油以后行驶的最大距离为7。
四、源代码与运行结果（基本思路和算法、源代码、运行结果） 任务一：
#include
void sort(int *a,int l,int h) { int i=l,j=h,k=a[l]; if(l>=h)
return; while(i int main() { int w[50],C,n,i,count,sum=0; FILE *fp=fopen(\ if(fp==NULL) return 0; while(fscanf(fp,\ { i=1; printf(\ while(i<=n) fscanf(fp,\ sort(w,1,n); for(i=1;i<=n;i++) printf(\ printf(\ count=sum=0; for(i=1;i<=n;i++) { sum+=w[i]; if(sum>C) break; count++; } printf(\总共装了%d个货物\\n\ } fclose(fp); return 0; } 任务二： #include while(fscanf(fp,\ { i=0; while(i<=n) fscanf(fp,\ sum=a[0]; i=1; while(i<=n) { sum+=a[i]; if(sum>d) { x[i]=1; sum=a[i]; } else x[i]=0; i++; } printf(\停下来加油的站有：\\n\ for(int i=1;i<=n;i++) if(x[i]) printf(\ printf(\ } fclose(fp); return 0; } 五、思考与体会