已知一個(gè)函數(shù)f可以得到1-5間的隨機(jī)數(shù)，問(wèn)怎么得到1-7的隨機(jī)數(shù)

glq2000

在 http://blog.csdn.net/DKarthas/archive/2007/11/05/1868212.aspx看到一個(gè)面試題，博主只是提出了問(wèn)題，沒(méi)有給出解答，所以在這發(fā)一下，希望知道解的tx解答下  ：）

問(wèn)題：

已知一個(gè)函數(shù)f可以等概率的得到1-5間的隨機(jī)數(shù)，問(wèn)怎么等概率的得到1-7的隨機(jī)數(shù)，

這個(gè)問(wèn)題是有解的么？ 若無(wú)解，說(shuō)明原因，若有解，那解是什么？

(該問(wèn)題已解決，劇透一下，正解在17樓~~~~~~~~)

evaspring

占著沙發(fā)這樣好的位置當(dāng)然要作點(diǎn)貢獻(xiàn)，公布下比較接近標(biāo)準(zhǔn)的答案：

算法思路是：
1. 通過(guò) rand5()*5+rand5() 產(chǎn)生 6 7 8 9 10 11 …… 26，27 28 29 30 這25個(gè)數(shù)，每個(gè)數(shù)的出現(xiàn)機(jī)率相等
2. 只需要前面 3*7 個(gè)數(shù)，所以舍棄后面的4個(gè)數(shù)
3. 將 6 7 8 轉(zhuǎn)化為 1，9 10 11 轉(zhuǎn)化為 2，……，24 25 26 轉(zhuǎn)化為 7。公式是 (a-3)/3

1. int rand7()
   
2. {
   
3. int a;
   
4. while( (a=rand5()*5+rand5()) > 26 );
   
5. return (a-3)/3;
   
6. }
   

復(fù)制代碼

或者

1. int rand7()
   
2. {
   
3.         int sum = 0;
   
4.         for(int i=0; i<7; i++)
   
5.         {
   
6.                   sum += ( rand5() - 1 ) * pow(5,i) ;
   
7.         }
   
8.         return (sum%7+1);
   
9. }

復(fù)制代碼

iamxmz

運(yùn)行7次f()加起來(lái)除5

寫(xiě)完之后想了一下,7只會(huì)出現(xiàn)一次,前邊的數(shù)都會(huì)出現(xiàn)很多次,這個(gè)不對(duì).

glq2000

回復(fù) 2# evaspring


    f()+f()%2 的取值范圍是 1到6啊
   
后來(lái)我改為    f()+f()%3， 這樣取值范圍倒是1到7了，但取七的概率是

前面需要為5， 后面需要為2或者5， 所以 1/5 * 2/5 = 2/25, 也不是1/7， 滿足不了等概率的條件。。。。。。。。。

egmkang

f() + f() % 2
evaspring 發(fā)表于 2010-07-06 18:41

這個(gè)好像不是平均分布的把

glq2000

回復(fù) 2# evaspring


    f()隨機(jī)返回1-5， 那f()運(yùn)行7次相加的話，再除以7的話，最大也就是 5*7/7 = 5, 根本取不到6和7啊。
   如果你的意思是對(duì)7取余，即使先不考慮等概率，取余的結(jié)果中包含0，而要求是對(duì)1-7返回等概率，不包括0。

   我感覺(jué)這個(gè)題是個(gè)數(shù)學(xué)題。。。。。。

glq2000

對(duì)，有兩點(diǎn)要特別注意，  一是等概率等返回1-7中的某個(gè)數(shù)，而是f()的取值是1-5，他可以等概率的返回一到五，現(xiàn)在要等概率的返回1-7，不包括0，

這個(gè)題目是有解的么？ 解是什么？ 無(wú)解的話，原因是？

churchmice

回復(fù) 6# glq2000


仔細(xì)看，人家是除以5

iamxmz

我改了,寫(xiě)錯(cuò)了,先寫(xiě)的除7.不過(guò)除5也不對(duì),這樣7只會(huì)出現(xiàn)1次.

egmkang

3樓是正解