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

《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告網(wǎng)絡(luò)10-1李俊實(shí)驗(yàn)一分治與遞歸基本題一：基本遞歸算法四、程序清單：#include<iostream>usingnamespacestd;intq(intn,intm) { if((n<1)||(m<1))return0; if((n==1)||(m==1))return1; if(n<m)returnq(n,n); if(n==m)return q(n,m-1)+1; returnq(n,m-1)+q(n-m,m); }intmain(){ inta,b,c; intq(intn,intm); cout<<"pleaseinputaandb"<<endl; cin>>a>>b; c=q(a,b); cout<<"整數(shù)的劃分為："<<c<<endl; return0;}測(cè)試數(shù)據(jù)及結(jié)果如下圖所示：基本題二：棋盤覆蓋問題程序清單：#include<iostream>#include<iomanip>usingnamespacestd;intBoard[1024][1024];//模擬棋盤inttile=0;//骨牌編號(hào),從0開始voidChessBoard(inttr,inttc,intdr,intdc,intsize);voidOutputBoard(intsize);intmain(){intsize,dr,dc;cout<<"請(qǐng)輸入方陣的規(guī)格k(方陣為k*k,須為2的冪):";cin>>size;cout<<"請(qǐng)輸入特殊方格的行號(hào)(矩陣下標(biāo)由零開始計(jì)算,即0~k-1):";cin>>dr;cout<<"請(qǐng)輸入特殊方格的列號(hào)(矩陣下標(biāo)由零開始計(jì)算,即0~k-1):";cin>>dc;ChessBoard(0,0,dr,dc,size);//覆蓋特殊棋盤OutputBoard(size);//輸出覆蓋后的棋盤return0;}voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌號(hào)s=size/2;//分割棋盤//覆蓋左角子棋盤if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盤中ChessBoard(tr,tc,dr,dc,s);else{//本棋盤中沒有特殊方格Board[tr+s-1][tc+s-1]=t;//把三格板t放在右下角,將此棋盤轉(zhuǎn)化為特殊棋盤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;//把三格板t放在左下角,將此棋盤轉(zhuǎn)化為特殊棋盤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;//把三格板t放在右上角,將此棋盤轉(zhuǎn)化為特殊棋盤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;//把三格板t放在左上角,將此棋盤轉(zhuǎn)化為特殊棋盤ChessBoard(tr+s,tc+s,tr+s,tc+s,s);//覆蓋其余部分}}voidOutputBoard(intsize){inti,j;for(i=0;i<size;i++){for(j=0;j<size;j++)cout<<setw(5)<<Board[i][j];cout<<endl;}}測(cè)試數(shù)據(jù)及結(jié)果如下圖所示：提高題一：二分搜索設(shè)a[0:n-1]是一個(gè)已排好序的數(shù)組。請(qǐng)改寫二分搜索算法，使得當(dāng)搜索元素x不在數(shù)組中時(shí)，返回小于x的最大元素的位置I和大于x的最大元素位置j。當(dāng)搜索元素在數(shù)組中時(shí)，I和j相同，均為x在數(shù)組中的位置。#include<iostream>usingnamespacestd;#definesize20intarray[size],n;boolBinarySearch(inta[],intn,intx);intmain(){ cout<<"請(qǐng)輸入所要查找的序列一共有幾個(gè)數(shù):";cin>>n; cout<<"請(qǐng)依次輸入查找序列,用空格隔開:"; for(intx=0;x<n;x++) cin>>array[x]; cout<<"請(qǐng)輸入您所要查找的數(shù):"; cin>>x;BinarySearch(array,n,x);return0;}boolBinarySearch(inta[],intn,intx){inti,j;intleft=0;intright=n-1;while(left<=right){intmid=(left+right)/2;if(x==a[mid]){i=j=mid;cout<<"您所要查找的數(shù)在該序列內(nèi),它的序號(hào)是"<<i<<endl;returntrue;}if(x>a[mid])left=mid+1;elseright=mid-1;}i=right;j=left;cout<<"您所要查找的數(shù)不在該序列內(nèi)，小于它的最大元素的位置為"<<i<<","<<"大于它的最小元素位置為"<<j;cout<<endl;returnfalse;}運(yùn)行結(jié)果實(shí)驗(yàn)二動(dòng)態(tài)規(guī)劃算法基本題一：最長公共子序列問題

