完整word版計算機算法與設計分析實驗報告

1、計算機算法與設計分析實 驗 報告班級 姓名 學號實驗一 分治與遞歸1、基本遞歸算法2、棋盤覆蓋問題3、二分搜索4、實驗小結實驗二 動態(tài)規(guī)劃算法1、最長公共子序列問題2、最大子段和問題3、實驗小結實驗三 貪心算法1、多機調度問題2、用貪心算法求解最小生成樹3、實驗小結實驗四 回溯算法和分支限界法1、符號三角形問題2、01 背包問題3、實驗小結目錄101212121418計算機組織與體系結構一一實驗報告9實驗分治與遞歸(4學時):基本遞歸算法一、實驗目的與要求1、熟悉C/C+語言的集成開發(fā)環(huán)境；2、通過本實驗加深對遞歸過程的理解二、實驗內容：掌握遞歸算法的概念和基本思想，分析并掌握“整數(shù)劃分”問題

2、的遞歸算法。三、實驗題任意輸入一個整數(shù)，輸出結果能夠用遞歸方法實現(xiàn)整數(shù)的劃分。#in clude using n ames pace std;int mai n()int a,b,c;int q(i nt n ,i nt m);cout請輸入整數(shù)及大于最大加數(shù)的數(shù) ab;c=q(a,b);cout所需要的劃分數(shù)為：ce ndl;return 0;int q(i nt n ,i nt m)if (n 1)|(m1) return 0; if (n=1)|(m=1) return 1;if (nm) return q(n,n);if (n=m) retur n q(n,m-1)+1; return

3、 q( n, m-1)+q( n-m,m);“OzneMPVJaOe忸蛀好“苗輸入整數(shù)及大加數(shù)的敕7 7W需要的劃分數(shù)為小石Press flny key Co cont * D:TEH P32De,bLig2 .exe*請輸入整數(shù)及大于最犬卽數(shù)的數(shù)7 11所需要的劃分數(shù)為：15 _Pvess any key to continue實驗結果: 結果分析：實驗時入得數(shù)據(jù)為：所要劃分的整數(shù)是7,他的劃分的最大加數(shù)的值不得大于7,根據(jù)實際其劃分的情況為15種，因而可知其程序的運行結果是正確的。:棋盤覆蓋問題一、實驗目的與要求1、掌握棋盤覆蓋問題的算法；2、初步掌握分治算法二、實驗題：要用圖示的4種不同

4、形2個L型骨牌不盤覆蓋問題：在一個 2kX 2k個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該 方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中， 態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 得重疊覆蓋。三、程序代碼：#in elude using n ames pace std;int tile=O; /全局變量，表示特殊格的號int board10001000;int mai n()int tr, tc, dr, dc, size;int tile=0; II全局變量，表示特殊格的號void chessBoard(i nt tr, i nt tc, i

5、nt dr, i nt dc, int size); cout輸入數(shù)據(jù) trtcdrdcsize;coute ndle ndl;chessBoard(tr, tc, dr, dc, size);for(i nt i=1;i=size;i+)for(i nt j=1;j=size;j+) coutboardij;coute ndl;return 0;特殊格的行號、列號棋void chessBoard(int tr, int tc, int dr, int dc, int size)/ 左上角行號、歹U號，盤大小if (size = 1)return;/?tiao chuint t = +tile

6、, / L 型骨牌號？s = size/2; /分割棋盤/覆蓋左上角子棋盤 if (dr tr + s & dc tc + s)/特殊方格在此棋盤中chessBoard(tr, tc, dr, dc, s);else/此棋盤中無特殊方格用t號L型骨牌覆蓋右下角boardtr + s - 1tc + s - 1 = t;/覆蓋其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);/覆蓋右上角子棋盤if (dr = tc + s) /特殊方格在此棋盤中chessBoard(tr, tc+s, dr, dc, s);else/此棋盤中無特殊方格 用t號L型骨牌覆蓋左下角

7、boardtr + s - 1tc + s = t; /覆蓋其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);/覆蓋左下角子棋盤if (dr = tr + s & dc = tr + s & dc = tc + s) /特殊方格在此棋盤中chessBoard(tr+s, tc+s, dr, dc, s);else/用t號L型骨牌覆蓋左上角boardtr + stc + s = t;/ 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s);試驗運行結果07 01Soo0 a a Q 10 4A 4L e03 09 o 0 0u

