河北工业大学算法实验

算法分析与设计

: 班级: 姓名: 学号:

实验报告

计算机科学与软件学院 计131班 张硕 133020 学院

实验一 利用分治算法，编程实现循环赛日程表安排问题

一、实验内容

1．实现《网球循环赛》问题的分治算法，并进行算法时间复杂性分析。 2．对实现的分治算法进行改进；

3．对上述改进后算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。

4. 设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。 二、实验目的

1．深刻理解并掌握“分治算法”的设计思想； 2．提高应用“分治算法”设计技能；

3．理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。 三、程序清单 （1）递归： #include int p[128][128]; void fenpei(int a) {

int b=a/2; if(b>1) {

fenpei(b); for(int i=0;i

for(int j=0;j

p[i+b][j+b]=p[i][j];

}

}

}

for(i=0;i

for(i=0;i

for(int j=0;j

p[i][j+b]=p[i+b][j]; for(int j=0;j

p[i+b][j]=p[i][j]+b;

else { }

p[0][0]=1; p[0][1]=2; p[1][0]=2; p[1][1]=1;

int main() {

int num;

cout<<\请输入参赛队伍数：\cin>>num; fenpei(num); cout<<\ \

for(int i=1;i

cout<

}

}

cout<

for(int j=0;j

cout<

cout<

（2）非递归 #include int p[128][128]; void fenpei(int a) {

p[0][0]=1; p[0][1]=2; p[1][0]=2; p[1][1]=1; int b=2; while(b

for(int i=0;i

for(i=0;i

for(int j=0;j

p[i+b][j+b]=p[i][j];

}

}

{ }

for(i=0;i

for(int j=0;j

p[i][j+b]=p[i+b][j]; for(int j=0;j

p[i+b][j]=p[i][j]+b;

int main() {

int num;

cout<<\请输入参赛队伍数：\cin>>num; fenpei(num); cout<<\ \

for(int i=1;i

cout<

for(int j=0;j

cout<

}

}

cout<

return 0;

四、调试步骤

改正程序，无误后运行程序，输入测试数据，观察输出结果与预期结果，若有误，则继续改正程序，无误后则程序完成。 五、运行结果：

六、分析与思考

在输入数据容量较庞大时，非递归算法要比递归算法速度快，但是递归算法在设计上较简单，方便。

实验二 利用动态规划算法编程求解0-1背包问题

一、实验内容

1．实现《0-1背包问题》问题的动态规划法编程，动态规划原理：动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。并进行算法时间复杂性分析。 2．对算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。

3. 设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。 二、实验目的

（1）熟练掌握动态规划思想及教材中相关经典算法。

（2）掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编程，求

解0/1背包问题。 三、程序清单 #include int V[20][20],x[10]; int max(int a,int b) { }

void bag(int w[],int v[],int n,int C)// {

int i,j;

for(i=0;i<=n;i++)

for(j=0;j<=C;j++) V[i][j]=0; if(a>=b)

return a;

else return b;

for(i=1;i<=n;i++) { }

for(j=C,i=n;i>0;i--) {

if(V[i][j]>V[i-1][j]) {

x[i]=1; j=j-w[i]; for(j=1;j<=C;j++)

if(j

V[i][j]=V[i-1][j];

else

V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);

}

}

} else

x[i]=0;

int main() {

int n,C,sum=0; int w[10],v[10];

cout<<\请输入物品数目：\cin>>n;

cout<<\请输入各物品重量：\for(int i=1;i<=n;i++) { }

cout<<\请输入各物品价值：\for(i=1;i<=n;i++) { }

cout<<\请输入限制重量：\cin>>C; bag(w,v,n,C); for(i=0;i<=n;i++) {

for(int j=0;j<=C;j++) {cout<>v[i]; //C+=v[i]; cin>>w[i]; //x[i]=0;

}

}

cout<<'\\n';

cout<<\所选商品序列为：\for(i=1;i<=n;i++) { }

cout<<\总价值为：\return 0;

cout<

sum+=v[i];

四、调试步骤

修改调试程序直至能正确得出预期结果。 五、运行结果

六、分析与思考

动态规划法的时间复杂度较高，且后续结果是依靠前面结果产生的。

实验三 利用贪心算法编程求解背包问题和 TSP问题

一、实验内容

1.实现背包问题的贪心算法编程，利用背包问题的三种贪心策略，（1）选择价值

最大的物品；（2）选择重量最轻的物品；（3）选择单位重量价值最大的物品。重点应用第三种贪心策略。

2.对算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。 3.设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。 二、实验目的

掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编程，求解背包问题和TSP问题。 三、程序清单 1、0-1背包 #include int y[10]; double x[10];

void tanxin1(int w[],int v[],int n,int C) {//价值最大

int W=0,temp=0,v1[10]; double V=0; for(int i=0;i

for(i=0;i

for(int j=i+1;j

if(v1[j]>v1[i])

{temp=v1[j];v1[j]=v1[i];v1[i]=temp; x[i]=0; y[i]=i; v1[i]=v[i];

}

}

}

temp=y[i];y[i]=y[j];y[j]=temp;}

for(i=0;i

cout<<\价值最大优先法所选商品序列为：\for(i=0;i

cout<<\总价值为\

cout<

{x[y[i]]=1;W+=w[y[i]];V+=v1[i];} else

{x[y[i]]=(double)(C-W)/w[y[i]];V+=v1[i]*x[y[i]];break;}

void tanxin2(int w[],int v[],int n,int C) {

//重量最轻

int W=0,temp=0,v1[10]; double V=0; for(int i=0;i

for(i=0;i

x[i]=0; y[i]=i; v1[i]=v[i];

}

}

for(int j=i+1;j

if(w[y[j]]

{temp=v1[j];v1[j]=v1[i];v1[i]=temp; temp=y[i];y[i]=y[j];y[j]=temp;}

for(i=0;i

for(i=0;i

cout<<\总价值为\

cout<

{x[y[i]]=1;W+=w[y[i]];V+=v1[i];} else

{x[y[i]]=(double)(C-W)/w[y[i]];V+=v1[i]*x[y[i]];break;}

void tanxin3(int w[],int v[],int n,int C) {

//价值/重量比最大 int W=0,temp=0,v1[10]; double V=0; for(int i=0;i

x[i]=0; y[i]=i; v1[i]=v[i];

}

}

for(i=0;i

for(i=0;i

for(i=0;i

cout<<\总价值为\

cout<

{x[y[i]]=1;W+=w[y[i]];V+=v1[i];} else

{x[y[i]]=(double)(C-W)/w[y[i]];V+=v1[i]*x[y[i]];break;} for(int j=i+1;j

//cout<

if(v1[j]/w[y[j]]>v1[i]/w[y[i]]) {temp=v1[i];v1[i]=v1[j];v1[j]=temp; //temp=w[i];w[i]=w[j];w[j]=temp; temp=y[i];y[i]=y[j];y[j]=temp;}

int main() {

int n,C; int w[10],v[10];

}

cout<<\请输入物品数目：\cin>>n;

cout<<\请输入各物品重量：\for(int i=0;i

cout<<\请输入各物品价值：\for(i=0;i

cout<<\请输入限制重量：\cin>>C; for(i=0;i

tanxin1(w,v,n,C);

cout<<\重量最轻优先法所选商品序列为：\tanxin2(w,v,n,C);

cout<<\价值重量比最大优先法所选商品序列为：\tanxin3(w,v,n,C); return 0;

x[i]=0; cin>>v[i]; cin>>w[i];

2、Tsp

#include int t[10][10]; int s[10]; int Tsp(int n)

本文来源：https://www.bwwdw.com/article/7uh2.html