# 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，这个好实现吗？

```<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>```

```<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>```

```<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>```

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

```<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>```

```<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. 如果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>```

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

Cracking the coding interview–问题与解答

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

Share