線性同餘演算法特徵

① 線性同餘演算法一般認為2∧k-1比2∧k要好,這是為什麼

電信彭宇演算法一般認為二這個要好不知道我提都交不上去。

② 如何評價一個偽隨機數生成演算法的優劣

從我的角度認為，達到設計需求的隨機就是優秀的無論它是真或假，是否滿足那個k1234其它領域不熟就不說，就游戲領域，我認為游戲領域不需要優秀的真隨機，需要的都是優秀的偽隨機。酷跑，我需要隨機拼接場景，道具，分值，以達到不單調重復的目的。但是我又需要控制游戲節奏，用戶的體驗節奏，因此我需要根據用戶的得分情況，失誤操作去設置一堆的閥值，來調整隨機規則，讓用戶不斷產生一種錯覺，這只是失誤，就差一點點，都是因為xxx同理可推，抽獎、掉落、攻擊、爆擊、合成等。個人以為，在實際應用領域，滿足設計需求的偽隨機比演算法優秀的真隨機優秀太多太多，當然一切前提是說明隨即需求，很多時候設計者自己都說不清他的隨機需求是啥，只是覺得需要隨機。

③ Java怎麼用線性同餘法跟取余法一起產生一個序列。

亂數是不重復的隨機數嗎?

很多演算法的每一個計算步驟都是固定的，而在下面我們要討論的概率演算法，允許演算法在執行的過程中隨機選擇下一個計算步驟。許多情況下，當演算法在執行過程中面臨一個選擇時，隨機性選擇常比最優選擇省時。因此概率演算法可在很大程度上降低演算法的復雜度。
概率演算法的一個基本特徵是對所求解問題的同一實例用同一概率演算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下，可將概率演算法大致分為四類:數值概率演算法，蒙特卡羅(Monte Carlo)演算法，拉斯維加斯(Las Vegas)演算法和舍伍德(Sherwood)演算法。
數值概率演算法常用於數值問題的求解。這類演算法所得到的往往是近似解。而且近似解的精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必要的，因此用數值概率演算法可得到相當滿意的解。
蒙特卡羅演算法用於求問題的准確解。對於許多問題來說，近似解毫無意義。例如，一個判定問題其解為「是」或「否」，二者必居其一，不存在任何近似解答。又如，我們要求一個整數的因子時所給出的解答必須是准確的，一個整數的近似因子沒有任何意義。用蒙特卡羅演算法能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴於演算法所用的時間。演算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅演算法的主要缺點就在於此。一般情況下，無法有效判斷得到的解是否肯定正確。
拉斯維加斯演算法不會得到不正確的解，一旦用拉斯維加斯演算法找到一個解，那麼這個解肯定是正確的。但是有時候用拉斯維加斯演算法可能找不到解。與蒙特卡羅演算法類似。拉斯維加斯演算法得到正確解的概率隨著它用的計算時間的增加而提高。對於所求解問題的任一實例，用同一拉斯維加斯演算法反復對該實例求解足夠多次，可使求解失效的概率任意小。
舍伍德演算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性演算法在最壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定演算法中引入隨機性將它改造成一個舍伍德演算法，消除或減少問題的好壞實例間的這種差別。舍伍德演算法精髓不是避免演算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關聯性。
本文簡要的介紹一下數值概率演算法和舍伍德演算法。
首先來談談隨機數。隨機數在概率演算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在概率演算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。
產生隨機數最常用的方法是線性同餘法。由線性同餘法產生的隨機序列a1,a2,...,an滿足
a0=d
an=(ban-1+c)mod m n=1,2.......
其中,b>=0, c>=0, d>=m。d稱為該隨機序列的種子。
下面我們建立一個隨機數類RadomNumber，該類包含一個由用戶初始化的種子randSeed。給定種子之後，既可產生與之相應的隨機數序列。randseed是一個無符號長整型數，既可由用戶指定也可由系統時間自動產生。
const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;
class RandomNumber
{
private:
//當前種子
unsigned long randseed;
public:
//構造函數，預設值0表示由系統自動產生種子
RandomNumber(unsigned long s=0);
//產生0-n-1之間的隨機整數
unsigned short Random(unsigned long n);
//產生[0，1)之間的隨機實數
double fRandom(void);
};
RandomNumber::RandomNumber(unsigned long s)
{
if(s==0)
randseed=time(0);
else
randseed=s;
}
unsigned short RandomNumber::Random(unsigned long n)
{
randseed=multiplier*randseed+adder;
return (unsigned short)((randseed>>16)%n);
}
double RandomNumber::fRandom(void)
{
return Random(maxshort)/double(maxshort);
}
函數Random在每次計算時，用線性同餘式計算新的種子。它的高16位的隨機性較好，將randseed右移16位得到一個0-65535之間的隨機整數然後再將此隨機整數映射到0-n-1范圍內。
對於函數fRandom,先用Random(maxshort)產生一個0-(maxshort-1之間的整型隨機序列)，將每個整型隨機數除以maxshort，就得到[0，1)區間中的隨機實數。
下面來看看數值概率演算法的兩個例子:
1.用隨機投點法計算π
設有一半徑為r的圓及其外切四邊形，如圖所示。向該正方形隨機投擲n個點。設落入圓內的點在正方形上均勻分布，因而所投入點落入圓內的概率為 πr^2/4r^2，所以當n足夠大時，k與n之比就逼近這一概率，即π/4。由此可得使用隨機投點法計算π值的數值概率演算法。具體實現時，只需要在第一次象限計算即可。

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);
}
再簡單舉個舍伍德演算法的例子。
我們在分析一個演算法在平均情況下的計算復雜性時，通常假定演算法的輸入數據服從某一特定的概率分布。例如，在輸入數據是均勻分布時，快速排序演算法所需的平均時間是O(n logn)。但是如果其輸入已經基本上排好序時，所用時間就大大增加了。此時，可採用舍伍德演算法消除演算法所需計算時間與輸入實例間的這種聯系。
在這里，我們用舍伍德型選擇演算法隨機的選擇一個數組元素作為劃分標准。這樣既能保證演算法的線性時間平均性能又避免了計算擬中位數的麻煩。非遞歸的舍伍德型演算法可描述如下:
template<class Type>
Type select(Type a[], int l, int r, int k)
{
static RandomNumber rnd;
while(true){
if(l>=r)
return a[l];
int i=l, j=l=rnd.Random(r-l+1);
Swap(a[i], a[j]);
j=r+1;
Type pivot=a[l];
while(true)
{
while(a[++i]<pivot);
while(a[--j]>pivot);
if(i>=j)
break;
Swap(a[i], a[j]);
}
if(j-l+1==k)
return pivot;
a[l]=a[j];
a[j]=pivot;
if(j-l+1<k)
{
k=k-j+l-1;
l=j+1;
}
else
r=j-1;
}
}
template <class Type>
Type Select(Type a[], int n, int k)
{
if(k<1||k>n)
throw OutOfBounds();
return select(a, 0, n-1, k);
}
平時我們一般開始考慮的是一個有著很好平均性能的選擇演算法，但在最壞情況下對某些實例演算法效率較低。這時候我們用概率演算法，將上述演算法改造成一個舍伍德型演算法，使得該演算法對任何實例均有效。
不過在有些情況下，所給的確定性演算法無法直接改造成舍伍德型演算法。這時候就可以藉助隨機預處理技術，不改變原有的確定性演算法，僅對其輸入進行隨機洗牌，同樣可以得到舍伍德演算法的效果。還是剛才的例子，換一種方法實現:
template<class Type>
void Shuffle(Type a[], int n)
{
static RandomNumber rnd;
for(int i=1;i<n;i++){
int j=rnd.Random(n-i)+i;
Swap(a[i], a[j]);
}
}

