算法分析與設(shè)計試驗報告

本文格式為Word版，下載可任意編輯——算法分析與設(shè)計試驗報告

算法分析與設(shè)計——試驗報告

課程名稱：算法分析與設(shè)計學(xué)號：08220429姓名：王洪朋專業(yè)班級：（非師范）計算機科學(xué)與技術(shù)081學(xué)院：數(shù)理與信息工程學(xué)院指導(dǎo)老師：宋炯

數(shù)理與信息工程學(xué)院

算法分析與設(shè)計——試驗報告

試驗一遞歸與分治策略

一、試驗?zāi)康?/p>

1、熟練把握遞歸與分治策略的思想并應(yīng)用其解決實際問題。2、利用遞歸與分治策略的思想解決Gray碼問題。二、試驗要求

Gray碼是一個長度為2n的序列。序列中無一致元素，每個元素都是長度為n位的串，相鄰元素恰好只有1位一致。用分治策略設(shè)計一個算法對任意的n構(gòu)造相應(yīng)的Gray碼。三、算法實現(xiàn)

#includeiostream{usingnamespacestd;couta[i];voidprint(inta[],intlength);}voidgray(intn,inta[],intlength);coutendl;intmain(void)}{intn;voidgray(intn,inta[],intlength)coutPleaseinputn:;{cinn;if(n==0)inta[n];{for(inti=0;in;i++)a[n]=1-a[n];{print(a,length);a[i]=0;}}elseprint(a,n);{gray(n-1,a,n);gray(n-1,a,length);return0;a[n]=1-a[n];}print(a,length);voidprint(inta[],intlength)gray(n-1,a,length);{}for(inti=length-1;i=0;i--)}試驗運行結(jié)果：

四、試驗總結(jié)

依照分治策略設(shè)計，利用遞歸方法構(gòu)造Grey碼。長度為n的Grey碼字符串，前半部分只要在長度為n-1的Grey碼前添0就可；后半部分令其次位為1，后幾位為前半部分的逆順序就可。

算法分析與設(shè)計——試驗報告

試驗二動態(tài)規(guī)劃

一、試驗?zāi)康?/p>

1、把握動態(tài)規(guī)劃的基本思想并應(yīng)用其解決實際問題。2、利用動態(tài)規(guī)劃的基本思想解決N堆石子合并問題。二、試驗要求

在一個圓形操場的四周擺放N堆石子，現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。試設(shè)計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分，并分析算法的計算繁雜性。

三、算法實現(xiàn)

#includeiostream#includestring#defineN500#defineoo2000000000#defineMIN(a,b)(a)(b)?(a):(b)#defineMAX(a,b)(a)(b)?(a):(b)usingnamespacestd;

typedefstruct{intc,d;}Node;intn;

intv[N];//每堆石頭的個數(shù)intsave[N];//輸出最優(yōu)解的具體合并需要隨時改變v的值，所以為了同時輸出最小，最大的合并，在完成一個任務(wù)之后需要回溯Nodef[N][N];//f[i][j]存儲最優(yōu)解，同時存儲合并線索

intsum[N][N];//sum[i][j]表示從第i堆起，順時針數(shù)j堆的石子總數(shù)

//遞歸打印子序列f[i][j]的合并過程voidPrint(inti,intj){intk,x;if(j!=1){Print(i,f[i][j].d);

x=(i+f[i][j].d-1)%n+1;Print(x,j-f[i][j].d);for(k=1;k=n;k++)if(v[k]0){

if(i==k||x==k)cout*v[k];//*號表示這次操作合并該堆elsecoutv[k];}

coutendl;v[i]=v[i]+v[x];

v[x]=-v[x];//置為-類似于刪除}}

//flag=0求最小得分,flag=1求最大得分voidSolve(intflag){

inti,j,k,x,t,result;

for(i=1;i=n;i++)//僅含一堆石子的序列不存在合并

f[i][1].c=f[i][1].d=0;

for(j=2;j=n;j++){//順推含2堆，3堆...n堆石子的各子序列的合并方案for(i=1;i=n;i++){t=sum[i][j];

if(flag==0)f[i][j].c=oo;//求最小得分，那么需要初始化為oo

elsef[i][j].c=0;//求最大得分，那么需要初始化為0for(k=1;k=j-1;k++){x=(i+k-1)%n+1;

if((flag==0f[i][k].c+f[x][j-k].c+tf[i][j].c)||(flag!=0f[i][k].c+f[x][j-k].c+tf[i][j].c)){f[i][j].c=f[i][k].c+f[x][j-k].c+t;f[i][j].d=k;}}}}

