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

实 验 报 告班级：学号：姓名：总成绩：课程名称：算法分析与设计实训实验项目：1、分治法实验 2、动态规划法实验 3、贪心法实验 4、回溯法实验5、分枝限界法实验 计算机 学院 工业中心202 实验室二一年 6 月 21 日 项目序号1项目名称分治法实验成绩小标题找最大值和最小值1、 方法思想 分治法是把规模大的问题，分割成n个形式相同规模一定或不可再分的子问题，递归地解决每个子问题，再把子问题的结果汇总，合并得到原问题的解。分治法在每一层递归上由三个步骤组成： (1) 划分(divide)：将原问题分解为若干规模较小、 相互独立、 与原问题形式相同的子问题。 (2) 解决(conquer)： 若子问题规模较小，则直接求解；否则递归求解各子问题。 (3) 合并(combine)： 将各子问题的解合并为原问题的解。 2、问题描述 我们将分治策略用于此问题，每次将问题分成大致相等的两部分，分别在这两部分中找出最大值与最小值，再将这两个子问题的解组合成原问题的解，就可得到该问题的分治算法。 3、算法描述REC-MAXMIN(i，j，fmax，fmin)1 if i=j2 then fmax fmin Ai3 if i=(j-1)4 then if AiAj5 then fmax Ai 6 fmin Aj else fmax Aj8 fmin Ai9 else mid (i+j)/210 REC-MAXMIN(i，mid，gmax，gmin)11 REC-MAXMIN(mid+1， j， hmax，hmin)12 fmax maxgmax，hmax13 fmin mingmin，hmin 4、程序清单 #includevoid FZFa(int i,int j,int &max,int &min,int a)if(i= =j)max=ai;min=aj;else if(i= =(j-1)if(aiaj)max=ai;min=aj;elsemax=aj;min=ai;elseint midd=(i+j)/2; int max1=0,min1=0,max2=0,min2=0; FZFa(i,midd,max1,min1,a); FZFa(midd+1,j,max2,min2,a); if(max1max2)max=max1;elsemax=max2;if(min1min2)min=min1;elsemin=min2;int main()int t=2,4;int max,min;FZFa(0,1,max,min,t);cout最大值：maxendl; cout最小值：minendl;return 0;5、实验结果（可用文字描述和贴图等方式表现实验结果）项目序号2项目名称动态规划法实验成绩小标题最长公共子序列1、方法思想 动态规划算法与分治法类似，其基本思想也是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适用于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。在分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而再需要时再找出已求的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不过孩子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。2、问题描述 最长公共子序列为题：给定两个序列X=x1,x2,x3xm和Y=y1,y2,y3yn,找出X和Y的最长公共子序列。3、算法描述LCSLENGTH(X, Y)1 m lengthX2 n lengthY3 for i 1 to m4 do li, 0 05 for j 1 to n6 do l0, j 07 for i 1 to m8 do for j 1 to n9 do if xi=yj10 then li, j li-1, j-1+1 bi, j112 else if li-1, j li, j-113 then li, j li-1, j14 bi, j2 15 else li, j li, j-116 bi, j317 return l andb 4、程序清单#includeint lcsleng(char x,char y,int a1010,int n,int m)int c1010;int i,j;for(i=1;i=m;i+)ci0=0;for(i=1;i=n;i+)c0i;for(i=1;i=n;i+)for(j=1;j=cij-1)cij=ci-1j;aij=2;elsecij=cij-1;aij=3;return cnm;void lcs(int i,int j,char x,int a1010)if(i=0|j=0)return;if(aij=1)lcs(i-1,j-1,x,a); coutxiendl;else if(aij=2)lcs(i-1,j,x,a);elselcs(i,j-1,x,a);int main()char a= kagajsj;char b= asjofgo;int t1010; int c=lcsleng(a,b,t,7,7);coutcendl; lcs(7,7,a,t);return 0;5、实验结果项目序号3项目名称贪心法成绩小标题活动选择问题1、方法思想 贪心算法总是做出再当前看来最好的选择，也就是说贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上看的局部最优选择。2、问题描述活动选择问题(activity-selection problem)即若干个具有竞争性的活动要求互斥使用某一公共资源，目标是选择最大的相容活动集合。 假定集合S=a1, a2, , an中含有n个希望使用某一资源的活动，这样的资源有教室、某一设备等，它们一次只能由一个活动使用。每个活动ai有开始时间(start time)si和完成时间(finish time)fi，其中，0sifi。如果某个活动ai被选中使用资源，则该活动在半开区间(si，fi这段时间占据资源。如果活动ai和aj在时间区间(si，fi 和(sj，fj上不重叠，则称它们是相容的(compatible)，即如果si fj或者sj fj ，活动ai和aj是相容的。 活动选择问题是选择最大的相容活动集合。 3、算法描述 RECUR-ACTIVITY-SELECT(s, f, i, j)1 m i+12 while mj and smfi /找Sij中第一个活动3 do m m+14 if mj /找到满足条件的活动m5 then return amRECUR-ACTIVITY-SELECT(s,f, m, j)/将m加入集合6 else return 4、程序清单#includeint recuractivityselect(int s,int f,int i,int j)int m=i+1,k=0;while(mj&smfi)m=m+1;if(mj)coutm ;k=1+recuractivityselect(s,f,m,j);return k;int budigui(int s,int f,int k,int n)k1=1;int i=1,m,t=2,w=1;for(m=2;m=fi)kt=m;t+;w+; i=m;return w;int main()int a=0,1,2,3,4,5,6,7,8,9,10,11;int p=0,1,2,0,5,3,5,6,8,8,2,12;int q=0,4,5,6,7,8,9,10,11,12,13,14;int t12=0;int i,f;cout 活动名称 ;for(i=0;i11;i+)coutai ;coutendl;cout 活动开始时间; for(i=0;i11;i+)coutpi ;coutendl; cout 活动结束时间;for(i=0;i11;i+)coutqi ;coutendl;cout最大相容活动序列是: ; f=recuractivityselect(p,q,0,12);coutendl;cout安排活动个数:fendl;coutendl; f=budigui(p,q,t,12);coutfendl;/*for(i=0;i12;i+)coutti0 do 4 xk xk+1 /到下一列5 while xk n & not PLACE(k) do6 xk xk+17 if xk n /找到一个位置8 then if k=n /测试是否为问题的解9 then output(X) /输出解10 else k k+1 /转下一行，即给下一个皇后找位置11 xk 0 /初始化当前皇后列取值12 else k k-1 /回溯13 return PLACE(k)1 i 12 while ik do 3 if (xi=xk or abs (xi-xk)=abs (i-k) /同一列或同一对角线有两个皇后4 then return (false)5 i i+16 return (true) 4、程序清单#include#includebool place(int k,int x)int j;for(j=1;j0)xk+=1;while(xk=n)&(!place(k,x)xk+=1;if(xk=n)if(k=n) for(int i=1;i=n;i+)for(int j=1;j=n;j+)if(j=xi)cout;elsecout;coutendl; coutendl;sum+; elsek+;xk=0;else k-;int main()int n=4,m,i,sum=0;int x5;for(i=0;i=n;i+)xi=0; backtrack(x,sum,n); coutsumendl; return 0;5、实验结果项目序号5项目名称分枝限界法- 成绩小标题0-1背包问题1、方法思想 分枝限界法是广度优先或者按照最大价值(或最小成本)搜索解空间树的过程。它也是一种系统地搜索问题解的方法。2、问题描述 某商店有n个物品， 第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数。 背包的容量为W，W为一非负数。目标是如何选择装入背包的物品，使装入背包的物品总价值最大。可将这个问题形式描述为，约束条件为xi0，1， 1in 3、算法描述LUBOUND(v, w, cw, cv, n, k, LBB, UBB)/cw表示背包可用权值， cv表示已得价值，LBB=-u(X)，UBB=-l(X)1 LBB cv2 c cw3 for i k to n do4 if cLower16 then Lower valu17 ans E18 else if cap wi /左孩子可行19 then INSERTNODE(E, i+1, 1, cap-wi, valu+vE, UBE) 20 LUBOUND(v, w, cap, valu, n, i+1, LBB, UBB) /右孩子是否成为活结点21 if UBBLower /判断右孩子是否成为活结点22 then INSERTNODE(E, i+1, 0, cap, valu, UBB)23 Lower maxLower, LBB-24 if 不存在活结点 then break/退出do-while循环25 EXTRACT-MAX(E) /下一个E结点是UB中最大的结点26 while (UB(E)Lower)27 PRINT(Lower, ans, n) 4、程序清单#include#include#define num 5/物品的个数int lbb=0,ubb=0;/当前的价值和当前重量int maxweight=75;/背包能能容的最大重量int f=1;struct aa int parent; /该结点的父结点号int Level; /结点所在层次int Tag; /该结点是否入列的标志int CW; /背包剩余空间int CV; /当前总价值int UB; /该结点最大下限界int id; /该结点标记号;struct aa ans100;typedef struct qnode aa bag100; int front,rear;LNode;void initLNode(LNode *&q) q=new LNode; q-front=q-rear=0;int LNodeEmpty(LNode *q) if(q-rear=q-front)return 1; elsereturn 0;void enLNode(LNode *&q,aa e) if(q-rear+1)%100=q-front) return ;coutrear=(q-rear+1)%100; q-bagq-rear=e;int deLNode(LNode *&q,aa &e) if(q-rear=q-front) return 0; q-front=(q-front+1)%100; e=q-bagq-front; return 1;LNode *q;void init(aa k)k.parent=0;k.Level=0;k.Tag=0;k.CW=0;k.CV=0;k.UB=0;k.id=f; initLNode(q);void add(aa t) ansf=t;f+;enLNode(q,t);void insertnode(int par,int lev,int t,int cap,int valu,int ub,int id)aa tp;tp.parent=par;tp.Level=lev;tp.Tag=t;tp.CW=cap;tp.CV=valu;tp.UB=ub;tp.id=id; add(tp);void print(int lower,aa ans,int n)cout终于做出来了,哈哈！endl;cout背包最大能装的价值是：lowerendl;int tt=f-1;cout=1;j-)if(anstt.Tag=1)coutj ;tt=anstt.parent;void lubound(int cv,int cw,int w,int v,int n,int k,int &lbb,int &ubb)lbb=cv;int c=cw;for(int i=k;i=n;i+)if(cwi)ubb=lbb+c*(float)v