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

..;.;.XXXX大學(xué)算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告院（系年 級(jí)姓 名：專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)研究方向：互聯(lián)網(wǎng)與網(wǎng)絡(luò)技術(shù)指導(dǎo)教師：XXXX大學(xué)目 錄題目1電梯調(diào)度 1題目描述 1算法文字描述 1算法程序流程 4算法的程序?qū)崿F(xiàn)代碼 8題目2切割木材 10題目描述 10算法文字描述 10算法程序流程 11算法的程序?qū)崿F(xiàn)代碼 15題目3設(shè)計(jì)題 17題目描述 17輸入要求 17輸出要求 17樣例輸入 17樣例輸出 17測(cè)試樣例輸入 18測(cè)試樣例輸出 18算法實(shí)現(xiàn)的文字描述 18算法程序流程 19算法的程序?qū)崿F(xiàn)代碼 20算法分析與設(shè)計(jì)課程總結(jié) 23參考文獻(xiàn) 24

題目1電梯調(diào)度3141020451（45103*4=124*4+10=264*9+2*10=5656451010，43*4=1253*4+20=32109*4+10=4646輸入要求：1nf1f2…fn，nnf1f2…fn表示需要?？康臉菍觧<=30，2<=f1<f2…fn<=31，每一個(gè)數(shù)字都用一個(gè)空格隔開。輸出要求：12算法文字描述1找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)；234解。..;.;.例如：給定金額n以及1，2,5分硬幣，求找n的最少硬幣數(shù)。1125n-1，n-2，n-5，這三種選nn-5具體的求解過程：F(1)F(2)F(1)F(2)F(3)F(4)F(5)F(6)F(n)11min{F(2)+1,F(1)+1}=2min{F(2)+1,F(3)+1}=21min{F(1)+1,F(4)+1,F(1)+1}=2…min{F(n-1)+1,F(n-2)+1,F(n-5)+1}算法設(shè)計(jì)思路及求解過程ii1在電梯運(yùn)行的每一個(gè)階段都需要作出相應(yīng)的決策，哪些乘客乘坐電梯到目的T1，T2min{max(T1,T2)}T1+1”狀態(tài)得到；T2k應(yīng)該選擇在此時(shí)下電梯（如圖1所示解。nn第k樓的乘客選擇在此下電梯…kk-1無論電梯當(dāng)前位于何處…3k層以下的乘客此刻都應(yīng)離開電梯21圖1解題結(jié)論 。使用i,jij綜上所述，可得如下狀態(tài)轉(zhuǎn)移方程：f(i,j)ij間。具體求解過程：第一步：計(jì)算初始狀態(tài)f(topFloor,1),f(topFloor,2),…,f(topFloor,n);第二步：根據(jù)狀態(tài)轉(zhuǎn)移方程計(jì)算f(i,j);第三步：根據(jù)計(jì)算最優(yōu)值時(shí)記錄的信息求解最優(yōu)解。..;.;.算法程序流程開始開始聲明布爾變量flag，初始值為真n0==nYflag=falseNi=ni=i1i>=1NY將當(dāng)前?？空?qǐng)求保存到f[i]行結(jié)束圖圖2Input函數(shù)流程圖主函數(shù)開始主函數(shù)開始調(diào)用input函數(shù)主函數(shù)結(jié)束N結(jié)果為真？Y調(diào)用solve函數(shù)求解圖圖4 main函數(shù)流程圖solve函數(shù)開始執(zhí)行solve函數(shù)開始執(zhí)行dp數(shù)組元素0和nextJ0calculate函數(shù)調(diào)用rebuildSolution函數(shù)solve函數(shù)結(jié)束圖3 solve函數(shù)流程圖i=topFloor1i=topFloor1calculate函數(shù)開始執(zhí)行輸出dp[1][n]Ni>=1YtopFloor=f[1]Ncalculate函數(shù)執(zhí)行結(jié)束j=1j=1i=i1Nj<=nYj<=n將dp[i][j]置為整型數(shù)最大值j=j+1Yjj=0調(diào)用tLeave(topFloor,1,j)函數(shù)并將計(jì)算結(jié)果保存至dp[topFloor][j]Nj++jj<=jY調(diào)用函數(shù)tStay(I,j,jj)計(jì)算留在電梯中的乘客到達(dá)目的地所需時(shí)間t1調(diào)用tLeave(I,jj+1,j)計(jì)算離開電梯的乘客到達(dá)目的地所需時(shí)間t2tmp=max(t1,t2)jj=jj+1Ndp[i][j]>tmpdp[i][j]=tmpnextJ[i][j]=jjY圖圖5 calculate函數(shù)流程圖tLeavetLeave函數(shù)開始執(zhí)行res=0l>rYtLeave函數(shù)執(zhí)行結(jié)束Nabs(currF-f[r]))*vw圖圖7 tLeave函數(shù)流程圖返回返回res值函數(shù)執(zhí)行結(jié)束tStay函數(shù)開始執(zhí)行res=0res=dp[i+1][jj]+veYj==jjNY1==iNres=0Y0==jjNres=dp[I+1][jj]+ve+st圖圖6 tStay函數(shù)流程圖算法的程序?qū)崿F(xiàn)代碼#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<limits>#include<vector>usingnamespacestd;constintmaxN=30,maxF=31;//電梯上一層樓所需時(shí)間，電梯每次?？繒r(shí)長(zhǎng)，人走一層樓所需時(shí)間constintve=4,st=10,vw=20;intn,f[maxN+1];數(shù)據(jù)讀取boolinput(){cin>>n;if(n==0)returnfalse;//注意：f[1...n]中樓層數(shù)從高到低排列for(inti=n;i>=1;i--)cin>>f[i];returntrue;}intdp[maxF+1][maxN+1],nextJ[maxF+1][maxN+1];//目前電梯在第currF層,第L層到第R層乘客離開電梯//函數(shù)返回這些離開電梯的乘客中最晚到達(dá)目的層所需時(shí)間inttLeave(intcurrF,intl,intr){if(l>r)return0;//僅需考慮兩端,無論此刻電梯在何處,第l-r層花時(shí)間最多的//一定是離電梯當(dāng)前所在樓層最遠(yuǎn)的乘客returnmax(abs(currF-f[l]),abs(currF-f[r]))*vw;}//現(xiàn)在電梯在第i層,電梯里面本來有j位乘客,離開電梯的乘客剩下jj位inttStay(inti,intj,intjj){//沒有乘客離開,電梯不停if(j==jj||i==1)returndp[i+1][jj]+ve;//所有人都離開電梯elseif(jj==0)return0;//一般情況，電梯在第i層?？縠lsereturndp[i+1][jj]+ve+st;}//voidcalculate(){//邊界：電梯在頂樓時(shí)所有人都必須下電梯inttopFloor=f[1];for(intj=1;j<=n;j++){//1,j表示停靠請(qǐng)求的編號(hào),編號(hào)越小表示編號(hào)?？繕菍釉礁遜p[topFloor][j]=tLeave(topFloor,1,j);}}for(inti=topFloor-1;i>=1;i--){//i表示電梯此刻所在位置for(intj=1;j<=n;j++){dp[i][j]=numeric_limits<int>::max();for(intjj=0;jj<=j;jj++){//計(jì)算離開電梯的人和留在電梯里面的人中到達(dá)目的地最晚的inttmp=max(tStay(i,j,jj),tLeave(i,jj+1,j));//在此求解花費(fèi)時(shí)間最短的乘客if(dp[i][j]>tmp){dp[i][j]=tmp;//jj以前的乘客均離開電梯nextJ[i][j]=jj;}}}}cout<<dp[1][n]<<endl;}//重構(gòu)最優(yōu)解voidrebuildSolution(){vector<int>stops;intj=nextJ[1][n],topFloor=f[1];for(inti=2;i<=topFloor;i++){if(nextJ[i][j]!=j){j=nextJ[i][j];if(j==0)break;}}cout<<stops.size();for(inti=0;i<stops.size();i++){cout<<""<<stops[i];}cout<<endl;}voidsolve(){memset(dp,0,sizeof(dp));memset(nextJ,0,sizeof(nextJ));calculate();rebuildSolution();}

