贪心算法实验报告
- 格式：doc
- 大小：70.00 KB
- 文档页数：9
贪心算法
实验目的与要求：
（1）掌握贪心算法的基本思想；
（2）能使用贪心算法求解一些相关问题；
实验设备（环境）：VC++6.0
实验内容：
（1）将课本上的多机调度问题用JAVA或者C语言进行编程实现，并分析该算法的时间复杂性。
（2）用贪心算法编程实现汽车加油问题。
题目描述
一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n和k个加油站位置，计算最少加油次数。
输入
输入数据的第一行有2个正整数n和k（n≤4000，k≤1000），表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。
输出
将计算出的最少加油次数输出。如果无法到达目的地，则输出”No Solution!”。
示例输入
7 7
1 2 3 4 5 1 6 6
示例输出
4
（3）用贪心算法编程实现最大整数问题。
题目描述
。
输入
n
N个数
输出
连成的多位数
示例输入
3
13，312，343
示例输出设有n个正整数，将它们连接成一排，组成一个最大的多位整数
34331213
实验步骤、实验结果及分析：
(1) 实验代码：
#include
#define N 20
typedef struct node{
int id ,time;//作业所需时间
}jobnode;
typedef struct Node{
int id ,avail;//id机器编号、avail每次作业的初始时间
}manode;
manode machine[N];
jobnode job[N];
/*找出下一个作业执行机器*/
manode *Find_min(manode a[],int m){
manode *temp=&a[0];
for(int i=1;i
if(a[i].avail avail)
temp=&a[i];
}
return temp;
}
/*对作业时间由大到小进行排序*/
void sort(jobnode t[],int n){
jobnode temp;
for(int i=0;i
for(int j=n-1;j
if (job[j].time >job[j-1].time ){
temp=job[j];
job[j]=job[j-1];
job[j-1]=temp;
}}}}
void main(){
int n,m,temp,i;
manode* ma;
printf("输入作业数目\n");
scanf("%d",&n);
printf("输入相应的作业所需处理的时间：\n");
for(i=0;i
scanf("%d",&job[i].time );
job[i].id =i+1;
}
printf("输入机器数目:\n");
scanf("%d",&m);
for(i=0;i
machine[i].id =i+1;
machine[i].avail =0;
}
putchar('\n');
if(n<=m){
printf("为每个作业分配一台机器，可完成任务！\n");
return;
}
sort(job,n);
for(i=0;i
ma=Find_min(machine,m);
printf("将机器：M%d从%d------>%d的时间段分配给作业：%d\n",ma->id ,ma->avail ,ma->avail +job[i].time ,job[i].id );
ma->avail +=job[i].time ;
}
temp=machine[0].avail ;
for(i=1;i
if(machine[i].avail >temp)
temp=machine[i].avail ;
}
putchar('\n');
printf("该批次作业完成所需时间为：%d\n",temp);
while(1);
}
实验结果截图:
（2）实验代码：加油问题代码
#include
void greedy(int d[],int n,int k){
int num=0;
int i=0;
int s=0;
for(i=0;i
if(d[i]>n){
printf("No Solution\n");
return;
}
}
for(i=0,s=0;i<=k;i++){
if(s
s+=d[i];
else if(s>n){
n=s-d[i];
num++;
}
}
printf("%d\n",num);
}
void main(){
int i,n,k;
int d[1000];
printf("请输入汽车可行驶公里数:");
scanf("%d",&n);
printf("请输入加油站的个数:");
scanf("%d",&k);
for(i=0;i<=k;i++)
scanf("%d",&d[i]);
greedy(d,n,k);
}
实验结果截图:
（3）实验代码：设有n个正整数，将它们连接成一排，组成一个最大的多位整数
#include
int Comparelnt(int a,int b)
{
int a1=a,b1=b,la=10,lb=10;
while(a/la)
{la*=10;
}
while(b/lb)
{
lb*=10;
}
return (a*lb+b)-(b*la+a);
}
int main()
{
int i,j,n;
int data[20],temp;
while(1)
{
scanf("%d",&n);
if(n<=0||n>20) break;
for(i=0;i
{
scanf("%d",&data[i]);
}
for(j=0;j
for(i=0;i
{
if(Comparelnt(data[i],data[i+1])<0)
{
temp=data[i+1];
data[i+1]=data[i];
data[i]=temp;
}
}
for(i=0;i
{
printf("%d",data[i]);
}
printf("\n");
}
return 0;
}
实验结果截图：
实验总结（包括过程总结、心得体会及实验改进意见等）：
指导教师评语：
1、完成所有规定的实验内容，实验步骤正确，结果正确；
2、完成绝大部分规定的实验内容，实验步骤正确，结果正确；
3、完成大部分规定的实验内容，实验步骤正确，结果正确；
4、基本完成规定的实验内容，实验步骤基本正确，所完成的结果基本正确；
5、未能很好地完成规定的实验内容或实验步骤不正确或结果不正确。
6、其它：
评定等级：A（优秀） B（良好） C（中等） D（及格） E（不及格）
成绩评定
教师签字
年 月 日
备注：
注：1、报告内的项目或设置，可根据实际情况加以补充和调整
2、教师批改学生实验报告应在学生提交实验报告10日内
