面试题--Google面试题--概率题--随机生成数

1。给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数

 

答案：此题的关键是让生成的 1 到 7 的数出现概率相同。

（用7下随机生成的1到5的数去决定下一个1到7的数）

只要我们可以从 n 个数中随机选出 1 到 n 个数，反复进行这种运算，直到剩下最后一个数即可。
我们可以调用 n 次给定函数，生成 n 个 1 到 5 之间的随机数，选取最大数所在位置即可满足以上要求。

例如
初始的 7 个数 [1,2,3,4,5,6,7].
7 个 1 到 5 的随机数 [5, 3,1,4,2,5,5]
那么我们保留下[1,6,7],
3 个1 到 5 的随机数[2,4,1]
那么我们保留下[6]
6 就是我们这次生成的随机数。