如何用 random9 求 random10

大意

如果有一个 random9() 函数，可以产生 1-9 的 整数随机数，请利用 random9 实现 random10 函数，返回 1-10 的整数随机数

要点

random9 只能随机产生 1-9 范围内的数，也就是 1-9 出现的概率是一样的；而如果要随机产生 1-10 范围的整数，就需要 1-10 出现的概率是一样的。

所以问题就变成了：如何通过等概率出现的 1-9 产生等概率的 1-10 ？

解决

以一种马后炮的思想尝试解释一下，看能不能说服自己。

random9 显然产生不了 10，所以肯定需要用到加/乘法，那如何产生 10？

• random9 + n
  如果只用加法，这样便可以随机产生[n+1, n+9]范围的整数，可以达到10，但是肯定不能产生[1, 10]范围内的数，所以这样不行。

• random9 * n
  如果只用乘法，这样便可以随机产生[n, 2n, 3n, …, 9n]，这样产生的数显然也不可能做到随机产生[1, 10]，因为中间存在空位，并且无法保证是等概率的。

要想等概率产生[1, 10]范围的数，可以利用等概率产生[1, 20]范围的整数，然后%10 + 1。这里有个重点，怎么样才能等概率？

既然 random9 加/乘一个固定的数，不能达到目的，那么如果加/乘一个不固定但是等概率出现的某一范围的数（也就是 random9）是否可行呢？

• random9 + random9
  能出现的最大数：9 + 9 = 18；能出现的最小数：1 + 1 = 2
  先考虑能否等概率出现10，先看2-18是否为等概率出现的。
  出现2、18的概率都是1/81，但出现3的概率是2/81，即1+2和2+1，这个就不是等概率出现的了，所以不能做到随机产生。
• random9 * random9
  最大数：81，最小数：1。
  是否连续？否。
  是否等概率？否。最大、小数的概率是1/81。但是9的概率是3/81。
• random9 * n + random9
  random9 * n 可等概率产生 1n,2n,3n…9n，如果加上 random9，是否等概率取决于1n和2n之间的间距，如果刚好等于9，那么加上random9就有希望产生连续、并且等概率的整数，范围为：[10, 90]。

如何通过等随机产生的 [10, 90] 来随机产生 [1, 10]?
将随机产生的 [10, 90] 限制为 [10, 89]，然后模10，便可以获得随机产生的[0, 9]，然后再加1，即可得到随机产生的[1, 10]。

总结为：先通过 random9 * 9 + random9 随机产生[10, 90]范围的整数，然后限制随机产生 [10, 89]，再模10，得到[0, 9]，再加1即可得到[1, 10]。

所以最终的代码：

while ((result = 9 * random9() + random9()) >= 90);
return result % 10 + 1;

但是，我看到的答案是这样的，还不太明白这两者之间有什么差别。

public int rand10() {
    int result;
    do {
        result = rand9()+(rand9()-1)*9;
    } while (result > 80);
    return 1 + (result - 1) % 10;
}

更加简单粗暴的方式

但是这个问题是由 random7 求 random10，不过思想是相通的。

感觉这一种方式更加通俗易懂，获取一维数组是随机的，获取第二维数组也是随机，整个过程都是随机的。

public static int random10() {
    int[][] seed = { { 1, 2, 3, 4, 5, 6, 7 }, { 8, 9, 10, 11, 12, 13, 14 },
            { 15, 16, 17, 18, 19, 20, 11 }, { 22, 23, 24, 25, 26, 27, 28 },
            { 29, 30, 31, 32, 33, 34, 35 }, { 36, 37, 38, 39, 40, 41, 42 },
            { 43, 44, 45, 46, 47, 48, 49 } };

    int result;
    do {
        result = seed[random7() - 1][random7() - 1];
    } while (result > 40);
    return result % 10 + 1;
}