算法-算法：rand()产生1~7之间的随机数，如何用rand()函数产生1~10之间的随机数

Question

已知有个rand7()的函数，返回1~7随机自然数，让利用这个rand7()构造rand10() 随机1~10。
（1）

要保证rand10()在整数1~10的均匀分布，可以构造一个（1~10）*n的均匀分布的随机整数区间（n为任何正整数）。假设x是这个（1~10）*n区间上的一个随机整数，那么x%10+1就是均匀分布在1~10区间上的整数。
如n=4，则构造了一个1~40的均分分布的随机整数区间
假设x=35，得到一个分布在1~10区间上的整数，即35%10+1=5+1=6
假设x=30，得到一个分布在1~10区间上的整数，即30%10+1=0+1=1
因为余数的取值区间为[0~9]，而我们需要的区间为[1~10]，故取余后再进行加1操作

Answer 1

个人觉得这种一个概率实现另外一种概率，其实简单说就是：
假设有2种概率：1~n, 1~m, 要让以n的概率实现m，则会有2种情况，n > m or n < m

如果n < m，则要加大n产生的范围

我们知道，10进制时，1位数的取值范围是 [0 ~ 9]，
2位数的取值范围则变成[0 ~ 9] * 10 + [0 ~ 9]，
3位数的取值范围则变成[0 ~ 9] * 10 * 10 + [0 ~ 9] * 10 + [0 ~ 9]，
....
即 10进制表示数的规则是
[0 ~ 10-1] * 10 ^ (位数-1) + [0 ~ 10-1] * 10 ^ (位数-2) + ... + [0 ~ 10-1]

即N进制表示数的规则是

[0 ~ N-1] * N ^ (位数-1) + [0 ~ N-1] * N ^ (位数-2) + ... + [0 ~ N-1]

设n为我们需要的进制数，则其表示数的规则是

[0 ~ n-1] * n ^ (位数-1) + [0 ~ n-1] * n ^ (位数-2) + ... + [0 ~ n-1]

如果 n < m , 则找到一个通过n进制产生的数大于m，

例如 [0 ~ n-1] * n + [0 ~ n-1] > m ,

因为 [0 ~ n-1] * n + [0 ~ n-1] > m, 则 [0 ~ n-1] * n + [0 ~ n-1] / m = a 余 b

那么就是 ([0 ~ n-1] * n + [0 ~ n-1] - b) = m * a

也就是通过 ([0 ~ n-1] * n + [0 ~ n-1] - b) ，我们可以实现m的a倍范围，即相当于我们多次产生[0 ~ m-1, 0 ~ m-1, ..., 0 ~ m-1], 概率是平均的.

说下理解的错误：

 return x % 10 + 1; //将该值的个位作为种子

这个不是取该值的个位，而是获取某个数是以[0 ~ m-1, 0 ~ m-1, ..., 0 ~ m-1]这种排列顺序中的[0 ~ m-1]集合中的某一个元素

基于这个问题：

这个能用rand7()表示1~10范围，但是能扩展一下用rand7()表示1~12么？这种方式是不是也有些局限性？
— douya0808

肯定没有局限性，任意一个数能用10进制表示，也必然可以用7进制或者12进制表示
那你这个题的例子来说：
n = 7， m = 12

因为 7 < 12，则增加范围，
[0 ~ n-1] * n + [0 ~ n-1] = [0 ~ 6] * 7 +[0 ~ 6] = [0 ~ 48] , 其中max = 48

max / 12 = 48 / 12 = 4 余 0, 则判定条件为 max < 12 * 4 - 1 （其中-1的原因是从0开始，貌似我上面好像忘记说这点了 - -!!）

修正后的范围为
[0 ~ 47]

转换成12机制和7进制的元素排列顺序如下

 10进制 00 01 02 03 04 05 06 07 08 09 10 11 12
07元素 00 01 02 03 04 05 06 00 01 02 03 04 05
07进制 00 01 02 03 04 05 06 10 11 12 13 14 15
12元素 00 01 02 03 04 05 06 07 08 09 10 11 00
12进制 00 01 02 03 04 05 06 07 08 09 0a 0b 10

10进制 13 14 15 16 17 18 19 20 21 22 23 24 25
07元素 06 00 01 02 03 04 05 06 00 01 02 03 04
07进制 16 02 21 22 23 24 25 26 30 31 32 33 34
12元素 01 02 03 04 05 06 07 08 09 10 11 00 01
12进制 11 12 13 14 15 16 17 18 19 1a 1b 20 21

10进制 26 27 28 29 30 31 32 33 34 35 36 37 38
07元素 05 06 00 01 02 03 04 05 06 00 01 02 03
07进制 35 36 40 41 42 43 44 45 46 50 51 52 53
12元素 02 03 04 05 06 07 08 09 10 11 00 01 02
12进制 22 23 24 25 26 27 28 29 2a 2b 30 31 32

10进制 39 40 41 42 43 44 45 46 47
07元素 04 05 06 00 01 02 03 04 05
07进制 54 55 56 60 61 62 63 64 65
12元素 03 04 05 06 07 08 09 10 11
12进制 33 34 35 36 37 38 39 3a 3b

可以看出，47 = 65（7进制） = 3b(12进制)， 即用7进制产生的数表示12进制表示(数的倍)数，
同样可以看出 [0 ~ 47] 正好是4次 [0 ~ 11]，每个元素+1，就变为4次[1 ~ 12]，概率是平均的