所谓实现Rand10()，本质就是保证：(1) 输出是1-10， (2) 每个输出都是等概率的。
感觉可以实现的方法有很多。我想到的是，Rand7()输出的是1-7,七种等概率的输出对Rand10()有帮助吗？好像差点什么。如果给我们的函数有五种等概率的输出，好歹还可将其映射到1-2,3-4,5-6,7-8,9-10这五类，每一类（两个数字）出现的概率还能够平均一点。怎么办呢？思路立马就有了，如果Rand7()给出七种可能，我们就取前五种呗，如果抽到了6或者7，那就不算，重新再来不就行了。这样，我们就能通过Rand7()得到五种等概率的输出。
有了这个思路，接下来也好办了。刚才通过一次Rand7()，得到等概率的五种输出，但是每种输出可以包含两个数字。如何将这两个数字再等概率地分开呢？那就再摇一次Rand7()呗。如果是奇数就选这两个数字中的奇数，如果是偶数就选这两个数字中的偶数。当然Rand7()会得到四个奇数和三个偶数并不公平，那我们就采用相同的思路，抽到７就不算，重来就行了。这样，对于奇偶性的抽取总是均等概率的。
综上，我们的Rand10()是分两步走，第一步利用Rand7()得到等概率的五种可能，然后再利用Rand7()得到等概率的两种可能。
对于这道题，面试官肯定会问，抽出一个数，需要调用Rand7()的次数的期望是多少。之所以我们抽一个Rand10()可能不止需要两次Rand7()操作，是因为可能会遇到retry的情况。我们可以大致算一算：
第一步：
1*5/7+2*(2/7)*5/7+3*(2/7)^2*5/7+...+k*(2/7)^(k-1)*5/7
第二步：
1*6/7+2*(1/7)*6/7+3*(1/7)^2*6/7+...+k*(1/7)^(k-1)*6/7
可以用等差等比数列的方法算一下，大概是2.6次左右。
我们先想一个简单的问题，如何通过rand10()实现rand7()？因为rand10()能够等概率地得到[0,1,2,3,4,5,6,7,8,9]，假如永远不会出现7,8,9的话那岂不就是rand7()了？因此一个简单的想法就是，如果rand10()得到了7,8,9就retry，直至rand10()出现的数在[0,6]范围内，然后把答案输出。
OK，接下来我们思考如何通过rand7()实现rand10()？有人会想，通过两次rand7()再相加，得到均匀分布的[0,1,2,3,4,5,6,7,8,9,10,11,12,13]，再对出现大于10的结果时进行retry就可以了。这个思路很正确，但是可惜的是，对于两个独立同均匀分布的随机变量X,Y，它们的加和不是均匀分布，而是二项分布。我们无法通过两次rand7()得到[0,13]均匀分布的随机数。
但是，我们可以用两次rand7()得到[0,48]均匀分布的随机数！我们考虑一个包含两位digit的七进制数ab，并且令a和b都是由rand7()得到的。那么ab代表了七进制的[00,66]之间连续、等概率的分布。转化为十进制的话，就是[0,48]之间连续、等概率的分布。利用之前的retry大法，对于X~U[0,48]的随机变量，当大于等于40时就进行retry，可以得到Y~U[0,39]。进一步，Y%10~U[0,9]，就得到了我们需要的答案!
可以计算，得到一个rand10()所需要调用的rand7()的次数的期望是2.45。
从信息论的角度来看，rand7()给出的信息量是log(7)，rand10()给出的信息量是log(10)，因此理论上的极限应该是log(10)/log(7)=1.183。如何接近这个答案呢？如果只是生成一个rand10()，这是如论如何也做不到的。但是这个标准答案的隐含意思是，如果想生成1000个rand10()，我们可能只需要调用1183次rand7().
我们可以扩展解法2，考虑一个7位的七进制数abcdefg，其中每一位都是rand7()得到的随机数。那么我们就得到了X~U[0,823542]。利用retry大法，对于大于等于800000的进行retry，就可以得到随机变量Y~U[0,799999]。我们发现对于Y，除了最高位之外，其他所有位置的digit都是符合[0,9]的均匀随机分布的，因此我们就可以通过拆解Y得到五个在[0,9]的均匀随机数，也就是答案。
所以，我们call了7次rand7()，得到了五个rand10()，近乎每7/5=1.2次调用就能实现结果（忽略了retry），效率是非常高的。