Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1057045
  • 博文数量: 573
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 66
  • 用 户 组: 普通用户
  • 注册时间: 2016-06-28 16:21
文章分类

全部博文(573)

文章存档

2018年(3)

2016年(48)

2015年(522)

分类: C/C++

2015-12-09 11:43:09

rand7()构造rand10()

题目:

已知有个rand7()的函数,返回1到7随机自然数,让利用这个rand7()构造rand10() 随机1~10。

方法一:

分 析:要保证rand10()在整数1-10的均匀分布,可以构造一个1-10*n的均匀分布的随机整数区间(n为任何正整数)。假设x是这个1-10*n 区间上的一个随机整数,那么x%10+1就是均匀分布在1-10区间上的整数。由于(rand7()-1)*7+rand7()可以构造出均匀分布在 1-49的随机数(原因见下面的说明),可以将41~49这样的随机数剔除掉,得到的数1-40仍然是均匀分布在1-40的,这是因为每个数都可以看成一 个独立事件。

下面说明为什么(rand7()-1)*7+rand7()可以构造出均匀分布在1-49的随机数:
首先 rand7()-1得到一个离散整数集合{0,1,2,3,4,5,6},其中每个整数的出现概率都是1/7。那么(rand7()-1)*7得到一个离 散整数集合A={0,7,14,21,28,35,42},其中每个整数的出现概率也都是1/7。而rand7()得到的集合B= {1,2,3,4,5,6,7}中每个整数出现的概率也是1/7。显然集合A和B中任何两个元素组合可以与1-49之间的一个整数一一对应,也就是说 1-49之间的任何一个数,可以唯一确定A和B中两个元素的一种组合方式,反过来也成立。由于A和B中元素可以看成是独立事件,根据独立事件的概率公式 P(AB)=P(A)P(B),得到每个组合的概率是1/7*1/7=1/49。因此(rand7()-1)*7+rand7()生成的整数均匀分布在 1-49之间,每个数的概率都是1/49。

程序:

int rand10()
{
     int x=0;
     do
     {
         x=(rand7()-1)*7+rand7();
     }
     while(x>40);
     return x%10+1;
}

方法二:
思想是把1到10这10个数分成2个集合(1,3,5,7,9)(2,4,6,8,10)
rand7 构造出 rand5,此时就能得到等概率的一个集合,(1,3,5,7,9)或者(2,4,6,8,10)。

   int rand5()
   {
        int x=0;
        do
        {
            x = rand7();
        }
        while(x>5);
        return x;
   }
用rand7构造出rand2
   int rand2()
   {
        int x=0;
        while(1)
        {
            x = rand7();
            if (4 == x)
                continue;
            if (x <= 3)
                return 1;
            else
                return 2;
        }
   }
最后用rand2和rand5构造rand10
   int rand10()
   {
        int x=0, y=0;
        x = rand2();
        y = rand5();
        if (1 == x)
            return 2*y-1;  //奇数集合
        else
            return 2*y;     //偶数集合
   }

阅读(839) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~