第四章5(貪心、動態(tài))(編輯修改稿)
2024-09-11 20:32 本頁面
【文章內(nèi)容簡介】 {[i][i+1]=i。m[i][j]=r[i]*r[i+1]*r[i+2]。returnm[i][j]。}intu=course(i,i)+course(i+1,j)+r[i]*r[i+1]*r[j+1]。[i][j]=ifor(intk==i+1。kj。k++){intt=course(i,k)+course(k+1,j)+r[i]*r[k+1]*r[j+1]。if(tu){u=t[i][j]=k。}}m[i][j]=u。returnu。} 上節(jié) 下節(jié)算法 3(非遞歸算法 )main（ ）{intn,r[100],m[100][100],[100][100]。peint(“Howmangmatrixes?”)。input(n)。peint(“Howsizeeverymatrixe?”)。for(i=1。i=n+1。i++)input(r[i])。for(i=1。i=n。i++)/初始化化數(shù)組 和 m。 /for(j=1。j=n。j++)[i][j]=0。for(i=1。in。i++){m[i][i]=0。\s=0\m[i][i+1]=r[i]*r[i+1]*r[i+2]。\s=1\[i][i+1]=i+1。} 上節(jié) 下節(jié)m[n][n]=0。for(s=2。s=n1。s++)/動態(tài)規(guī)劃過程 /for(i=1。ins+1。i++){j=i+s。m[i][j]=m[i][i]+m[i+1][j]+r[i]*r[i+1]*r[j+1]。[i][j]=i。for(k=i+1。kj。k++){t=m[i][k]+m[k+1][j]+r[i]*r[k+1]*r[j+1]。if(tm[i][j]){m[i][j]=t。[i][j]=k。}}}print(“Theleastcalculatequantity： ”m[1][n])。for(i=1。i=n。i++){print(“換行符 ”)。for(j=1。j=n。j++)print([i][j])。}} 上節(jié) 下節(jié)輸出部分的算法設(shè)計以上算法中關(guān)于矩陣相乘的結(jié)合方式，只是簡單的輸出了數(shù)組的內(nèi)容，不容易直觀地被利用，還需要繼續(xù)進(jìn)行必要的人工處理，才能真正找到矩陣相乘的結(jié)合方式。怎么樣更直觀、合理地輸出結(jié)合過程？即算法的輸出能使用戶直接了解計算矩陣的過程。首先看一下 數(shù)組存儲的信息意義，它是一個二維數(shù)組，元素 [i][j]存儲的是 Mi—— Mj相乘的組合點 k1， 也就是說：Mi*Mi+1*…… *Mj是由 Mi*Mi+1*…… Mk和 Mk+1*…… Mj同樣，在數(shù)組 中我們也能找到 Mi—— Mk相乘的組合點 k2，Mk+1—— Mj相乘的組合點 k3， …… 。從數(shù)組信息中找到了大規(guī)模問題與小規(guī)模問題的遞歸關(guān)系：輸出算法 記 k1=[1][n]， 則最后一次運算的結(jié)合過程是 M1*……*Mk1 和 Mk1+1*……* Mn 記 k2=[1][k1]， M1*……*Mk1 的結(jié)合過程是 M1*……*Mk2 和 Mk2+1*……*Mk1 ……bine(inti,intj){if(i=j)return。bine(i,[i][j])。bine([i][j]+1,j)。print（ M,i,“*M”， [i][j]） 。print（ andM,[i][j]+1,“*M”， j） 。} 上節(jié) 下節(jié) 這一節(jié)問題的 設(shè)計角度是從遞推思想進(jìn)行 的 ,設(shè)計中只要找出大規(guī)模問題與小規(guī)模問題 (子問題 )之間的遞推關(guān)系 ,最后一個子問題所得最優(yōu)解就是原問題的最優(yōu)解。 【 例 4】 求兩個字符序列的最長公共字符子序列 。 【 例 5】 最長不降子序列 。 上節(jié) 下節(jié) 突出遞推的動態(tài)規(guī)劃應(yīng)用【 例 4】 求兩個 字符序列 的 最長 公共字符子序 列。 問題分析 算法設(shè)計 算法 (遞歸形式 ) 算法 (非遞歸 ) 上節(jié) 下節(jié)問題分析 若 A的長度為 n，若 B的長度為 m， 則 A的子序列共有： Cn1+Cn2+ Cn3+……+ Cnn=2n1 B的子序列共有： Cm1+Cm2+ Cm3+……+ Cmm=2m1 如采用枚舉策略，當(dāng) m=n時，共進(jìn)行串比較：Cn1*Cm1+Cn2*Cm2+Cn3*Cm3+……+ Cnn*Cnn22n 次，耗時太多 ,不可取。 此問題不可能簡單地分解成幾個獨立的子問題，也不能用分治法來解。所以，我們只能用動態(tài)規(guī)劃的方法去解決 。 上節(jié) 下節(jié)算法設(shè)計1．遞推關(guān)系分析 設(shè) A=“a0 ， a1， … ， am1” ， B=“b0 ， b1， … ， bn1”， Z=“z0,z1,…,zk1” 為它們的最長公共子序列。 有以下 結(jié)論 ： 1）如果 am1=bn1,則 zk1=am1=bn1,且 “ z0,z1,…,zk2” 是 “ a0,a1,…,am2” 和 “ b0,b1,…,bn2” 的一個最長公共子序列； 2）如果 am1≠bn1 ， 則若 zk1≠am1 ， 蘊涵 “ z0， z1， …， zk1” 是 a0,a1,…,am2 和 b0,b1,…,bn1 的一個最長公共子 序列； 3）如果 am1≠bn1 ， 則若 zk1≠bn1 ， 蘊涵 “ z0， z1， …， zk1” 是 “ a0， a1， … ， am1” 和 “ b0， b1， …
公司管理相關(guān)推薦
鄂ICP備17016276號-1