| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2094 人关注过本帖
标题:随机函数之等概率问题
只看楼主 加入收藏
帅的让人抽
Rank: 4
来 自:安徽
等 级:业余侠客
帖 子:94
专家分:224
注 册:2010-9-30
结帖率:100%
收藏
已结贴  问题点数:10 回复次数:10 
随机函数之等概率问题
编写一个函数,通过返回一个范围1至6的随机整数来模拟掷骰子,这6个值出现的概率应该相等。
这个问题大多人做的时候,可能这样做:
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int fun_throw(void)
{

 //local declarations
 static int is_seeded=0;

 int value;


 //statements


 if(!is_seeded)

 {
  is_seeded=1;
  srand(time(NULL));

 }  //if

value=rand();
return   value%6+1;
}  //fun_throw

int main()
{
  //local declarations 
    int num;
    int i;

 
  //statements    
 printf("请输入要投掷的次数:");

 scanf("%d",&num);

 printf("\n");

 for(i=0;i<num;i++)
     printf("%6d\n",fun_throw());

 return  0;
}  //main

其实这是错的。


随机数函数返回的最大值为32 767(这里就以它为例,标准C规定它至少为32 767),也就是说返回的数在0~32 767之间,总的个数为sum=32768.
为了得到1~6之间的随机整数,我们可以将一个随机数对6取模,得到0~5之间的整数,再将这个值加1便可以了。
在0~32 765之间对6取模得到各个值(0~5)的概率是相等的,每个数字有32 766/6=5461种情况,各个数字发生都是等概率的。但是32 766、32 767对6取模后得到的是0和1 ,加1后得到是1和2.
value=rand()%6+1;
由上面可知,在整个过程中,1和2出现的次数比其他四个数字(3,4,5,6)多了一次,即概率大。
数字1,2在整个过程中出现的概率为5462/32 768,而3,4,5,6出现的概率为5461/32 768.
虽然这个差别很小,但却是不容忽视的。因为这里产生的随机数范围很小而已,我们再看下面的:
如果需要函数产生1~30 000之间的随机数,同样我们可以通过:
value=rand()%30 000+1;
来做。
通过上面的分析我们可知,函数产生的随机数在0~29 999之间通过取模加1得到的是在1~30 000之间的数,它们都均出现一次,概率相等。
但是在后面的30 000~32 767之间,通过取模再加1得到的数在1~2768之间。
也就是说,如果我们利用这个函数试图产生一个范围在1~30 000之间的随机数时,前2768个值出现的概率是后面那些值出现概率的两倍。
前2768个值(1~2768)的概率相等,为:2/32 768.
后面值(2769~30 000)的概率为:1/32 768.
这种误差就大了。
正确的代码为:
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define  MAX  (int) ((((long)RAND_MAX+1)/6)*6-1)

int fun_throw(void)
{//local declarations
 static int is_seeded=0;

 int value;


 //statements


 if(!is_seeded)

 {
  is_seeded=1;
  srand(time(NULL));

 }  //if

do
{
    value=rand();

 }
while(value>MAX);

return   value%6+1;
}  //fun_throw

int main()
{
  //local declarations 
    int num;
    int i;

 
  //statements    
 printf("请输入要投掷的次数:");

 scanf("%d",&num);

 printf("\n");

 for(i=0;i<num;i++)
     printf("%6d\n",fun_throw());

 return  0;
}  //main
搜索更多相关主题的帖子: color 
2011-04-21 19:56
voidx
Rank: 12Rank: 12Rank: 12
来 自:邯郸
等 级:火箭侠
帖 子:1250
专家分:3538
注 册:2011-4-7
收藏
得分:2 
美琴姐以前讨论过这个话题了
2011-04-21 19:59
帅的让人抽
Rank: 4
来 自:安徽
等 级:业余侠客
帖 子:94
专家分:224
注 册:2010-9-30
收藏
得分:0 
回复 2楼 voidx
随机抽牌问题……

樱花下落的速度依然是秒速五厘米,即使发了一千次短信,
心与心之间也只能靠近一厘米……
2011-04-21 20:02
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:2 
哦,早就知道这问题,不过没怎么深入想过怎么解决。原来就是滤去多的那部分……

可是这样也会引发其它一些问题。比如你举的第二例子,由于要滤去的值占了很大一个区间范围,这就使得随机生成的数有很大的概率落在里面,本来一个 10 秒能执行完的程序会有很大的可能执行 20 秒以上。虽然可能性很小,但也有执行几个小时的隐患。
这种算法一般是不太可取的。

另一个,这个分析是假设 rand 确实是返回 0~RAND_MAX 间的均匀分布。但其实事实根本不是这样。
一般来说,伪随机数的生成算法,是指生成满足均匀分布假设的一种算法。只能说我们可以以很高的概率相信它返回的是均匀分布。
2011-04-21 20:10
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
回复 2楼 voidx
哦?!御坂姐以前也提过这个?那我去搜搜旧帖子~
2011-04-21 20:11
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
收藏
得分:2 
我一直想知道有时间做种子和没时间做种子有什么区别?

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2011-04-21 20:16
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
收藏
得分:0 
回复 2楼 voidx
我搜过了,好像没有啊

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2011-04-21 20:23
帅的让人抽
Rank: 4
来 自:安徽
等 级:业余侠客
帖 子:94
专家分:224
注 册:2010-9-30
收藏
得分:0 
回复 6楼 waterstar
用时间做种子时,每次产生的随机序列是不相同的。如果不用随机种子函数或者用一个常数作为随机种子,那么每次程序运行时产生的随机序列是相同的。
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main(void)

{  //statements
        srand(11);
        printf("%d\n",rand());
        printf("%d\n",rand());
        printf("%d\n",rand());
        return  0;
} //main

程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main(void)

{  //statements
        srand(time(NULL));
        printf("%d\n",rand());
        printf("%d\n",rand());
        printf("%d\n",rand());
        return  0;
}

樱花下落的速度依然是秒速五厘米,即使发了一千次短信,
心与心之间也只能靠近一厘米……
2011-04-22 11:37
帅的让人抽
Rank: 4
来 自:安徽
等 级:业余侠客
帖 子:94
专家分:224
注 册:2010-9-30
收藏
得分:0 
回复 4楼 pangding
那随机抽牌洗牌问题该怎样解释……

樱花下落的速度依然是秒速五厘米,即使发了一千次短信,
心与心之间也只能靠近一厘米……
2011-04-22 11:40
voidx
Rank: 12Rank: 12Rank: 12
来 自:邯郸
等 级:火箭侠
帖 子:1250
专家分:3538
注 册:2011-4-7
收藏
得分:0 
对不起大家,我搞错了,收回 2 楼发言
2011-04-22 12:14
快速回复:随机函数之等概率问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019551 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved