14

ここStackoverflowで初めて。アルゴリズムの検索で誰かが私を助けてくれることを願っています。

指定された範囲で、合計が指定された合計になる N 個の乱数を生成する必要があります。

例: 合計が 11 になる数字を 3 つ生成します。

範囲:

  1. 1 ～ 3 の値。
  2. 5 ～ 8 の値。
  3. 値は 3 ～ 7 です。

この例で生成される数値は、2、5、4 です。

私はすでにたくさん検索しましたが、必要な解決策を見つけることができませんでした。

次のようにモジュロを使わない定数和の N 数のように生成することは可能 です 。

または、N 個のランダムな値を生成し、それらを合計して、定数の合計をランダムな合計で割り、その後、ここで提案されているように、各乱数にその商を掛けます。

主な問題、これらの解決策を採用できない理由は、ランダム値のすべてに異なる範囲があり、範囲内で値を均一に分散する必要があることです (たとえば、値を切り捨てると発生する最小/最大で頻度が発生しません)最小/最大よりも小さい/大きい)。

また、乱数（その例では、値1、2または3）を取り、範囲内（最小/最大または最小と合計の残りのいずれか小さい方に応じて）内の値を生成するソウルションについても考えました）、与えられた合計からその数を引き、すべてが配布されるまでそれを続けます。しかし、それは恐ろしく非効率的です。アルゴリズムのランタイムが固定されている方法を実際に使用できます。

私はそれをJavaで実行しようとしています。しかし、誰かがすでに解決策を用意している場合を除いて、その情報はそれほど重要ではありません。私が必要とするのは、アルゴリズムの説明またはアイデアだけです。

4

3 に答える 3

9

まず、この問題は次と同等であることに注意してください。

x_1、...、x_k - それぞれに制限があるように、合計すると数値 y になる k 個の数値を生成します。

2番目は、数値から下限を単純に減らすことで実現できます-したがって、あなたの例では、次と同等です:

x1 <= 2 となる 3 つの数値を生成します。x2 <= 3; x3 <= 4; x1+x2+x3 = 2

2番目の問題はさまざまな方法で解決できることに注意してください。そのうちの1つは次のとおりです。

h_i要素ごとに繰り返しのあるリストを生成します-h_iは要素の制限ですi- リストをシャッフルし、最初の要素を選択します。

あなたの例では、リストは次のとおりです。[x1,x1,x2,x2,x2,x3,x3,x3,x3]- それをシャッフルして、最初の 2 つの要素を選択します。

(*) リストのシャッフルは、 fisher-yatesアルゴリズムを使用して実行できることに注意してください。(必要な制限を超えた後、途中でアルゴリズムを中止できます)。

于 2013-11-09T14:33:09.077 に答える
2

2この問題は、最小の 9 を超える位置をランダムに分配することと同じ3です。

したがって、最小値 (1/5/3) から開始し、次にサイクル2時間を [0-2] (3位置) の (疑似) ランダム値を生成し、インデックス付きの値をインクリメントします。

例えば

  • 1/5/3開始
  • 最初のランダム = 1 ... インクリメント インデックス 1 ... 1/6/3
  • 2nd random=0 ... インクリメントインデックス 0 ... 2/6/3

2+6+3=11

編集

これをもう一度読んで、理解しました。これはまさに @KarolyHorvath が言及したことです。

于 2013-11-09T15:21:22.383 に答える