p******n
发帖数: 32 | 1 Write a method to generate a random number between 1 and 7, given a method
that
generates a random number between 1 and 5.
careercup 150里面的，也是那个amazon面经帖子里的面试题，我没看明白solution里
面的算法。谁能给解释一下？ | p******r
发帖数: 2999 | 2 rand5()随机产生1-5
(rand5()-1)*5生成0,5,10,15,20
(rand5()-1)*5+rand5()就能随机生成1-25之间的数
然后通过模7来生成1-7的随机数
由于25不能被7整除，所以只考虑1-21之间
最后的表达式为
((rand5()-1)*5+rand5())%7+1
【在 p******n 的大作中提到】
: Write a method to generate a random number between 1 and 7, given a method
: that
: generates a random number between 1 and 5.
: careercup 150里面的，也是那个amazon面经帖子里的面试题，我没看明白solution里
: 面的算法。谁能给解释一下？
| j*****4
发帖数: 292 | 3 原题没说清楚。应该是uniform产生uniform，否则就没啥意义了。
如果是要求uniform，遇到22-25要pass，所以取1-21
【在 p******r 的大作中提到】
: rand5()随机产生1-5
: (rand5()-1)*5生成0,5,10,15,20
: (rand5()-1)*5+rand5()就能随机生成1-25之间的数
: 然后通过模7来生成1-7的随机数
: 由于25不能被7整除，所以只考虑1-21之间
: 最后的表达式为
: ((rand5()-1)*5+rand5())%7+1
| x*****p
发帖数: 1707 | 4 If you bypass 22-25, it is not uniform any more. | g**e
发帖数: 6127 | 5 it is.
【在 x*****p 的大作中提到】
: If you bypass 22-25, it is not uniform any more.
| p******n
发帖数: 32 | 6 明白了，那么遇到这类题用randN()产生randM()的思路就是首先想办法用randN()产生
一个最小可
能的M的倍数，比如，1*M不行，看看能不能产生2M，2M不行能不能产生3M，以此类推。
然后再对M取
模。
【在 p******r 的大作中提到】
: rand5()随机产生1-5
: (rand5()-1)*5生成0,5,10,15,20
: (rand5()-1)*5+rand5()就能随机生成1-25之间的数
: 然后通过模7来生成1-7的随机数
: 由于25不能被7整除，所以只考虑1-21之间
: 最后的表达式为
: ((rand5()-1)*5+rand5())%7+1
|
|
