算法設計與分析報告-

算法設計與分析報告-算法設計與分析實驗班級：計科09—4班姓名：楊見寶時間：2011.12.25實驗一分治與遞歸基本題一：基本遞歸算法一、實驗目的與要求熟悉C/C++語言的集成開發(fā)環(huán)境；通過本實驗加深對遞歸過程的理解二、實驗內(nèi)容：掌握遞歸算法的概念和基本思想，分析并掌握“整數(shù)劃分”問題的遞歸算法。三、實驗題任意輸入一個整數(shù)，輸出結(jié)果能夠用遞歸方法實現(xiàn)整數(shù)的劃分。實驗代碼#include<iostream.h>#include<iomanip.h>#definemax1024voidprint(int*map,intlen){staticinttotal=1;cout<<"劃分"<<setw(4)<<total++<<":";for(inti=0;i<len;i++)cout<<setw(5)<<map[i];cout<<endl;}intp(intn,intm,int*map,intlen){if(n>=1&&m==1){map[len]=1;算法設計與分析報告-全文共17頁，當前為第1頁。p(n-1,m,map,len+1);算法設計與分析報告-全文共17頁，當前為第1頁。return1;}elseif(n==0&&m==1){print(map,len);return1;}elseif(n==1&&m>1){map[len]=n;print(map,len+1);return1;}elseif(n<m){returnp(n,n,map,len);}elseif(n==m){map[len]=m;print(map,len+1);returnp(n,m-1,map,len)+1;}else{map[len]=m;ints1=p(n-m,m,map,len+1);}}intmain(){intn;cout<<"請輸入一個整數(shù)：";cin>>n;intmap[max]={0};intlen=0;cout<<n<<"的劃分個數(shù)是"<<p(n,n,map,len)<<endl;return0;}算法設計與分析報告-全文共17頁，當前為第2頁。算法設計與分析報告-全文共17頁，當前為第2頁。基本題二：棋盤覆蓋問題一、實驗目的與要求1、掌握棋盤覆蓋問題的算法；2、初步掌握分治算法二、實驗題：

盤覆蓋問題：在一個2k×2k個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。實驗代碼#include<iostream>usingnamespacestd;inttile=0;intboard[4][4];voidmain(){ voidchessBoard(inttr,inttc,intdr,intdc,intsize); chessBoard(0,0,4,4,4); for(inti=0;i<4;i++) { for(intj=0;j<4;j++) printf("%4d",board[i][j]); cout<<endl; }} voidchessBoard(inttr,inttc,intdr,intdc,intsize) { if(size==1)return; intt=tile++, s=size/2; if(dr<tr+s&&dc<tc+s) chessBoard(tr,tc,dr,dc,s);算法設計與分析報告-全文共17頁，當前為第3頁。 else{算法設計與分析報告-全文共17頁，當前為第3頁。 board[tr+s-1][tc+s-1]=t; chessBoard(tr,tc,tr+s-1,tc+s-1,s); } if(dr<tr+s&&dc>=tc+s) chessBoard(tr,tc+s,dr,dc,s); else{ board[tr+s-1][tc+s]=t; chessBoard(tr,tc+s,tr+s-1,tc+s,s); } if(dr>=tr+s&&dc<tc+s) chessBoard(tr+s,tc,dr,dc,s); else{ board[tr+s][tc+s-1]=t; chessBoard(tr+s,tc,tr+s,tc+s-1,s); } if(dr>=tr+s&&dc>=tc+s) chessBoard(tr+s,tc+s,dr,dc,s); else{ board[tr+s][tc+s]=t; chessBoard(tr+s,tc+s,tr+s,tc+s,s); } }程序?qū)崿F(xiàn)實驗二動態(tài)規(guī)劃算法

基本題一：最長公共子序列問題一、實驗目的與要求1、熟悉最長公共子序列問題的算法；2、初步掌握動態(tài)規(guī)劃算法；二、實驗題算法設計與分析報告-全文共17頁，當前為第4頁。

若給定序列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}。算法設計與分析報告-全文共17頁，當前為第4頁。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。

