怎樣寫描寫初春的作文呢

1、1蒼穹龍騎 http:/2理解產(chǎn)生偽隨機數(shù)的算法理解產(chǎn)生偽隨機數(shù)的算法掌握數(shù)值概率算法的設(shè)計思想掌握數(shù)值概率算法的設(shè)計思想掌握舍伍德算法的設(shè)計思想掌握舍伍德算法的設(shè)計思想掌握拉斯維加斯算法的設(shè)計思想掌握拉斯維加斯算法的設(shè)計思想掌握蒙特卡羅算法的設(shè)計思想掌握蒙特卡羅算法的設(shè)計思想學習要點3概率算法的特點1. 當算法執(zhí)行過程中面臨選擇時，概率算法通當算法執(zhí)行過程中面臨選擇時，概率算法通常比最優(yōu)選擇算法省時。常比最優(yōu)選擇算法省時。2. 對所求問題的同一實例用同一概率算法求解對所求問題的同一實例用同一概率算法求解兩次，兩次求解所需的時間甚至所得的結(jié)果兩次，兩次求解所需的時間甚至所得的結(jié)果可能有相當大的

2、差別。可能有相當大的差別。3. 設(shè)計思想簡單，易于實現(xiàn)。設(shè)計思想簡單，易于實現(xiàn)。4概率算法的分類數(shù)值概率算數(shù)值概率算法法A A蒙特卡羅算法蒙特卡羅算法B B舍伍德算法舍伍德算法D D 拉斯維加斯算法拉斯維加斯算法C C5隨機數(shù)隨機數(shù)在概率算法設(shè)計中扮演著十分重要的隨機數(shù)在概率算法設(shè)計中扮演著十分重要的角色。角色。在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因在現(xiàn)實計算機上無法產(chǎn)生真正的隨機數(shù)，因此在概率算法中使用的隨機數(shù)都是一定程度上隨此在概率算法中使用的隨機數(shù)都是一定程度上隨機的，即機的，即偽隨機數(shù)偽隨機數(shù)。6隨機數(shù)線性同余法線性同余法是產(chǎn)生偽隨機數(shù)的最常用的方法。由是產(chǎn)生偽隨機數(shù)的最常用的方法。由

