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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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
|
|