河北工业大学2016算法与设计实验报告讲解.docx

河北工业大学 算法分析与设计 2016 实验报告 学院: 计算机科学与软件学院 班级: 姓名: 学号: 实验一 【实验学时】 4学时 【实验目的】 1．深刻理解并掌握“分治算法”的设计思想； 2．提高应用“分治算法”设计技能； 3．理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。 【问题描述】 设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次; （3）循环赛一共进行n-1天. 按照分治的策略，可将所有参赛的选手分为两部分，n＝2k个选手的比赛日程表就可以通过为n/2＝2k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时。 【源程序】 #includestdio.h #includemath.h void GameTable(int k, int a[80][80]) { int n=2; int i, j, t, temp; a[1][1]=1; a[1][2]=2; a[2][1]=2; a[2][2]=1; for (t=1; tk; t++) { temp=n; n=n*2; for(i=temp+1; i=n; i++) for(j=1; j=temp; j++) a[i][j]=a[i-temp][j]+temp; for(i=1; i=temp; i++) for(j=temp+1; j=n; j++) a[i][j]=a[i+temp][j-temp]; for(i=temp+1;i=n; i++) for(j=temp+1; j=n; j++) a[i][j]=a[i-temp][j-temp]; } } int main() { int i,j,k; int a[80][80]; printf(请输入k的数值 k=); scanf(%d,k); GameTable(k,a); for(i=1; i=pow(2,k); i++) { for(j=1; j=pow(2,k); j++) printf(%5d,a[i][j]); printf(\n); } return 0; } 【运行结果】 【分析总结】 本次实验思路简单，并且编程实现也不复杂。通过这次试验，我对于分治法的设计思想理解地更加深入。其主要思想就是将一个大问题，分解为一个个的小问题，知道每个小问题很容易求出解为止。最后再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出元问题的解。 实验二 【实验学时】 4学时 【实验目的】 （1）熟练掌握动态规划思想及教材中相关经典算法。 （2）掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编 程，求解0/1背包问题。? 【问题描述】 0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, …, xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。 【源程序】 //本程序的测试用例是课本上的例题 #include stdio.h int x[100], V[100][100]; int max(int a, int b) { return (ab ? a : b); } int KnapSack(int w[], int v[], int n, int C) { int i,j; //初始化第0列 for(i=0; i=n; i++) V[i][0]=0; //初始化第0行 for(j=0; j=C; j++) V[0