當前位置:首頁 » 操作系統 » 隨機的演算法

隨機的演算法

發布時間: 2022-02-01 05:39:44

1. 隨機演算法、函數

產生整數rand的原理是:
y=ax+b(mod n)其中,n一般是一個很大的素數,幾萬。
a也是大素數。而且a,b,n都是常數。所以rand的產生決定於x,
他被稱為seed。
每一個seed都是上一次產生的y的函數。這樣,如果直接取seed=y的話,
雖然產生的rand之間相關性甚小,但只要知道某個y,就能推知以後的rand。
為避免這種情況,一般取seed為y和當時計算機的時間的函數,如seed=y+t

2. 隨機演算法

一般用a=rand(n),為了防止重復用srand(time(NULL)); 很簡單的

3. 求一隨機演算法(牛人進)

設置數組長度n n-1個元素都是最小值 有一個最大值 然後寫個產生隨機數的方法 ,
循環給數據元素 加隨機數 加的時候去嚴重數組和 如果超出最大值就放棄,當循環到最後的時候如果還沒可以加, 最後一個元素 用 減法(要比最大值小),如果比最大值大 那就再分

4. 隨機化的演算法

在我們的生活中,人們經常會去擲色子來看結果,投硬幣來決定行動,這就牽涉到一個問題:隨機。
計算機為我們提供好了隨機方法(部分計算器也提供了),那麼對於有些具有瑕疵的演算法,如果配上隨機化演算法的話,又是可以得到一樣不到的結果。
這種演算法看上去是憑著運氣做事,其實,隨機化演算法是有一定的理論基礎的,我們可以想像,在[1,10000]這個閉區間里,隨機1000次,隨機到2這個數的幾率是多大,何況1000次的隨機在計算機程序中僅僅是一眨眼的功夫。可以看出,隨機化演算法有著廣闊的前景。只是由於隨機化演算法比較難於掌控,所以並不是很多人都接觸過他,但肯定有很多人都聽說過。
下面,我們就隨機化問題,舉一個例子:
一個長度在4..10的字元串中,需要判定是否可以在字元串中刪去若干字元,使得改變後字元串符合以下條件之一:
(1)AAAA;(2)AABB;(3)ABAB;(4)ABBA。
例如:長度為6字元串「POPKDK」,若刪除其中的「O」,「D」兩個字母,則原串變為:「PPKK」,符合條件(2)AABB。
分析:
這道題很容易想到一種演算法:運用排列組合:枚舉每4個字母,然後逐一判斷。演算法是可行的,但是如果需要題目中加上一句話:需要判斷n個字元串,且n<=100000,那麼這樣的耗時是不能讓人忍受①的,因為在枚舉的過程中,是非常浪費時間的。
(①:這里是指信息學中要求演算法的普遍運算時間為:1000ms)
所以這道題有可能可以藉助於隨機化演算法,下面我們來算一下在10個組符中取4個字元一共有多少種取法:C(4,10)=210。那麼很容易得知,隨機化演算法如果隨機100次,能都到的結果基本上就正確了,而隨機時的時間消耗是O(1),只需要判斷沒有隨機重復即可,判重的時間復雜度也為O(1),並且最多隨機100次,這樣就可以有效地得到答案,最大運算次數為:O(100n),這是在計算機的承受范圍內(1000ms)的。
從這里就能看出,隨機化演算法是一個很好的概率演算法,但是它並不能保證正確,而且它單獨使用的情況很少,大部分是與其他的演算法:例如貪心、搜索等配合起來運用。
再舉一個例子:
排序問題。快速排序是排序方法中較為便捷的方法之一,但是由於它極不穩定,最好的時候時間復雜度為O(n㏒n),這里的㏒是指以2為底的對數運算。最壞的時候能達到與普通排序方法一樣的O(n^2)。
而制約快速排序的有兩個:一是數據,越無序的數據,快排的速度越快;二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關系。
所以,在快速排序中加入隨機化演算法無疑是十分重要的。

5. 隨機演算法的介紹

《隨機演算法》是高等教育出版社出版的圖書,作者是莫特瓦尼、拉格哈文。主要介紹了演算法本身包含了隨機數生成器的演算法。

6. 求隨機數計算演算法

用VB,rnd函數直接生成

7. 隨機數演算法

可以把已有數據放到數組里,然後產生隨機下標,根據下標取到的數據可以認為是隨機的。

8. 隨機數演算法是什麼

