rand 5()を使用してrand 7()を生成
に答える
rand 5はランダムに1,2,3,4,5を生成することができる.rand 7はランダムに1,2,3,4,5,6,7を生成することができる.rand 5は6,7を直接生成することはできないので,rand 5を直接用いて関数rand 7を実現することはあまり入手しにくいようだ.逆にしたら?rand 7をあげて、rand 5を実現させて、これは実現しますか?
非常に直感的な考えはrand 7を1〜5の間の数が生成されるまで呼び出し続け、戻ることである.コードは次のとおりです.
int Rand5(){
int x = ~(1<<31); // max int
while(x > 5)
x = Rand7();
return x;
}
， 1 5 ？ ， 1 5 ， ， ， Rand7 (1/7)， ， ，Rand5 1 5 。 ？ ， 1 5 1/5 OK 。 ， Rand5 1 。 while ， 1 5 。 ， 1 Rand7 ， ， ，… n 。 1 1， 1/7； 2 1， 1 1 5 6，7， (2/7)*(1/7)， 。 1 ：
P(x=1)=1/7 + (2/7) * 1/7 + (2/7)^2 * 1/7 + (2/7)^3 * 1/7 + ...
=1/7 * (1 + 2/7 + (2/7)^2 + ...) //
=1/7 * 1 / (1 - 2/7)
=1/7 * 7/5
=1/5
Rand5 1,2,3,4,5 (1/5 )。 ， ， a > b， Randa Randb。 ， Randa 1 a ，Randb 1 b 。 ：
// a > b
int Randb(){
int x = ~(1<<31); // max int
while(x > b)
x = Randa();
return x;
}
， Rand5 Rand7， Rand5 Randa， a > 7， 。 ， Randa 1 a 。 ，
Rand5() + Rand5() - 1
1 9 ， ？ 。 1 ： Rand5() 1 ：(1, 1)； 2 ：(1, 2) (2, 1)； 6 。 。 ？
， 。 ：
5 * (Rand5() - 1) + Rand5()
Rand5 1 5 ， 1 0 4 ， 5 ：0,5,10,15,20。 Rand5() 1,2,3,4,5。 1 25， ， 1 25。OK， 。
， ：
int Rand7(){
int x = ~(1<<31); // max int
while(x > 7)
x = 5 * (Rand5() - 1) + Rand5() // Rand25
return x;
}
のコードに か がありますか? るにはwhileループが も われるかもしれません.Rand 25は1から25の を し、1から7の だけwhileループを び し、 されたほとんどの を ててしまうからです.このような は らかによくない. てる をできるだけ なくしなければならないので、whileの を して、xを25に も い25 の7の と することができます.したがって、 をx>21に することができ、xの は1〜21である.さらにモデリング により1−7にマッピングすればよい.コードは のとおりです.int Rand7(){
int x = ~(1<<31); // max int
while(x > 21)
x = 5 * (Rand5() - 1) + Rand5() // Rand25
return x%7 + 1;
}
， 1 7 。
， 。 Randa， Randb。Randa Randb 1 a 1 b ，a，b ( )。 Randa Randb。
， ：
-
a > b， 2； Randa2 = a * (Randa – 1) + Randa， 1 a2 。 a2 b， Randa3 = a * (Randa2 – 1) + Randa… ak > b， Randak , RandA。
-
1 RandA( Randa Randak )， A > b， Randb：
// A > bint Randb(){
int x = ~(1<<31); // max int
while(x > b*(A/b)) // b*(A/b) A A b
x = RandA();
return x%b + 1;
}
の の から、 を する2つの RandaとRandbを えると、 の でRandabを に し、1からa*bまでの を することができます.Randab = b * (Randa - 1) + Randb
Randab = a * (Randb - 1) + Randa
さらに すれば、ランダムにaからbを する を え、ランダムにcからdを する を することもできます. のある は えてみてください.ここでは しません.
はブロガーのオリジナル で、ブロガーの を ずに してはならない.