随机数与给定随机数生成器[0,m)产生另一个随机数生成器[0, n)(均匀分布)

引言

对于C语言中的rand()函数是返回一个整数n[0, 32767],这个整数是一个伪随机数(通过seed加以一定方法的计算而得)，即每次调用它，产生的随机数均一样，因为产生随机数的种子seed如果不加以指定，那么默认总是为长整数1L。并且如果接着调用rand()函数，那么产生的这个数也是一定的(即第一个随机数确定了，后面所产生的随机数都将是一定的，而指定种子就是让第一个随机数不一样)，因为当前的seed是由上次的seed计算而来，即seed=f(seed),而随机数为（(seed=f(seed))g(x),g(x)为常函数），因此它会产生一个伪随机序列（当然如果每次的种子（系统时间，某个长度经常改变的系统文件的长度等）不一样，这个序列就会不一样）

#include <stdio.h> // io操作
#include <stdlib.h> // srand(),rand()
#include <time.h> // 系统时间

void test1();
void test2();

int main(void){
    test1();
    test2();
    return 0;
}

void test1(){
    srand(10); // 指定一个固定的值作为种子，默认固定的种子为1
    for(int i = 0; i < 26; i++){
        printf("%d ", rand()%10); // 每次都会产生26个一样的整数[0, 10)序列
    }
    return;
}

void test2(){
    srand((unsigned)time(NULL)); // 以时刻变化的系统时间作为种子
    for(int i = 0; i < 26; i++){
        printf("%d ", rand()%10); // 每次产生的26个整数[0, 10)序列都不一样
    }
    return;
}

随机数生成器

问题：我们给定一个随机数生成器[0, m),现要求生成一个随机数生成器[0, n), 并且是均匀分布的。
思路：我们记randn()为一个随机数生成器[0, n)。
即要求，randm()–>randn()
情形一：当n<=m时，则无需转换，筛选即可

int r;
do{
    r = randm();
}while(r>=n);

情形二：当n>m时，此时又有两种情况，第一种，m<n<=m*m（文章末尾解释此处）时，取一个t，使得当t最小时，满足(k=tm)>=n(易得t<=m)，那么这个randk()的表示式就为randk() = randm()*t+randt(),又因为k>=n，所以此时已是情形一，故按照情形一即可生成随机数生成器randn()
第二种，n>m*m时，则应该首先产生随机数生成器randx()(其中x=m*m),再然后按照第一种情况处理，如果仍不满足则先生成randy()(其中y=x*x)，再按第一种情况处理，如此进行，直到满足为止。

// 指定rand7(),生成rand10(), 7*7>=10
    rand14() = rand7()*2+rand2() // 2*7>=10
    // 情形一处理，由rand14()得到rand10()
// 指定rand7(),生成rand60(), 7*7<60
    rand49() = rand7()*7+rand7()
    rand98() = rand49()*2+rand2()
    // 情形一处理，由rand98()得到rand60()
/*
对于n>m*m的情况，还可将n进行形如a*b(1<a<=b且a尽可能小(尽可能小是为了使现有randm()更方便的实现randa(),当然a<=m或者a是m的整数倍最好) <==> 1<a<=b且a-b->1)的分解(当n为质数时，则n=N(N为素数，且N>n,N-n最小)),或者直接`a=sqrt(n);a=ceil(a);N=a*a;randN();`
*/
// 指定rand7(),生成rand60(), 7*7<60
     // 60 = 10*6
    rand14() = rand7()*2+rand2()
    // 情形一处理，由rand14()得到rand10()
    rand60() = rand10()*6+rand6()