在計算機中並沒有一個真正的隨機數發生器,但是可以做到使產生的數字重復率很低,這樣看起來好象是真正的隨機數,實現這一功能的程序叫偽隨機數發生器。有關如何產生隨機數的理論有許多如果要詳細地討論,需要厚厚的一本書的篇幅。不管用什麼方法實現隨機數發生器,都必須給它提供一個名為「種子」的初始值。而且這個值最好是隨機的,或者至少這個值是偽隨機的。「種子」的值通常是用快速計數寄存器或移位寄存器來生成的。下面講一講在C語言里所提供的隨機數發生器的用法。現在的C編譯器都提供了一個基於ANSI標準的偽隨機數發生器函數,用來生成隨機數。它們就是rand()和srand()函數。這二個函數的工作過程如下:」)首先給srand()提供一個種子,它是一個unsignedint類型,其取值范圍從0~65535;2)然後調用rand(),它會根據提供給srand()的種子值返回一個隨機數(在0到32767之間)3)根據需要多次調用rand(),從而不間斷地得到新的隨機數;4)無論什麼時候,都可以給srand()提供一個新的種子,從而進一步「隨機化」rand()的輸出結果。這個過程看起來很簡單,問題是如果你每次調用srand()時都提供相同的種子值,那麼,你將會得到相同的隨機數序列,這時看到的現象是沒有隨機數,而每一次的數都是一樣的了。例如,在以17為種子值調用srand()之後,在首次調用rand()時,得到隨機數94。在第二次和第三次調用rand()時將分別得到26602和30017,這些數看上去是很隨機的(盡管這只是一個很小的數據點集合),但是,在你再次以17為種子值調用srand()後,在對於rand()的前三次調用中,所得的返回值仍然是在對94,26602,30017,並且此後得到的返回值仍然是在對rand()的第一批調用中所得到的其餘的返回值。因此只有再次給srand()提供一個隨機的種子值,才能再次得到一個隨機數。下面的例子用一種簡單而有效的方法來產生一個相當隨機的「種子」值----當天的時間值:g#椋睿悖歟醯洌澹Γ歟簦唬螅簦洌椋錚瑁Γ紓簦弧。#椋睿悖歟醯洌澹Γ歟簦唬螅簦洌歟椋猓瑁Γ紓簦弧。#椋睿悖歟醯洌澹Γ歟簦唬螅螅Γ#矗罰唬簦穡澹螅瑁Γ紓簦弧。#椋睿悖歟醯洌澹Γ歟簦唬螅螅Γ#矗罰唬簦椋恚澹猓瑁Γ紓簦弧。觶錚椋洹。恚幔椋睿ǎ觶錚椋洌。。椋睿簟。椋弧。醯睿螅椋紓睿澹洹。椋睿簟。螅澹澹洌鄭幔歟弧。螅簦潁醯悖簟。簦椋恚澹狻。簦椋恚澹攏醯媯弧。媯簦椋恚澹ǎΓ幔恚穡唬簦椋恚澹攏醯媯弧。螅澹澹洌鄭幔歟劍ǎǎǎǎ醯睿螅椋紓睿澹洹。椋睿簦簦椋恚澹攏醯媯簦椋恚澹Γ幔恚穡唬埃疲疲疲疲。ǎ醯睿螅椋紓睿澹洹。椋睿簦簦椋恚澹攏醯媯恚椋歟歟椋簦恚蕖。ǎ醯睿螅椋紓睿澹洹。椋睿簦簦椋恚澹攏醯媯恚椋歟歟椋簦恚弧。螅潁幔睿洌ǎǎ醯睿螅椋紓睿澹洹。椋睿簦螅澹澹洌鄭幔歟弧。媯錚潁ǎ椋劍埃唬椋Γ歟簦唬保埃唬椋。穡潁椋睿簦媯ǎΓ瘢醯錚簦唬ィ叮洌Γ#梗玻唬睿Γ瘢醯錚簦籦egjrand());}上面的程序先是調用_ftime()來檢查當前時間yc並把它的值存入結構成員timeBuf.time中wae當前時間的值從1970年1月1日開始以秒計算aeh在調用了_ftime()之後在結構timeBuf的成員millitm中還存入了當前那一秒已經度過的毫秒數,但在DOS中這個數字實際上是以百分之一秒來計算的。然後,把毫秒數和秒數相加,再和毫秒數進行異或運算。當然也可以對這兩個結構成員進行更多的計算,以控制se......餘下全文>>

9. 隨機演算法的基本概念

隨機演算法是演算法本身包含了隨機數生成器的演算法。根據《演算法導論(中文第二版)》描述,在進行演算法分析的時,有時可以在獲得了一定輸入分布信息之後對輸入的分布進行一定的假定,在此基礎上進行平均情況分析得到演算法的時間復雜度。然而有時候無法獲得輸入分布的信息,這時可以在演算法本身增加一定的隨機性,繼而實現對演算法進行平均情況分析。通過設計隨機演算法有效地避免較多的較壞情況輸入的出現,從而提高演算法的平均情況下的性能。

10. 有哪些隨機數演算法呢

1、數值概率演算法:用於數值問題的求解。所得到的解幾乎都是近似解,近似解的精度
隨著計算時間的增加而不斷地提高。
2、拉斯維加斯演算法(LasVegas):要麼給出問題的正確答案,要麼得不到答案。反復求解多次,可
使失效的概率任意小。
3、蒙特卡羅演算法(MonteCarlo):總能得到問題的答案,偶然產生不正確的答案。重復運行,每一次
都進行隨機選擇,可使不正確答案的概率變得任意小。
4、舍伍德演算法(Sherwood):很多具有很好的平均運行時間的確定性演算法,在最壞的情況下性能很
壞。引入隨機性加以改造,可以消除或減少一般情況和最壞情況的差別。

熱點內容
cad解壓錯誤 發布:2024-03-29 15:01:45 瀏覽:78
存儲指令集 發布:2024-03-29 14:39:27 瀏覽:649
資料庫表刪除數據 發布:2024-03-29 14:39:26 瀏覽:367
出c語言整除 發布:2024-03-29 14:28:22 瀏覽:572
芬尼壓縮機 發布:2024-03-29 14:24:11 瀏覽:464
電腦數據實時上傳本地伺服器軟體 發布:2024-03-29 14:07:57 瀏覽:920
尋秦記源碼 發布:2024-03-29 13:56:17 瀏覽:496
linux的備份命令 發布:2024-03-29 13:41:22 瀏覽:383
csgo建議什麼配置 發布:2024-03-29 13:31:44 瀏覽:980
電腦ftp服務如何禁用 發布:2024-03-29 13:24:48 瀏覽:332