隨機演算法代碼

A. JS實現隨機化快速排序的實例代碼

演算法的平均時間復雜度為O(nlogn)。但是當輸入是已經排序的數組或幾乎排好序的輸入，時間復雜度卻為O(n^2)。為解決這一問題並保證平均時間復雜度為O(nlogn)的方法是引入預處理步驟，它惟一的目的是改變元素的順序使之隨機排序。這種預處理步驟可在O(n)時間內運行。能夠起到同樣作用的另一種簡單方法是在演算法中引入一個隨機元素，這可以通過隨機地選擇拆分元素的主元來實現。隨機選擇主元的結果放寬了關於輸入元素的所有排列的可能性相同的步驟。引入這一步來修正原先的快速排序，可得到下面所示的隨機化快速排序。新演算法只是在區間[low…high]中一致隨機地選擇一個索引v，並將A[v]和A[low]交換，然後按照原來的快速排序演算法繼續。這里，parseInt(Math.random()*(high-low+1)
+
low)返回一個在low和high之間的數。
復制代碼
代碼如下:
/****************************************
演算法：split
輸入：數組A[low...high]
輸出：
1.若有必要，輸出按上述描述的重新排列的數組A;
2.劃分元素A[low]的新位置w;
****************************************/
function
split(array,
low,
high)
{
var
i
=
low;
var
x
=
array[low];
for(var
j
=
low
+
1;
j
<=
high;
j++)
{
if(array[j]
<=
x)
{
i
++;
if(i
!=
j)
{
var
temp
=
array[i];
array[i]
=
array[j];
array[j]
=
temp;
}
}
}
temp
=
array[low];
array[low]
=
array[i];
array[i]
=
temp;
return
i;
}
/****************************************
演算法：rquicksort
輸入：A[0...n-1]
輸出：按非降序排列數組A[0...n-1]
rquicksort(A,
0,
n-1);
****************************************/
function
rquicksort(array,
low,
high)
{
if(low
<
high)
{
/******隨機化拆分元素的主元*******/
var
v
=
parseInt(Math.random()*(high-low+1)
+
low);
var
tmp
=
array[low];
array[low]
=
array[v];
array[v]
=
tmp;
/******隨機化拆分元素的主元*******/
var
w
=
split(array,
low,
high);
rquicksort(array,
low,
w
-1);
rquicksort(array,
w
+1,
high);
return
array;
}
}
var
array
=
[33,
22,
11,
88,
23,
32];
array
=
rquicksort(array,
0,
array.length-1);
console.log(array);

B. 隨機演算法，求解題過程和完整c代碼

還沒學

C. 求各種產生隨機數的演算法

