《【2017年整理】算法分析与设计——实验报告》由会员分享，可在线阅读，更多相关《【2017年整理】算法分析与设计——实验报告（6页珍藏版）》请在金锄头文库上搜索。
1、课程名称： 算法分析与设计 学 号： 08220429 姓 名： 王 洪 朋 专业班级： （非师范）计算机科学与技术 081 学 院： 数理与信息工程学院 指导老师： 宋 炯 数理与信息工程学院实验一 递归与分治策略一、实验目的1、熟练掌握递归与分治策略的思想并应用其解决实际问题。2、利用递归与分治策略的思想解决 Gray 码问题。二、实验要求Gray 码是一个长度为 2n 的序列。序列中无相同元素，每个元素都是长度为 n 位的串，相邻元素恰好只有 1 位相同。用分治策略设计一个算法对任意的 n 构造相应的 Gray 码。三、算法实现#include using namespace std;v
2、oid 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-)cout#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; / 输出最优解的具体合并需
3、要随时改变 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 fij.c) fij.c = fik.c + fxj
4、-k.c + t;fij.d = k;result = f1n.c; k = 1;for(i = 2; i result)result = fin.c;k = i;coutn;coutvi;memcpy(save+1, v+1, n*sizeof(v1);for(i = 1; i using namespace std;#define N 50class MinWmechineint n; /部件个数int m; /供应商个数int COST; /题目中的 Cint cw; /当前的重量int cc; /当前花费int bestw; /当前最小重量int bestxN; int savexN;
5、 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;jwij;coutcij; if(wij=n) if(cw bestw | bestw=-1)bestw=cw; for(int j=0;jn; j+) /把当前搜过的路径记下来savexj=bestxj;re
6、turn;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;int main(void)MinWmechine Y;Y.prinout();return 0;实验运行结果：四、实验总结回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