④ 計算機產生偽隨機數的周期是多少演算法是什麼

為追求真正的隨機序列，人們曾採用很多種原始的物理方法用於生成一定范圍內滿足精度（位數）的均勻分布序列，其缺點在於：速度慢、效率低、需佔用大量存儲空間且不可重現等。為滿足計算機模擬研究的需求，人們轉而研究用演算法生成模擬各種概率分布的偽隨機序列。偽隨機數是指用數學遞推公式所產生的隨機數。從實用的角度看，獲取這種數的最簡單和最自然的方法是利用計算機語言的函數庫提供的隨機數發生器。典型情況下，它會輸出一個均勻分布在0和1區間內的偽隨機變數的值。其中應用的最為廣泛、研究最徹底的一個演算法即線性同餘法。

線性同餘法LCG（Linear Congruence Generator）

選取足夠大的正整數M和任意自然數n0，a，b，由遞推公式：

ni+1=（af（ni）+b）mod M i=0，1，…，M-1

生成的數值序列稱為是同餘序列。當函數f（n）為線性函數時，即得到線性同餘序列：

ni+1=（a*ni+b）mod M i=0，1，…，M-1

以下是線性同餘法生成偽隨機數的偽代碼：

Random（n，m，seed，a，b）
{
r0 = seed；
for （i = 1；i<=n；i++）
ri = （a*ri-1 + b） mod m
}