多的很呀！別撤消呀，千萬！ 不過幾乎都是偽隨機數。 隨機序列的演算法 找到了兩個演算法, 第一個很簡單, 但可惜不是隨機的, 第二個是典型的偽隨機數演算法, 可惜要用到2的幾百萬次方這樣巨大的整數, 真痛苦 要是有UNIX上計算密碼的源代碼就好了 第一種做法: f(k) = (k*F(N-1)) mod F(N)其中, k是一個序列號, 就是要取的那個數的順序號 F(N)是這樣一個序列 F(0) = 0, F(1) = 1, F(N+2) = F(N+1)+F(N) (for N>=0)第二種做法V = ( ( V * 2 ) + B .xor. B ... )(Mod 2^n)N+1 N 0 2V是要取的隨機數, B是個種子, n是隨機數的最大個數 原來這個問題, 很高難, 不少數學高手都為解決這個問題寫了論文, 咳咳, 偶真是個白痴 呵呵, 效果肯定是不錯啦, 因為用不到很大的表. 至於應用是這樣的, 比如, 你要給每個用戶在注冊的時候一個ID但有不希望用戶在看到自己的ID的時候能知道其他用戶的ID, 如果用SEQUENCE來生成ID的話, 一個用戶只要把自己的ID減1就能得到其它用戶的ID了. 所以要用隨機數來做ID, 這樣用戶很難猜到其他用戶的ID了. 當然主要的問題是, 隨機數可能重復. 因此希望使用一個隨機數做種子用它來確定一組"無規律"的自然數序列, 並且在這個序列中不會出現重復的自然數. 在這里使用的方法生成的序列並不是沒有規律的, 只不過這個軌律很難被發現就是了. Xn+1 = (aXn + b) mod c (其中, abc通常是質數)是一種被廣泛使用的最簡單的隨機數發生演算法, 有研究表表明這個演算法生成的隨機數基本上符合統計規律, java, BORLAND C等用的都是這個方法, 一般只要保證第一個種子是真正的隨機數就行了, 下面來說一下重復的問題, 上述方法會有可能出現重復, 因為當(aXn + b)有可能是同樣的數或者說余數相同的數, 因此要想不重復就得變形 偶想到的方法是 Xn=(a*n + b) mod c n是一個在1到c之間的整數, a*n + b就是一個線性公式了, 且若n不同則a*n + b也不同, 它們除上質數c得到的余數也肯定不同, 因為 若不考慮a和b而只有n的時候, 每次的結果都是n,而線性公式, 只不過移動了這條直線的位置和斜率而已, 每個結果仍然不會相同的, 為了增加不可預計性, 偶又為上面那個公式設計了, 隨機數種子, 於是就變成了這個樣子 F(N)=(隨機數*(N+隨機數))MOD 一個質數 這樣就能夠產生 1到選定質數之間的一個"無規律"的自然數序列了, 只要改變隨機數就能改變序列的次序 在應用的時候, 要把隨機數種子和最後用到的序列號保存到一個表裡, 每此使用的時候取出來算好, 再把序列號更新一下就可以了 具體地說, 就是可以建一個表來保存每個序列的隨機數種子, 然後再為這個序列建一個SEQUENCE就行瞭然後就SELECT MOD(序列控製表.隨機數*(SEQ.NEXTVAL+序列控製表.隨機數)),序列控製表.質數) FROM 序列控製表 WHERE 序列控製表.序列ID=XX就OK了注意 序列控製表.質數 決定了序列的范圍

D. 求一PASCAL大牛教我隨機演算法....

一個基本的隨機代碼：
begin
randomize;
writeln(random(100));//在1~100范圍內隨機生成數
end.
隨機演算法經典用途：騙分

流程或執行結果。隨機化演算法基於隨機方法，依賴於概率大小。
隨機化演算法概述
在我們的生活中，人們經常會去擲色子來看結果，投硬幣來決定行動，這就牽涉到一個問題：隨機。
計算機為我們提供好了隨機方法（部分計算器也提供了），那麼對於有些具有瑕疵的演算法，如果配上隨機化演算法的話，又是可以得到一樣不到的結果。
定義：
這種演算法看上去是憑著運氣做事，其實，隨機化演算法是有一定的理論基礎的，我們可以想像，在[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)。
而制約快速排序的有兩個：一是數據，越無序的數據，快排的速度越快；二是中間點的枚舉。
因為兩個制約條件都與隨機有著不可分開的關系。
所以，在快速排序中加入隨機化演算法無疑是十分重要的。
運用在：
（1）數據讀入時，隨機排放數據位置。
（2）中間點的枚舉進行多次隨機化後決定。
這樣就基本上將快速排序的時間復雜度維持在最好狀態。
如有不明，Q我：1027321803
某沙茶寫/貼

E. 微信紅包的隨機演算法是怎樣實現的

我們在一個20人的群中，自己發紅包以及結合其他人發出紅包的情況，整合成兩輪的數據。每次金額設置都是20塊並且有20個，第一輪是發了15次，第二輪是發了19次，總結成表格，然後為了避免突發的數據影響判斷，我們將兩輪數據雜糅從而生成了其他的三輪數據，一共是五輪數據。羅列如下表，高亮的數據為最佳手氣。每一列的數據最早搶到紅包的在最底端，越往上越晚搶。
從所有黃色的數值（最佳手氣金額）可看出，所有最佳手氣值都在平均值*2的前後附近（平均值=總金額/紅包總個數，這里平均值=20/20=1），事實上確實如此，可通過微信紅包分發演算法得到驗證，演算法具體見後文
然後我們選取部分數據開始製作散點圖。橫軸為1-20，分別表示搶到紅包的人的編號，隨遞增而越早。也就是20代表最早搶到的人。縱軸為金額。同樣的形狀顏色的點代表一次發紅包，然後我們抓取部分數據顯示為散點圖，越密集代表該順序位的用戶得到的金額越穩定。散點圖如下：

