算法设计实验报告

华北电力大学实验报告|实验名称算法设计与分析综合实验课程名称算法设计与分析|专业班级：学生姓名：学 号：成 绩：指导教师：实验日期：综合实验一 分治策略归并排序一、实验目的及要求归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。 实验要求：(1) 编写一个模板函数：template vtypename T, MergeSort(T *a, int n);以及相应的 一系列函数，采用分治策略，对任意具有:bool operatorv(const T&x,const T&y);比较运算符 的类型进行排序。(2) 与STL库中的函数std:sort(.)进行运行时间上的比较，给出比较结果如：动态 生成 100 万个随机生成的附点数序列的排序列问题, 给出所用的时间比较。二、所用仪器、设备计算机、Visual C+软件。三、实验原理分治原理：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些 子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。当我们 求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接 求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解 成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求 整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子 问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。归并原理：归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Con quer )的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列； 即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称 为二路归并。四、实验方法与步骤归并过程为：比较ai和 aj的大小，若aiaj，则将第一个有序表中的元素ai复 制到rk中，并令i和k分别加上1；否则将第二个有序表中的元素aj复制到rk中，并 令j和k分别加上1,如此循环下去，直到其中一个有序表取完，然后再将另一个有序表 中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实 现，先把待排序区间s,t以中点二分，接着把左边子区间排序，再把右边子区间排序，最 后把左区间和右区间用一次归并操作合并成有序的区间s,t。实现时间计量：#define _CLOCK_T_DEFINEDsrand(unsigned)time(0);定义一数组an;对每一个赋予一值。ai=ra nd();得到随即数。duration =(double)(finish -start)/CLOCKS_PER_SEC;start=clock();将系统时间赋予Start。以便以后进行比较。std:sort(b,b+1000);系统执行 1000 个数据。Finish-Start 为最终结果。五、实验结果与数据处理实验结果截图：0. iLil!77.57073178.21 rS42.039812.2311535.3125T& 517381 . 119325 822467 12S253.127234.530062 132255109.4775.2633321 047703 329859.521 1&. 1 128G7.H17455 419788 72Z83S . ?2&283.72 7654.6S23.&911SG.&1斗424.751E5 383299.598417.9710461 510542.312090.911S713&5&. 1143Z8.317730.91T828 32Q025.72009G1l&q.371421.771S97.38 ZZT& &G743 66944.77889S.43345 211G&35.G1 1097.ti12511 .65533 928883.310533.73533 1281S.5810441 812087 12090.9 11S7 12255.1123&7.313QG3 713&5&.1143Z8.314SG5.T17754.517730.91T828 318454.2198742Q025.72009G2Q43G.S 2G490.G23766 52453324640.924?fi6.224839.22&G30.32672$.22&74G.32&7SS. 1ZS3GS.斗 2S3S9 T ZS439.9237583046630302 232511.732719515283.216031.118729.119QE0.2221Q3.12491G.82672$.22&74G.32&7SS.12&SG5.G26991.92S3S9 T ZS439.9237582889S29397 131304 531465.43169 331747.932202 9-M 22G17e+037std : :/ : Qms輸入需墓显示的排序方法:1 H Ji l-k.T 2.=td-krf0Pres& any key to eoritinue实验代码：#include #include #include#include #include using namespace std; templateclass Type void MergSort(Type a, int n)Type *b = new Type n;int s = 1; while (s n) MergPass(a, b, s, n); s += s; MergPass(b, a, s, n); s += s;templatevoid MergPass(Type x, Type y, int s, int n) int i = 0;while (i = n - 2 * s)Merg(x, y, i, i + s - 1, i + 2 * s - 1);i = i + 2 * s;if (i + s n)Merg(x, y, i, i + s - 1, n - 1);elsefor (int j = i; j = n - 1; j+) yj = xj;templatevoid Merg(Type c, Type d, int l, int m, int r)int i = l, j = m + 1, k = l;while (i = m) & (j = r) if (ci m)for (int q = j; q = r; q+) dk+ = cq;elsefor (int q = i; q = m; q+) dk+ = cq;float randf(float base, float up)return (rand() % (int)(up - base) * RAND_MAX)/(float)RAND_MAX ; /产生随机数 void printArray(float *a,int N)for(int i=0;i0) coutaiendl;else coutai ;void main()int ArrayLen = 5;cout请输入元素个数：ArrayLen;float *array = new floatArrayLen;float *arrays = new floatArrayLen;float mn, ene;printf(数组已建立：n);srand(unsigned)time(NULL); /设置随机数的 seedfor (int i = 0; i ArrayLen; i+)mn = (float)rand(); /产生小数ene = randf(1,10000)+mn;arraysi =ene; arrayi = ene;/cout需要排序的归并数组:n;/printArray(array, ArrayLen);int flag = 1;while (flag != 0)coutn 输入需要显示的排序方法： endl; cout 1.归并排序 2.std排序0.退出 flag;switch (flag)case 0:break;case 1:clock_t s = 0, e = 0;s = clock();MergSort(array, ArrayLen);e = clock();cout排序后的序列为：endl;/printArray(array, ArrayLen);cout nMergSort 运行了 ： (e - s) ms endl; break;case 2:clock_t start1 = 0, end1 = 0;start1 = clock();std:sort(&arrays0, &arraysArrayLen);end1 = clock();/printArray(array, ArrayLen);cout nstd:sort 运行了： (end1 - start1) ms sFileName = sFileName1;ifstream fin(sFileName);char ch4;fin.getline(ch, 4);int n1 = atoi(ch);cout 节点数目:n1 n = n1;this-t = new THaffmanNode2 * n1 - 1;this-nNext = n1;char ch1;for (int i = 0; in1; i+)fin.get(ch1);ti.c = ch1;fin.ignore(100, ,);fin.getline(ch, 4);ti.f = atoi(ch);for (int i = 0; in; i+)cout ti.c ti.f endl;for (int i = 0; i= 2)THaffmanNode nn, nr, nl;nl = PQ.top();PQ.pop();nr = PQ.top();PQ.pop();nn.f = nl.f + nr.f;nn.l = nl.idx;nn.r = nr.idx;nn.idx = nNext+;tnl.idx.p = nn.idx; tnr.idx.p = nn.idx; tnn.idx = nn; PQ.push(nn);elset2 * n - 2.p = -1;break;Huffman:Huffman(void)void Huffman:OutputTree()for (int i = 0; i2 * n - 1; i+)cout 权重： ti.f ;cout 左孩子： ti.l ;cout 右孩子： ti.r ;cout 父节点： ti.p ;cout 在数组的位置： ti.idx endl; /现在数组中存的是哈弗曼数void Huffman:OutputCode()/用 stack 来依次记录各编码的 0 1 编码std:stackint, std:list sk;THaffma nN ode n temp, n tempi; for (int i = 0; ivn; i+)n temp = ti;while (n temp.p != -1)n temp1 = tn temp.p;if (tn temp1.1 .idx = n temp.idx) sk.push(O);n temp = n temp1; else sk.push(1); n temp = n temp1;int i1 = sk.size();cout ti.f :;for (int i = 0; ii1; i+) cout sk.top(); sk.pop();cout #in cludeclass Quee nfrie nd int n Quee n(i nt);private:bool Place(int k);void Backtrack(i nt t);int n,*x;当前解long sum;当前已找到的可行方案数;bool Quee n:Place(i nt k)for (int j=1;jvk;j+)if (abs(k-j)=abs(xj-xk)|(xj=xk) return false; return true;void Queen:Backtrack(int t)if (tn)sum+;达到叶结点for(int i=1;i=n;i+) coutxi ; coutendl;for(i=1;i=n;+i)for(int j=1;j=n;+j) if(xi!=j) cout. ;else cout#; coutendl; coutendl;elsefor (int i=1;i=n;i+) /搜索子结点xt=i;/进入第 i 个子结点if (Place(t) Backtrack(t+1);int nQueen(int n)Queen X;初始化XX.n=n;X.sum=0;int *p=new int n+1;for(int i=0;i=n;i+)pi=0;X.x=p;X.Backtrack(1);/对整个解空间回溯搜索delete p;return X.sum;void main()int a=0,b=0;coutII*欢迎进入皇后问题*e ndl;int flag=1; while(flag) coutv 请输入皇后数a;b=nQueen(a);coutvv方案个数：vvbvvendl;coutvv是否继续？ 1为是,0为否flag;综合实验四背包问题的贪心算法一、实验目的及要求问题:给定如下n种物品的编号，及其价值；背包重量为c,求最佳装包方案，才能使其装入背包的价值最大。物品编号12n重量w1w2w n价值v1v2vn具体要求：将背包问题进行类的封装；能对任意给定的 n 种物品的重量、价值及背包限重，输出以上表格（ 或纵向输出）； 输出背包问题的解；本题要求采用 STL 库中的排序算法数据进行排序。二、所用仪器、设备计算机、Visual C+软件。三、实验原理贪心算法解决背包问题有几种策略：（1）一种贪心准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利 用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的 物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=100,10,10, p = 20,15,15, c = 105。当利用价值贪婪准则时，获得的解为x= 1,0,0 ,这种方案的总价 值为 2 0。而最优解为 0 , 1 , 1 ，其总价值为 3 0。（2）另一种方案是重量贪心准则是：从剩下的物品中选择可装入背包的重量最小的 物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最 优解。考虑n= 2 ,w=10,20, p=5,100, c= 2 5。当利用重量贪婪策略时，获得的解为x =1,0,比最优解 0 , 1 要差。（3）还有一种贪心准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该 项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次 类推，尽可能的多放，直到装满背包。四、实验方法与步骤首先计算每种物品单位重量的价值Vi/Wi，然后依贪心选择策略，将尽可能多的单 位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量 未超出C,则选择单位重量价值次高的物品，并尽可能多的装入背包。依此策略一直进 行下去，直到背包装满为止。采用贪婪准则：每次选择p/w最大的物品放入背包。注意在这之前的计算每种物品单位重量的价值Vi/Wi后，进行排序。五、实验结果与数据处理实验截图:1 D:Pragram Fi IesVC + + 6.0MSDev98Bi n.请输入物品的重屋利价值：口囂競;精聽I菁瓣罷请输入第3亍物品的蚕量和价值3请输入第斗个物品的重量和价值斗斗54.59.9清输入背包容积；7.堤审物晶的编寻和重量:分另L为:1.00 2.002.003.0G4.002.0Q： 12.3OPress anyto continue複狗拼音输入法全：主要代码如下:#include #define M 4struct nodefloat no;/编号float value;float weight;float wweight;/若 是最后一个的用量int flag;NodeM,temp;float Value,curvalue=0;float Weight,curweight=0;/按性价比排序void sort()int i,j;for(i=0;iM-1;i+)for(j=i+1;jM;j+)if(Nodei.value/(float)Nodei.weight)Nodej.value/(float)Nodej.weight)temp=Nodei;Nodei=Nodej;第页共页Nodej=temp;/可切割装载方法void load2()int i;for(i=0;iM;i+)if(Nodei.weight+curweight)Weight&(curweightWeight) float t=Weight-curweight;curvalue+=(Nodei.value)/(Nodei.weight)*t; curweight=Weight;Nodei.flag=2;Nodei.wweight=t;elseNodei.flag=0;/进行结果的输出void putout()int i;printf(选中物品的编号和重量分别为：“)；printf(nr);for(i=0；iM；i+)if(Nodei.flag=1)printf(%.2f,Nodei.no)；printf( )；printf(%.2f,Nodei.weight)；printf(nr)；else if(Nodei.flag=2)printf(%.2f,Nodei.no)；printf( )；printf(%.2f,Nodei.wweight)；printf(nr)；printf（n 总价值为:.2f,curvalue）;int main()int i;static int p;printf(请输入物品的重量和价值：n);for(i=0;iM;i+)printfC请输入第4个物品的重量和价值,i+1);scanf(%f%f%f,&Nodei.no,&Nodei.weight,&Nodei.value);printf(n 请输入背包容积：);scanf(%f,&Weight);sort();load2();putout();return 0;综合实验六 (选做) 0-1背包问题的求解一、实验内容：0-1 背包问题有多种解法，如动态规划方法，回溯方法，分枝限界方法等。对于同一 种问题，请参照教材中的算法，给出相应的程序实现。注: 0/1背包问题：给定n种物品和一个容量为C的背包，物品i的重量是叫，其价 值为vi,背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最 大。其中，每种物品只有全部装入背包或不装入背包两种选择。二、所用算法的基本思想及复杂度分析：1.动态规划法求解 0/1背包问题：1 )基本思想：令V(i，j)表示在前i(1 J n)个物品中能够装入容量为j(1 J j J C)的背包中的物品的最大值，则可以得到如下动态函数：V (i,0)二 V (0, j)二 0V )_|V(i -1, j)(j w )i ii按照下述方法来划分阶段：第一阶段，只装入前 1 个物品，确定在各种情况下的背 包能够得到的最大价值；第二阶段，只装入前 2 个物品，确定在各种情况下的背包能够 得到的最大价值；以此类推，直到第n个阶段。最后，V仇C)便是在容量为C的背包中第 页共 页装入n个物品时取得的最大价值。2) 代码：#include #includeusing namespace std;#define N 100/最多可能物体数struct goods /物品结构体 int sign; /物品序号int w;/物品重量int p;/物品价值aN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int max(int a,int b)return ab?b:a;int n,C,bestP=0,cp=0,cw=0;int XN,cxN;int VN10*N; for(int i=0;i=n;i+)Vi0=0;for(int j=0;j=C;j+)V0j=0;for(i=1;i=n;i+)int KnapSack2(int n,goods a,int C,int x) /初始化第0列/初始化第0行/计算第i行，进行第i次迭代for(j=1;j=C;j+)if(j0;i-)if (VijVi-1j)xi-1=1;j=j-ai-1.w;else xi-1=0;return VnC;返回背包取得的最大价值int main（）goods bN;printf（物品种数 n:）;scanf（%d，&n）; 输入物品种数printf（背包容量 C:）;scanf（%d，&C）; 输入背包容量for （int i=0;in;i+）输入物品i的重量w及其价值vprintf（物品d 的重量 w%d及其价值 v%d:,i+1,i+1,i+1）;scanf（%d%d,&ai.w,&ai.p）;bi=ai;int sum2=KnapSack2（n,a,C,X）;调用动态规划法求0/1背包问题 printf（动态规划法求解0/1背包问题:nX=）;for（i=0;in;i+）coutXi;输出所求Xn矩阵printf（装入总价值%dn,sum2）;for （i=0;iW4及其价值U斗: 物品5的重量叽5及其价值v5： 物品的及其价值u疋: 动态规划法求解日门背包问题：X= G 0 0 0 1 1 装入总价值51Press ang key to continuo搜狗拼音输入法全：4）复杂度分析：动态规划法求解0/1背包问题的时间复杂度为：T（n）= O（nXC。第页共页2.回溯法求解 0/1背包问题：1)基本思想：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数 (bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。 这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子 集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。 当右子树中有可能包含最优解时就进入右子树搜索。2)代码:#include#includeusing namespace std;#define N 100 /最多可能物体数struct goods /物品结构体int sign; /物品序号int w;/物品重量int p; /物品价值aN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int max(int a,int b)return an-1)if(bestPcp)for (int k=O;kn;k+) Xk=c xk; 存储最优路径bestP=cp;return bestP;if(cw+ai.w=C) /进入左子树cw=cw+ai.w;cp=cp+ai.p;cxai.sign=1; /装入背包BackTrack(i+1);cw=cw-ai.w;cp=cp-ai.p; /回溯，进入右子树cxai.sign=0; /不装入背包BackTrack(i+1);return bestP;int KnapSack3(int n,goods a,int C,int x)for(int i=0;in;i+)xi=0;ai.sign=i;sort(a,a+n,m);将各物品按单位重量价值降序排列BackTrack(0);return bestP;int main()goods bN;printf(物品种数 n:);scanf(%d,&n);/输入物品种数printf(背包容量 C:);scanf(%d,&C);/输入背包容量for (int i=0;in;i+) /输入物品i的重量w及其价值vprintf(物品d 的重量 w%d及其价值 v%d:,i+1,i+1,i+1);scanf(%d%d,&ai.w,&ai.p);bi=ai;int sum3=KnapSack3(n,a,C,X);调用回溯法求 0/1 背包问题 printf(回溯法求解0/1背包问题:nX=);for(i=0;in;i+)coutXi ;/输出所求 Xn矩阵printf(装入总价值%dn,sum3);for (i=0;in;i+)ai=bi;恢复aN顺序3)运行结果：nD;Program Files.口物品冲数n： 6背包容量C： 3G撫品1的重w4及其价值讥粕；8 19 恂話5力蚩屋矶5及柴价但：9 16柳品&的重w&及其价值m6 :7 12回溯法求解卽1背包问题：X= 0 0 1 1 0 1 装入总价值曲Press any ky to continue捜狗拼音输入法全：4）复杂度分析：最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为：T（n） （2n）。由于 其对蛮力法进行优化后的算法，其复杂度一般比蛮力法要小。空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一个一维数组，即 回溯法求解0/1背包问题的空间复杂度为（n）。3分支限界法求解背包问题:1）基本思想：分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下, 分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件 的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束 条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下 的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点, 则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点, 仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点 时为问题的最优值。2）代码：#include#includeusing namespace std;#define N 100最多可能物体数struct goods 物品结构体int sign; 物品序号int w;物品重量int p;物品价值aN;bool m（goods a,goods b）第页共页return (a.p/a.w)(b.p/b.w);int max(int a,int b)return aHi/2.b)swap(Hi, Hi/2); elsedone = true;i = i/2;/堆中元素下移void mov_down(HEAP H, int n, int i)bool done = false; if(2*i)=n)while(!done & (i = 2*i) = n)if(i+1 Hi.b) i+; if(Hi/2.bHi.b) swap(Hi/2, Hi);elsedone = true; /往堆中插入结点 void insert(HEAP H, HEAP x, int &n)n+;Hn = x; mov_up(H,n); /删除堆中结点 void del(HEAP H, int &n, int i)HEAP x, y;x = Hi; y = Hn;n -; if(i=x.b) mov_up(H,i);else mov_down(H, n, i); /获得堆顶元素并删除 HEAP del_top(HEAP H, int &n)HEAP x = H1; del(H, n, 1); return x;/计算分支节点的上界void bound( KNAPNODE* node, int M, goods a, int n)int i = node-k;float w = node-w;float p = node-p;if(node-wM) / 物体重量超过背包载重量 node-b = 0;/ 上界置为 0elsewhile(w+ai.w=M)&(in)w += ai.w;/ 计算背包已装入载重p += ai+.p; / 计算背包已装入价值if(ib = p + (M - w)*ai.p/ai.w;elsenode - b = p;/用分支限界法实现 0/1背包问题int KnapSack4(int n,goods a,int C, int X)int i, k = 0; / 堆中元素个数的计数器初始化为 0int v;KNAPNODE *xnode, *ynode, *znode;HEAP x, y, z, *heap;heap = new HEAPn*n; / 分配堆的存储空间for( i=0; in; i+)ai.sign=i; /记录物体的初始编号 sort(a,a+n,m);/ 对物体按照价值重量比排序xnode = new KNAPNODE; / 建立父亲结点 for( i=0; is1i = false;xnode-k = xnode-w = xnode-p = 0;while(xnode-ks1ynode-k = true;/ 装入第 k 个物体ynode-w += aynode-k.w; / 背包中物体重量累计 ynode-p += aynode-k.p; / 背包中物体价值累计 ynode-k +; / 搜索深度+ bound(ynode, C, a, n); / 计算结点 y 的上界y.b = ynode-b;y.p = ynode;insert(heap, y, k);/结点 y 按上界的值插入堆中znode = new KNAPNODE; / 建立结点 z*zn