其中種子參數seed可以任意選擇，常常將它設為計算機當前的日期或者時間；m是一個較大數，可以把它取為2w，w是計算機的字長；a可以是0.01w和0.99w之間的任何整數。

應用遞推公式產生均勻分布隨機數時，式中參數n0，a，b，M的選取十分重要。

例如，選取M=10，a=b =n0=7，生成的隨機序列為{6，9，0，7，6，9，……}，周期為4。

取M=16，a=5，b =3，n0=7，生成的隨機序列為{6，1，8，11，10，5，12，15，14，9，0，3，2，13，4，7，6，1……}，周期為16。

取M=8，a=5，b =1，n0=1，生成的隨機序列為{6，7，4，5，2，3，0，1，6，7……}，周期為8。

Visual C++中偽隨機數生成機制

用VC產生隨機數有兩個函數，分別為rand（void）和srand（seed）。rand()產生的隨機整數是在0~RAND_MAX之間平均分布的，RAND_MAX是一個常量（定義為：#define RAND_MAX 0x7fff）。它是short型數據的最大值，如果要產生一個浮點型的隨機數，可以將rand()/1000.0，這樣就得到一個0~32.767之間平均分布的隨機浮點數。如果要使得范圍大一點，那麼可以通過產生幾個隨機數的線性組合來實現任意范圍內的平均分布的隨機數。

其用法是先調用srand函數，如

srand( (unsigned)time( NULL ) )

這樣可以使得每次產生的隨機數序列不同。如果計算偽隨機序列的初始數值（稱為種子）相同，則計算出來的偽隨機序列就是完全相同的。要解決這個問題，需要在每次產生隨機序列前，先指定不同的種子，這樣計算出來的隨機序列就不會完全相同了。以time函數值（即當前時間）作為種子數，因為兩次調用rand函數的時間通常是不同的，這樣就可以保證隨機性了。也可以使用srand函數來人為指定種子數分析以下兩個程序段，

程序段1：

