算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告.doc

實(shí) 驗(yàn) 報(bào) 告班級(jí)：學(xué)號(hào)：姓名：總成績：課程名稱：算法分析與設(shè)計(jì)實(shí)訓(xùn)實(shí)驗(yàn)項(xiàng)目：1、分治法實(shí)驗(yàn) 2、動(dòng)態(tài)規(guī)劃法實(shí)驗(yàn) 3、貪心法實(shí)驗(yàn) 4、回溯法實(shí)驗(yàn)5、分枝限界法實(shí)驗(yàn) 計(jì)算機(jī) 學(xué)院 工業(yè)中心202 實(shí)驗(yàn)室二一年 6 月 21 日 項(xiàng)目序號(hào)1項(xiàng)目名稱分治法實(shí)驗(yàn)成績小標(biāo)題找最大值和最小值1、 方法思想 分治法是把規(guī)模大的問題，分割成n個(gè)形式相同規(guī)模一定或不可再分的子問題，遞歸地解決每個(gè)子問題，再把子問題的結(jié)果匯總，合并得到原問題的解。分治法在每一層遞歸上由三個(gè)步驟組成： (1) 劃分(divide)：將原問題分解為若干規(guī)模較小、 相互獨(dú)立、 與原問題形式相同的子問題。 (2) 解決(conquer)： 若子問題規(guī)模較小，則直接求解；否則遞歸求解各子問題。 (3) 合并(combine)： 將各子問題的解合并為原問題的解。 2、問題描述 我們將分治策略用于此問題，每次將問題分成大致相等的兩部分，分別在這兩部分中找出最大值與最小值，再將這兩個(gè)子問題的解組合成原問題的解，就可得到該問題的分治算法。 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、實(shí)驗(yàn)結(jié)果（可用文字描述和貼圖等方式表現(xiàn)實(shí)驗(yàn)結(jié)果）項(xiàng)目序號(hào)2項(xiàng)目名稱動(dòng)態(tài)規(guī)劃法實(shí)驗(yàn)成績小標(biāo)題最長公共子序列1、方法思想 動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適用于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。在分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。如果能夠保存已解決的子問題的答案，而再需要時(shí)再找出已求的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。為了達(dá)到這個(gè)目的，可以用一個(gè)表來記錄所有已解決的子問題的答案。不過孩子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃的基本思想。2、問題描述 最長公共子序列為題：給定兩個(gè)序列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、實(shí)驗(yàn)結(jié)果項(xiàng)目序號(hào)3項(xiàng)目名稱貪心法成績小標(biāo)題活動(dòng)選擇問題1、方法思想 貪心算法總是做出再當(dāng)前看來最好的選擇，也就是說貪心算法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上看的局部最優(yōu)選擇。2、問題描述活動(dòng)選擇問題(activity-selection problem)即若干個(gè)具有競(jìng)爭(zhēng)性的活動(dòng)要求互斥使用某一公共資源，目標(biāo)是選擇最大的相容活動(dòng)集合。 假定集合S=a1, a2, , an中含有n個(gè)希望使用某一資源的活動(dòng)，這樣的資源有教室、某一設(shè)備等，它們一次只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)ai有開始時(shí)間(start time)si和完成時(shí)間(finish time)fi，其中，0sifi。如果某個(gè)活動(dòng)ai被選中使用資源，則該活動(dòng)在半開區(qū)間(si，fi這段時(shí)間占據(jù)資源。如果活動(dòng)ai和aj在時(shí)間區(qū)間(si，fi 和(sj，fj上不重疊，則稱它們是相容的(compatible)，即如果si fj或者sj fj ，活動(dòng)ai和aj是相容的。 活動(dòng)選擇問題是選擇最大的相容活動(dòng)集合。 3、算法描述 RECUR-ACTIVITY-SELECT(s, f, i, j)1 m i+12 while mj and smfi /找Sij中第一個(gè)活動(dòng)3 do m m+14 if mj /找到滿足條件的活動(dòng)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 活動(dòng)名稱 ;for(i=0;i11;i+)coutai ;coutendl;cout 活動(dòng)開始時(shí)間; for(i=0;i11;i+)coutpi ;coutendl; cout 活動(dòng)結(jié)束時(shí)間;for(i=0;i11;i+)coutqi ;coutendl;cout最大相容活動(dòng)序列是: ; f=recuractivityselect(p,q,0,12);coutendl;cout安排活動(dòng)個(gè)數(shù):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 /找到一個(gè)位置8 then if k=n /測(cè)試是否為問題的解9 then output(X) /輸出解10 else k k+1 /轉(zhuǎn)下一行，即給下一個(gè)皇后找位置11 xk 0 /初始化當(dāng)前皇后列取值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) /同一列或同一對(duì)角線有兩個(gè)皇后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、實(shí)驗(yàn)結(jié)果項(xiàng)目序號(hào)5項(xiàng)目名稱分枝限界法- 成績小標(biāo)題0-1背包問題1、方法思想 分枝限界法是廣度優(yōu)先或者按照最大價(jià)值(或最小成本)搜索解空間樹的過程。它也是一種系統(tǒng)地搜索問題解的方法。2、問題描述 某商店有n個(gè)物品， 第i個(gè)物品價(jià)值為vi，重量(或稱權(quán)值)為wi，其中vi和wi為非負(fù)數(shù)。 背包的容量為W，W為一非負(fù)數(shù)。目標(biāo)是如何選擇裝入背包的物品，使裝入背包的物品總價(jià)值最大?？蓪⑦@個(gè)問題形式描述為，約束條件為xi0，1， 1in 3、算法描述LUBOUND(v, w, cw, cv, n, k, LBB, UBB)/cw表示背包可用權(quán)值， cv表示已得價(jià)值，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) /右孩子是否成為活結(jié)點(diǎn)21 if UBBLower /判斷右孩子是否成為活結(jié)點(diǎn)22 then INSERTNODE(E, i+1, 0, cap, valu, UBB)23 Lower maxLower, LBB-24 if 不存在活結(jié)點(diǎn) then break/退出do-while循環(huán)25 EXTRACT-MAX(E) /下一個(gè)E結(jié)點(diǎn)是UB中最大的結(jié)點(diǎn)26 while (UB(E)Lower)27 PRINT(Lower, ans, n) 4、程序清單#include#include#define num 5/物品的個(gè)數(shù)int lbb=0,ubb=0;/當(dāng)前的價(jià)值和當(dāng)前重量int maxweight=75;/背包能能容的最大重量int f=1;struct aa int parent; /該結(jié)點(diǎn)的父結(jié)點(diǎn)號(hào)int Level; /結(jié)點(diǎn)所在層次int Tag; /該結(jié)點(diǎn)是否入列的標(biāo)志int CW; /背包剩余空間int CV; /當(dāng)前總價(jià)值int UB; /該結(jié)點(diǎn)最大下限界int id; /該結(jié)點(diǎn)標(biāo)記號(hào);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背包最大能裝的價(jià)值是：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