若給定序列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}。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。#include<iostream>#include<stdlib.h>#include<string.h>usingnamespacestd;#defineN20voidLCSLength(intm,intn,charx[N+1],chary[N+1],intc[N+1][N+1],intb[N+1][N+1]){ inti,j; 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]==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; } } } for(ints=1;s<=m;s++) { for(intt=1;t<=n;t++) { cout<<c[s][t]; }cout<<endl; } cout<<"所得最大公共子串長度："<<c[m][n]<<endl;}voidLCS(inti,intj,charx[N+1],intb[N+1][N+1]){ if(i==0||j==0)return; if(b[i][j]==1) { LCS(i-1,j-1,x,b); cout<<x[i]; } elseif(b[i][j]==2) { LCS(i-1,j,x,b); } else { LCS(i,j-1,x,b); } }intmain(){ charstr1[N+1],str2[N+1]; intc[N+1][N+1]; intb[N+1][N+1]; intstr1_len,str2_len; cout<<"請(qǐng)依次輸入兩個(gè)字符串str1、str2"<<endl; cout<<"str1:"<<endl; cin>>str1+1; cout<<"str2:"<<endl; cin>>str2+1; str1_len=strlen(str1+1);cout<<"str1的長度："<<str1_len<<endl;str2_len=strlen(str2+1);cout<<"str2的長度："<<str2_len<<endl;LCSLength(str1_len,str2_len,str1,str2,c,b);LCS(str1_len,str2_len,str1,b); cout<<endl; return0;}運(yùn)行結(jié)果基本題二：最大字段和問題

若給定n個(gè)整數(shù)組成的序列a1，a2，a3，……an，求該序列形如ai＋ai＋1＋……＋an的最大值。#include<iostream>usingnamespacestd;intmaxsum(intn,inta[]);intmain(){ intarray[20],n; cout<<"請(qǐng)輸入所要求解的個(gè)數(shù):"; cin>>n; cout<<"請(qǐng)依次輸入各數(shù)，用空格隔開:"<<endl; for(intx=0;x<n;x++) cin>>array[x];maxsum(n,array); return0;}intmaxsum(intn,inta[]){ intsum=0,b=0; for(inti=0;i<=n;i++) {if(b>0)b=b+a[i]; elseb=a[i]; if(b>sum)sum=b; } cout<<"最大字段和為:"<<sum; cout<<endl; return0;}運(yùn)行結(jié)果實(shí)驗(yàn)三貪心算法

基本題一：多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。#include<iostream>usingnamespacestd;//作業(yè)typedefstructJob{ intID;//作業(yè)號(hào) inttime;//作業(yè)花費(fèi)的時(shí)間}Job;//作業(yè)鏈表的節(jié)點(diǎn)typedefstructJobNode{ intID; inttime; JobNode*next;}JobNode,*pJobNode;//鏈表的表頭typedefstructHeader{ ints;//作業(yè)完成的時(shí)間 pJobNodenext;}Header,*pHeader;//在m臺(tái)機(jī)器中找到最先完成作業(yè)的一臺(tái)intSelectMin(Header*M,intm){ intk=1,i; for(i=1;i<=m;i++) { if(M[i].s<M[k].s) { k=i; } } returnk;}//從大到小排序voidSort(Job*pData,intnum){ JobTemp; inti,j;for(i=1;i<num;i++) { for(j=i+1;j<=num;j++) { if(pData[j].time>pData[i].time) { Temp=pData[i];pData[i]=pData[j];pData[j]=Temp; } } }}//貪心算法voidGreedy(Job*p,intm,intn){ HeaderH[100]; inti,temp,sum; for(i=1;i<=m;i++) { H[i].s=0; } for(i=1;i<=m;i++) { H[i].s=H[i].s+p[i].time; } for(i=m+1;i<=n;i++) { temp=SelectMin(H,m); H[temp].s=H[temp].s+p[i].time; } sum=H[1].s; for(i=1;i<=m;i++) { if(sum<H[i].s) { sum=H[i].s; } } cout<<"加工時(shí)間最短為"<<sum<<endl;}voidmain(){ intm,n,i; Job*job; cout<<"機(jī)器臺(tái)數(shù)m："<<endl; cin>>m; cout<<"作業(yè)數(shù)n："<<endl; cin>>n;job=newJob[n]; for(i=1;i<=n;i++) { cout<<"第"<<i<<"個(gè)作業(yè)所需要的時(shí)間："<<endl; cin>>job[i].time; job[i].ID=i; } Sort(job,n); Greedy(job,m,n);}運(yùn)行結(jié)果:提高題二：汽車加油問題

