470. 用 Rand7() 实现 Rand10()（拒绝采样）

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例 1:

输入: 1
输出: [2]

示例 2:

输入: 2
输出: [2,8]

示例 3:

输入: 3
输出: [3,8,10]

提示:

• 1 <= n <= 105

进阶:

• rand7()调用次数的 期望值 是多少 ?
• 你能否尽量少调用 rand7() ?

本质数学概率题。

枚举如下：
	a	1	2	3 4 5 6 7 b 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 0 4 5 6 7 8 9 0 1 5 6 7 8 9 0 1 2 6 7 8 9 0 1 2 3 7 8 9 0 1 2 3 4 去掉右上角的 6 7 8 7 8 9 8 9 0 后 每个数字的出现次数为4次，0-9的概率相同 所以程序思路就很明了,当结果扫到右上角的时候进行递归调用，直到输出其他结果 a=rand7(); b=rand7(); if(a>4&&b<4) return rand10(); else return (a+b)%10+1; 平均调用2.45次rand7()， ( PS:解释一下为什么是2.45............拉开看 分布列如下：调用次数为1次，P=40/49；2次P=(9/49)*(40/49); 3次P=(9/49)^2*(40/49); ............N次 P=(9/49)^（n-1）*(40/49)； 平均调用次数为期望==（次数*概率）求和==1*40/49+2*(9/49)*(40/49)+(9/49)^2*(40/49)+...............+n*(9/49)^（n-1）*(40/49); 求出后结果为2*49/40=2.45 )

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int temp1=rand7();
        int temp2=rand7();
        if(temp1>4&&temp2<4) return rand10();
        return (temp1+temp2)%10+1;
    }
};

原文地址：http://www.cnblogs.com/zzzlight/p/16916540.html