湖南第一师范学院信息科学与工程学院实验报告

课程名称： 算法分析与设计 成绩评定： 实验项目名称： 实验三：贪心算法程序设计 指导教师： 岳珂娟

学生姓名： 李召英 学号：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=a[i]&&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 int main() { int a[20],d,x[20],n,i,sum; FILE *fp=fopen(\ if(fp==NULL) return 0;

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;

}

五、思考与体会