标签搜索

目 录CONTENT

文章目录

给你一个能生成1到5随机数的函数,用它写一个函数生成1到7的随机数.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 11 阅读 / 3,097 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

给你一个能生成1到5随机数的函数,用它写一个函数生成1到7的随机数

@[toc]

一、问题

已知rand5()产生1-5的随机整数利用该函数生成函数rand7()产生1-7的随机整数

二、分析

  •  rand5可以随机生成1 ~ 5;目标生产rand7,使其可以随机生成1 ~ 7。 rand5并不能直接产生6,7。我们可能想到 + 2,但是+ 2生产的是3 ~ 7,不满足题意。
  •  所以直接用rand5去实现函数rand7似乎不太好入手,那么我们反向思考一下,如果给你rand7,让你实现rand5,这个好实现吗?
  •  其实反过来是可以的,因为rand7的生成随机数范围多了6和7,生成1 ~ 5的随机数的概率仍然是随机的,所以我们就需要对6和7下手
  •  怎样操作6和7才可以使rand7生成随机数的范围为0 ~ 5并且忽略6和7呢?答案就是如果rand7生成的随机数大于5,就继续调用rand7,这样rand7既满足了生成随机数的范围为1 ~ 5并且保证了随机
#include <iostream>
#include <ctime>
#include <unistd.h>
#include <limits.h>
using namespace std;

int Rand7()
{
    return rand() % 7 + 1;
}

//使用Rand7等概率生成1 ~ 5的随机数
int Rand5()
{
    int num = INT_MAX;
    while(num > 5)
    {
       num = Rand7();
    }
    return num;
}


int main()
{
    srand((unsigned)time(NULL));
    while(1)
    {
        cout<<Rand5()<<endl;                                                                                                                
        sleep(1);    
    }    
    return 0;    
}
  •  那么Rand5这个函数可以等概率地产生1到5的数吗?
  •  首先,它确确实实只会返回1到5这几个数, 其次,对于这些数,都是由Rand7等概率产生的(1/7),没有对任何一个数有偏袒(如果生成的随机数大于5,就会继续调用该函数), 直觉告诉我们,Rand5就是等概率地产生1到5的。
  •  事实呢?让我们来计算一下, 产生1到5中的数的概率是不是1/5就OK了。
  •  比如说,让我们来计算一下Rand5生成1 的概率是多少。上面的函数中有个while循环,只要没生成1到5间的数就会一直执行下去。
  •  因此,我们要的1可能是第一次调用Rand7时产生,也可能是第二次,第三次,…第n次。 第1次就生成1,概率是1/7;第2次生成1,说明第1次没生成1到5间的数而生成了6,7, 所以概率是(2/7)*(1/7),依次类推。生成1的概率计算如下:
P(x=1)=1/7+(2/7)*1/7+(2/7)^2*1/7+(2/7)^3*1/7+...
      =1/7*(1+2/7+(2/7)^2+...)// 等比数列
      =1/7*1/(1-2/7)
      =1/7*7/5
      =1/5
  •  上述计算说明Rand5函数是等概率地生成1,2,3,4,5的(1/5的概率)。从上面的分析中, 我们可以得到一个一般的结论,如果a > b,那么一定可以用Randa去实现Randb。其中, Randa表示等概率生成1到a的函数,Randb表示等概率生成1到b的函数。代码如下:
// a > b
int RandA(){};

int RandAtoB()
{
    int num = INT_MAX;
    while(num > b)
        num = RandA();
    return num;
}

三、错解

  •  回到正题,现在题目要求我们要用Rand5来实现Rand7只要我们将Rand5 映射到一个能产生更大随机数的Randa,其中a > 7,就可以套用上面的模板了。 这里要注意一点的是,你映射后的Randa一定是要满足等概率生成1到a的。比如,
Rand5() + Rand5() - 1;
  •  上述代码可以生成1到9的数,但它们是等概率生成的吗?不是生成1只有一种组合: 两个Rand5()都生成1时:(1, 1);而生成2有两种:(1, 2)和(2, 1);生成6更多
  •  它们的生成是不等概率的。那要怎样找到一个等概率生成数的组合呢?

四、正解一

我们先给出一个组合,再来进行分析。组合如下:

5 * (Rand5() - 1) + Rand5();
  •  第一个Rand5产生1到5的随机数,减1就产生0到4的随机数,乘以5后可以产生的随机数是:0,5,10,15,20。
  •  第二个Rand5()产生的随机数是1,2,3,4,5。那么我们可以得到1到25的随机数, 而且每个数都只由一种组合得到,即上述代码可以等概率地生成1到25
  •  OK, 到这基本上也就解决了.

套用上面的模板,我们可以得到如下代码:

int Rand5(){};

int Rand7()
{
    int num = INT_MAX;
    while(num > 7)
        num = 5 * (Rand5() - 1) + Rand5();
    return num;
}

五、正解二

  •  上面的代码有什么问题呢?可能while循环要进行很多次才能返回。
  •  因为Rand25会产生1到25的数,而只有1到7时才跳出while循环, 生成大部分的数都舍弃掉了。这样的实现明显不好,我们应该让舍弃的数尽量少
  •  于是我们可以修改while中的判断条件,让x与(最接近25)且(小于25)的(7的倍数)相比。
  •  于是判断条件可改为x > 21,于是x的取值就是1到21。 我们再通过取模运算把它映射到1-7即可。代码如下:
int Rand5(){};

int Rand7()
{
    int num = INT_MAX;
    while(num > 21)
        num = 5 * (Rand5() - 1) + Rand5();
    return num % 7 + 1;
}
  •  这个实现就比上面的实现要好,并且可以保证等概率生成1到7的数。

六、拓展

  •  让我们把这个问题泛化一下,从特殊到一般。现在我给你两个生成随机数的函数Randa,Randb。Randa和Randb分别产生1到a的随机数和1到b的随机数,a,b不相等(相等就没必要做转换了)。现在让你用Randa实现Randb
  •  通过上文分析,我们可以得到步骤如下:
  •  步骤1:如果a > b,进入步骤2;
  •  否则构造Randa2 = a * (Randa – 1) + Randa, 表示生成1到a2 随机数的函数。如果a2 仍小于b,继教构造 Randa3 = a * (Randa2 - 1) + Randa…直到ak > b,这时我们得到Randak , 我们记为RandA。
  •  步骤2:步骤1中我们得到了RandA(可能是Randa或Randak ),其中A > b, 我们用下述代码构造Randb:
int RandA(){};

// A > b
int Randb()
{
    int num = INT_MAX:
    
    // b * (A / b)表示最接近A且小于A的b的倍数
    while(num > b * (A / b)) 
    	//这里的RandA()代表着经过n(0,1,2...n)次计算过后的RandA;详情请
    	//见步骤2;
        num = RandA();
    return num % b + 1;
}
  •  从上面一系列的分析可以发现,如果给你两个生成随机数的函数Randa和Randb, 你可以通过以下方式轻松构造Randab,生成1到a*b的随机数
Randab = b * (Randa - 1) + Randb
Randab = a * (Randb - 1) + Randa
0

评论区