关键是 Uniform. 如果2 * Rand7() 变为[2, 14]再减1变为[1, 13],生成的各个数字的概率不是相等的；e.g. rand2()等概率生成1,2, 但是对于 (rand2()-1) + rand2():

1
2
3
4
5
6
rand2() - 1   +   rand()2  =  ?
 {0, 1}           [1, 2]
   0               1          1
   0               2          2
   1               1          2
   1               2          3

不是等概率的;

但是如果 (rand2()-1)*2 + rand2():

1
2
3
4
5
6
(rand2() - 1)*2   +   rand()2  =  ?
 {0, 2}               [1, 2]
   0                   1          1
   0                   2          2
   2                   1          3
   2                   2          4

rand2()生成rand4().

为什么 上面乘2 之后就可以了? 对于rand3(): {1, 2, 3}, 如果按照相同的操作: (rand3() - 1) * 3 + rand3():

1
2
3
4
5
6
7
8
9
10
11
12
(rand3() - 1)*3   +   rand()3  =  ?
 {0,1,2} * 3         {1, 2, 3}
  {0, 3, 6}
   0                   1          1
                       2          2
                       3          3
   3                   1          4
                       2          5
                       3          6
   6                   1          7
                       2          8
                       3          9

(rand3() - 1) * 3 + rand3() 刚好可以等概率生成 {0, ..., 9}.

可以看出, (randN() - 1) * N 对于原randN()来说，刚好上升一个维度并且接壤上，得到的结果就是等概率的。

回到前面的rand2()生成rand4(),那么反过来用rand4()重新回到rand2(): rand4() % 2 + 1:

1
2
3
4
5
rand4() % 2 + 1 =  ?
   1               2
   2               1
   3               2
   4               1

同理，也可以用rand6()生成rand2():

1
2
3
4
5
6
7
rand6() % 2 + 1 =  ?
  1               2
  2               1
  3               2
  4               1
  5               2
  6               1

i.e. rand2N()都可以通过rand2N() % 2 + 1得到rand2()。 所以，回到这道题，我们可以先凑出rand10N()，然后再通过 rand10N() % 10 + 1 来获得 rand10().

rand7()直接变为(rand7()-1) * 7 + rand7(), [0, 6]*7 + [1, 7]得到[1, 49], 明显超过了10; 随机得到一个[1, 10N]的范围内的数之后就可以%10操作往[1,10]`上靠.

  • [1, 49]: 首先要得到[1,10N], 如果要操作次数最少，当然是最容易得到的最好: [1,40]范围最大；
  • [1, 40]的%10操作 => 等概率的[0, 9];
  • [0, 9] + 1 => [1, 10], i.e. rand10()