資源描述:
《算法分析動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、-重慶大學(xué)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目:動(dòng)態(tài)規(guī)劃的應(yīng)用學(xué)院:計(jì)算機(jī)學(xué)院專(zhuān)業(yè)班級(jí):信息安全1班年級(jí):2011級(jí)姓名:******學(xué)號(hào):2011****完成時(shí)間:2013年6月1日指導(dǎo)教師:陳波重慶大學(xué)教務(wù)處制.---重慶大學(xué)本科學(xué)生實(shí)驗(yàn)項(xiàng)目任務(wù)書(shū)實(shí)驗(yàn)題目動(dòng)態(tài)規(guī)劃的應(yīng)用學(xué)院計(jì)算機(jī)學(xué)院專(zhuān)業(yè)信息安全1班年級(jí)2011任務(wù)描述:有m排n列的柱樁,每一排的柱樁從左向右標(biāo)號(hào)為1,2,…,n,且在每個(gè)柱樁上預(yù)先放好價(jià)值不一樣的寶石?,F(xiàn)在有位雜技演員從第一排的第1號(hào)柱樁開(kāi)始跳躍,每次都必須跳到下一排的柱樁上,且每次跳躍最多只能向左或向右移動(dòng)一個(gè)樁子。也就是說(shuō)如果現(xiàn)在雜技演員站在第
2、j號(hào)樁上,那么他可跳到下一排的第j號(hào)樁上,也可跳到下一排的第j-1(ifj>1)或者j+1(ifj
3、容:1).完整的源碼2).不依賴(lài)于IDE環(huán)境的可執(zhí)行文件及測(cè)試數(shù)據(jù)3).電子版本項(xiàng)目報(bào)告,報(bào)告中至少包括對(duì)算法思想、遞推方程式及該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)、程序結(jié)構(gòu)的描述以及計(jì)算復(fù)雜度分析,以及測(cè)試結(jié)果c.第15周周五之前交,請(qǐng)直接提交至SAKAI。說(shuō)明:1.不依賴(lài)于IDE環(huán)境的可執(zhí)行文件指exe及其支持dll,測(cè)試數(shù)據(jù)均在同一目錄中,在任意一臺(tái)WinXP機(jī)器上直接雙擊exe即可運(yùn)行。2.測(cè)試數(shù)據(jù)不少于20排20列,按照前述的格式放在test.txt文件里,執(zhí)行結(jié)果存入output.txt文件里.---參考資料:AlgorithmDesign,JonK
4、leiberg.EvaTardos,CornellUniversity任務(wù)下達(dá)日期2013年5月26日完成日期2013年6月1日說(shuō)明:學(xué)院、專(zhuān)業(yè)、年級(jí)均填全稱(chēng),如:計(jì)算機(jī)學(xué)院、計(jì)算機(jī)科學(xué)與技術(shù)、2011。.---實(shí)驗(yàn)報(bào)告正文主要內(nèi)容包括:1算法思想(a),使用動(dòng)態(tài)規(guī)劃自下而上方法,定義數(shù)組gem[i][j]表示第i排第j列木樁上的寶石數(shù),數(shù)組maxb[i][j]表示從第i排第j列木樁到最后一排木樁所獲得的最大寶石數(shù)。公式為:maxb[i][j]=max{gem[i][j]+maxb[i+1][j-1],gem[i][j]+maxb[i+1][j],
5、gem[i][j]+maxb[i+1][j+1]}其中i從n取到1求maxb的偽代碼如下:Dynamic-Bottom-To-Up(maxb,gem,row,line)for(inti=1;i<=row;i++)maxb[line][i]=gem[line][i];//初始化maxbfor(inti=line-1;i=>1;i--)for(intj=row;j>=1;j--)maxb[i][j]=max{gem[i][j]+maxb[i+1][j-1],gem[i][j]+maxb[i+1][j],gem[i][j]+maxb[i+1][j+1]}
6、由上述代碼可知,最多兩個(gè)for循環(huán),所以,時(shí)間復(fù)雜度為O(n2).(b),用數(shù)組path[]記錄獲得最大價(jià)值的路徑,思想是自上而下比較每排的maxb最大值,將位置賦給數(shù)組path[],然后再判斷該最大值的下排與之相鄰的三個(gè)maxb值,而后重復(fù)上面的操作,直到最后一排。求path的偽代碼如下:path[1]=1//因?yàn)槊看味际菑牡谝慌诺牡谝粯堕_(kāi)始,所以,path[1]=1n=1;for(inti=2;i<=line;i++)max{maxb[i][n-1],maxb[i][n],maxb[i][n+1]}path[i]=n;//如果maxb[i][n
7、]最大,則n=n-1;由該代碼可知,求path的時(shí)間復(fù)雜度為O(n)。2關(guān)鍵代碼描述#include#include.---usingnamespacestd;voidmain(){ofstreamoutfile;//實(shí)驗(yàn)結(jié)果讀入outfile文件中ifstreaminfile;//實(shí)驗(yàn)數(shù)據(jù)從infile文件中讀入outfile.open("output.txt",ios::trunc);infile.open("test.txt",ios::in);if(infile==NULL)cout<<"文件內(nèi)沒(méi)有內(nèi)容
8、!";intline,row;infile>>line;infile>>row;int**gem;int**maxb;//