当前位置: 代码迷 >> 综合 >> 随机数与给定随机数生成器[0,m)产生另一个随机数生成器[0, n)(均匀分布)
  详细解决方案

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

热度:69   发布时间:2023-12-13 00:27:36.0
  • 引言

对于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); // 指定一个固定的值作为种子,默认固定的种子为1for(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>=10rand14() = rand7()*2+rand2() // 2*7>=10// 情形一处理,由rand14()得到rand10()
// 指定rand7(),生成rand60(), 7*7<60rand49() = 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*6rand14() = rand7()*2+rand2()// 情形一处理,由rand14()得到rand10()rand60() = rand10()*6+rand6()

注解:m<n<=m*m –>由randm()所能一次产生的最大范围的随机数生成器为randm()*m+randm(),即randN()(N=m*m=(m-1)*m+(m-1)+1)

另外,给定随机数生成器[0,m)产生另一个随机数生成器(n1, n2)(均匀分布),可将(n1, n2)转为(0, n2-n1)即可