3

1 から 5 の間の乱数を生成するメソッドを指定して、1 から 7 の間の乱数を生成するアルゴリズムを作成したいと考えています。

私は1つの解決策を rand(5)/5*7 と考えました??

これはうまくいくはずだと思います。

誰でも最適な解決策を教えてもらえますか?

私はこの解決策をどこかで読みましたが、「 int num = 5 * (rand5() - 1) + (rand5() - 1);」を保持することをどのように考えたのかわかりません。. 1 から 7 までの乱数を生成することは理解していますが、このロジックをどのように考えたのか、何を伝えようとしているのかが頭に浮かびません。誰でもこれに光を当ててください。

public static int rand7() {
while (true) {
    int num = 5 * (rand5() - 1) + (rand5() - 1);
    if (num < 21) 
        return (num % 7 + 1);
}
}
4

2 に答える 2

12

投稿したコードは、accept-reject アルゴリズムの例です。表現

5 * (rand5() - 1) + (rand5() - 1);

0 から 24 の間で均一に分布する乱数を生成します。最初の項は、0 から 4 の間の乱数の 5 倍であり、セット {0, 5, 10, 15, 20} のいずれかを等しい確率で生成します。2 番目は 0 から 4 の間の乱数です。2 つの乱数はおそらく独立しているため、それらを加算すると 0 から 24 の間で均一に分布する乱数が得られます。2 番目の数は、最初の項によって生成された数の間のギャップを「埋めます」。 .

次に、テストは 21 以上の番号を拒否し、プロセスが繰り返されます。数値がテストに合格すると、0 から 20 (両端を含む) の間で一様に分布する乱数になります。この範囲は、 を使用して 7 つの数字 (0 から 6 の間) に分割され% 7、1 つが追加されてから返されます。区間 [0, 20] には 21 個の数値があり、21 は 7 で割り切れるため、0 から 6 までの数値は同じ確率で発生します。

表では:

A           B              num
rand5()-1   rand5()-1      5 * A + B        num % 7 + 1
---------   ---------      ---------        -----------
0           0              0                1
1           0              5                6
2           0              10               4
3           0              15               2
4           0              20               7
0           1              1                2
1           1              6                7
2           1              11               5
3           1              16               3
4           1              21               reject
0           2              2                3
1           2              7                1
2           2              12               6
3           2              17               4
4           2              22               reject
0           3              3                4
1           3              8                2
2           3              13               7
3           3              18               5
4           3              23               reject
0           4              4                5
1           4              9                3
2           4              14               1
3           4              19               6
4           4              24               reject

最後の列には、範囲 [1, 6] の各数値が 3 つあることに注意してください。

ロジックを理解するもう 1 つの方法は、基数 5 の算術について考えることです。rand5()は 1 から 5 までのランダムな整数を生成するため、5 進数の乱数を生成するために使用できますrand5() - 1。1 から 7 までの数字 (つまり、0 から 6 まで) を生成しようとしているので、7 つの数字を得るには、少なくとも 2 つの 5 進数が必要です。それでは、ランダムな 2 桁の基数 5 の数字を 1 桁ずつ生成してみましょう。それ5*(rand5() - 1) + (rand5() - 1)がそうです。0 から 6 (0 から 11 5 )の間の数値が得られるまで、これを何度も繰り返すことができます。ただし、生成している 2 桁の数を拒否する方が効率的です。これを行うには、7 の倍数である 2 桁の 5 進数の最大値まで (ただし、これを含まない) すべてを使用します。たまたま 41 です。5、これは 21 10です。( 1 ではなく 0 から開始するため、41 5% 7自体を除外します。) 0 から 6 の間の数値が必要なので、 を使用して範囲を縮小します。([0, 40 5 ]にはちょうど 3 つの 7 個の整数範囲があるため、3 で割ることもできます。ただし、剰余演算子を使用すると、[0, 6] の範囲を目指していることが明確になります。 )

PS 提案されたソリューションは機能しません。範囲は正しいように見えますが、この式は 5 つの異なる数値しか生成できないため、正しいとは言えません。0 を生成することもできます ( rand5()1 を返す場合)。浮動小数点乱数の生成を扱っている場合は、そのような単純なスケーリングが適切なアプローチになります。(ただし、スケーリングの前に 0 にシフトしてから、範囲の正しい下限を取得するために 1 に戻す必要があります。式は、と思いますが1 + 7 * (rand5() - 1) / 5、rand5()浮動小数点数ではなく整数を返します。)

于 2013-08-23T04:35:33.103 に答える