Implement rand7() using rand5()

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i.e., implement rand7() using rand5()).

解答

rand5可以随机生成1,2,3,4,5;rand7可以随机生成1,2,3,4,5,6,7。 rand5并不能直接产生6,7,所以直接用rand5去实现函数rand7似乎不太好入手。 如果反过来呢?给你rand7,让你实现rand5,这个好实现吗?

一个非常直观的想法就是不断地调用rand7,直到它产生1到5之间的数,然后返回。 代码如下:

<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand5</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">5</span><span class="p">)</span>
        <span class="n">x</span> <span class="o">=</span> <span class="n">Rand7</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>

等等,这个函数可以等概率地产生1到5的数吗?首先,它确确实实只会返回1到5这几个数, 其次,对于这些数,都是由Rand7等概率产生的(1/7),没有对任何一个数有偏袒, 直觉告诉我们,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的概率计算如下:

<code>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
</code>

上述计算说明Rand5是等概率地生成1,2,3,4,5的(1/5的概率)。从上面的分析中, 我们可以得到一个一般的结论,如果a > b,那么一定可以用Randa去实现Randb。其中, Randa表示等概率生成1到a的函数,Randb表示等概率生成1到b的函数。代码如下:

<code class="language-cpp" data-lang="cpp"><span class="c1">// a &gt; b</span>
<span class="kt">int</span> <span class="nf">Randb</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">b</span><span class="p">)</span>
        <span class="n">x</span> <span class="o">=</span> <span class="n">Randa</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>

回到正题,现在题目要求我们要用Rand5来实现Rand7,只要我们将Rand5 映射到一个能产生更大随机数的Randa,其中a > 7,就可以套用上面的模板了。 这里要注意一点的是,你映射后的Randa一定是要满足等概率生成1到a的。比如,

<code>Rand5() + Rand5() - 1
</code>

上述代码可以生成1到9的数,但它们是等概率生成的吗?不是。生成1只有一种组合: 两个Rand5()都生成1时:(1, 1);而生成2有两种:(1, 2)和(2, 1);生成6更多。 它们的生成是不等概率的。那要怎样找到一个等概率生成数的组合呢?

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

<code>5 * (Rand5() - 1) + Rand5()
</code>

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

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

<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand7</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">7</span><span class="p">)</span>
        <span class="n">x</span> <span class="o">=</span> <span class="mi">5</span> <span class="o">*</span> <span class="p">(</span><span class="n">Rand5</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">Rand5</span><span class="p">()</span> <span class="c1">// Rand25</span>
    <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>

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

<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand7</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">21</span><span class="p">)</span>
        <span class="n">x</span> <span class="o">=</span> <span class="mi">5</span> <span class="o">*</span> <span class="p">(</span><span class="n">Rand5</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">Rand5</span><span class="p">()</span> <span class="c1">// Rand25</span>
    <span class="k">return</span> <span class="n">x</span><span class="o">%</span><span class="mi">7</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span></code>

这个实现就比上面的实现要好,并且可以保证等概率生成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:
<code class="language-cpp" data-lang="cpp"><span class="c1">// A &gt; b</span>
<span class="kt">int</span> <span class="nf">Randb</span><span class="p">(){</span>
    <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
    <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">b</span><span class="o">*</span><span class="p">(</span><span class="n">A</span><span class="o">/</span><span class="n">b</span><span class="p">))</span> <span class="c1">// b*(A/b)表示最接近A且小于A的b的倍数</span>
        <span class="n">x</span> <span class="o">=</span> <span class="n">RandA</span><span class="p">();</span>
    <span class="k">return</span> <span class="n">x</span><span class="o">%</span><span class="n">b</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span></code>

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

<code>Randab = b * (Randa - 1) + Randb
Randab = a * (Randb - 1) + Randa
</code>

如果再一般化一下,我们还可以把问题变成:给你一个随机生成a到b的函数, 用它去实现一个随机生成c到d的函数。有兴趣的同学可以思考一下,这里不再讨论。

全书题解目录:

Cracking the coding interview–问题与解答

 

reference: http://www.hawstein.com/posts/19.10.html