一輛汽車加滿油后可以行駛N千米。旅途中有若干個(gè)加油站。若要使沿途的加油次數(shù)最少，設(shè)計(jì)一個(gè)有效的算法，指出應(yīng)在那些加油站?？考佑?。并證明你的算法能產(chǎn)生一個(gè)最優(yōu)解。#include<iostream.h>intmain(){intn,k,way[10];intsum=0,count=0,flag=1;cout<<"加滿油后可行駛k公里，k為:";cin>>k;cout<<"沿途有n個(gè)加油站,n為:";cin>>n;cout<<"依次輸入兩個(gè)加油站之間的距離:";for(inti=0;i<=n;++i)cin>>way[i];for(intj=0;j<=n;++j){sum+=way[j];if(sum>n){++count;sum=way[j];}if(way[j]>n){flag=0;break;}}if(flag)cout<<"最少加油次數(shù)為:"<<count<<endl;elsecout<<"NoSolution";return0;}運(yùn)行結(jié)果

實(shí)驗(yàn)四回溯算法和分支限界法基本題一：符號(hào)三角形問題下面都是“-”。下圖是由14個(gè)“+”和14個(gè)“-”組成的符號(hào)三角形。2個(gè)同號(hào)下面都是“+”，2個(gè)異號(hào)下面都是“-”。+

+

-

+

-

+

++

-

-

-

-

+-

+

+

+

-

-

+

+

-

-

+

-

-

-

+

在一般情況下，符號(hào)三角形的第一行有n個(gè)符號(hào)。符號(hào)三角形問題要求對(duì)于給定的n，計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含的“+”和“-”的個(gè)數(shù)相同。#include<iostream.h>classTriangle{friendintComputer(int);private:voidBacktrack(intt);intn,//第1行符號(hào)的個(gè)數(shù)half,//每個(gè)三角形總符號(hào)數(shù)的一半count,//統(tǒng)計(jì)減號(hào)的個(gè)數(shù)**p;//指向三角形的二維指針longsum;//統(tǒng)計(jì)符合條件的的三角形的個(gè)數(shù)};voidTriangle::Backtrack(intt){inti,j,k,s,f;if((count>half)||(t*(t-1)/2-count>half))return;//如果加號(hào)或減號(hào)的個(gè)數(shù)大于符號(hào)三角形中總符號(hào)數(shù)的一半則退出函數(shù)if(t<=n)//回溯條件直到nfor(i=0;i<2;i++){p[1][t]=i;count+=i;for(j=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//判斷下行符號(hào)count+=p[j][t-j+1];}if(t>=n){//輸出符合條件的三角形f=0;for(j=1;j<=t;j++)for(k=1;k<=t-j+1;k++)f+=p[j][k];if(f==half){//如果減號(hào)是總符號(hào)數(shù)的一半則輸出并將sum加1cout<<"第"<<++sum<<"個(gè)三角形"<<'\n';for(j=1;j<=t;j++){for(s=1;s<j;s++)cout<<"";//2個(gè)空格for(k=1;k<=t-j+1;k++){if(p[j][k]==1)cout<<"-";//3個(gè)空格elsecout<<"+";//3個(gè)空格}cout<<'\n';}cout<<'\n';}}Backtrack(t+1);//回溯for(j=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}intComputer(intn)//友元函數(shù)調(diào)用Triangle類的成員函數(shù){inti,j;TriangleX;X.n=n;X.count=0;X.sum=0;X.half=n*(n+1)/2;if(X.half%2==1)return0;//如果是一個(gè)三角形符號(hào)的總數(shù)是奇數(shù)則不符合條件，返回0X.half=X.half/2;int**p=newint*[n+1];//分配新行for(i=0;i<=n;i++)p[i]=newint[n+1];//分配新列for(i=0;i<=n;i++)for(j=0;j<=n;j++)p[i][j]=0;//給p所指向的二維數(shù)組賦值為0X.p=p;X.Backtrack(1);returnX.sum;}voidmain(){inti,n;cout<<"請(qǐng)輸入第一行的符號(hào)個(gè)數(shù)：";cin>>i;n=Computer(i);cout<<"共有"<<n<<"個(gè)符號(hào)三角形"<<endl;}運(yùn)行結(jié)果基本題二：0—1背包問題給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?#include<iostream.h>intn,c,bestp;//物品的個(gè)數(shù)，背包的容量，最大價(jià)值intp[10000],w[10000],x[10000],bestx[10000];//物品的價(jià)值，物品的重量