C提供的标准随机函数是rand(),返回0~RAND_MAX,共RAND_MAX+1个随机数,如果我需要更大的随机数范围应如何做?
试设计:
long random(long n);返回0~n-1间的等概率随机数
分情况讨论
如果n<RAND_MAX+1,大可以用rand()%n的方法做,但这样做也并不能满足等概率性,设r=RAND_MAX%n,得到0~r的概率要稍大一些,尤其在n较接近RAND_MAX时,当n较小时影响可以忽略。
if(n<=RAND_MAX)
{
r=RAND_MAX-(RAND_MAX+1)%n;//尾数
t=rand();
while(t>r)t=rand();
return t%n;
}
如果n>=RAND_MAX+1,我的想法是分段抽样,分成[n/(RNAD_MAX+1)]段,先等概率得到段再得到每段内的某个元素,这样分段也类似地有一个尾数问题,不是每次都刚好分到整数段,一定或多或少有一个余数段,这部分的值如何选取?
选到余数段的数据拿出来选取,先进行一次选到余数段概率的事件发生,然后进行单独选取:
else
{
r=n%(RAND_MAX+1);//余数
if(happened((double)r/n))//选到余数段的概率
return n-r+random(r);
else
return rand()+random(n/RAND_MAX)*RAND_MAX;
}
如果选不到余数段再进行分段选取:
return rand()+random(n/(RAND_MAX+1))*(RAND_MAX+1);
完整的代码:
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
static const double MinProb=1.0/(RAND_MAX+1);
bool happened(double probability)//probability 0~1
{
if(probability<=0)return false;
if(probability<MinProb)
return rand()==0&&happened(probability*(RAND_MAX+1));
if(rand()<=probability*(RAND_MAX+1))
return true;
return false;
}
long random(long n)//产生0~n-1之间的等概率随机数
{
long r,t;
if(n<=RAND_MAX)
{
r=RAND_MAX-(RAND_MAX+1)%n;//尾数
t=rand();
while(t>r)t=rand();
return t%n;
}
else
{
r=n%(RAND_MAX+1);//余数
if(happened((double)r/n))//取到余数的概率
return n-r+random(r);
else
return rand()+random(n/(RAND_MAX+1))*(RAND_MAX+1);
}
}
void main()
{
int v[10000];
long i;
for(i=0;i<10000;++i)
v[i]=0;
for(i=0;i<500000;++i)
v[random(10000)]++;
for(i=0;i<10000;++i)
cout<<v[i]<<",";
cout<<endl;
}
正文
产生任意范围内的等概率随机数2005-08-17 21:34:00
【评论】 【打印】 【字体:大 中 小】 本文链接:http://blog.pfan.cn/rickone/3890.html
阅读(14812) | 评论(9)
版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!
评论