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

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