算法设计与分析实验.docx
《算法设计与分析实验.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验.docx（11页珍藏版）》请在冰点文库上搜索。
算法设计与分析实验
暨南大学本科实验报告专用纸
课程名称算法设计与分析成绩评定
实验项目名称分治策略与动态规划指导教师李展
实验项目编号01实验项目类型设计类实验地点南海楼6楼
学生姓名陈奕豪学号2012051351
学院信息科学技术学院系计算机系专业软件工程
实验时间年月日
一、实验目的：
本实验涉及用分治策略和动态规划算法来求解优化组合问题。
通过上机实验使学员学会程序的录入和调试；通过实验结果的比较，使学员了解两种算法的主要特点。
二、实验内容：
第二章实验题
必做——算法分析题1:
线性时间选择问题
●问题描述
给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素
●主要思路及步骤
1.把a数组中元素分为5个一组,选每组中位数后分别将他们移向数组头,再用同样的方法选取中位数的中位数x,然后按x把a数组分为两个划分,重复上述过程直至划分中元素个数少于75,返回要求值
●算法描述
TypeSelect（Typea[],intp,intr,intk）
{
if（r-p<75）{
用某个简单排序算法对数组a[p:
r]排序;
returna[p+k-1];
};
for（inti=0;i<=（r-p-4）/5;i++）
将a[p+5*i]至a[p+5*i+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+1;
if（k<=j）returnSelect（a,p,i,k）;
elsereturnSelect（a,i+1,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
voidSwap（int*i,int*j）{
inta;
a=*i;
*i=*j;
*j=a;
}//交换函数
intPartition（int*a,intp,intr）{
inti=p,j=r+1;
intx=a[p];
while（true）{
while（a[++i]while（a[--j]>x）;
if（i>=j）break;
Swap（&a[i],&a[j]）;
}
a[p]=a[j];
a[j]=x;
returnj;
}
voidQuickSort（int*a,intp,intr）{
if（pintq=Partition（a,p,r）;
QuickSort（a,p,q-1）;
QuickSort（a,q+1,r）;
}//快速排列
intPartition_S（int*a,intp,intr,intx,int*count）{
inti,j=p,temp,z=0;
for（i=0;i<=r;i++）{
if（a[i]!
=x）z++;
else{
temp=a[z];
a[z]=a[j];
a[j]=temp;
j++;
z++;
（*count）++;
}
}
i=p,j=r+1;
while（true）{
while（a[++i]while（a[--j]>x）;
if（i>=j）break;
Swap（&a[i],&a[j]）;
}
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-1];
}
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（"数组a下标p到p+（r-p-4）/5的元素"）;
for（i=p;i<=p+（r-p-4）/5;i++）
printf（"%d",a[i]）;//输出
（1）
intx=Select（a,p,p+（r-p-4）/5,（r-p+6）/10）;
printf（"\n拟中位数:
%d\n",x）;//输出
（2）
intcount=0;
i=Partition_S（a,p,r,x,&count）;
printf（"以%d为基准的划分:
",x）;
for（t=p;t<=r;t++）
printf（"%d",a[t]）;//输出（3）
printf（"\n\n"）;
j=i-p;
if（k<=j）returnSelect（a,p,i-1,k）;
elseif（count>=1&&jelsereturnSelect（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,1018,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（"%d",a[j]）;
printf（"\n"）;
printf（"第%d小的数是%d\n",z,i）;
return0;
}
实验截图：
●实验总结
基本熟悉线性时间选择算法的结构
第三章实验题
选做——算法实现题2:
二维0-1背包问题（P793-4）
●问题描述
●分析与解答
要求：
给出最优值的递归关系
●算法描述
●输入和输出
要求：
物品不少于10个，输出最优值数组的全部值和最后的最优解
算法实现：
#include
intm[100][100][100];
intmin（inti,intj）
{
returnii:
j;
}
intmax（inti,intj）
{
returni>j?
i:
j;
}
voidKnapsack（int*v,int*w,intc,int*b,intd,intn）
{
intmin（inti,intj）;
intmax（inti,intj）;
inti,j,k;
intjMax=min（w[n]-1,c）;//可选物品只有n
intkMax=min（b[n]-1,d）;//同上
for（j=0;j<=jMax;j++）
for（k=kMax;k<=d;k++）
m[n][j][k]=0;//可选物品只有n且重量不足
for（j=jMax;j<=c;j++）
for（k=0;k<=kMax;k++）
m[n][j][k]=0;//可选物品只有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-1;i>1;i--）
{
jMax=min（w[i]-1,c）;
kMax=min（b[i]-1,d）;
for（j=0;j<=jMax;j++）
for（k=0;k<=d;k++）
m[i][j][k]=m[i+1][j][k];
for（j=0;j<=c;j++）
for（k=0;k<=kMax;k++）
m[i][j][k]=m[i+1][j][k];
for（j=w[i];j<=c;j++）
for（k=b[i];k<=d;k++）
m[i][j][k]=max（m[i+1][j][k],m[i+1][j-w[i]][k-b[i]]+v[i]）;
}
m[1][c][d]=m[2][c][d];
if（c>=w[1]&&d>=b[1]）
m[1][c][d]=max（m[1][c][d],m[2][c-w[1]][d-b[1]]+v[1]）;
}
voidTraceback（int*w,intc,int*b,intd,intn,int*x）
{
for（inti=1;i{
if（m[i][c][d]==m[i+1][c][d]）
x[i]=0;
else
{
x[i]=1;
c-=w[i];
d-=b[i];
}
}
x[n]=（m[n][c][d]）?
1:
0;
}
intmain（）
{
intn,c,d,i;
printf（"请输入物品个数、背包容量、背包容积:
"）;
scanf（"%d%d%d",&n,&c,&d）;
intv[100],w[100],b[100],x[100];
printf（"请输入每个物品的价值、重量、体积：
\n"）;
for（i=1;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（"背包中有以下序列的物品:
\n"）;
for（i=1;i{
if（x[i]==1）
{
printf（"%d",i）;
}
}
printf（"\n总价值为：
%d.\n",m[1][c][d]）;
return0;
}
：
数据：
升级会员 