計算機算法設(shè)計與分析課程設(shè)計(編輯修改稿)
2025-02-12 08:08 本頁面
【文章內(nèi)容簡介】 也是一棵最優(yōu)二叉搜索樹。因此最優(yōu)二叉搜索樹問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。遞歸計算最優(yōu)值：最優(yōu)二叉搜索樹的平均路長為，則所求的最優(yōu)值為。由最優(yōu)二叉搜索樹問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計算的遞歸式如下：初始時。記為，則為所求的最優(yōu)值。計算的遞歸式為：據(jù)此，可設(shè)計出解最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法。 算法實現(xiàn)題: 給出標(biāo)識符集{1,2,3}={do,if,stop}存取概率，若b1= b2= b3= a0= a1= a2= a3=源程序如下：includeiostreamusing namespace std。void OptimalBinarySearchTree(float a[],float b[],int n,float m[][20],int s[][20],float w[][20]){ //求解最優(yōu)值的方法 int i,r,k。 float t。 for(i=0。i=n。i++){ w[i+1][i]=a[i]。 //搜索不到的點,最優(yōu)解為0 m[i+1][i]=0。 } for(r=0。rn。r++) for(i=1。i=nr。i++){ int j=i+r。 //左子樹為空 w[i][j]=w[i][j1]+a[j]+b[j]。 m[i][j]=m[i+1][j]。 s[i][j]=i。 for(k=i+1。k=j。k++){ t=m[i][k1]+m[k+1][j]。 if(tm[i][j]) { //以k為根節(jié)點，左子樹不為空 m[i][j]=t。 s[i][j]=k。 } } m[i][j]+=w[i][j]。 } for(i=1。i=n。i++) for(int j=1。j=n。j++) couts[i][j]=s[i][j]endl。}void print(int i,int j,int s[][20],int S[]) //遞歸輸出結(jié)果{ if(j=i){ int k=s[i][j]。 cout(。 print(i,k1,s,S)。 cout)。 cout S[k] 。 cout(。 print(k+1,j
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1