題目2切割木材時(shí)每次切割時(shí)由于鋸子本身有一定的寬度，因此每切割一次就會(huì)浪費(fèi)掉一些木料。請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序使木匠能夠用最少的木材切割出所需的木塊。輸入描述：L（0<L<=30000）,W（0<W<=1000）,其后的若干個(gè)整數(shù)分別表示制作家具時(shí)需要的木塊的長(zhǎng)度。輸出描述：每個(gè)測(cè)試樣例輸出一行，為一個(gè)整數(shù)N，表示制作家具時(shí)需要購(gòu)買的木塊的數(shù)量。樣例輸入：10001002502505006501000100050200250250500650970樣例輸出：34算法文字描述Step1：聲明求解結(jié)果變量res=0，剩余未切割木料數(shù)量count=n，當(dāng)前已切割木料長(zhǎng)度和cw=0，目前最大切割長(zhǎng)度bestW=0，求解標(biāo)記數(shù)組visited[n]，當(dāng)前最優(yōu)求解數(shù)組nVisited[n]，問題求解狀態(tài)記錄數(shù)組res_arr[n]，鋸口寬度sw；Step2：當(dāng)剩余未切割木料數(shù)量count0和求解。當(dāng)i<n-1時(shí)，搜索左子樹的條件：當(dāng)前節(jié)點(diǎn)未被訪問且cw+data[i]<=w+sw，訪問左子樹時(shí)第i層相應(yīng)節(jié)點(diǎn)時(shí)將相應(yīng)訪問標(biāo)記visited[i]置為true，遞歸搜索該節(jié)點(diǎn)的左子樹；遞歸搜索右子樹時(shí)，將當(dāng)前節(jié)點(diǎn)訪問標(biāo)記visited[i]置為false；Step3：當(dāng)i>n-1nVisitedbestWStep4：1res_arrcount，res++，2,3,4count=0。算法程序流程開始開始調(diào)用input函數(shù)讀取測(cè)試用例讀取數(shù)據(jù)成功與否？Y 函數(shù)求解N輸出結(jié)果res值結(jié)束圖圖8main函數(shù)流程圖開始開始flag=true,n=0讀取原材料長(zhǎng)度w0==wYflag=falseNNYtrue==flagNY返回flag值程序結(jié)束讀取木材長(zhǎng)度，并保存至數(shù)組data第n個(gè)位置ch=='\n'n=n+1讀取下一個(gè)字符ch圖圖9 input函數(shù)流程圖開始開始res=0,count=ncount>0N返回res值結(jié)束Yres=res+1cw=0,count=0,bestW=0,i=0調(diào)用backtrack(0,0)函數(shù)求解Ni<nYfalse==res_arr[i]YN res_arr[i]=nVisited[i]i=i+1false==res_arr[i]NYcount=count+1圖10 solve函數(shù)流程圖開始開始i>n1YbestW<cwNYfalse==res_arr[i]bestW=cwYi=0cw+data[i]+k*sw<=wYNi<ni=i+1Nvisited[i]=true,cw+=data[i],k=k+1Y遞歸調(diào)用backtrack(i+1,k)nVisited[i]=visited[i]Ncw=data[i],k=k1visited[i]=falseN遞歸調(diào)用backtrack(i+1,k)結(jié)束圖11 backtrack函數(shù)流程圖算法的程序?qū)崿F(xiàn)代碼#include<stdio.h>#include<malloc.h>#include<cstring>#defineMAX_SAMPLE_LENGTH50/*回溯法求解*/int*in=(int*)malloc(MAX_SAMPLE_LENGTH*sizeof(int));int*data=(int*)malloc(MAX_SAMPLE_LENGTH*sizeof(int));bool*visited=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool));bool*nVisited=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool));bool*res_arr=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool));intw; //原材料長(zhǎng)度intn; //數(shù)據(jù)元素個(gè)數(shù)intsw; //鋸口寬度intcw; //當(dāng)前已鋸木頭長(zhǎng)度和intres; //求解結(jié)果intbestW;//當(dāng)前求解最大值boolinput(){boolflag=true;//初始化數(shù)據(jù)保存數(shù)組memset(in,0,MAX_SAMPLE_LENGTH*sizeof(int));memset(visited,false,MAX_SAMPLE_LENGTH*sizeof(bool));memset(res_arr,false,MAX_SAMPLE_LENGTH*sizeof(bool));memset(nVisited,false,MAX_SAMPLE_LENGTH*sizeof(bool));//記錄輸入數(shù)據(jù)個(gè)數(shù)n=0;//讀取數(shù)據(jù)-原材料(木頭)長(zhǎng)度scanf("%d",&w);if(0==w)flag=false;//鋸口寬度scanf("%d",&sw);while(flag){scanf("%d",data+n);n++;charch=getchar();if(ch=='\n')break;}returnflag;}voidbacktrack(inti,intk){if(i>n-1){if(bestW<cw){//記錄最優(yōu)值bestW=cw;//記錄當(dāng)前最優(yōu)解for(inti=0;i<n;i++){nVisited[i]=visited[i];}}returnreturn;}//進(jìn)入右子樹條件if(!res_arr[i]&&cw+data[i]+k*sw<=w){//記錄當(dāng)前已鋸木頭數(shù)量k++;//進(jìn)入右子樹實(shí)際操作cw+=data[i];//訪問標(biāo)記visited[i]=true;cw-=data[i];k--;}visited[i]=false;backtrack(i+1,k);}intsolve(int*data,intn){res=0;//求解結(jié)果初始化intcount=n;while(count>0){//初始化,cw當(dāng)前已鋸木頭長(zhǎng)度和,//count剩余未鋸木頭數(shù)量,bestW本次求解最大長(zhǎng)度和cw=0,count=0,bestW=0;backtrack(0,0);for(inti=0;i<n;i++){//更新待解決問題狀態(tài)if(!res_arr[i])res_arr[i]=nVisited[i];//剩余未求解元素個(gè)數(shù)if(!res_arr[i]) count++;}//記錄求解結(jié)果res++;}returnres;}intmain(){while(input()){solve(data,n);printf("\n%d\n",res);}}..;.;.

