計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)[王曉東][電子教案]第7章(編輯修改稿)
2024-09-01 17:22 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 或更高級(jí)的結(jié)點(diǎn)，它所跳過的結(jié)點(diǎn)數(shù)不再準(zhǔn)確地維持在 2i1。經(jīng)過這樣的修改，就可以在插入或刪除一個(gè)元素時(shí)，通過對(duì)跳躍表的局部修改來維持其平衡性。 13 跳躍表 在一個(gè)完全跳躍表中，具有 i級(jí)指針的結(jié)點(diǎn)中有一半同時(shí)具有 i+1級(jí)指針。為了維持跳躍表的平衡性，可以事先確定一個(gè)實(shí)數(shù) 0p1，并要求在跳躍表中維持在具有 i級(jí)指針的結(jié)點(diǎn)中同時(shí)具有 i+1級(jí)指針的結(jié)點(diǎn)所占比例約為 p。為此目的，在插入一個(gè)新結(jié)點(diǎn)時(shí)，先將其結(jié)點(diǎn)級(jí)別初始化為 0，然后用隨機(jī)數(shù)生成器反復(fù)地產(chǎn)生一個(gè) [0， 1]間的隨機(jī)實(shí)數(shù) q。如果 qp，則使新結(jié)點(diǎn)級(jí)別增加 1，直至 q?p。由此產(chǎn)生新結(jié)點(diǎn)級(jí)別的過程可知，所產(chǎn)生的新結(jié)點(diǎn)的級(jí)別為 0的概率為 1p，級(jí)別為 1的概率為p(1p)， … ，級(jí)別為 i的概率為 pi(1p)。如此產(chǎn)生的新結(jié)點(diǎn)的級(jí)別有可能是一個(gè)很大的數(shù)，甚至遠(yuǎn)遠(yuǎn)超過表中元素的個(gè)數(shù)。為了避免這種情況，用 作為新結(jié)點(diǎn)級(jí)別的上界。其中 n是當(dāng)前跳躍表中結(jié)點(diǎn)個(gè)數(shù)。當(dāng)前跳躍表中任一結(jié)點(diǎn)的級(jí)別不超過 np/1lognp/1log14 拉斯維加斯 ( Las Vegas )算法 拉斯維加斯算法的一個(gè)顯著特征是它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。 void obstinate(Object x, Object y) {// 反復(fù)調(diào)用拉斯維加斯算法 LV(x,y)，直到找到問題的一個(gè)解 y bool success= false。 while (!success) success=lv(x,y)。 } 設(shè) p(x)是對(duì)輸入 x調(diào)用拉斯維加斯算法獲得問題的一個(gè)解的概率。一個(gè)正確的拉斯維加斯算法應(yīng)該對(duì)所有輸入 x均有 p(x)0。 設(shè) t(x)是算法 obstinate找到具體實(shí)例 x的一個(gè)解所需的平均時(shí)間 ,s(x)和 e(x)分別是算法對(duì)于具體實(shí)例 x求解成功或求解失敗所需的平均時(shí)間，則有： 解此方程可得： ))()() ) ((1()()()( xtxexpxsxpxt ????)()( )(1)()( xexp xpxsxt ???15 n后問題 對(duì)于 n后問題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置的。由此容易想到下面的 拉斯維加斯算法 。 在棋盤上相繼的各行中隨機(jī)地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至 n個(gè)皇后均已相容地放置好，或已沒有下一個(gè)皇后的可放置位置時(shí)為止。 如果將上述隨機(jī)放置策略與回溯法相結(jié)合，可能會(huì)獲得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告失敗。隨機(jī)放置的皇后越多，后繼回溯搜索所需的時(shí)間就越少，但失敗的概率也就越大。 stopVegas p s e t 0 5 12 16 整數(shù)因子分解 設(shè) n1是一個(gè)整數(shù)。關(guān)于整數(shù) n的因子分解問題是找出 n的如下形式的唯一分解式： 其中， p1p2…p k是 k個(gè)素?cái)?shù)， m1,m2,…,m k是 k個(gè)正整數(shù)。 如果 n是一個(gè)合數(shù)，則 n必有一個(gè)非平凡因子 x， 1xn，使得 x可以整除 n。 給定一個(gè)合數(shù) n，求 n的一個(gè)非平凡因子的問題稱為整數(shù) n的因子分割問題。 kmkmm pppn ?21 21?int Split(int n) { int m = floor(sqrt(double(n)))。 for (int
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1