详解C语言的随机数生成及其相关题目
产生随机数的基本方法
本文中,笔者将介绍c语言所提供的随机数发生器的用法。现在的c编译程序都提供了一个基于一种ANSI标准的伪随机数发生器函数,用来生成随机数。Microsoft和Borland都是通过rand()和srand()函数来支持这种标准的,它们的工作过程如下:
首先,给srand()提供一个“种子”,它是一个unsignde int类型,其取值范围是从0到65,535 ;
然后,调用rand(),它会根据提供给srand()的“种子”值返回一个随机数(在0到32,767之间);
根据需要多次调用rand(),从而不断地得到新的随机数;
无论什么时候,你都可以给srand()提供一个新的“种子”,从而进一步“随机化"rand()的输出结果。
这个过程看起来很简单,问题是如果你每次调用srand()时都提供相同的“种子”值,那么你将会得到相同的“随机”数序列。例如,在以17为“种子”值调用srand()之后,在你首次调用rand()时,你将得到随机数94;在你第二次和第三次调用rand()时,你将分别得到26,602和30,017。这些数看上去是相当随机的(尽管这只是一个很小的数据点集合),但是,在你再次以17为“种子”值调用srand()之后,在对rand()的前三次调用中,所得到的返回值仍然是94、26,602和30,017,并且此后得到的返回值仍然是在对rand()的第一批调用中所得到的其余的返回值。因此,只有再次给srand()提供一个随机的“种子”值,才能再次得到一个随机数。
下面的例子用一种简单而有效的办法来产生一个相当随机的“种子”值——当天的时间值。
# include <stdlib. h> # include <stdio. h> # include <sys/types. h> # include <sys/timeb. h> void main (void){ int i ; unsigned int seedVal; struct_timeb timeBuf ; _ftime (&timeBuf) ; seedVal = ( ( ( ( (unsigned int)timeBuf, time & 0xFFFF) + (unsigned int)timeBuf, millitm) ^ (unsigned int)timeBuf, millitm) ; srand ((unsigned int)seedVal) ; for(i=O;i<lO;++i) printf (" %6d\n" ,rand ( ) ) ; }
上例先是调用_ftime()来检索当前时间,并把它的值存入结构成员timeBuf.time中,当前时间的值从1970年1月1日开始以秒计算。在调用了_ftime()之后,在结构timeBuf的成员millitm中还存入了在当前那一秒已经度过的毫秒数,但在DOS中这个数字实际上是以百分之一秒来计算的。然后,把毫秒数和秒数相加,再和毫秒数进行一次异或运算。你可以对这两个结构成员施加更多的逻辑运算,以控制seedVal的取值范围,并进一步加强它的随机性,但上例所用的逻辑运算已经足够了。
注意,在前面的例子中,rand()的输出并没有被限制在一个指定的范围内,假设你想建立一个彩票选号器,其取值范围是从1到44。你可以简单地忽略掉rand()所输出的在该范围之外的值,但这将花费许多时间去得到所需的全部(例如6个)彩票号码。假设你已经建立了一个令你满意的随机数发生器,它所产生的随机数据范围是从0到32,767(就象前文中提到过的那样),而你想把输出限制在1到44之间,下面的例子就说明了如何来完成这项工作:
int i ,k ,range ; int rain, max ; double j ; min=1; /* 1 is the minimum number allowed */ max=44; /* 44 is the maximum number allowed */ range=max-min; /* r is the range allowed; 1 to 44 */ i=rand(); /* use the above example in this slot */ /* Normalize the rand() output (scale to 0 to 1) */ /* RAND_MAX is defined in stdlib, h */ j= ((double)i/(double)RAND_MAX) ; /* Scale the output to 1 to 44 */ i= (int)(j * (double)range) ; i+ =min;
上例把输出的随机数限制在1到44之间,其工作原理如下:
得到一个在O到RAND_MAX(32,767)之间的随机数,把它除以RAND_MAX,从而产生一个在0到1之间的校正值;
把校正值乘以所需要的范围值(在本例中为43,即44减去1),从而产生一个在O到43之间的值;
把该值和所要求的最小值相加,从而使该值最终落在正确的取值范围——1到44之内。
你可以用不同的min和max值来验证这个例子,你会发现它总是会正确地产生在新的rain和max值之间的随机数。
下面来看一下随机数的相关练习题目
题目
给定了rand7,如何生成rand3?
思路
一个非常直观的思路,就是不断的调用rand7,直到它产生1-3之间的数,然后返回。代码如下:(如果有同学说这里没有3,但是不代表我不能判断和3的大小比较吧)
#include <stdio.h> int rand_3() { int x; while (x = rand_7()) { if (x <= 3) { return x; } } }
接下来,就是判断rand_3是否能等概率的产生1,2,3.也就是我们需要计算产生1,2,3的概率是否都是1/3.
首先,rand_7可以等概率的产生1-7,我们以rand_3生成1为例,假设:
- 第一次生成1的概率是1/7
- 第二次生存1的概率是4/7 * 1/7,因此第一次肯定是生成了大于3的数例如4,5,6,7,概率是4/7
- 同理,第三次生成1的概率是(4/7)^2 * 1/7
因此,rand_3生成1的概率是P(x=1)= 1/7 + (4/7) * 1/7 + (4/7)^2 * 1/7 + ... + (4/7)^n-1 * 1/7 //等比数列
= 1/7 * ((1 - (4/7)^n) / 1 - 4/7) = 1/7 * 7/3 = 1/3
同理,可验证生成2,3的概率均为1/3
结论
上述证明说明rand3可以等概率的产生1,2,3.从上面的分析,我们可以得出一个更一般的结论:
如果a>b,我们一定可以用rand_a去实现rand_b.其中,rand_a是等可能的生成1-a,rand_b是等可能的生成1-b
扩展
现在给定两个生成随机数的函数rand_a和rand_b,rand_a和rand_b分别产生1-a和1-b的随机数,a和b不相等,现在让你用rand_a实现rand_b,方法如下:
- 如果a>b,则可以直接采用上述方法
- 如果a<b, 则构造rand_a^2=a * (rand_a - 1) + rand_a,表示生成1-a^2的随机数,如果a^2还小于b,那么继续构造rand_a^3=a * (rand_a^2 - 1) + rand_a
举例说明
阿里2014年笔试题目,是给定生成1-7的随即函数rand_7,看是否能生成其它随机数?
我们先看一下是否能等概率生成1-49,构造rand_49 = 7 * (rand_7 - 1) + rand_7 (ps:别问我7从哪里来的,rand_7既然能随即生成1-7,我当然可以获得到7了)
rand_7 - 1能等概率的生成0, 1, 2, 3, 4, 5, 6,每个数的生成概率都是1/7,所以*7之后,可以等概率的生成0,7,14,21,28,35,42,每个数的概率都是1/7
既然0,7,14,21,28,35,42每个数的概率都是1/7,当每个数都加上+rand_7之后,则1-49是等概率产生的,1/7 × 1/7 = 1/49,中间不会出现重复数据
所以,我们用rand_7产生了rand_49,有了rand_49,按照最初上面过滤的方法,我们当然可以获得任何小于49的随机函数
您可能感兴趣的文章
- 04-02c语言函数调用后清空内存 c语言调用函数删除字符
- 04-02c语言的正则匹配函数 c语言正则表达式函数库
- 04-02func函数+在C语言 func函数在c语言中
- 04-02c语言中对数函数的表达式 c语言中对数怎么表达
- 04-02c语言用函数写分段 用c语言表示分段函数
- 04-02c语言编写函数冒泡排序 c语言冒泡排序法函数
- 04-02c语言没有round函数 round c语言
- 04-02c语言分段函数怎么求 用c语言求分段函数
- 04-02C语言中怎么打出三角函数 c语言中怎么打出三角函数的值
- 04-02c语言调用函数求fibo C语言调用函数求阶乘
阅读排行
本栏相关
- 04-02c语言函数调用后清空内存 c语言调用
- 04-02func函数+在C语言 func函数在c语言中
- 04-02c语言的正则匹配函数 c语言正则表达
- 04-02c语言用函数写分段 用c语言表示分段
- 04-02c语言中对数函数的表达式 c语言中对
- 04-02c语言编写函数冒泡排序 c语言冒泡排
- 04-02c语言没有round函数 round c语言
- 04-02c语言分段函数怎么求 用c语言求分段
- 04-02C语言中怎么打出三角函数 c语言中怎
- 04-02c语言调用函数求fibo C语言调用函数求
随机阅读
- 08-05DEDE织梦data目录下的sessions文件夹有什
- 01-10使用C语言求解扑克牌的顺子及n个骰子
- 08-05织梦dedecms什么时候用栏目交叉功能?
- 01-11Mac OSX 打开原生自带读写NTFS功能(图文
- 01-10C#中split用法实例总结
- 01-11ajax实现页面的局部加载
- 08-05dedecms(织梦)副栏目数量限制代码修改
- 01-10SublimeText编译C开发环境设置
- 04-02jquery与jsp,用jquery
- 01-10delphi制作wav文件的方法