規律一：我們可以看到，所有紅包大多數金額分布在0.5到1.5元之間，顯示為圖中方框所示，大部分點都分布在這個位置。然後是順序位密集程度的對比，可以發現20、19，也就是最先搶到紅包的人，小圓圈所示基本的點都集中在小范圍，說明先搶紅包的人得到的金額會比較穩定，但同時最佳手氣的概率也比較低。大圓圈所示的是極不穩定，飄忽的金額分布，表示越晚搶紅包得到的金額會飄忽不穩，但同時，搶到最佳手氣等大金額的紅包概率也比早搶的高。
根據上面的分析，我們又寫了一個過濾計數函數，針對金額的分段的紅包個數進行統計：
比如2.0-2.5
得到如下金額分布：
折線圖：
規律二：絕大多數的紅包的金額都集中在1-1.5，也就是說20塊錢發20個紅包的金額分布集中在比平均數大一點點的附近，同時較大幅超過平均數金額的紅包大大少於低於於平均數的紅包數量。
那我們繼續擴大數據的規模，將幾輪數據的均值和標准差分別做成折線圖：
綜合上面各個折線圖的情況，我們可以得到越早搶紅包的標准差越小，越晚搶紅包的標准差越大，但同時，由均值和總額可以看出來，越早搶紅包的均值往往要更高，紅包金額得到最佳手氣概率也會相對較小，越晚搶紅包的人則得到最佳手氣等大手氣的概率更大。
為了得到更為趨近規律的曲線和規律，我們決定將兩輪真實數據合並起來，然後給出冪函數的趨近線（虛線），如下圖：
由於均值受極值波動影響較大，所以我們去除一些因為偶然差產生的極端點（圓圈的點）從而發現是遞增的趨勢。
規律三：可以很明顯的看到，均值是隨著搶紅包的越晚而緩慢遞減，標准差值同時也往上遞增，這個趨勢結合之前的分析，我們猜想，即標准差越大說明，領取到最大的紅包和最小紅包的風險越大，也就是說越晚搶標准差越大，對於冒險主義者來講是最好的，因為他有很大概率獲得最大的金額，但也大概率獲得最小的紅包，風險與收益並存；均值越大，說明每次都拿到一個不大不小的紅包，雖然獲得最小和最大金額紅包的概率很小，但起碼不虧本，也就是說越早搶，均值越穩定，這比較適合不喜歡冒險的人。
驗證預測結果：
21：24分發送預測結果到另一位同學微信：

隨後開始發紅包：

結果：
最佳手氣為第8個人且金額為1.13
與預測結果一致，規律基本正確！
總結：
（1）最佳手氣為1.13塊，根據我們推導的預測公式=總額/紅包總個數*2*隨機數（0-2的double數）, 也就是說最佳手氣在總額/紅包總個數*2值的前後附近。這里我們判斷在0.8-1.3之間，推斷正確
（2)平均值為0.5元，0.5-0.8元的紅包有3個，小於0.5的紅包有6個，說明大於平均值的紅包個數多於小於平均值的個數。與我們的第二點預測完全正確
(3)最佳手氣位置：根據我們的散點圖發現，最先搶到紅包的人，得到的金額會比較穩定，但同時最佳手氣的概率也比較低。表示越晚搶紅包得到的金額波動較大，但同時搶到最佳手氣等大金額的紅包概率也比早搶的高。所以我們推斷，最佳手氣位置在最後20%-30%之間。
微信紅包隨機分發演算法c＋＋模擬：
基本思路：每次搶到一個紅包金額等於：紅包剩餘金額/紅包剩餘個數*2*隨機數（0-1的double型），如果計算的結果小於等於0.01，則取0.01值
主要代碼：
double packages[50000];
double Luckiest_money=0;
void getPackage(int remainSize,double remainMoney){
srand((unsigned)time(NULL));
for(int i=0;i

F. C語言抽取隨機數怎麼編寫

源程序代碼以及演算法解釋如下：

產生1-10隨機數程序：

#include <iostream>

#include <time.h>

using namespace std;

int main()

{

const int n = 10;//定義隨機數個數

int number[n] = { NULL };//定義隨機數存儲的數組

srand((unsigned)time(NULL));//初始化隨機函數

number[0] = rand() % n;//第一個隨機數無需比較

cout << number[0] << " ";

for (int i = 1; i < n; i++)//其餘隨機數循環產生

{

int j = 0;

number[i] = rand() % n;//產生隨機數

while (1)

{

if (number[i] == number[j])//若有相同則繼續循環重新安排隨機數

{

number[i] = rand() % n;//產生隨機數

j = 0;//若遇到相同的就從頭遍歷

continue;

}

if (j == (i - 1))//若遍歷完就跳出

break;

j++;

}

cout << number[i] << " ";

}

cout << endl;

return 0;

}

程序運行結果如下：

(6)隨機演算法代碼擴展閱讀：

利用vector進行隨機數輸出：

#include <iostream>

#include <vector>

#include <time.h>

using namespace std;

int main()

{

const int n = 10;

int randnum;

vector<int> number;

for (int i = 0; i < n; i++)

{

number.push_back(i + 1);//從尾部添加元素

cout << number[i] << " ";

}

cout << endl;

srand((unsigned)time(NULL));

for (int j = 0; j < n; j++)//其餘隨機數循環產生

{

randnum = rand() % (n - j);//rand函數生成的隨機數是0-（n-1）

cout << number.at(randnum) << " ";

number.erase(number.begin() + randnum);

}

cout << endl;

return 0;

}

G. java中如何產生64位隨機數

1.新建工程和類，在類中導入包import java.util.*。

H. 求一個java的隨機演算法，高手來

好好的看一下就知道為什麼list的長度與count 相同時，總是出現死循環 。
你在int[] a=new int[count]; 這一步操作時，數組a中的數據全部默認為0，而int rs=ran.nextInt(list.size()); 返回的值是0到list.size()-1的數。當list的長度與count 相同時，在產生最後一個隨機數時，只能產生0，可是0在數組a中又存在了，所以就死循環了。

編程時，多注意邊界問題。

I. 隨機演算法、函數

產生整數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

J. 求「米勒-拉賓素數隨機測試演算法」C語言代碼+詳細注釋。財富不是問題！！！

//參數入口為test(lld n)
typedef __int64 lld;
const lld MAX=10;
lld multi(lld a,lld b,lld m)//加法代替乘法，防止溢出__int64
{
lld ret=0;
a%=m;
while(b)
{
if(b&1) if((ret+=a)>=m) ret-=m;
if((a<<=1)>=m) a-=m;
b>>=1;
}
return ret;
}
lld mod(lld a,lld b,lld m)
{
lld x,y;
if(b==1)//1次冪，直接返回
return a%m;
x=mod(a,b>>1,m);//二分求冪
y=multi(x,x,m);//平方一下
if(y==1&&x!=1&&x!=m-1)//如果結果是1的時候，如果x不是1而且不是m-1那麼m必然不是素數。
return 0;
if(b&1)//奇數的情況，再乘上一個a
y=multi(y,a,m);
return y;
}
lld gen(lld m)
{
lld ret=1,i;
for(i=0;i<4;i++)
ret*=rand();
ret%=m;
if(ret<0)
ret+=m;
return ret;
}
//入口
bool test(lld n)
{
lld a,i,tmp;
if(n<2)//小於2不是素數
return 0;
if(n==2)//2是素數，直接返回
return 1;
if((n&1)==0)//偶數
return 0;
for(i=0;i<MAX;i++)//測試最大次數
{
a=gen(n-1)+1;//生成一個2到n-2的數字
tmp=mod(a,n-1,n);//快速冪
if(tmp!=1)//結果不是1，不是素數
return 0;
}
return 1;//是素數
}