實驗代碼#include<iostream>usingnamespacestd;intmain(){ char*x,*y; int**c,**b; voidLCSLength(char*x,char*y,intm,intn,int**c,int**b); voidLCS(inti,intj,char*x,int**b); cout<<"請輸入X序列的元素數(shù)目："; intm; cin>>m; cout<<"請輸入X序列："; x=newchar[m]; cin>>x; cout<<"請輸入Y序列的元素數(shù)目："; intn; cin>>n; cout<<"請輸入Y序列："; y=newchar[n]; cin>>y; b=newint*[m+1]; for(inti=0;i<=m;i++) b[i]=newint[n+1]; c=newint*[m+1]; for(inti=0;i<=m;i++) c[i]=newint[n+1]; LCSLength(x,y,m,n,(int**)c,(int**)b); cout<<"最長公共序列元素個數(shù)是："<<c[m][n]<<endl; cout<<"最長公共子序列是:"; LCS(m,n,x,(int**)b); return0;}voidLCSLength(char*x,char*y,intm,intn,int**c,int**b){算法設計與分析報告-全文共17頁，當前為第5頁。inti,j;算法設計與分析報告-全文共17頁，當前為第5頁。for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}} }voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i-1];}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}算法設計與分析報告-全文共17頁，當前為第6頁。程序?qū)崿F(xiàn)算法設計與分析報告-全文共17頁，當前為第6頁。基本題二：最大字段和問題

一、實驗目的與要求1、熟悉最長最大字段和問題的算法；2、進一步掌握動態(tài)規(guī)劃算法；二、實驗題

若給定n個整數(shù)組成的序列a1，a2，a3，……an，求該序列形如ai＋ai＋1＋……＋an的最大值。實驗代碼#include<iostream>usingnamespacestd;intMaxSum(intn,int*a,int&besti,int&bestj){ intsum=0; for(inti=1;i<=n;i++) for(intj=i;j<=n;j++) { intthissum=0; for(intk=i;k<=j;k++)thissum+=a[k]; if(thissum>sum) { sum=thissum; besti=i; bestj=j; } } returnsum;}voidmain(){ inta[8]={-2,-1,2,4,-3,8,7,-9};算法設計與分析報告-全文共17頁，當前為第7頁。 intbesti=1;算法設計與分析報告-全文共17頁，當前為第7頁。 intbestj=1; cout<<MaxSum(8,a,besti,bestj)<<endl; cout<<besti<<endl<<bestj;}程序?qū)崿F(xiàn)實驗三貪心算法

基本題一：多機調(diào)度問題一、實驗目的與要求1、熟悉多機調(diào)度問題的算法；2、初步掌握貪心算法；二、實驗題

