算法分析與設計課程設計報告2

XXXX算法設計與分析課程設計報告院年級：姓名：專業(yè)：計算機科學與技術(shù)研究方向：互聯(lián)網(wǎng)與網(wǎng)絡技術(shù)指導教師：XXXX大學目錄題目1電梯調(diào)度..........................................1題目2切割木材.........................................10..................................................................................................................11題目3設計題...........................................17算法分析與設計課程總結(jié)..................................23參考文獻................................................24II題目1電梯調(diào)度1.1題目描述一棟高達31層的寫字樓只有一部電梯，其中電梯每走一層需花費4秒，并且在每一層樓?？康臅r間為1020454樓、5樓和10靠則三位乘客到達辦公室所需要的時間為3*4=12秒，則最后一位乘客到達辦公室的時間為56秒，相應的停靠計劃為4510均停10，這樣到第4樓的乘客所需時間為3*4=12秒，到第5樓的乘客所需時間為3*4+20=32秒，到第10樓的乘客所需時間為9*4+10=46秒，即最后到達目的樓層的顧客所需時間為46秒。輸入要求：輸入的第1行為整數(shù)nf1f2…fn，其中n表示有n層樓需要?？浚琻=0表示沒有更多的測試用例，程序終止運行。f1f2…fn表示需要?？康臉菍虞敵鲆螅?2行輸出?？看螖?shù)和相應的?？糠桨?，每一個數(shù)字用一個空格隔開。1.2算法文字描述程序?qū)崿F(xiàn)的算法思想，將待求解問題分解成若干個子問題，先求解子問題，錄所有已解決的子問題的答案。不管子問題以后是否被使用，只要他被計算過，○○具體步驟如下：1找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)；2遞歸地定義最優(yōu)值；○○3以自底向上的方式計算最優(yōu)值；4解。1例如：給定金額n以及1，2,5分硬幣，求找n的最少硬幣數(shù)。對于大于1分的找零理所當然可以找零12分和5分的找零與此類似，那么找零時就有三種選擇，即找零后剩余金額為n的最優(yōu)找零方案包含了金額n-5的最優(yōu)找零方案，于是可得如下狀態(tài)轉(zhuǎn)移方程：(?+1()={(?+1(?+1具體的求解過程：初始化F(1)=1,F(2),F(5)=1F(n)min{F(n-1)+1,F(n-2)+1,F(n-5)+1}算法設計思路及求解過程以將“電梯還剩i個人”表述成“電梯里面的乘客還要去i1層開始向上運行，任意時刻的狀態(tài)都可以由“電梯當前所處樓層”和“電梯里1在電梯運行的每一個階段都需要作出相應的決策，哪些乘客乘坐電梯到目的層，哪些乘客選擇爬樓梯到達目的地。決策后，電梯里面的乘客被分成兩部分：2為T1，離開電梯的各自到達目的地所需時間為T2，則min{max(T1,T2)}就是當前狀態(tài)的最優(yōu)解，其中T1可以由“當前層數(shù)+1”和“決策后剩下的人”確定的狀態(tài)得到；T2則為下電梯走樓梯到達目的走樓梯最多的那一位乘客所花時間。如果去第k層的乘客選擇在當前樓層下電梯，那么第層的乘客也應該選擇在此時下電梯（如圖1解。nkk321圖1為了進一步處理停靠請求，對樓層按從高到低進行排序，并以此進行編號，i,j兩個參數(shù)表示電梯當前的狀態(tài)，即電梯在第i層，電梯中有j位乘客。綜上所述，可得如下狀態(tài)轉(zhuǎn)移方程：f(i,j)=t2)}{=(+1,)+=max{|[]?|?+≤≤}+1≤≤f(i,j)表示電梯在第ij個人都到達目的地所需要的最短時間。具體求解過程：第一步：計算初始狀態(tài)f(topFloor,1),f(topFloor,2),…,f(topFloor,n);第二步：根據(jù)狀態(tài)轉(zhuǎn)移方程計算f(i,j);第三步：根據(jù)計算最優(yōu)值時記錄的信息求解最優(yōu)解。31.3算法程序流程nNYYN返回圖24NY圖4solve函數(shù)開始執(zhí)行初始化dp數(shù)組元素值為0和nextJ數(shù)組元素為0調(diào)用calculate函數(shù)調(diào)用rebuildSolution函數(shù)solve函數(shù)結(jié)束圖35YNNNYYNYNY圖56NYres=max(abs(currF-f[l]),abs(currF-f[r]))*vw圖7YNYNYN圖671.4算法的程序?qū)崿F(xiàn)代碼,maxF=31;,st=,vw=20;n,f[maxN+)false;}dp[maxF+][maxN+],nextJ[maxF+][maxN+1,LR,,}i,j,(j==jji==1)][jj]所有人都離開電梯,0);i表示?？空埱蟮木幪柧幪栐叫”硎揪幪柾？繕菍釉礁?dp[topFloor][j]=tLeave(topFloor,,j);8}表示電梯此刻所在位置計算離開電梯的人和留在電梯里面的人中到達目的地最晚的{jj}}}}cout<<dp[}int>][n],topFloor=f[}}}9題目2切割木材2.1題目描述請設計一個程序使木匠能夠用最少的木材切割出所需的木塊。輸入描述：一個整數(shù)為所購買的木塊的長度（0<L<=30000）,第二個整數(shù)為鋸子的寬度W（0<W<=1000）,其后的若干個整數(shù)分別表示制作家具時需要的木塊的長度。輸出描述：每個測試樣例輸出一行，為一個整數(shù)N，表示制作家具時需要購買的木塊的數(shù)量。樣例輸入：10001002502505006501000100050200250250500650970樣例輸出：342.2算法文字描述此題目是裝載問題的一個變種，與裝載問題不同的是此問題沒有給出“船”Step1：聲明求解結(jié)果變量res=0，剩余未切割木料數(shù)量count=n，當前已切割木料長度和visited[n]，當前最優(yōu)求解數(shù)組sw；Step2：當剩余未切割木料數(shù)量count大于0時，利用回溯法進行最大子集i<n-1cw+data[i]<=w+sw，10訪問左子樹時第i層相應節(jié)點時將相應訪問標記visited[i]置為true，遞歸搜索該節(jié)點的左子樹；遞歸搜索右子樹時，將當前節(jié)點訪問標記visited[i]置為false；Step3：當i>n-1時，獲得一種切割方案，若此次求解結(jié)果優(yōu)于已得求解結(jié)nVisitedbestW的值；Step4：利用回溯法完成1次木料切割后，更當前問題求解狀態(tài)res_arr數(shù)組，根據(jù)最新的求解狀態(tài)更新未切割木料數(shù)量count，同時res++，若count=0則求解結(jié)束，否則重復2,3,4直至count=0。2.3算法程序流程Y值N圖811YNNYN圖912YNNYYNNY圖13YYYNNYNN圖142.4算法的程序?qū)崿F(xiàn)代碼#include#include#include#回溯法求解int*in=(*)malloc(MAX_SAMPLE_LENGTH*sizeofint));int*data=(*)malloc(MAX_SAMPLE_LENGTH*sizeof(int));bool*visited=(*)malloc(MAX_SAMPLE_LENGTH*sizeofbool));bool*nVisited=(*)malloc(MAX_SAMPLE_LENGTH*sizeofbool));bool*res_arr=(*)malloc(MAX_SAMPLE_LENGTH*sizeofbool));鋸口寬度當前已鋸木頭長度和求解結(jié)果記錄輸入數(shù)據(jù)個數(shù);讀取數(shù)據(jù)原材料木頭長度-()鋸口寬度"%d"(ch==\n)break;}}backtrack(i,){記錄最優(yōu)值記錄當前最優(yōu)解}}15;}進入右子樹條件進入右子樹實際操作訪問標記}}int*data,;(count>){,本次求解最大長度和更新待解決問題狀態(tài)剩余未求解元素個數(shù)}記錄求解結(jié)果}}printf(\n%d\n}}16題目3設計題3.1題目描述給定一個數(shù)塔，如圖所示。在此數(shù)塔中，從頂部出發(fā)，在每一節(jié)點可以大。圖3.2輸入要求第一行輸入一個整數(shù)表示數(shù)塔的層數(shù)，第行為數(shù)塔對應節(jié)點的數(shù)值。3.3輸出要求第一行輸出路徑數(shù)值和，第二行輸出具體路徑。3.4樣例輸入5131112407166141581271324113.5樣例輸出91(1,1)->(2,1)->(3,1)->(4,2)->(5,3)3.6測試樣例輸入1771198121074152319178211216322524283127859101113153.7測試樣例輸出113(1,1)->(2,1)->(3,2)->(4,3)->(5,3)->(6,4)->(7,5)3.8算法實現(xiàn)的文字描述動態(tài)規(guī)劃采用自底向上逐層分階段決策1)第1次決策，針對第4層如果最優(yōu)路徑經(jīng)過6，則從第4層到第5層應該經(jīng)過12，則第4+第5層的最大路徑為6+12=18如果最優(yōu)路徑經(jīng)過14，則從第4層到第5層應該經(jīng)過13，則第4+第5層的最大路徑為13+14=27……這樣實際上將5階數(shù)塔變?yōu)?階數(shù)塔問題了。2)逐層向上遞推，最后得到問題的最優(yōu)解()=()={()=(+),(++1))+(≤<Step1：聲明變量數(shù)塔層數(shù)n，待處理數(shù)據(jù)節(jié)點數(shù)值數(shù)組data[n][n],結(jié)果（狀態(tài)）數(shù)組d[n][n];Step2：輸入數(shù)塔層數(shù)n，維數(shù)組data和d分配內(nèi)存空間；Step3：初始化第n層結(jié)果（狀態(tài)）數(shù)組值；Step4：根據(jù)狀態(tài)轉(zhuǎn)移方程求解d(i,j)，其中i從n-1到1，j從1到i；Step5：輸出d(1,1)；Step6：根據(jù)數(shù)組d求解具體路徑并輸出。183.9算法程序流程n函函NYNY圖19NYNYYNtemp_max=max(dp[index1],dp[index1+1])index1=(i+1)*n+j,index2=i*n+j圖3.10算法的程序?qū)崿F(xiàn)代碼#include#include#include#includeint*data=NULL;//存儲數(shù)塔原始數(shù)據(jù)int*dp=NULL;//狀態(tài)值記錄n;塔的層數(shù)動態(tài)規(guī)劃實現(xiàn)數(shù)塔求解{,index2=;初始化i=;i<{20}}}};printf("%d\n);首先輸出塔頂元素=-如果dp[i][j]則說明下一步應該是如果+1]則說明下一步應該是index=i*n+j+;ifprintf("->(%d,%d)",i+,j+);}}"%d"data=(int*)malloc(n*n*sizeofint));memset(data,,n*n*sizeofint));d