算法设计与分析实验.docx
《算法设计与分析实验.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验.docx（9页珍藏版）》请在冰点文库上搜索。
算法设计与分析实验
暨南大学本科实验报告专用纸
课程名称算法设计与分析成绩评定
实验项目名称分治霞略与动态规划指导教师李展
实验项目编号01实验项目类型设计类实验地点南海楼6楼
学生姓名陈奕豪学号2012051351
学院信息科学技术学院系计算机系专业软件工程
实验时间年月曰
一、实验目的:
本实验涉及用分治策略和动态规划算法来求解优化组合问题。
通过上机实验使学员学会程序的录入和调试；通过实验结果的比较，使学员了解两种算法的主要特点。
二、实验内容：
第二章实验题
•问题描述给定线性序集中n个元素和一个整数k,lWkWn,要求找出这n个元
素中第k小的元素•主要思路及步骤
1.把a数组中元素分为5个一组，选每组中位数后分别将他们移向数组头，再用同样的方法选取中位数的中位数x,然后按x把a数组分为两个划分，重复上述过程直至划分中元素个数少于75,返回要求值
•算法描述
TypeSelect（Typea[],intp,intr,intk）
if（「pv75）{
用某个简单排序算法对数组a[p:
r]排序；
returna[p+k・l];
};
for（inti=0;i<=（r-p-4）/5;i++）
将a[p+5*i]至a[p+5巧+4]的第3小元素
与a[p+i]交换位置；
〃找中位数的中位数，r-p-4即上面所说的n-5
Typex=Select（a,p,p+（r-p-4）/5,（r-p+6）/10）;
inti=Partition（a,p,r,x）,
j=i-p+l;
if（k<=j）returnSelect（a,p,i,k）;
elsereturnSelect（a.i+l,r,k-j）;
}
•输入和输出
自行设计数组a的元素的值，要求元素个数不少于80个，并实现以下输岀：
（1）输出数组a中下标范围从p到p+（r-p-4）/5的元素；
（2）输出x的值，判断x是否为数组a中下标范围从p到p+（r-p-4）/5的拟中位数；
（3）输出数组a中下标范圉从p到r的元素，验证其是否为以x为基准元素的划分。
源代码：
：
#include
#include
#include
voidS*i,int*j）{
inta;
a=*i;
*i=*j;*j=a;
}〃交换函数
intPartition（int*a,intp,intr）{
inti=pj=r+l;
intx=a[p];while（true）{
while（a[++i]x）;
if（i>=g）break;
S[i],&a[j]）;
a[p]=a[j];
voidQuickSort（int*a,intp,intr）{if（Pintq=Partition（a,p,r）;QuickSort（a,p,q-l）;
QuickSort（a,q+l,r）;
}〃快速排列
intPartition_S（int*a，intp,intr,intx.int*count）{intij=p,temp,z=O;
for（i=0;i<=r;i++）{
if（a[i]!
=x）z++;else{
temp=a[z];a⑵=a[j];a[j]=temp;j++;
Z++；
（*count）++;
i=pj=r+l;
while（true）{while（a[++i]vx&&ix）;if（i>=j）break;S[i],&aU]）;
}
a[p]=a[j]；
a[j]=x;
returnj;
}〃划分函数
intSelect（int*a,intp,intr,intk）{if（r-p<75）{
QuickSort（a,p,r）;returna[p+k-l];
}
inti,j,t;
for（i=0;i<=（r-p-4）/5;i++）{QuickSort（a,p+5*i,p+5*i+4）;inttemp=a[p+i];a[p+i]=a[p+i*5+2];a[p+i*5+2]=temp;
}
printf（lf数组a下标p到p+（r-p-4）/5的元素”）;
for（i=p;i<=p+（r-p-4）/5;i++）
printf（n%d”,a[i]）;〃输出⑴
intx=Select（a,p,p+（r-p-4）/5,（r-p+6）/10）;printf（n\n拟中位数:
％d\n”,x）;〃输出⑵
intcount=0;
i=Partition_S（a,p,r,x,&count）;printf（M以％（1为基准的划分:
”,x）;for（t=p;t<=r;t++）
printf（n%d”,a[t]）;〃输出（3）printf（"\n\nn）;
j=i-P；
if（k<=j）returnSelect（a,pJ-l,k）;
returna[i];
elseif（count>=l&&jvi&&k<=j+count-l）elsereturnSelect（a,i+count,r,k-j-count）;
intmain（）{
inti,n,j;
inta[80]={1059,1285,50,32,788,651,106,42,67,7,1287,395,412,132,213,398,1750,406,1834,703,210,1102,1210,1092,161,1736,578,965,1037,881,1754,813,268,558,1961,1271,776,146,544,1921,514,1049,636,1275,1415,1294,929,765,472,187,1575,194,1342,1309,1026,1836,502,1412,289,161,137,1943,367,1163,1047,896,132,1375,428,655,94,111,636,103,101&1099,479,465,346,1720};
printf（”输入k的值:
”）;
scanf（”％d”,&n）;
intz=n;
i=Select（a,0,79,n）;
QuickSort（a,0,79）;//排序,方便査看结果for（j=0;j<80;j++）
printf（n%d”,a[j]）;
printf（n\nM）;
printf（”第％d小的数是%d\n”,z,i）;
return0;
实验截图:
■•C:
\Users\Sony\Documents\TencentFiles\836571263\FileRecv\VC6・0green\MyP「ojects\dd仁・lo丄回
第?
小的数是蚀
Pressanykeytocontinue
•实验总结
基本熟悉线性时间选择算法的结构
•问题描述
•分析与解答
要求：
给出最优值的递归关系
•算法描述
•输入和输出
要求：
物品不少于10个，输出最优值数组的全部值和最后的最优解
算法实现：
#include
intm[100][100][100];
intmin（inti,intj）
{
returnii:
j;
}
intmax（intijntj）
{
returni>j?
i:
j;
}
voidKnapsack（int*v,int*w,intc,int*bjntd,intn）
intmin（inti.intj）;
intmax（intijntj）;
inti,j,k;
intjMax=min（w[n]-l,c）;〃可选物品只有n
intkMax=min（b[n]-1,d）;//同上
for（j=0;j<=jMax;j++）
for（k=kMax;k<=d;k++）
m[n][j][k]=O;//可选物品只有n且重量不足for（j=jMax;j<=c;j++）
for（k=0;k<=kMax;k++）
m[n][j][k]=O;//可选物品只有n且体积不足for（j=w[n];j<=c;j++）
for（k=b[n];k<=d;k++）
m[n][j][k]=v[n];//可选物品只有n且能装下
for（i=n-l;i>l;i—）
{
jMax=min（w[i]-l,c）;
kMax=min（b[i]-1,d）;
for（j=0;j<=jMax;j++）
for（k=0;k<=d;k++）
m[i]U][k]=m[i+l]U][k];
for（j=0;j<=c;j++）
for（k=0;k<=kMax;k++）
m[i][j][k]=m[i+l]fj][k];
for（j=w[i];j<=c;j++）
for（k=b[i];kv=d;k++）m[i][j][k]=max（m[i+l]|j][k],m[i+l]|j-w[i]][k-b[i]]+v[i]）;
}
m[l][c][d]=m[2][c][d];
if（c>=w[1]&&d>=b[1]）
m[l][c][d]=max（m[l][c][d],m⑵[c-w[l]][d-b[l]]+v[l]）;
}
voidTraceback（int*w,intc,int*b,intd,intn,int*x）
{
for（inti=l;i{
if（m[i][c][d]==m[i+l][c][d]）
x[i]=0;
else
x[i]=l；
c-=w[i];
d-=b[i];
x[n]=（m[n][c][d]）?
1:
0;
}
intmain（）
{
intn,c,d,i;
printf（H请输入物品个数、背包容量、背包容积:
”）；
scanf（n%d%d%dM,&n,&c,&d）;
intv[100],w[100],b[100],x[100];
printf（HW输入每个物品的价值、重量、体积：
\n”）;
for（i=l;i<=n;i++）
{
scanf（”％d%d%d”,&v[i],&w[i],&b[i]）;
}
Knapsack（v,w,c,b,d,n）;
Traceback（w,c,b,d,n,x）;
printf（H背包屮有以下序列的物品:
\n“）；
for（i=l;iprintf（n%d打）;
printf（n\n总价值为：
%d.\n",m[l][c][d]）;
return0;
升级会员 