8、 0s SA s A15 n 13-I115. M1 IId e Q 0Oan#xe1 f. & 0 ke Vn20OJ V21H44KHKMtt 北：LZilH0 0 0 0 3to con t n u_三：二分搜索、實驗目的與要求1熟悉二分搜索算法;2、初步掌握分治算法；二、實驗題1設a0:n-1是一個已排好序的數(shù)組。請改寫二分搜索算法，使得當搜索元素x不在數(shù)組中 時，返回小于x的最大元素的位置I和大于x的最大元素位置j。當搜索元素在數(shù)組中時，I 和j相同，均為x在數(shù)組中的位置。三、程序代碼：#in clude using n ames pace std; int mai n()int c

9、onst len gth=100;int n, x;int ale ngth;cout依次輸入數(shù)組的長度，數(shù)組內容，要查找的數(shù)” n;/輸入數(shù)組的長度for(i nt i=0;i ai;cin x;void Bin arySearch(i nt a,i nt n ,i nt x);Bin arySearch(a, n, x);return 0;void BinarySearch(int a,int n,int x)/n:數(shù)組長度，i， j 分別表示下標int i,j,mid=0,left=0;int right=n-1;while(left=0)int mid=(left+right)/2;

10、if(x=amid)i=j=mid; break;if(xamid) left=mid+1;elseright=mid-1;if (i=j)&(i=0)cout所找的數(shù)據(jù)在數(shù)組中下標為：ie ndl;elsei=right;j=left;cout所找的數(shù)據(jù)不在數(shù)組中，其前后下標為:i,je ndl;儘次輸入數(shù)組的長度，數(shù)組內容，要查找的數(shù)5 1 2 3 4 5 3所找的數(shù)據(jù)在數(shù)組中下斫為.2Press any key to cant inue如上圖所示數(shù)組的長度為5,其內容2,結果是正確的依次為1 2 3 4 5，所要找的數(shù)據(jù)位 3,他的下表正好是il人數(shù)?且日:枚度！裁mH谷要的處 713

11、46 7 8 9to continue1找的數(shù)據(jù)不在數(shù)組中，其前后下標為；2.3Press any key7,輸入的數(shù)組是1 3 4 6 7 8 9，所要查找的數(shù)字式 5，它不在數(shù)組中, 2,3結果是正確的。如上圖數(shù)組的長度為 其前后的下表分別為 實驗小結：第一個實驗自己做了出來, 到實際上就有點問題了， 的，雖然自己沒能做出來,實驗動態(tài)規(guī)劃算法然而第二個實驗卡了很久，對棋盤覆蓋問題上課聽懂了但是應用 最后還是在同學的幫助下完成的！ 后面的這個提高題也是查考同學 但是感覺還是應該去學習！最長公共子序列問題一、實驗目的與要求1、熟悉最長公共子序列問題的算法；2、初步掌握動態(tài)規(guī)劃算法；二、實驗題若

12、給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk,是X的子序列是指存在一個 嚴格遞增下標序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B , C, D , B是序列X=A , B, C, B , D, A , B的子序列，相應的遞增下標序列為2 , 3, 5, 7。給定2個序列X和丫，當另一序列Z既是X的子序列又是 丫的子序列時，稱 Z是序列X 和丫的公共子序列。三、實驗程序#in clude using n ames pace std;int fun( char *x)char *y=x;while(*y+);return y-x-1;void L

13、CSLe ngth(char *x ,char *y,i nt m,i nt n, i nt *c, i nt *b)int i ,j;=for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) elsecij=ci-1j; bij=2;cij=cij-1; bij=3;void LCS(i nt i ,i nt j, char *x ,int *b)if (i =0 II j=0) return;if (bij= 1)LCS(i-1,

14、j-1,x,b); prin tf(%c,xi);else if (bij= 2)LCS(i-1,j,x,b); else LCS(i,j-1,x,b);int mai n()char x50,y50;int m,n;int *c =new in t*50,*b =new in t*50; for(i nt i=0;i50;i+)ci =new in t50;bi =n ew in t50;/int c5050,b5050;cout x;couty; m=fu n(x); n=fu n(y);LCSLe ngth(x,y, m,n, c,b);LCS(m, n,x,b); coute ndl;

15、 return 0;四、運行結果H.H.abdjhfd ac iedjd二：最大子段和問題一、實驗目的與要求1、熟悉最長最大字段和問題的算法；2、進一步掌握動態(tài)規(guī)劃算法；二、實驗題若給定n個整數(shù)組成的序列 ai, a2, a?, 大值。三、程序清單#in cludean，求該序列形如ai+1 +a*的最using n ames pace std;int MaxSum(i nt n,i nt *a,i nt & besti,i nt & bestj)int sum=0;for(i nt i=O;i n;i+)int thissum=0;for(i nt j=i;jsum)sum=thissum;

