算法分析与设计——实验报告.doc

课程名称： 算法分析与设计 学 号： 08220429 姓 名： 王 洪 朋 专业班级： （非师范）计算机科学与技术081 学 院： 数理与信息工程学院 指导老师： 宋 炯 数理与信息工程学院实验一 递归与分治策略一、实验目的1、熟练掌握递归与分治策略的思想并应用其解决实际问题。2、利用递归与分治策略的思想解决Gray码问题。二、实验要求Gray码是一个长度为2n的序列。序列中无相同元素，每个元素都是长度为n 位的串，相邻元素恰好只有1位相同。用分治策略设计一个算法对任意的n构造相应的Gray码。三、算法实现#include using namespace std;void print(int a, int length);void gray(int n, int a, int length);int main(void)int n;coutn;int an;for (int i = 0; i = 0; i-)coutai;coutendl;void gray(int n, int a, int length)if(n = 0)an = 1 - an;print(a, length);elsegray(n - 1, a, length);an = 1 - an;print(a, length);gray(n - 1, a, length);实验运行结果：四、实验总结按照分治策略设计，利用递归方法构造Grey码。长度为n的Grey码字符串，前半部分只要在长度为n-1的Grey码前添0就可；后半部分令第二位为1，后几位为前半部分的逆顺序就可。实验二动态规划一、实验目的1、掌握动态规划的基本思想并应用其解决实际问题。2、利用动态规划的基本思想解决N堆石子合并问题。二、实验要求在一个圆形操场的四周摆放N堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性。三、算法实现#include #include #define N 500#define oo 2000000000#define MIN(a, b) (a)(b)?(a):(b)using namespace std;typedef struct int c, d; Node;int n;int vN; / 每堆石头的个数int saveN; / 输出最优解的具体合并需要随时改变 v 的值，所以为了同时输出最小，最大的合并，在完成一个任务之后需要回溯Node fNN; / fij存储最优解，同时存储合并线索int sumNN; / sumij 表示从第 i 堆起，顺时针数j堆的石子总数/ 递归打印子序列fij的合并过程void Print(int i, int j)int k, x;if(j != 1) Print(i, fij.d);x = (i + fij.d - 1)%n + 1;Print(x, j - fij.d);for(k = 1; k 0)if(i = k | x = k) cout*vk ; / *号表示这次操作合并该堆else coutvk ;coutendl;vi = vi + vx;vx = -vx; / 置为- 类似于删除/ flag = 0求最小得分, flag = 1 求最大得分void Solve(int flag)int i, j, k, x, t, result;for(i = 1; i = n; i+) / 仅含一堆石子的序列不存在合并fi1.c = fi1.d = 0;for(j = 2; j = n; j+) / 顺推含2堆，3堆.n堆石子的各子序列的合并方案for(i = 1; i = n; i+) t = sumij;if(flag = 0) fij.c = oo; / 求最小得分，那么需要初始化为 ooelse fij.c = 0; / 求最大得分，那么需要初始化为 0for(k = 1; k = j-1; k+) x = (i + k - 1)%n + 1;if(flag = 0 & fik.c + fxj-k.c + t fij.c) fij.c = fik.c + fxj-k.c + t;fij.d = k;result = f1n.c; k = 1;for(i = 2; i = n; i+)if(flag = 0 & fin.c result)result = fin.c;k = i;cout(flag = 0 ? 最小 : 最大)得分是 resultendl;cout合并过程如下:endl;Print(k, n);coutsum1nendl;int main()int i, j;cout输入石子堆数：n;cout输入每堆石子数：endl;for(i = 1; i vi;memcpy(save+1, v+1, n*sizeof(v1);for(i = 1; i = n; i+) sumi1 = vi;for(j = 2; j = n; j+)for(i = 1; i = n; i+)sumij = vi + sumi%n+1j-1;Solve(0);memcpy(v+1, save+1, n*sizeof(v1);Solve(1);return 0;实验运行结果：四、实验总结动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。实验三回溯法一、实验目的1、了解回溯法的基本思想。2、运用回溯法解决最小重量机器设计问题。二、实验要求最小重量机器设计问题。设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。三、算法实现#includeusing namespace std;#define N 50class MinWmechineint n; /部件个数int m; /供应商个数int COST; /题目中的Cint cw; /当前的重量int cc; /当前花费int bestw; /当前最小重量int bestxN; int savexN; int wNN;int cNN; public:MinWmechine();void machine_plan(int i);void prinout();MinWmechine:MinWmechine()cw=0; /当前的重量cc=0; /当前花费bestw=-1; /当前最小重量bestxN; savexN; coutn;coutm;coutCOST; for(int j=0;jm;j+) for(int i=0;in;i+) cout请输入第 j+1 个供应商的第 i+1wij; cout请输入第 j+1 个供应商的第 i+1cij; if(wij0 | cij0) cout=n) if(cw bestw | bestw=-1) bestw=cw; for(int j=0;jn; j+) /把当前搜过的路径记下来 savexj=bestxj; return;for(int j=0; jm; j+) /依次递归尝试每个供应商 if(cc+cijCOST) cc+=cij; cw+=wij; bestxi=j; machine_plan(i+1); bestxi=-1; cc-=cij; cw-=wij; void MinWmechine:prinout()int i,j,ccc=0; for(j=0;jm;j+) for(i=0;in;i+) cout第 j+1 供应商的第 i+1 部件重量：wij价格：cijn; for(j=0; jn; j+) bestxj=-1; machine_plan(0);coutn最小重量机器的重量是: bestwendl;for(int k=0; kn; k+) cout 第 k+1 部件来自供应商 savexk+1n; ccc+=cksavexk;coutn该机器的总价钱是: cccendl;coutendl;i