題目3設(shè)計(jì)題給定一個(gè)數(shù)塔，如12所示。在此數(shù)塔中，從頂部出發(fā)，在每一節(jié)點(diǎn)可以大。

圖12數(shù)塔點(diǎn)的數(shù)值。輸出要求第一行輸出路徑數(shù)值和，第二行輸出具體路徑。樣例輸入513111240716614158127132411樣例輸出91(1,1)->(2,1)->(3,1)->(4,2)->(5,3)測(cè)試樣例輸入7119812107415231917821121632252428312785910111315測(cè)試樣例輸出113(1,1)->(2,1)->(3,2)->(4,3)->(5,3)->(6,4)->(7,5)算法實(shí)現(xiàn)的文字描述動(dòng)態(tài)規(guī)劃采用自底向上逐層分階段決策146，4512，4+56+12=1814，4513，4+513+14=27……這樣實(shí)際上將5階數(shù)塔變?yōu)?階數(shù)塔問題了。逐層向上遞推，最后得到問題的最優(yōu)解data矩陣?？梢暂^為容易地得到問題狀態(tài)轉(zhuǎn)移方程：Step1：聲明變量數(shù)塔層數(shù)n，待處理數(shù)據(jù)節(jié)點(diǎn)數(shù)值數(shù)組data[n][n],結(jié)果（狀態(tài)）數(shù)組d[n][n];Step2：n，datadStep3：n（狀態(tài)）數(shù)組值；Step4：d(i,j)，in-11，j1Step5：d(1,1)；Step6：根據(jù)數(shù)組d求解具體路徑并輸出。..;.;.算法程序流程開始開始結(jié)束輸入n為數(shù)組data分配內(nèi)存空0函數(shù)打印求解結(jié)果分配內(nèi)存空0index=0,i=0函數(shù)求解i<nNYi=i+1j=0Nj<nj=j+1Yindex=i*n+jij存至data[index]圖13main函數(shù)流程圖開始開始index1=0,index2=0i=0i<nNi=n-2i=i+1Yi>=0Ndp[index1]=data[index1]index1=(n-1)*n+i結(jié)束Yj=0j=j+1j<nNi=i-1dp[index2]=temp_max+data[index2]Yex1],dp[index1+1])index2=i*n+j圖14 tower_walk函數(shù)流程圖算法的程序?qū)崿F(xiàn)代碼#include#include<stdio.h>#include<cstring>#include<malloc.h>#include<math.h>usingnamespacestd;int*data=NULL;//存儲(chǔ)數(shù)塔原始數(shù)據(jù)int*dp=NULL;//狀態(tài)值記錄intn;//塔的層數(shù)/*動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)數(shù)塔求解*/voidtower_walk(){intindex1=0,index2=0;//dp初始化for(inti=0;i<n;++i){index1=(n-1)*n+i;dp[index1]=data[index1];}inttemp_max;for(inti=n-2;i>=0;--i){for(intj=0;j<=i;++j){//使用遞推公式計(jì)算dp的值index1=(i+1)*n+j;index2=i*n+j;temp_max=(dp[index1]>dp[in