3、線性同余法產(chǎn)生的隨機序列線性同余法產(chǎn)生的隨機序列a0,a1,an滿足滿足:, 2 , 1mod)(10nmcbaadann其中其中b 0，c 0，d m。d稱為該隨機序列的種子。稱為該隨機序列的種子。m應(yīng)取充分大，因此可取應(yīng)取充分大，因此可取m為機器大數(shù)，另外應(yīng)為機器大數(shù)，另外應(yīng)取取gcd(m,b)=1，因此可取，因此可取b為一素數(shù)。為一素數(shù)。7數(shù)值概率算法 8計算值 設(shè)有一半徑為設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨的圓及其外切四邊形。向該正方形隨機地投擲機地投擲n個點。設(shè)落入圓內(nèi)的點數(shù)為個點。設(shè)落入圓內(nèi)的點數(shù)為k。由于所投入的。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓

4、內(nèi)的概率點在正方形上均勻分布，因而所投入的點落入圓內(nèi)的概率為為 。 當當n足夠大時，足夠大時，k與與n之比就逼近這一概率：之比就逼近這一概率：2244rrnk49計算值 程序代碼如下：程序代碼如下：double Darts(int n) / 用隨機投點法計算用隨機投點法計算 值值 static RandomNumber dart; int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+y*y)=1) k+; return 4*k/double(n);10計算定積分設(shè)設(shè)f(

5、x)是是0，1上的連續(xù)函數(shù)，且上的連續(xù)函數(shù)，且0 f(x) 1。需要計算的積分為需要計算的積分為 ,積分積分I等于圖中的等于圖中的綠綠色面積色面積G。10)(dxxfI11計算定積分在圖所示單位正方形內(nèi)均勻地作投點試驗，則在圖所示單位正方形內(nèi)均勻地作投點試驗，則隨機點落在曲線下面的概率為隨機點落在曲線下面的概率為 假設(shè)向單位正方形內(nèi)隨機地投入假設(shè)向單位正方形內(nèi)隨機地投入n個點個點(xi,yi)。如果有。如果有m個點落入個點落入G內(nèi)，則隨機點落入內(nèi)，則隨機點落入G內(nèi)的概率內(nèi)的概率 10)(010)()(xfrdxxfdydxxfyPnmI12計算定積分 程序代碼如下：程序代碼如下：double

6、Darts(int n) / 用隨機投點法計算用隨機投點法計算定積分定積分 static RandomNumber dart; int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (y=f(x) k+; return k/double(n);13解非線性方程組求解下面的非線性方程組求解下面的非線性方程組0),(0),(0),(21212211nnnnxxxfxxxfxxxf其中，其中，x1,x2,xn是實變量，是實變量，fi是未知量是未知量x1,x2,xn的非線性實函數(shù)。要求確定

7、上述方程組在指定求的非線性實函數(shù)。要求確定上述方程組在指定求根范圍內(nèi)的一組解根范圍內(nèi)的一組解*2*1,nxxx14注：一般而言，概率算法費時，但設(shè)計思注：一般而言，概率算法費時，但設(shè)計思想簡單，易實現(xiàn)。對于精度要求高的問題，想簡單，易實現(xiàn)。對于精度要求高的問題，可以提供較好的初值?？梢蕴峁┹^好的初值。解非線性方程組 n線性化方法線性化方法n求函數(shù)極小值方法求函數(shù)極小值方法2( )( )ixfx15解非線性方程組 在求根區(qū)域在求根區(qū)域D內(nèi)，選定隨機點內(nèi)，選定隨機點x0作為隨機搜索的出發(fā)點。作為隨機搜索的出發(fā)點。1. 按照預(yù)先選定的分布（正態(tài)分布、均勻分布等），逐個按照預(yù)先選定的分布（正態(tài)分布、均

8、勻分布等），逐個選取隨機點選取隨機點xj，計算目標函數(shù)，滿足精度要求的隨機點就，計算目標函數(shù)，滿足精度要求的隨機點就是近似解。是近似解。2. 在算法的搜索過程中，假設(shè)第在算法的搜索過程中，假設(shè)第j步隨機搜索得到的隨機搜步隨機搜索得到的隨機搜索點為索點為xj。在第。在第j+1步，生成隨機搜索方向和步長，計算步，生成隨機搜索方向和步長，計算出下一步的增量出下一步的增量 xj。從當前點。從當前點xj依依 xj得到第得到第j+1步的隨機步的隨機搜索點。當搜索點。當( (x) ) epsilon)&(j Steps) /計算隨機搜索步長因子計算隨機搜索步長因子 if (fx M) a/= k;succe

9、ss = false; for (int i = 1; i n; i+) /計算隨機搜索方向和增量計算隨機搜索方向和增量 ri = 2.0 * rnd.fRandom() 1; if (success) for(int i=1; i = n; i+) dxi = a * ri; else for(int i=1; i = n; i+) dxi = a * ri;17解非線性方程組/計算下一個搜索點計算下一個搜索點 for(int i=1; i = n; i+) xi += dxi; /計算目標函數(shù)值計算目標函數(shù)值 fx = f(x,n); if (fx tA(n) 的可能性。的可能性。20舍伍

10、德(Sherwood)算法注：當注：當s(n)與與tA(n)相比可忽略時，舍伍德算相比可忽略時，舍伍德算法可獲得很好的平均性能法可獲得很好的平均性能。舍伍德算法設(shè)計的基本思想舍伍德算法設(shè)計的基本思想 希望獲得一個概率算法希望獲得一個概率算法B B，用該算法，用該算法處理問題的輸入，使得對問題的輸入規(guī)模處理問題的輸入，使得對問題的輸入規(guī)模為為n n的每一個實例均有的每一個實例均有)()()(nsntxtAB21舍伍德(Sherwood)算法 這兩種算法的核心都在于選擇合適的劃分這兩種算法的核心都在于選擇合適的劃分基準。舍伍德算法隨機地選擇一個數(shù)組元素作基準。舍伍德算法隨機地選擇一個數(shù)組元素作為劃

11、分基準。為劃分基準。線性時間選擇算法線性時間選擇算法 No.1快速排序算法快速排序算法 No.222舍伍德(Sherwood)算法如果所給的確定性算法無法直接改造成舍伍如果所給的確定性算法無法直接改造成舍伍德型算法。此時可借助于隨機預(yù)處理技術(shù)，不改變德型算法。此時可借助于隨機預(yù)處理技術(shù)，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德算法的效果。樣可收到舍伍德算法的效果。 如，對于確定性選擇算法，可以用下面的洗牌如，對于確定性選擇算法，可以用下面的洗牌算法算法shuffle將數(shù)組將數(shù)組a中元素隨機排列，然后用確定中元素隨機排列，然后用

12、確定性選擇算法求解。這樣做所收到的效果與舍伍德型性選擇算法求解。這樣做所收到的效果與舍伍德型算法的效果是一樣的。算法的效果是一樣的。 23舍伍德(Sherwood)算法Shuffle函數(shù)的代碼：函數(shù)的代碼：templatevoid Shuffle(Type a, int n)/ 隨機洗牌算法隨機洗牌算法 static RandomNumber rnd; for (int i=0;i0。設(shè)。設(shè)t(x)是算法是算法obstinate找找到具體實例到具體實例x的一個解所需的平均時間的一個解所需的平均時間 ,s(x)和和e(x)分分別是算法對于具體實例別是算法對于具體實例x求解成功或求解失敗所需的求解

13、成功或求解失敗所需的平均時間，則有：平均時間，則有： 。 解此方程可得：解此方程可得： )()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt32n后問題對于對于n后問題的任何一個解而言，每一個后問題的任何一個解而言，每一個皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機放置的。由此容易想到性，而更象是隨機放置的。由此容易想到拉斯拉斯維加斯算法維加斯算法。如果將上述隨機放置策略與回溯法相如果將上述隨機放置策略與回溯法相結(jié)合，可能會獲得更好的效果結(jié)合，可能會獲得更好的效果。33n后問題可以先在棋盤的若干行中

14、隨機地放置皇后，可以先在棋盤的若干行中隨機地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個然后在后繼行中用回溯法繼續(xù)放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，后繼回溯搜解或宣告失敗。隨機放置的皇后越多，后繼回溯搜索所需的時間就越少，但失敗的概率也就越大。索所需的時間就越少，但失敗的概率也就越大。 stopVegaspset01.0000262.00-262.0050.503933.8847.2380.39120.046513.0010.20222.1134 給定一個合數(shù)給定一個合數(shù)n n，求，求n n的一個非平凡因子的問題稱為整的一個非平凡因子的問題稱為整數(shù)數(shù)n n的因子分割

15、問題。的因子分割問題。整數(shù)因子分解設(shè)設(shè)n1是一個整數(shù)。關(guān)于整數(shù)是一個整數(shù)。關(guān)于整數(shù)n的因子分解問題是的因子分解問題是找出找出n的如下形式的唯一分解式：的如下形式的唯一分解式： 。 其中，其中，p1p2pk是是k個素數(shù)，個素數(shù)，m1,m2,mk是是k個個正整數(shù)。如果正整數(shù)。如果n是一個合數(shù)，則是一個合數(shù)，則n必有一個非平凡必有一個非平凡因子因子x，1xn，使得，使得x可以整除可以整除n。 kmkmmpppn212135整數(shù)因子分解int Split(int n) int m = floor(sqrt(double(n); for (int i=2; i=m; i+) if (n%i=0) ret

16、urn i; return 1; 事實上，算法事實上，算法split(n)split(n)是對范圍是對范圍在在1 1x x的所有整數(shù)的所有整數(shù)進行了試除而得到進行了試除而得到范圍在范圍在1 1x x2 2的任一的任一整數(shù)的因子分割。整數(shù)的因子分割。 36Pollard算法 在開始時選取在開始時選取0n-1范圍內(nèi)的隨機數(shù)，然后范圍內(nèi)的隨機數(shù)，然后遞歸地由遞歸地由 產(chǎn)生無窮序列產(chǎn)生無窮序列 對于對于i=2k，以及，以及2k1) & (dn) coutdendl; if (i=k) y=x; k*=2; 對對Pollard算法更深入的算法更深入的分析可知，執(zhí)行算法的分析可知，執(zhí)行算法的while循環(huán)

17、約循環(huán)約 次后，次后，Pollard算法會輸出算法會輸出n的的一個因子一個因子p。由于。由于n的最的最小 素 因 子小 素 因 子 p ， 故， 故Pollard算法可在算法可在O(n1/4)時間內(nèi)找到時間內(nèi)找到n的一個素因的一個素因子。子。np38蒙特卡羅(Monte Carlo)算法設(shè)設(shè)p是一個實數(shù)，且是一個實數(shù)，且1/2pn/2時，稱元素x是數(shù)組T的主元素。 templatebool Majority(Type *T, int n)/ 判定主元素的蒙特卡羅算法 int i=rnd.Random(n)+1; Type x=Ti; / 隨機選擇數(shù)組元素 int k=0; for (int j

18、=1;jn/2); / kn/2 時T含有主元素templatebool MajorityMC(Type *T, int n, double e)/ 重復(fù)調(diào)用算法Majority int k=ceil(log(1/e)/log(2); for (int i=1;i0，算法majorityMC重復(fù)調(diào)用log(1/) 次算法majority。它是一個偏真蒙特卡羅算法，且其錯誤概率小于。算法majorityMC所需的計算時間顯然是O(nlog(1/ )。44素數(shù)測試：對于給定的正整數(shù)n，判定n是一個素數(shù)的充要條件是(n-1)! -1(mod n)。void power( unsigned int a, unsigned int p, unsigned int