計(jì)算機(jī)算法設(shè)計(jì)與分析課程設(shè)計(jì)(編輯修改稿)
2025-07-13 05:28 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ,1 ?? 的一棵最優(yōu)二叉搜索樹(shù)，其平均路長(zhǎng)為 ijp 。 ijT 的根結(jié)點(diǎn)存儲(chǔ)元素 mx 。其左右子樹(shù) lT 和 rT 的平均路長(zhǎng)分別為 lp 和rp 。由于 lT 和 rT 中結(jié)點(diǎn)深度是它們?cè)?ijT 中的結(jié)點(diǎn)深度減 1，故有： rjmlmijijiji pwpwwpw ,11, ?? ??? 由于 lT 是關(guān)于集合 ? ?1, ?mi xx ? 的一棵二叉搜索樹(shù)，故 1, ?? mil pp 。若 1, ?? mil pp ，則用 1, ?miT 替換 lT 可得到平均路長(zhǎng)比 ijT 更小的二叉搜索樹(shù)。這與 ijT 是最優(yōu)二叉搜索樹(shù)矛盾。故 lT 是一棵最優(yōu)二叉搜索樹(shù)。同理可證 rT 也是一棵最優(yōu)二叉搜索樹(shù)。因此最優(yōu)二叉搜索樹(shù)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 遞歸計(jì)算最優(yōu)值： 最優(yōu)二叉搜索樹(shù) ijT 的平均路長(zhǎng)為 ijp ，則所求的最優(yōu)值為 np,1 。由最優(yōu)二叉搜索樹(shù)問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計(jì)算 ijp 的遞歸式如下： ? ? jipwpwwpw jkjkkikijkijijiji ???? ?????? ,1,11,1, m i n 初始時(shí)， nip ii ???? 1,01, 。 記 jiji pw , 為 ? ?jim, ，則 ? ? nnn ppwnm ,1,1,1,1 ?? 為所求的最優(yōu)值。 計(jì)算 ? ?jim, 的遞歸式為： ? ? ? ? ? ?? ? jijkmkimwjim jkiji ?????? ?? ,11, min, ? ? niiim ???? 1,01, 據(jù)此，可設(shè)計(jì)出解最優(yōu)二叉搜索樹(shù)問(wèn)題的動(dòng)態(tài)規(guī)劃算法。 算法實(shí)現(xiàn)題 : 給出標(biāo)識(shí)符集 {1,2,3}={do,if,stop}存取概率，若 b1= b2= b3= a0= a1= a2= a3= 源程序如下： includeiostream using namespace std。 《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告 7 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]。 //搜索不到的點(diǎn) ,最優(yōu)解為 0 m[i+1][i]=0。 } for(r=0。rn。r++) for(i=1。i=nr。i++){ int j=i+r。 //左子樹(shù)為空 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é)點(diǎn)，左子樹(shù)不為空 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
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1