result=f[1][n].c;k=1;for(i=2;i=n;i++)

if((flag==0f[i][n].cresult)||(flag!=0

算法分析與設(shè)計——試驗報告

f[i][n].cresult)){

result=f[i][n].c;k=i;}

cout(flag==0?最小:最大)得分是resultendl;

cout合并過程如下:endl;Print(k,n);

coutsum[1][n]endl;}intmain(){inti,j;

cout輸入石子堆數(shù)：endl;cinn;

cout輸入每堆石子數(shù)：endl;for(i=1;i=n;i++)cinv[i];memcpy(save+1,v+1,n*sizeof(v[1]));for(i=1;i=n;i++)sum[i][1]=v[i];for(j=2;j=n;j++)for(i=1;i=n;i++)

sum[i][j]=v[i]+sum[i%n+1][j-1];Solve(0);

memcpy(v+1,save+1,n*sizeof(v[1]));Solve(1);return0;}

試驗運行結(jié)果：

四、試驗總結(jié)

動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，但是經(jīng)分解得到的子問題往往不是相互獨立的。不同子問題的數(shù)目往往只有多項式量級。在用分治法求解時，有些子問題被重復(fù)計算了大量次。假使能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。

試驗三回溯法

一、試驗?zāi)康?/p>

1、了解回溯法的基本思想。

2、運用回溯法解決最小重量機器設(shè)計問題。

算法分析與設(shè)計——試驗報告

二、試驗要求

最小重量機器設(shè)計問題。設(shè)某一機器由n個部件組成，每一種部件可以從m個不同的供應(yīng)商處購得。設(shè)wij是從供應(yīng)商j處購得的部件i的重量，cij是相應(yīng)的價格。試設(shè)計一個算法，給出總價格不超過c的最小重量機器設(shè)計。三、算法實現(xiàn)

#includeiostreamusingnamespacestd;#defineN50classMinWmechine{

intn;//部件個數(shù)intm;//供應(yīng)商個數(shù)intCOST;//題目中的Cintcw;//當(dāng)前的重量intcc;//當(dāng)前花費intbestw;//當(dāng)前最小重量intbestx[N];intsavex[N];intw[N][N];intc[N][N];public:MinWmechine();

voidmachine_plan(inti);voidprinout();};

MinWmechine::MinWmechine(){

cw=0;//當(dāng)前的重量cc=0;//當(dāng)前花費

bestw=-1;//當(dāng)前最小重量bestx[N];savex[N];

cout請輸入部件個數(shù)：;cinn;

cout請輸入供應(yīng)商個數(shù)：;cinm;

cout請輸入總價格不超過：;cinCOST;

for(intj=0;jm;j++){

for(inti=0;in;i++){

cout請輸入第j+1個供應(yīng)商的第i+1個部件的重量：;cinw[i][j];

cout請輸入第j+1個供應(yīng)商的第i+1個部件的價格：;cinc[i][j];

if(w[i][j]0||c[i][j]0){

cout重量或價錢不能為負(fù)數(shù)！\n;i=i-1;}}}}

voidMinWmechine::machine_plan(inti){

if(i=n){

if(cwbestw||bestw==-1){

bestw=cw;

for(intj=0;jn;j++)//把當(dāng)前搜過的路徑記錄下來來

savex[j]=bestx[j];}return;}

for(intj=0;jm;j++)//依次遞歸嘗試每個供應(yīng)商{

if(cc+c[i][j]COST){

cc+=c[i][j];cw+=w[i][j];bestx[i]=j;machine_plan(i+1);bestx[i]=-1;

算法分析與設(shè)計——試驗報告

cc-=c[i][j];cw-=w[i][j];}}}

voidMinWmechine::prinout(){

inti,j,ccc=0;for(j=0;jm;j++){

for(i=0;in;i++){

cout第j+1供應(yīng)商的第i+1部件重量：w[i][j]價格：c[i][j]\n;}}

for(j=0;jn;j++){

bestx[j]=-1;

}machine_plan(0);

cout\n最小重量機器的重量是:bestwendl;for(intk=0;kn;k++){

cout第k+1部件來自供應(yīng)商savex[k]+1\n;ccc+=c[k][save