河北工业大学2016算法分析与设计实验报告

《河北工业大学2016算法分析与设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、河北工业大学算法分析与设计2016实验报告学院：计算机科学与软件学院班级：姓名：学号：实验一【实验学时】4学时【实验目的】1.深刻理解并掌握“分治算法”的设计思想；2.提高应用“分治算法”设计技能；3.理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法來解决。【问题描述】设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛H

2、程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天.按照分治的策略，可将所有参赛的选手分为两部分，n=2k个选手的比赛H程表就可以通过为n/2=2k-l个选手设计的比赛H程表来决定。递归地执行这种分割，直到只剩下2个选手吋。【源程序】#include#includevoidGameTable(intk,inta[80][80]){intn=2;inti,j,t,temp;a[l][l]=l;a[l][2]:2;a[2][l]=2;a[2][

3、2]=1;for(t=l;t

4、][80];printf("请输入k的数值k=");scanf(〃％d〃，&k);GameTable(k,a);for(i=l;i<=pow(2,k);i++){for(j=l;j<=pow(2,k);j++)printf("%5d",a[i][j]);printfCrT);}return0;}【运行结果】请输入k的数值k=31234567821436587341278564321876556781234658721437856341287654321Pressanykeytocontinue^【分析总结】木次实验思路简单，并且编

5、程实现也不复杂。通过这次试验，我对于分治法的设计思想理解地更加深入。其主要思想就是将一个大M题，分解为一个个的小问题,知道每个小问题很容易求出解为止。最后再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出元问题的解。实验二【实验学时】4学时【实验目的】(1)熟练掌握动态规划思想及教材屮相关经典算法。(2)掌握动态规划算法求解W题的一般特征和步骤；使用动态规划法编程，求解0/1背乜问题。【问题描述】0/1背包问题是给定n个重量为{wl,w2,…，wn}、价值为{vl,v2,…，vn}的物品和一个容量为C的背乜，求这些物品中的

6、一个最有价值的了集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包,或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0吋，表示物品i没有被装入背包,xi=l时，表示物品i被装入背包。0/1背包问题町以看作是决策一个序列(xl,x2,…，xn),对任一•变量xi的决策是决定xi=l还是xi=0。在对xi_l决策后，已确定了(xl，…，xi-1),在决策xi时，问题处于卜列两种状态之一：(1)竹包容量不足以装入物品i，则xi=0,背包不增加价值；(2)背包容量可以装入物品i,则xi=l,背包的价值增加了vi。

7、这两种情况下背包价值的最大者应该是对xi决策后的背包价值。【源程序】//本程序的测试用例是课本上的例题^includeintx[100]，V[100][100];intmax(inta,intb){return(a〉b?a:b);}intKnapSack(intw[]，intv[]，intn,intC){inti,j;//初始化第0列for(i=0;i〈=n;i++)V[i][0]=0;//初始化第0行for(j=0;j<=C;j++)V[O][j]=O;//双重for循环完成填表过程for(i=l;i<=n;i+

8、+)for(j=l;j<=C;j++)if(j