《動(dòng)態(tài)規(guī)劃算法 第四章 試驗(yàn)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《動(dòng)態(tài)規(guī)劃算法 第四章 試驗(yàn)報(bào)告（6頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)?zāi)康模豪斫鈩?dòng)態(tài)規(guī)劃的基本思想，理解動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題的重疊性質(zhì)。熟練掌握典型的動(dòng)態(tài)規(guī)劃問(wèn)題。掌握動(dòng)態(tài)規(guī)劃思想分析問(wèn)題的一般方法，對(duì)較簡(jiǎn)單的問(wèn)題能正確分析，設(shè)計(jì)出動(dòng)態(tài)規(guī)劃算法，并能快速編程實(shí)現(xiàn)。 實(shí)驗(yàn)內(nèi)容：編程實(shí)現(xiàn)講過(guò)的例題：最長(zhǎng)公共子序列問(wèn)題、矩陣連乘問(wèn)題、凸多邊形最優(yōu)三角剖分問(wèn)題、電路布線問(wèn)題等。本實(shí)驗(yàn)中的問(wèn)題，設(shè)計(jì)出算法并編程實(shí)現(xiàn)。 實(shí)驗(yàn)過(guò)程： 1. 最長(zhǎng)公共子序列問(wèn)題 1.1問(wèn)題描述 若給定序列X=，則另一序列Z=是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列

2、 ik>，使得對(duì)于所有j=1,2,…,k有 即求它們的公共子序列。 1.2算法分析 設(shè)序列X=和Y=的一個(gè)最長(zhǎng)公共子序列Z=，則： i. 若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列； ii. 若xm≠yn且zk≠xm ，則Z是Xm-1和Y的最長(zhǎng)公共子序列； iii. 若xm≠yn且zk≠yn ，則Z是X和Yn-1的最長(zhǎng)公共子序列。 其中Xm-1=，Yn-1=，Zk-1=

3、z2, …, zk-1>。 最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 用c[i,j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中Xi=，Yj=。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列，故c[i,j]=0。建立遞歸關(guān)系如下： 1.3程序框圖 1.4程序源代碼 #include #include<

4、string.h> int lcs_length(char x[], char y[]); int main() { char x[100],y[100]; int len,i,n; scanf("%d",&n); for(i=0;i

5、 n=strlen(y); for(i=0;il[i-1][j]) l[i][j]=l[i][j-1]; else l[i][j]=l[i-1][j]; return

6、 l[m][n]; } 2. 矩陣連乘積問(wèn)題 2.1問(wèn)題描述 矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。 若A是一個(gè)p×q的矩陣，B是一個(gè)q×r的矩陣，則其乘積C=AB是一個(gè)p×r的矩陣。由該公式知計(jì)算C=AB總共需要pqr次的數(shù)乘。其標(biāo)準(zhǔn)計(jì)算公式為： 若給定n個(gè)矩陣{A1,A2,…,An}。其中Ai與Ai+1是可乘的，i=1,2,…,n-1。要求計(jì)算出這n個(gè)矩陣的連乘積A1A2…An。使得數(shù)乘的次數(shù)最少。 2.2算法思想 應(yīng)用動(dòng)態(tài)規(guī)劃，得到 遞歸公式： 2.3程序框圖

7、 2.4程序源代碼 #include int N; void main() { int p[101],i,j,k,r,t,v,n; int m[101][101]; //為了跟講解時(shí)保持一致數(shù)組從1開始 int s[101][101]; //記錄從第i到第j個(gè)矩陣連乘的斷開位置 scanf("%d",&N); for(v=0;v

8、 for(i=0;i<=n;i++) scanf("%d",&p[i]); //讀入p[i]的值(注意：p[0]到p[n]共n+1項(xiàng)) for(i=1;i<=n;i++) //初始化m[i][i]=0 m[i][i]=0; for(r=1;r

9、-1]*p[i]*p[j]; //給m[i][j]賦初值 s[i][j]=i; for(k=i+1;k

10、馬問(wèn)題 3.1問(wèn)題描述 田忌與齊王賽馬，雙方各有n匹馬參賽（n<=100），每場(chǎng)比賽賭注為1兩黃金，現(xiàn)已知齊王與田忌的每匹馬的速度，并且齊王肯定是按馬的速度從快到慢出場(chǎng)，現(xiàn)要你寫一個(gè)程序幫助田忌計(jì)算他最好的結(jié)果是贏多少兩黃金（輸用負(fù)數(shù)表示）。 3.2算法思想 先排序，齊王的馬的速度放在數(shù)組a中，田忌的馬的速度放在數(shù)組b中。本問(wèn)題應(yīng)用的算法是動(dòng)態(tài)規(guī)劃和貪心算法相結(jié)合解決的。從兩人的最弱的馬入手： 若田忌的馬快，就讓這兩匹馬比賽； 若田忌的馬慢，干脆就讓他對(duì)付齊王最快的馬； 若兩匹馬的速度相等，這時(shí)有兩種選擇方案，或者它倆比賽，或者對(duì)付齊王最快的馬。 定義子問(wèn)題：l(i，j)為齊王

11、的從第i匹馬開始的j匹馬與田忌的最快的j匹馬比賽，田忌所獲得的最大收益。 則： 程序具體實(shí)現(xiàn)時(shí)，為了適合c數(shù)據(jù)從0開始，稍加變動(dòng)，定義子問(wèn)題：l(i，j)為齊王的從第i匹馬開始到第i＋j匹馬共j+1匹馬與田忌的最快的j+1匹馬比賽，田忌所獲得的最大收益。初始化時(shí)：l[i][0]表示齊王的第i匹馬與田忌最快的馬比賽的結(jié)果。 3.3程序框圖 3.4程序源代碼 #include v

12、oid readdata(); void init(); int N,n,a[100],b[100],l[100][100]; void main() { int i,j,k; scanf("%d",&N);//測(cè)試?yán)拥脗€(gè)數(shù) for(k=0;k=0;i--) for(j=1;j

13、f(a[i+j]>b[j]) l[i][j]=l[i+1][j-1]-1; else if(l[i+1][j-1]-1>l[i][j-1]) l[i][j]=l[i+1][j-1]-1; else l[i][j]=l[i][j-1]; printf("%d\n",l[0][n-1]); } } void readdata() { int i; scanf("%d",&n);//馬的個(gè)數(shù)：- for(i=0;i

14、的速度； for(i=0;i

15、 init() { int i; qsort(a,n); qsort(b,n); for(i=0;i