lab5贪心算法设计与应用Word文档下载推荐.docx
- 文档编号:4683058
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:10
- 大小:53.50KB
lab5贪心算法设计与应用Word文档下载推荐.docx
《lab5贪心算法设计与应用Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《lab5贪心算法设计与应用Word文档下载推荐.docx(10页珍藏版)》请在冰点文库上搜索。
三.实验目的和要求
理解贪心算法的基本原理,掌握贪心算法设计的基本方法及其应用;
四.实验内容
(一)加油问题(ProblemSet1702):
1.问题描述
一个旅行家想驾驶汽车从城市A到城市B(设出发时油箱是空的)。
给定两个城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。
设d[1]=0<
d[2]<
…<
d[n]。
要花最少的油费从城市A到城市B,在每个加油站应加多少油,最少花费为多少?
2.具体要求
Input
输入的第一行是一个正整数k,表示测试例个数。
接下来几行是k个测试例的数据,每个测试例的数据由三行组成,其中第一行含4个正整数,依次为A和B两个城市之间的距离d1、汽车油箱的容量c(以升为单位)、每升汽油能行驶的距离d2、沿途油站数n(1<
=n<
=200);
第二行含n个实数d1,d2,…,dn,表示各油站离出发点的距离(d1=0);
第三行含n个实数p1,p2,…,pn,表示各油站每升汽油的价格。
同一行的数之间用一个空格隔开。
Output
对于每个测试例输出一行,含一个实数,表示从城市A到城市B所要花费的最少油费(输出的结果精确到小数点后一位)。
若问题无解,则输出“NoSolution”。
3.代码如下:
#include<
stdio.h>
#defineMAX20
voidlook(floatdis[],floatpir[],intn,intd2,intoil)//dis距离起点距离,pir油价
{
inti,j,k;
floatpirce=0.0,c1=0,x,c2;
for(j=0;
j<
=n;
j++)
{
for(i=j+1;
i<
i++)
{
if(pir[i]<
pir[j])
{
k=i;
c2=(dis[k]-dis[j])/d2;
if(c2>
=oil)
{
x=oil-c1;
}
else
x=c2-c1;
if(x<
0)
{
x=0;
}
pirce=pirce+pir[j]*x;
break;
}
}
c1=c1+x-((dis[j+1]-dis[j])/d2);
}
printf("
%.1f"
pirce);
}
voidmain()
intk,i,j,n[MAX],c[MAX],d1[MAX],d2[MAX],length[MAX],flag[MAX];
floatA[MAX][MAX],B[MAX][MAX];
输入测试例个数:
\n"
);
scanf("
%d"
&
k);
for(i=0;
k;
printf("
输入第%d个数据:
i+1);
flag[i]=0;
scanf("
%d%d%d%d"
d1[i],&
c[i],&
d2[i],&
n[i]);
length[i]=c[i]*d2[i];
for(j=0;
n[i];
scanf("
%f"
A[i][j]);
A[i][n[i]]=d1[i]*1.0;
B[i][j]);
B[i][n[i]]=0.0;
for(j=n[i];
j>
0;
j--)
if(A[i][j]-A[i][j-1]>
length[i])
flag[i]=1;
if(flag[i]==1)
printf("
第%d次结果:
"
NOsolution!
else
最少油费:
look(A[i],B[i],n[i],d2[i],c[i]);
(二)黑白点的匹配(ProblemSet1714):
设平面上分布着n个白点和n个黑点,每个点用一对坐标(x,y)表示。
一个黑点b=(xb,yb)支配一个白点w=(xw,yw)当且仅当xb>
=xw和yb>
=yw。
若黑点b支配白点w,则黑点b和白点w可匹配(可形成一个匹配对)。
在一个黑点最多只能与一个白点匹配,一个白点最多只能与一个黑点匹配的前提下,求n个白点和n个黑点的最大匹配对数。
接下来几行是k个测试例的数据,每个测试例的数据由三行组成,其中第一行含1个正整数n(n<
16);
第二行含2n个实数xb1,yb1,xb2,yb2,…,xbn,ybn,(xbi,ybi),i=1,2,…,n表示n个黑点的坐标;
第三行含2n个实数xw1,yw1,xw2,yw2,…,xwn,ywn,(xwi,ywi),i=1,2,…,n表示n个白点的坐标。
同一行的实数之间用一个空格隔开。
对于每个测试例输出一行,含一个整数,表示n个白点和n个黑点的最大匹配对数。
#include"
iostream.h"
math.h"
structpoint
doublex,y;
};
voidsort(point*a,intn)
inti,j;
pointp;
for(i=1;
for(j=i+1;
n;
if(a[i].x>
a[j].x||(a[i].x==a[j].x&
&
(a[i].y>
a[j].y)))
p=a[i];
a[i]=a[j];
a[j]=p;
doubledis(pointpointw,pointpointb)
doubledist;
dist=sqrt(pow((pointb.x-pointw.x),2)+pow((pointb.y-pointw.y),2));
returndist;
intmain()
inti,j,n,k;
cin>
>
point*pointw=newpoint[n];
point*pointb=newpoint[n];
int*b=newint[n];
cin>
pointb[i].x;
pointb[i].y;
pointw[i].x;
pointw[i].y;
sort(pointw,n);
b[i]=1;
intcount=0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- lab5 贪心 算法 设计 应用