小話隨機數
本文正體字版由OpenCC轉換
標準函數庫中函數rand()可以生成0~RAND_MAX之間的一個隨機數，其中RAND_MAX 是stdlib.h中定義的一個整數，它與系統有關。 例如在我的機器上，RAND_MAX=32767。可以使用 printf("%ld",RAND_MAX);查看。
調用rand()可以生成一個隨機數，但我們往往需要的是一個有上下界的隨機數。
例如 要產生一個[a,b]之間的隨機整數x
x = rand()%(b-a+1)+a
產生區間[a,b]上的隨機實數
z = ((double)rand()/RAND_MAX)*(b-a) + a
衆所周知，計算機產的隨機序列實際上是一個有很長週期的序列（通過線性同餘算法），這就是僞隨機數。隨機數產生時需要一個seed(種子)，才能產生隨機數。
在Pascal 和 Basic 中，都可以使用 randomize;來初始化種子。而在C中，需要用srand(unsigned int)函數給予一個種子。 例如srand(time(NULL));
一般來說在OI中，依靠隨機數的算法較爲穩定，它不受隨機序列的影響（難道有人看過默認的隨機序列，專門設計出一組卡隨機的測試數據？？？？）。所以srand調用與否沒有太大關係。況且time()函數定義在 time.h 中，某些評測系統禁止使用time.h。我一般都是srand(rand());。
線性同餘方法（LCG）是個產生僞隨機數的方法。
它是根據遞歸公式：
其中A,B,M是產生器設定的常數。
LCG的週期最大爲M，但大部分情況都會少於M。要令LCG達到最大週期，應符合以下條件：
1. B,M互質；
2. M的所有質因子的積能整除A − 1；
3. 若M是4的倍數，A − 1也是；
4. A,B,N0都比M小；
5. A,B是正整數。
使用線性同餘算法產生僞隨機數 轉自http://www.blog.edu.cn/user1/20989/archives/2005/989163.html C語言中有個random(n)函數，可以產生0——n-1之間的僞隨機數，rand()函數可以產生0——32767之間的僞隨機數，一般需要配合使用srand(long)給出隨機種子，或者使用randomize()函數來根據系統時間指定隨機種子。
常用的產生僞隨機數的算法是線性同餘法，下面是我寫的代碼，相信通過代碼，大家可以很容易地明白僞隨機數原理：
算法：an+1=b*an+c mod m；a0=d。d爲種子。
int d;/*種子*/
long My_Rand(long b,long c,long m)
{
return d=(b*d+c)%m;/*產生隨機數，並記錄，用來產生下一個僞隨機數*/
}
long gcd1(long m,long n)
{/*求最大公約數，算法中的b和m一般取互素*/
long r;
while((r=m%n)!=0)
{
m=n;
n=r;
}
return n;
}
long gcd(long m)
{/*計算與m互素的b*/
long i=2;
while(gcd1(i,m)!=1)
i++;
return i;
}
void main()
{
long b,c,m;
int count;
int i;
m=32767;
b=gcd(m);
c=5001;
d=3;
count=800;
for(i=0;i<count;i++)/*產生800個僞隨機數*/
{
if(i%10==0)
printf("\n");
printf("%8ld",My_Rand(b,c,m));
}
}
當種子d爲131時運行結果如下：
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
30434 365 5761 16553 5370 15771 3806 12643 30317 131
5293 15617 3498 12027 29085 30434 365 5761 16553 5370
15771 3806 12643 30317 131 5293 15617 3498 12027 29085
當種子數爲151時，運行結果如下：
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
31714 2925 10881 26793 25850 23964 20192 12648 30327 151
5333 15697 3658 12347 29725 31714 2925 10881 26793 25850
23964 20192 12648 30327 151 5333 15697 3658 12347 29725
上次修改時間 2017-02-03