16、besti=i;bestj=j；return sum;int mai n()int *a=new in t50;int x,n ,besti,bestj;H.coutn;cout請輸入字符串中的每個數(shù)字：for(i nt i=0;i ai;x=MaxSu m(n, a,besti,bestj);cout最大子段和為：起始位置：besti+1至bestj+1結果為： xe ndl;return 0;四、運行結杲實驗小結然后再查詢第二列進行對比！最大子段和感覺第一個求公共子序列感覺和遞歸查詢差不多, 就像求整列的和！實驗三貪心算法（2學時）:多機調度問題、實驗目的與要求1熟悉多機調度問題的算法;計

17、算機組織與體系結構一一實驗報告112、初步掌握貪心算法；二、實驗題要求給出一種作業(yè)調度方案，使所給的n個作業(yè)在盡可能短的時間內由 m臺機器加工處理完成。約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作 業(yè)不能拆分成更小的子作業(yè)。三、實驗程序#in clude using n ames pace std;typ edef struct Jobint ID;/作業(yè)號int time;/作業(yè)所花費的時間Job;Job J10;typ edef struct JobNode / 作業(yè)鏈表的節(jié)點int ID;int time;JobNode *n ext;JobNode,* pJ

18、obNode;typedef struct Header /鏈表的表頭，不同的機器？ int s;p JobNode n ext;Header,* pH eader;in t l=1;int mai n()/表示其最大的容量/Job J10;Header M10;int m,n;/機器的個數(shù)cout請輸入數(shù)據(jù)作業(yè)的個數(shù)與機器的個數(shù)nm;cout請輸入所有的任務的相關數(shù)據(jù)e ndl;for(i nt i=1;i=m;i+)Mi.s=0;/表示其最大容量for( l=1;lJl.IDJl.time;int SelectMi n(Header* M,i nt m);/SelectMi n(M ,m)

19、;for(l=1;l=n ;l+)cout第l個任務在第” MSelectMin(M,m)臺機器上完成endl;return 0;計算機組織與體系結構一一實驗報告int SelectMi n(Header* M,i nt m) /有幾臺機器，就創(chuàng)建幾個鏈表15int k=1;for(i nt i=1;i=m;i+)if(Mi.s=M1.s) k=i;最小的加入,s標識時間的和值Mk.s+=Jl.time; return k;/k是標識第幾臺機器加入作業(yè)五、實驗結果蒼f - D:UE MADebog1 .exe請輸人數(shù)據(jù)作業(yè)的個數(shù)與機器的個數(shù)5 3請輸入所有的任務的相關數(shù)據(jù)t0 9876S432

20、1il個任務在英M3臺啊器上気成3入任#在2鬥1臺汛器上g感4個任4在第m合磯器上蕪成5個任共在第臺機器上完成Press any kep to cant inue用貪心算法求解最小生成樹一、實驗要求與目的1、熟悉貪心算法的基本原理與適用范圍。2、使用貪心算法編程，求解最小生成樹問題。二、實驗內容1、任選一種貪心算法（Prim或Kruskal），求解最小生成樹。對算法進行描述和復雜性分析。 編程實現(xiàn)，并給出測試實例三、實驗程序#in clude using n ames pace std;int const in f=100;int mai n()int n=6;e ndl;cout所給圖的最小

21、生成樹一次選定的邊是表示為:int c77= inf,inf,inf,inf,inf,inf,inf,inf,in f,6,1,5,i nf,inf, inf,inf,inf,5,in f,3, inf,inf,1 ,5,i nf,5,6,4,in f,5, in f,5,i nf,in f,2,inf,in f,3,6, inf,in f,6,inf,inf,in f,4,2,6,i nf;/c12=6;c14=5;c13=1;c23=5;c34=5;c25=3;c26=2;/c35=6;c36=4;c56=6;c21=6;c41=5;c31=1;c32=5;c43=5;c52=3;c62=

22、2;/c53=6;c63=4;c65=6;void p rim(i nt n ,i nt c77);prim( n,c);return 0;void prim(i nt n,i nt c77)int lowcost7;int closet7;bool s10;s1=true;for(i nt i=2;i=n;i+) lowcosti=c1i; closeti=1; si=false;int j=1;for(i=1;i n; i+)int mi n=inf;int j=1;for(i nt k=2;k=n ;k+)if(lowcostk0)min=lowcostk; j=k;coutjclose

23、tje ndl; sj=true;for(k=2;k=n;k+) if(cjklowcostk )&(!sk) lowcostk=cjk; closetk=j;四、實驗結果cT y：VTEMP2Debug氐ex護所給圖的最小注成樹一次選走的邊是表示為131634&2352Press anv key to continue五、實驗小結貪心算法上課老師講的時候也能聽懂， 講的例子也能明白，但是在實際調度時遇到了不小的 麻煩！最后在老師和同學的幫助下完成了！ 盡管自己沒有做出來， 但是對貪心算法的實際操 作有了更一步的把握！實驗四 回溯算法和分支限界法（2學時）一：符號三角形問題一、實驗目的與要求1

24、、掌握符號三角形問題的算法；2、初步掌握回溯算法；二、實驗題圖下面都是“-”。下圖是由14個“ + ”和14個“-”組成的符號三角形。2個同號下面都是“ + ”2個異號下面都是“-”。 在一般情況下，符號三角形的第一行有 題要求對于給定的n,計算有多少個不同的符號三角形，使其所含的“ 三、實驗程序n個符號。符號三角形問+ ”和“-”的個數(shù)相#in elude using n ames pace std;typ edef un sig ned char uchar; int sum; uchar* p;char ch2=+,-; int n;int half; int count; void B

25、ackTrace(i nt t) /符號存儲空間；表示滿足要求的三角形個數(shù) /第一行符號總數(shù)用來計算-的個數(shù)if (tn)sum+;cout第sum個三角形：endl; for (i nt i=1;i=n;i+)for (i nt j=1;ji;j+)cout;for (j=1;j=n-i+1;j+)coutch p ij;計算機組織與體系結構一一實驗報告17coute ndl; elsefor (i nt i=0;i=1;i+) p1t=i;coun t+=i;II確定第一行第t個的值;/用來計算-的個數(shù)；for (int j=2;j=t;j+)pjt-j+1=pj-1t-j+1F pj-1

26、t-j+2;2行開始增加的一第一行大于等于2時確定后面從第coun t+=pjt-j+1;列中符號，計算-個數(shù);if (cou nt = half & (t*(t+1)I2-cou nt) = half)II約束條件;BackTrace(t+1);for (j=2;j=t;j+)cou nt-=pjt-j+1;coun t-=p1t;回溯，判斷另一種符號情況;int mai n()coutn;coun t=0;sum=0;half= n*( n+1)/2;if (half%2=0)half=halfI2;p=new uchar* n+1; for (i nt i=0;i=n;i+)H.p i=

27、new uchar n+1;memset (p i,0,sizeof(uchar)* (n+1);計算機組織與體系結構一一實驗報告BackTrace(l);for (i=0;i=n ;i+)delete pi;delete p;cout滿足要求的三角形符號共有：sum個;19 elsecout不存在這樣的三角形符號!H. return 0;五、實驗結果皐齊仝膏訝待的j如3満足要求的三甬形符號吐有工0個Pice any Ke# to conrnu&二：0 1背包問題一、實驗目的與要求1、掌握0 1背包問題的回溯算法；2、進一步掌握回溯算法；二、實驗題：給定n種物品和一背包。物品i的重量是wi，其

28、價值為Vi,背包的容量為 C。問應如何選擇 裝入背包的物品，使得裝入背包中物品的總價值最大？三、實驗程序#in cludeusing n ames pace std;class Knapfriend int Knap sack(i nt p ,i nt w,i nt c,i nt n ); public:void prin t()for(i nt m=1;m =n; m+) coutbestxm; coute ndl;private:int Boun d(i nt i); void Backtrack(i nt i);int c;/背包容量int n; /物品數(shù)int *w;/物品重量數(shù)組 i

29、nt *p;/物品價值數(shù)組int cw;/當前重量int cp;/當前價值int best p;/當前最優(yōu)值int *bestx;/當前最優(yōu)解int *x;/當前解;int Knap:Bo un d(i nt i)/計算上界int cleft=c-cw;/ 剩余容量int b=c p;/以物品單位重量價值遞減序裝入物品while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;/裝滿背包if(i n)if(best pcp)for(i nt j=1;j=n;j+)計算機組織與體系結構一一實驗報告bestxj=xj; best p=cp; return;if(cw+wibestp)/ 搜索右子樹xi=0;Backtrack(i+1);class Objectfriend int Knap sack(i nt p ,i nt w,i nt c,i nt n); public:int op erator=a.d);private:int ID;float d;int Knap sack(i nt p ,i nt