侯瑞哲的博客

Ruizhe's Blog

0%

使用函数randa()来实现函数randb()

发表于 更新于 Valine：

使用函数randa()来实现函数randb()

原文引自：https://blog.csdn.net/wangruitao1991/article/details/51678815

我们由浅入深，首先来看：

  1. 给你一个能成1到7随机数的函数，用它写一个生成1到5的随机数。即使用rand7来实现rand5

    rand7可以随机生成1，2，3，4，5，6，7，是等概率的，这里直观的想法是不断地电泳rand7，直到它生成1到5之间的数，然后返回。代码如下：

    1
    2
    3
    4
    5
    6
    7
    int rand5() {
      inx x = ~(1<<31);  // max int
      while (x > 5){
        x = rand7();
      }
      return x;
    }

    这个函数可以等概率的产生1到5的数码？首先，它确确实实只会返回1到5这几个数，其次，对于这些数，都是由rand7等概率的产生的1/7，没有对任何一个数有偏袒，直觉告诉我们，rand5就是等概率的产生1到5的。事实呢？让我们来计算一下，产生1到5中的数是不是1/5就OK了。

    产生1的概率：等于第一次产生1的概率，加上第一次生成6，7第二次产生1的概率，加上... $$ p(x=1) = 1/7 + 2/7 * 1/7 + (2/7)^2 * 1/7 + ... \

    = 1/7 * (1 + 2/7 + (2/7)^2+...)\

    = 1/7 * 1 / (1-2/7)\

    = 1/5\ $$ 其他同理，所以从上面的分析，我们可以得到一个一般的结论，如果a > b，那么一定可以用randa实现randb。其中，randa表示等概率生成1到a的函数，randb表示等概率生成1到b的函数。代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    ;// a > b
    int randb() {
      inx x = ~(1 << 31); // max int
     while (x > b) {
          x = randa();
      }
        return x;
    }

    这里还有没有优化的空间呢。我们想如果a大于b很多，那么这个循环大多数是无法退出的。这是我们可以找到一个最接近a的b的整数倍b * (A/b)，大于这个整数倍就继续循环，否则就返回 randa()%b + 1 。代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    // a > b
    int randa() {
      int x =  ~(1 << 31); //  max int
      while (x > b * (a / b)) {
        x = randa();
      }
      return x % b + 1;
    }

    好了，a大于b时这个问题得到完美的解决了。那么a小于b的时候呢。

    比如，如何用rand5实现rand7。

    我们只需要将rand5映射到一个能产生更大随机数的randa，a > 7，这个问题就可以解决了。这里要注意，映射之后的randa也应该是等概率生成1到a的。

    如何映射呢。其实可以将rand5想象成一个五进制数。2个rand5就可以表示25种情况。

    5 * (rand5() - 1) + rand5()，可以等概率的产生1-25之间的数字。

    根据上面的模板我们可以得到以下的代码：

    1
    2
    3
    4
    5
    6
    7
    int rand7() {
      int x = ~(1 << 31); // max int
      while (x > 7) {
        x = 5 * (rand5() - 1) + rand5();
      }
      return x;
    }

    在根据上面的模板简化：

    1
    2
    3
    4
    5
    6
    7
    int rand7() {
      int x = ~(1 << 31); // max int
      while (x > 21) {
        x = 5 * (rand5() - 1) + rand5();
      }
      return x % 7 +1;
    }

    通过上文分析，我们可以得到步骤如下：

    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：
    1
    2
    3
    4
    5
    6
    7
    // A > b
    int Randb(){
        int x = ~(1<<31); // max int
        while(x > b*(A/b)) // b*(A/b)表示最接近A且小于A的b的倍数
            x = RandA();
        return x%b + 1;
    }

    从上面一系列的分析可以发现，如果给你两个生成随机数的函数Randa和Randb， 你可以通过以下方式轻松构造Randab，生成1到a*b的随机数。

    1
    2
    Randab = b * (Randa - 1) + Randb
    Randab = a * (Randb - 1) + Randa