動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)與應(yīng)用

1、可編輯WORD版本資料-學(xué)海無(wú)涯可編輯WORD版本資料-學(xué)海無(wú)涯 3/3可編輯WORD版本資料-學(xué)海無(wú)涯(完整word版)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)與應(yīng)用 實(shí)驗(yàn)報(bào)告 課程算法設(shè)計(jì)與分析實(shí)驗(yàn)實(shí)驗(yàn)名稱動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)與應(yīng)用第 1 頁(yè) 一、實(shí)驗(yàn)?zāi)康?1.加深對(duì)動(dòng)態(tài)規(guī)劃算法的基本原理的理解，掌握用動(dòng)態(tài)規(guī)劃方法求解最優(yōu)化問(wèn)題的方法步驟及應(yīng)用； 2.用動(dòng)態(tài)規(guī)劃設(shè)計(jì)整數(shù)序列的最長(zhǎng)遞增子序列問(wèn)題的算法，分析其復(fù)雜性，并實(shí)現(xiàn)； 3.用動(dòng)態(tài)規(guī)劃設(shè)計(jì)求凸多邊形的三角剖分問(wèn)題的算法，分析其復(fù)雜性，并實(shí)現(xiàn)。 4.選做題：用動(dòng)態(tài)規(guī)劃設(shè)計(jì)求解0/1背包問(wèn)題的算法，分析其復(fù)雜性，并實(shí)現(xiàn)。 二、實(shí)驗(yàn)內(nèi)容 (一) 最長(zhǎng)遞增子序列問(wèn)題 1.

2、問(wèn)題描述 求一個(gè)由n個(gè)整數(shù)組成的整數(shù)序列的最長(zhǎng)遞增子序列。一個(gè)整數(shù)序列的遞增子序列可以是序列中非連續(xù)的數(shù)按照原序列順序排列而成的。最長(zhǎng)遞增子序列是其遞增子序列中長(zhǎng)度最長(zhǎng)的。 2. 具體要求（若在ACM平臺(tái)上提交程序，必須按此要求）平臺(tái)上1700題 輸入：輸入的第一行是一個(gè)正整數(shù)n，表示測(cè)試?yán)齻€(gè)數(shù)。接下來(lái)幾行是n個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)測(cè)試?yán)臄?shù)據(jù)由兩行組成，其中第一行為一個(gè)正整數(shù)k (k0 i=i-1; j=j-1; else if(Hij=1) i=i-1; else j=j-1; C0=B0; for(i=0;i=Lij-1) Lij=Li-1j; Hij=1; else Lij=Lij-1;

3、 Hij=2; printf( %d,Lnn); length=Lnn; printf(n); printf(第%d個(gè)子序列元素：,num+1); Lcss(H,n,A,length,B); /*主函數(shù)*/ void main() int m,i,j,AMAX,BMAX,CMAX,DMAX; printf(測(cè)試?yán)膫€(gè)數(shù)：n); scanf(%d, for(i=0;i #include float distance100100; #define MAX 100 /*求凸邊形的各個(gè)頂點(diǎn)與其它頂點(diǎn)的距離*/ void dis(int count,float xMAX,float yMAX) int

4、i,j; for(i=0;iam) s=am; return s; /*主函數(shù)*/ void main() int m,i,j,AMAX; float xMAX,yMAX,lengthMAX; printf(輸入測(cè)例個(gè)數(shù)：n); scanf(%d, for(i=0;im;i+) printf(輸入第%d測(cè)例數(shù)的頂點(diǎn)數(shù)為:nn,i+1); scanf(%d, for(j=0;j scanf(%f, scanf(%f, dis(Ai,x,y);/調(diào)用函數(shù)求各個(gè)頂點(diǎn)間的距離 lengthi=triangle(0,Ai-1);/調(diào)用函數(shù)求n個(gè)頂點(diǎn)的凸多邊形的n-3條弦的長(zhǎng)度之和 printf(nn); printf(結(jié)果如下：nn); for(i=0;im;i+) printf(%.3f,lengthi); printf(nn); 五、實(shí)驗(yàn)結(jié)果 實(shí)驗(yàn)四.(1).cpp 按照實(shí)驗(yàn)要求輸入測(cè)試?yán)玫降膶?shí)驗(yàn)結(jié)果是： 實(shí)驗(yàn)四.(2).cpp 按照實(shí)驗(yàn)要求輸入測(cè)試?yán)?，得到的?shí)驗(yàn)結(jié)果是： 六、總結(jié) 1.主要要注意實(shí)驗(yàn)中的細(xì)節(jié) 2.在寫(xiě)算法