//包含頭文件
void main() {
int count=0;
for (int i=0;i<10;i++){
srand((unsigned)time(NULL));
count++;
cout<<"No"<
//包含頭文件
void main() {
int count=0;
srand((unsigned)time(NULL));
for (int i=0;i<10;i++){
count++;
cout<<"No"<
No1=9694 No2=9694 No3=9694 No4=9694 No5=9694
No6=9694 No7=9694 No8=9694 No9=9694 No10=9694

程序段2的運行結果為：

No1=10351 No2=444 No3=11351 No4=3074 No5=21497
No6=30426 No7=6246 No8=24614 No9=22089 No10=21498

可以發現，以上兩個程序段由於隨機數生成時選擇的種子的不同，運行的結果也不一樣。rand()函數返回隨機數序列中的下一個數(實際上是一個偽隨機數序列，序列中的每一個數是由對其前面的數字進行復雜變換得到的)。為了模模擬正的隨機性，首先要調用srand()函數給序列設置一個種子。為了更好地滿足隨機性，使用了時間函數time()，以便取到一個隨時間變化的值，使每次運行rand()函數時從srand()函數所得到的種子值不相同。偽隨機數生成器將作為"種子"的數當作初始整數傳給函數。這粒種子會使這個球（生成偽隨機數）一直滾下去。

程序段1中由於將srand（）函數放在循環體內，而程序執行的CPU時間較快，調用time函數獲取的時間精度卻較低（55ms），這樣循環體內每次產生隨機數用到的種子數都是一樣的，因此產生的隨機數也是一樣的。而程序段2中第1次產生的隨機數要用到隨機種子，以後的每次產生隨機數都是利用遞推關系得到的。 基於MFC的隨機校驗碼生成

Web應用程序中經常要利用到隨機校驗碼，校驗碼的主要作用是防止黑客利用工具軟體在線破譯用戶登錄密碼，校驗碼、用戶名、密碼三者配合組成了進入Web應用系統的鑰匙。在利用VC開發的基於客戶機/瀏覽器（Client/Server）模式的應用軟體系統中，為了防止非法用戶入侵系統，通常也要運用隨機校驗碼生成技術。

⑤ 想知道這兩個結果的原理100 - Random(100) * Random(100) div 100; 或 100 - Random(Random(100));

線性同餘法(Linear Congruential Method)
目前使用的大多數隨機數發生器是線性同餘發生器，它是Lehmer於1951年提出的.
其通式為 Xi+1=(a*Xi+c)mod m
Ui+1=Xi+1／m 其中a為乘子(常數)，C為增量(常數)，X0為種子，m為模。
線性同餘法有如下特點：
(1)0≤Xi≤m-1,即Xi只能從0，1，2，……，m-1這m個整數中取值；
(2)適當選擇m,a,c,可使Xi產生循環，無論X0取何值，其循環順序是相同的。其循環周期稱為發生器周期，記為P。若p=m,則稱該發生器具有滿周期。

這樣的方法生成的是偽隨機數,因為數列的前驅和後繼的相關的,他服從均勻分布.
你想要的是不服從均勻分布的隨機數,可以對產生的隨機數列進行非線性運算,就可以得到其他分布.工程上浮從各種分布的隨機數都是這樣產生的.
你可以用sqrt(random(10000))試試看.

⑥ 線性同餘 是什麼

自己領悟把

一．計算機中隨機數的產生
現在，在計算機，用來產生隨機數的演算法是「線性同餘」法。所謂線性同餘，其實就是下面兩個式子。假設I就是一個隨機數的序列，Ij+1與Ij的關系如下：
Ij+1 =Ij * a+c (mod m)
或是Ij+1 =Ij *a (mod m)，
其中，不妨取a=16807，m=2147483647，以為一常數。寫個簡單的程序就是：
long r;

void scand( long v)//初始化隨機種子數
{
r = v;
}

long rand()//產生隨機數
{
r = (r*a + c)%m;//a,c,m為常數
return r;
}
再看一下稍復雜一點的：(Random () 的 Borland 的實現)
long long RandSeed = #### ;
unsigned long Random(long max)
{
long long x ;
double i ;
unsigned long final ;
x = 0xffffffff;
x += 1 ;
RandSeed *= ((long long)134775813);
RandSeed += 1 ;
RandSeed = RandSeed % x ;
i = ((double)RandSeed) / (double)0xffffffff ;
final = (long) (max * i) ;
return (unsigned long)final;
}
二．計算機產生的隨機數不是真的隨機數
[引:]我們建立了真正調用偽隨機數生成器的 random()。但什麼是偽隨機數生成器？假定需要生成介於 1 和 10 之間的隨機數，每一個數出現的幾率都是一樣的。理想情況下，應生成 0 到 1 之間的一個值，不考慮以前值，這個范圍中的每一個值出現的幾率都是一樣的，然後再將該值乘以 10。請注意，在 0 和 1 之間有無窮多個值，而計算機不能提供這樣的精度。
為了編寫代碼來實現類似於前面提到的演算法，常見情況下，偽隨機數生成器生成 0 到 N 之間的一個整數，返回的整數再除以 N。得出的數字總是處於 0 和 1 之間。對生成器隨後的調用採用第一次運行產生的整數，並將它傳給一個函數，以生成 0 到 N 之間的一個新整數，然後再將新整數除以 N 返回。這意味著，由任何偽隨機數生成器返回的數目會受到 0 到 N 之間整數數目的限制。
在大多數的常見隨機數發生器中，N 是 232? （大約等於 40 億），對於 32 位數字來說，這是最大的值。換句話說，我們經常碰到的這類生成器能夠至多生成 40 億個可能值。而這 40 億個數根本不算大，只是指尖這么大。
偽隨機數生成器將作為「種子」的數當作初始整數傳給函數。這粒種子會使這個球（生成偽隨機數）一直滾下去。偽隨機數生成器的結果僅僅是不可預測。由偽隨機數生成器返回的每一個值完全由它返回的前一個值所決定（最終，該種子決定了一切）。如果知道用於計算任何一個值的那個整數，那麼就可以算出從這個生成器返回的下一個值。
結果，偽隨機數生成器是一個生成完全可預料的數列（稱為流）的確定性程序。一個編寫得很好的的 PRNG 可以創建一個序列，而這個序列的屬性與許多真正隨機數的序列的屬性是一樣的。例如：
PRNG 可以以相同幾率在一個范圍內生成任何數字。
PRNG 可以生成帶任何統計分布的流。
由 PRNG 生成的數字流不具備可辨別的模式。
PRNG 所不能做的是不可預測。如果知道種子和演算法，就可以很容易地推算出這個序列。

計算機產生的隨機數一般都只是一個周期很長的數列，不是真的隨機數。也就是說，隨機數一般是偽隨機數，每個隨機數都是由隨機種子開始的一個已定的數列（周期很長）。一般地，為了隨機數更真一點，隨機種子在系統中通常是參照系統時鍾生成的。
看看下面這個例子,從中，讀者應能有所體會。
main()
{
int i;
scand(time(NULL)); /＊可向計算機讀取其時鍾值，並把值自動設為隨機數種子＊／
for(i=0;i<10;i++){
printf("%10d",1+(rand()%6));/*這里1是移動值，他等於所需的連續整數＊／
｝ ／＊數值范圍的第一個數；b是比例因子；他＊／
return(0); ／＊等於所需的連續整數值的范圍寬度；＊／
}
從數學上講，為了得到一個周期性更長的隨機序列，我們可以使用如下方法：（這是我在一個書上看到的，詳細的情況大家可以查一查，我自己也記不清了，呵呵）
float rand(long* im)
{
int j; long k; static long iy=0; static long iv[NTAB];
float temp;
if(*im<=0||!iy)
{
if(-(*im)<1) *im=1;
else *im=-(*im);
for(j=NTAB+7;j>=0;j--){
k=(*im)/IQ;
*im=IA*(*im-k*IQ)-k*IR;
if(*im<0)
*im+=IM;
if(j<NTAB)
iv[j]=*im;
} iy=iv[0]; }
k=(*im)/IQ;
*im=IA*(*im-k*IQ)-k*IR;
if(*im<0) *im+=IM;
j=iy/NDIV;
iy=iv[j];
iv[j]=*im;
if((temp=float(AM*iy))>RNMX) return float(RNMX);
else return temp;
}

[注:]有文講 ，根據Randomize的工作原理，利用函數Timer得到從午夜開始到現在經過的秒數，然後再根據要得到的隨機數值大小對該數值進行"「衰減」處理，這樣得到的數值則可稱得上是真正意義的隨機數值，我認為，這也是人為的方法，仍有它的確定性和周期性，仍稱不上是真正的隨機數，單純改變偽隨機數的生成邏輯計算方法並不能達到目的，最有效的辦法只能是改變rand_seed，就是種子。而且，改變後的rand_seed不應該是人為的。（註：目前，在 Intel 的PIII處理器中內置了一個與CPU溫度相關的隨機數生成器，算是一個比較有效的種子生成器。）更好的辦法是根據「隨機事件」生成隨機數，如鍵盤和滑鼠輸入值、中斷、磁碟讀取等等。然而，許多伺服器沒有鍵盤和滑鼠，許多「黑盒」產品也不帶有硬碟，因此很難找到好的隨機數源，當然，通訊密鑰也就一樣不安全。而如網路狀態等也不能很好地保證隨機數的「隨機性」。電器雜訊和聲音頻率也許是很好的隨機數源，但大多數人恐怕並不願意在計算機中增加這種設備，而且也可能出現設備失靈和外部操縱（影響）等問題。對於要處理大量連接的網關伺服器，是必須要考慮的問題。如果可以通過，精確檢測機器cpu的通電電流強度，來作為隨機數種子，或是其他一些沒有人為因素的干擾的，且瞬間變化快的方法獲得種子，必將能產生符和要求的隨機數。

三．幾種隨機數的獲取辦法
1.產生一個范圍內的隨機數
一般地，我們可用j=1+(int)(n*rand()/(RAND_MAX+1.0))來生成一個0到n之間的隨機數。
若用int x = rand() % 100;來生成 0 到 100 之間的隨機數這種方法是不可取的，比較好的做法是： j=(int)(100.0*rand()/(RAND_MAX+1.0)) ，當然，我們也可是使用random(100)。下面的例子都是用了random(n).
2、篩選型隨機數 如希望取0-99的隨機數，但不能是6。
解決方法：
x = random(100);
while (x==6) {
x = random(100);
}
又如希望取0-99的隨機數，但不要5的倍數 解決方法：
x = random(100);
while ((x ％ 5)==0) {
x = random(100);
}
3、從連續的一段范圍內取隨機數。
如從40--50的范圍內取隨機數。 解決方法： x=random(11)+40
4、從一組亂數中取隨機數。 如：從 67, 87, 34, 78, 12, 5, 9, 108, 999, 378十個數中隨機取數。 解決方法：可以用數組將些十個數存貯，然後把0－－9中取出的隨機數作為序號，實現隨機取數。
a = new Array(67, 87, 34, 78, 12, 5, 9, 108, 999, 378);
j = random(10);
x = a[j];
四．產生具有一定分布的隨機數
關於這點，有一篇文章寫得很好，請看：
非均勻分布隨機數的產生及其在計算機模擬研究中的應用
作者：胡性本 劉向明 方積乾
單位：胡性本（湖北職工醫學院 荊州434000）； 劉向明（湖北職工醫學院 荊州434000 現為華中理工大學生物工程系博士研究生）； 方積乾（湖北職工醫學院 荊州434000 中山醫科大學）
關鍵詞：非均勻分布隨機數；計算機模擬；程序設計
摘 要：非均勻分布隨機數在進行計算機模擬研究中有重要作用，但計算機高級語言通常都只提供產生均勻分布隨機數的函數，給研究工作帶來困難。該文提出的方法，較好地解決了這一問題，有很強的適用性。

中圖分類號：O 242.1
文章編號：1004-4337(2000)01-0059-02▲
1 問題的提出
常用的計算機高級程序設計語言，大多提供了產生在〔0，1〕區間內連續均勻分布的獨立隨機數r的函數。若將產生的隨機數作簡單的變換X=a+(b-a)r，就能得到在區間〔a,b〕上均勻分布的隨機數X。如果與取整或舍入函數結合運用，還可得到離散均勻分布的隨機數，給計算機模擬提供了方便。但在很多情況下進行計算機模擬需要用到按某些特定規律分布的非均勻隨機數。例如，在離子通道門控模型的模擬研究中，就經常要用到服從指數分布、對數分布、正態分布、普畦松分布等非均勻分布的隨機數。這時可以在源程序中編寫一個函數或過程來產生。我們在近年來所進行的計算機模擬研究工作〔1,2〕中，大量使用了非均們分布的隨機數，獲得成功。由於離散隨機數可以由連續隨機數通過取整或舍入等途徑轉換而得，本文只側重介紹非均勻分布連續隨機數的產生原理和應用實例，並給出了用類PASCAL語言〔3〕編寫的相應的函數和過程。掌握了任何一種計算機高級語言編程技術和數據結構知識的人，都能很方便地轉換成能上機運行的程序，有很大的靈活性與很強的實用性。
2 產生原理
假定連續隨機變數X是連續隨機變數R的函數
x= ® (1)
由概率統計知識可知，X與R在對應點的分布函數的數值應當相等，即產生R的反變換
F(x)=F® (2)
其中，r為(1)式的解，即r= -1(x)=Ψ(x)
在特殊情況下，若R是在〔0，1〕區間內的均勻分布的連續隨機變數，那麼R<r的概率P(R<r)=r。此時，(2)式可以簡化為
F(x)=F®=r (3)
其反函數
x=F-1® (4)
具有分布函數F，現予以證明：因為分布函數是單調遞增函數，其反函數存在。由概率知識可知，對任意實數X，有
P(X<x)=P(F-1(R)<x)=P(R<F(x))
因為R是在〔0，1〕區間上的均勻分布的連續隨機變數，故P(R<F(x))=F(x)，即F-1®具有分布函數F。
(4)式表明，要產生一個服從某種分布的隨機數，可以先求出其分布函數的反函數的解析式，再將一個在〔0，1〕區間內的均勻隨機數的值代入其中計算就可以了。
3 應用實例
例1 產生密度函數滿足指數分布

的隨機數，其中α>0。
因為 ，故分布函數為：

由(4)式可得
(5)
當r為〔0，1〕區間內的均勻隨機數時，1-r也是〔0，1〕區間內的均勻隨機數，故(5)式還可以簡化為：
(6)
假定計算機高級語言已提供了產生在〔0，1〕區間內均勻分布的隨機數的函數RND(0)，則根據(6)式可以寫出產生服從指數分布的隨機數的類PASCAL語言的函數如下：
FUNC get_exp_random(alpha:real):real;
｛產生服從指數分布的隨機數，值參alpha為比例參數｝
get_exp_random=-ln(RND(0))/alpha;
ENDF； ｛get_exp_random｝
例2 產生服從正態分布的隨機數
正態分布X～N(a,σ)都可以由標準的正態分布X′～N(0,1)經過變換X=a+σX′得到，在此只討論服從標准正態分布的隨機數的產生方法。標准正態分布的密度函數為：
(7)
但其分布函數不能用有限的解析形式來表示，給轉換帶來困難，但可以用以下的變換來產生隨機數。
假定r1與r2是〔0,1〕區間的兩個獨立的均勻分布隨機數，現將其作如下的變換，令
(8)
再將其反變換為：
(9)
(9)式中的C為常數。由此可導出其密度函數為：
(10)
比較(10)式與(7)式，可知X1與X2是兩個相互獨立的服從正態分布的隨機變數，因而(8)式是與(4)相當的據以產生隨機數的表達式。由此可以寫出產生服從標准正態分布隨機數的類PASCAL語言的過程如下：
PROC gauss(VAR x1,x2:real);
｛產生服從正態分布的隨機數對，用變數參數x1與x2傳遞隨機數｝
pi:=3.14159265; ｛賦π值｝
r1:=RND(0); r2:=RND(0);
s:=SQRT(-2*ln(r1)); ｛中間變數賦值｝
x1:=s*cos(2*pi*r2);
x2:=s*sin(2*pi*r2);
｛正態分布隨機數賦給變數參數｝
ENDP； ｛gauss｝
此過程每調用一次能產生兩個相互正交的標准正態分布隨機數。

⑦ 如何編程實現線性同餘發生器演算法生成偽隨機數

#include <iostream>
#include <ctime>
using namespace std;int main(){srand(time(NULL)); //這個產生種子的函數在這個位置
for (int i=0;i<50;i++)
{ int n=rand()%10; //n1,n1,n1 cout<<n<<" ";
}
cout<<endl;
}另一個改成：#include <iostream>
#include <ctime>
using namespace std;int main(){ for (int i=0;i<50;i++)
{ srand(time(NULL)); //這個產生種子的函數在這個位置 int n=rand()%10; //n1,n1,n1 cout<<n<<" ";
}
cout<<endl;
}

⑧ 線性同餘法產生偽隨機數流，給定初始值：a=5，c=3，m6，種子值=5，則生成的第一個[0，1]區

摘要 您好！很高興為您解答！

⑨ 線性同餘方程的特點及求解是什麼

線性同餘方程 在數論中，線性同餘方程是最基本的同餘方程，「線性」表示方程的未知數次數是一次，即形如： 的方程。此方程有解當且僅當 b 能夠被 a 與 n 的最大公約數整除（記作 gcd(a,n) | b）。這時，如果 x0 是方程的一個解，那麼所有的解可以表示為： 其中d 是a 與 n 的最大公約數。在模 n 的完全剩餘系 {0,1,…,n-1} 中，恰有 d 個解。 目錄 1 例子 2 求特殊解 3 線性同餘方程組 4 參見 例子 在方程 3x ≡ 2 (mod 6) 中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程無解。 在方程 5x ≡ 2 (mod 6) 中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一個解: x=4。 在方程 4x ≡ 2 (mod 6) 中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有兩個解: x=2 and x=5。 求特殊解 對於線性同餘方程 ax ≡ b (mod n) (1) 若d = gcd(a, n 整除 b ，那麼為整數。由裴蜀定理，存在整數對 (r,s) （可用輾轉相除法求得）使得 ar+sn=d，因此 是方程 (1) 的一個解。其他的解都關於與 x 同餘。 舉例來說，方程 12x ≡ 20 (mod 28) 中d = gcd(12,28) = 4 。注意到 ，因此 是一個解。對模 28 來說，所有的解就是 {4,11,18,25} 。 線性同餘方程組 線性同餘方程組的求解可以分解為求若干個線性同餘方程。比如，對於線性同餘方程組： 2x ≡ 2 (mod 6) 3x ≡ 2 (mod 7) 2x ≡ 4 (mod 8) 首先求解第一個方程，得到x ≡ 1 (mod 3)，於是令x = 3k + 1，第二個方程就變為： 9k ≡ 1 (mod 7) 解得k ≡ 3 (mod 7)。於是，再令k = 7l + 3，第三個方程就可以化為： 42l ≡ 16 (mod 8) 解出：l ≡ 0 (mod 4)，即 l = 4m。代入原來的表達式就有 x = 21(4m) + 10 = 84m + 10，即解為： x≡ 10 (mod 84) 對於一般情況下是否有解，以及解得情況，則需用到數論中的中國剩餘定理。 參見 二次剩餘 中國剩餘定理 談談解線性同餘方程 因為ACM/ICPC中有些題目是關於數論的，特別是解線性同餘方程，所以有必要准備下這方面的知識。關於這部分知識，我先後翻看過很多資料，包括陳景潤的《初等數論》、程序設計競賽例題解、「黑書」和很多網上資料，個人認為講的最好最透徹的是《演算法導論》中的有關章節，看了之後恍然大悟。經過幾天的自學，自己覺得基本掌握了其中的「奧妙」。拿出來寫成文章。 那麼什麼是線性同餘方程？對於方程：ax≡b(mod m)，a，b，m都是整數，求解x 的值。 解題常式：pku1061 青蛙的約會 解題報告 符號說明： mod表示：取模運算 ax≡b(mod m)表示：(ax - b) mod m = 0，即同餘 gcd(a,b)表示：a和b的最大公約數 求解ax≡b(mod n)的原理： 對於方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整數。而ax≡b(mod n)的解可以由x，y來堆砌。具體做法，見下面的MLES演算法。 第一個問題：求解gcd(a,b) 定理一：gcd(a,b) = gcd(b,a mod b) 實現：古老的歐幾里德演算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附：取模運算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二個問題：求解ax + by = gcd(a,b) 定理二：gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 則：x = y' y = x' - a / b * y' 實現： triple Extended_Euclid(int a,int b) { triple result; if(b == 0) { result.d = a; result.x = 1; result.y = 0; } else { triple ee = Extended_Euclid(b,mod(a,b)); result.d = ee.d; result.x = ee.y; result.y = ee.x - (a/b)*ee.y; } return result; } 附：三元組triple的定義 struct triple { int d,x,y; }; 第三個問題：求解ax≡b(mod n) 實現：由x，y堆砌方程的解 int MLES(int a,int b,int n) { triple ee = Extended_Euclid(a,n); if(mod(b,ee.d) == 0) return mod((ee.x * (b / ee.d)),n / ee.d); else return -1; }//返回-1為無解，否則返回的是方程的最小解 說明：ax≡b(mod n)解的個數： 如果ee.d 整除 b 則有ee.d個解； 如果ee.d 不能整除 b 則無解。

求採納