計(jì)算機(jī)算法設(shè)計(jì)與分析課程設(shè)計(jì)-文庫吧資料
2025-06-15 05:28本頁面
【正文】 } m[i][j]+=w[i][j]。 if(tm[i][j]) { //以 k為根節(jié)點(diǎn)，左子樹不為空 m[i][j]=t。k=j。 s[i][j]=i。 //左子樹為空 w[i][j]=w[i][j1]+a[j]+b[j]。i=nr。rn。 //搜索不到的點(diǎn) ,最優(yōu)解為 0 m[i+1][i]=0。i=n。 float t。 算法實(shí)現(xiàn)題 : 給出標(biāo)識符集 {1,2,3}={do,if,stop}存取概率，若 b1= b2= b3= a0= a1= a2= a3= 源程序如下： includeiostream using namespace std。 記 jiji pw , 為 ? ?jim, ，則 ? ? nnn ppwnm ,1,1,1,1 ?? 為所求的最優(yōu)值。 遞歸計(jì)算最優(yōu)值： 最優(yōu)二叉搜索樹 ijT 的平均路長為 ijp ，則所求的最優(yōu)值為 np,1 。同理可證 rT 也是一棵最優(yōu)二叉搜索樹。這與 ijT 是最優(yōu)二叉搜索樹矛盾。由于 lT 和 rT 中結(jié)點(diǎn)深度是它們在 ijT 中的結(jié)點(diǎn)深度減 1，故有： rjmlmijijiji pwpwwpw ,11, ?? ??? 由于 lT 是關(guān)于集合 ? ?1, ?mi xx ? 的一棵二叉搜索樹，故 1, ?? mil pp 。 ijT 的根結(jié)點(diǎn)存儲元素 mx 。 最優(yōu)子結(jié)構(gòu)性質(zhì)： 二叉搜索樹 T 的一棵含有結(jié)點(diǎn) ji xx ,? 和葉結(jié)點(diǎn) ? ? ? ?11 , ?? jjii xxxx ? 的子樹可以看作是有序集 ? ?ji xx ,? 關(guān)于全集合 ? ?11 , ?? ji xx ? 的一棵二叉搜索樹，其存取概率為以下的條件概率： ? ?jkiwbb ijkk ??? / ? ?jhiwaa ijhh ???? 1/ 《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告 6 式中， njiabbaw jjiiij ???????? ? 1,1 ?。在一般情況下，不同的二叉搜索樹的平均路長是不相同的。0,0 njbnia ji ?????? 110 ???? ??nj jni i ba ? ?nn ababa , 110 ? 稱為集合 S的存取概率分布。顯然有： 。 設(shè)在第 (1)中情形中找到元素 ixx? 的概率為 ib ；在第 (2)種情形中確定 ? ?1, ?? ii xxx 的概率為 ia 。二叉樹的葉結(jié)點(diǎn)是形如 ? ?1, ?ii xx 的開區(qū)間，在表示 S的二叉搜索樹中搜索元素 x，返回的結(jié)果有兩種情況： （ 1）在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到 ixx? 。 } 運(yùn)行結(jié)果如下： 圖 1 ? 動(dòng)態(tài)規(guī)劃 — 最優(yōu)二叉搜索樹 最優(yōu)二叉搜索樹問題描述和分析： 《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告 5 設(shè) ? ?nxxxS , 21 ?? 是有序集，且 nxxx ??? ?21 ，表示有序集 S 的二叉搜索樹利用二叉樹的結(jié)點(diǎn)存儲有序集中的元素。 printf(\n)。in。 printf(排列后的數(shù)列 為： \n)。data[i])。in。 printf(請輸入要排列的數(shù)列： \n)。 scanf(%d,amp。 //對右半段排序 《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告 4 } int main() { int i,n,data[size]。 quick_sort(data,p,q1)。 } void quick_sort(int data[],int p,int r) { if(p=r) return。 data[j]=n。 data[j]=temp。 temp=data[i]。 w
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1