要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。實驗代碼#include<iostream>#include<iomanip>usingnamespacestd;typedefstructJob{intID;inttime;}Job;typedefstructJobNode{intID;inttime;JobNode*next;算法設計與分析報告-全文共17頁，當前為第8頁。}JobNode,*pJobNode;算法設計與分析報告-全文共17頁，當前為第8頁。typedefstructHeader{ints;JobNode*next;}Header,pHeader;intmain(){ voidQuickSort(Job*job,intleft,intright); voidoutSort(Job*job,intn); voiddisplay(Header*M,intm); intSelectMin(Header*M,intm); voidsolve(Header*head,Job*job,intn,intm); intm,n; cout<<"\t\t《多機調(diào)度問題》\n"; cout<<"請輸入機器臺數(shù)m:"; cin>>m;Header*head=newHeader[m]; cout<<"請輸入作業(yè)個數(shù)n:"; cin>>n; Job*job=newJob[n]; cout<<"\n請按序號輸入每個作業(yè)調(diào)度所需時間time："; for(inti=0;i<n;i++) { cin>>job[i].time; job[i].ID=i; } QuickSort(job,0,n-1); outSort(job,n); solve(head,job,n,m); display(head,m); cout<<endl<<endl; return0;}intSelectMin(Header*M,intm){intk=0;for(inti=1;i<m;i++){if(M[i].s<M[k].s) k=i;算法設計與分析報告-全文共17頁，當前為第9頁。}算法設計與分析報告-全文共17頁，當前為第9頁。returnk;}voidQuickSort(Job*job,intleft,intright){ intmiddle=0,i=left,j=right; Jobitemp; middle=job[(left+right)/2].time; do { while((job[i].time>middle)&&(i<right)) i++; while((job[j].time<middle)&&(j>left)) j--; if(i<=j) { itemp=job[j]; job[j]=job[i]; job[i]=itemp; i++; j--; } }while(i<=j); if(left<j) QuickSort(job,left,j); if(right>i) QuickSort(job,i,right);}voiddisplay(Header*M,intm){ JobNode*p; for(inti=0;i<m;i++) { cout<<"\n第"<<i<<"臺機器上處理的工作序號："; if(M[i].next==0) continue; p=M[i].next; do{ cout<<p->ID<<''; p=p->next; }while(p!=0); }算法設計與分析報告-全文共17頁，當前為第10頁。}算法設計與分析報告-全文共17頁，當前為第10頁。voidoutSort(Job*job,intn){ cout<<"\n按工作時間由大到小為:\n時間：\t"; for(inti=0;i<n;i++) cout<<setw(4)<<job[i].time; cout<<"\n序號：\t"; for(inti=0;i<n;i++) cout<<setw(4)<<job[i].ID;}voidsolve(Header*head,Job*job,intn,intm){ intk; for(inti=0;i<m&&i<n;i++) { JobNode*jobnode=newJobNode; jobnode->time=job[i].time; jobnode->ID=job[i].ID; jobnode->next=0; head[i].s=jobnode->time; head[i].next=jobnode; } if(n<=m) { for(inti=0;i<m;i++) { head[i].s=0; head[i].next=0; } } if(n>m) { for(inti=0;i<n;i++) { JobNode*p; JobNode*jobnode=newJobNode; jobnode->time=job[i].time; jobnode->ID=job[i].ID; jobnode->next=0; k=SelectMin(head,m); p=head[k].next; head[k].s+=jobnode->time; while(p->next!=0)算法設計與分析報告-全文共17頁，當前為第11頁。 p=p->next;算法設計與分析報告-全文共17頁，當前為第11頁。 p->next=jobnode; } }}程序?qū)崿F(xiàn)

實驗四回溯算法和分支限界法基本題一：符號三角形問題一、實驗目的與要求1、掌握符號三角形問題的算法；2、初步掌握回溯算法；二、實驗題圖下面都是“-”。下圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。+

+

-

+

-

+

++

-

-

-

-

+-

+

+

+

-

-

+

+

-

-

+

-

-

-

+

在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。實驗代碼#include"iostream"usingnamespacestd;算法設計與分析報告-全文共17頁，當前為第12頁。typedefunsignedcharuchar;算法設計與分析報告-全文共17頁，當前為第12頁。charcc[2]={'+','-'};intn,half,counter;uchar**p;longsum;voidBacktrace(intt){inti,j;if(t>n){sum++;cout<<"第"<<sum<<"個:\n";for(i=1;i<=n;++i){for(j=1;j<i;++j){cout<<"";}for(j=1;j<=n-i+1;++j){cout<<cc[p[i][j]]<<"";}cout<<"\n";}}else{for(i=0;i<2;++i){p[1][t]=i;counter+=i;for(j=2;j<=t;++j){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];counter+=p[j][t-j+1];}if((counter<=half)&&(t*(t+1)/2-counter<=half)){Backtrace(t+1);}for(j=2;j<=t;++j){counter-=p[j][t-j+1];}counter-=i;} }}算法設計與分析報告-全文共17頁，當前為第13頁。intmain()算法設計與分析報告-全文共17頁，當前為第13頁。{cout<<"請輸入第一行符號個數(shù)n：";cin>>n;counter=0;sum=0;half=n*(n+1)/2;inti=0;if(half%2==0){half/=2;p=newuchar*[n+1];for(i=0;i<=n;++i){p[i]=newuchar[n+1];memset(p[i],0,sizeof(uchar)*(n+1));}Backtrace(1);for(i=0;i<=n;++i){delete[]p[i];}delete[]p;}cout<<"\n總共"<<sum<<"個"<<endl;return0;}

程序?qū)崿F(xiàn)基本題二：0—1背包問題算法設計與分析報告-全文共17頁，當前為第14頁。一、實驗目的與要求算法設計與分析報告-全文共17頁，當前為第14頁。1、掌握0—1背包問題的回溯算法；2、進一步掌握回溯算法；二、實驗題：給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?實驗代碼#include<iostream>usingnamespacestd;intmin(intx,inty){ if(x>y) returny; else returnx;}intmax(intx,inty){ if(x>y