算法設(shè)計(jì)與分析報(bào)告-

算法設(shè)計(jì)與分析報(bào)告-算法設(shè)計(jì)與分析實(shí)驗(yàn)班級(jí)：計(jì)科09—4班姓名：楊見(jiàn)寶時(shí)間：2011.12.25實(shí)驗(yàn)一分治與遞歸基本題一：基本遞歸算法一、實(shí)驗(yàn)?zāi)康呐c要求熟悉C/C++語(yǔ)言的集成開(kāi)發(fā)環(huán)境；通過(guò)本實(shí)驗(yàn)加深對(duì)遞歸過(guò)程的理解二、實(shí)驗(yàn)內(nèi)容：掌握遞歸算法的概念和基本思想，分析并掌握“整數(shù)劃分”問(wèn)題的遞歸算法。三、實(shí)驗(yàn)題任意輸入一個(gè)整數(shù)，輸出結(jié)果能夠用遞歸方法實(shí)現(xiàn)整數(shù)的劃分。實(shí)驗(yàn)代碼#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;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第1頁(yè)。p(n-1,m,map,len+1);算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第1頁(yè)。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<<"請(qǐng)輸入一個(gè)整數(shù)：";cin>>n;intmap[max]={0};intlen=0;cout<<n<<"的劃分個(gè)數(shù)是"<<p(n,n,map,len)<<endl;return0;}算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第2頁(yè)。算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第2頁(yè)?；绢}二：棋盤(pán)覆蓋問(wèn)題一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握棋盤(pán)覆蓋問(wèn)題的算法；2、初步掌握分治算法二、實(shí)驗(yàn)題：

盤(pán)覆蓋問(wèn)題：在一個(gè)2k×2k個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其它方格不同，稱(chēng)該方格為一特殊方格，且稱(chēng)該棋盤(pán)為一特殊棋盤(pán)。在棋盤(pán)覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤(pán)上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。實(shí)驗(yàn)代碼#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);算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第3頁(yè)。 else{算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第3頁(yè)。 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)實(shí)驗(yàn)二動(dòng)態(tài)規(guī)劃算法

基本題一：最長(zhǎng)公共子序列問(wèn)題一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長(zhǎng)公共子序列問(wèn)題的算法；2、初步掌握動(dòng)態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第4頁(yè)。

若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對(duì)于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第4頁(yè)。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱(chēng)Z是序列X和Y的公共子序列。給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長(zhǎng)公共子序列。

實(shí)驗(yàn)代碼#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<<"請(qǐng)輸入X序列的元素?cái)?shù)目："; intm; cin>>m; cout<<"請(qǐng)輸入X序列："; x=newchar[m]; cin>>x; cout<<"請(qǐng)輸入Y序列的元素?cái)?shù)目："; intn; cin>>n; cout<<"請(qǐng)輸入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<<"最長(zhǎng)公共序列元素個(gè)數(shù)是："<<c[m][n]<<endl; cout<<"最長(zhǎng)公共子序列是:"; LCS(m,n,x,(int**)b); return0;}voidLCSLength(char*x,char*y,intm,intn,int**c,int**b){算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第5頁(yè)。inti,j;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第5頁(yè)。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);}算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第6頁(yè)。程序?qū)崿F(xiàn)算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第6頁(yè)?；绢}二：最大字段和問(wèn)題

一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長(zhǎng)最大字段和問(wèn)題的算法；2、進(jìn)一步掌握動(dòng)態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題

若給定n個(gè)整數(shù)組成的序列a1，a2，a3，……an，求該序列形如ai＋ai＋1＋……＋an的最大值。實(shí)驗(yàn)代碼#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};算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第7頁(yè)。 intbesti=1;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第7頁(yè)。 intbestj=1; cout<<MaxSum(8,a,besti,bestj)<<endl; cout<<besti<<endl<<bestj;}程序?qū)崿F(xiàn)實(shí)驗(yàn)三貪心算法

基本題一：多機(jī)調(diào)度問(wèn)題一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉多機(jī)調(diào)度問(wèn)題的算法；2、初步掌握貪心算法；二、實(shí)驗(yàn)題

要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。實(shí)驗(yàn)代碼#include<iostream>#include<iomanip>usingnamespacestd;typedefstructJob{intID;inttime;}Job;typedefstructJobNode{intID;inttime;JobNode*next;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第8頁(yè)。}JobNode,*pJobNode;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第8頁(yè)。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《多機(jī)調(diào)度問(wèn)題》\n"; cout<<"請(qǐng)輸入機(jī)器臺(tái)數(shù)m:"; cin>>m;Header*head=newHeader[m]; cout<<"請(qǐng)輸入作業(yè)個(gè)數(shù)n:"; cin>>n; Job*job=newJob[n]; cout<<"\n請(qǐng)按序號(hào)輸入每個(gè)作業(yè)調(diào)度所需時(shí)間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;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第9頁(yè)。}算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第9頁(yè)。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<<"臺(tái)機(jī)器上處理的工作序號(hào)："; if(M[i].next==0) continue; p=M[i].next; do{ cout<<p->ID<<''; p=p->next; }while(p!=0); }算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第10頁(yè)。}算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第10頁(yè)。voidoutSort(Job*job,intn){ cout<<"\n按工作時(shí)間由大到小為:\n時(shí)間：\t"; for(inti=0;i<n;i++) cout<<setw(4)<<job[i].time; cout<<"\n序號(hào)：\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)算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第11頁(yè)。 p=p->next;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第11頁(yè)。 p->next=jobnode; } }}程序?qū)崿F(xiàn)

實(shí)驗(yàn)四回溯算法和分支限界法基本題一：符號(hào)三角形問(wèn)題一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握符號(hào)三角形問(wèn)題的算法；2、初步掌握回溯算法；二、實(shí)驗(yàn)題圖下面都是“-”。下圖是由14個(gè)“+”和14個(gè)“-”組成的符號(hào)三角形。2個(gè)同號(hào)下面都是“+”，2個(gè)異號(hào)下面都是“-”。+

+

-

+

-

+

++

-

-

-

-

+-

+

+

+

-

-

+

+

-

-

+

-

-

-

+

在一般情況下，符號(hào)三角形的第一行有n個(gè)符號(hào)。符號(hào)三角形問(wèn)題要求對(duì)于給定的n，計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含的“+”和“-”的個(gè)數(shù)相同。實(shí)驗(yàn)代碼#include"iostream"usingnamespacestd;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第12頁(yè)。typedefunsignedcharuchar;算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第12頁(yè)。charcc[2]={'+','-'};intn,half,counter;uchar**p;longsum;voidBacktrace(intt){inti,j;if(t>n){sum++;cout<<"第"<<sum<<"個(gè):\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;} }}算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第13頁(yè)。intmain()算法設(shè)計(jì)與分析報(bào)告-全文共17頁(yè)，當(dāng)前為第13頁(yè)。{cout<<"請(qǐng)輸入第一行符號(hào)個(gè)數(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<<"個(gè)"<<endl;return0;}

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