9

離散一様分布に従わない乱数を生成するのに問題があります。

たとえば、（簡単にするために）5つの数値があるとすると、数値kが生成される確率はk/15になります。（k = 1から5）

私の考えは、rand（）を使用して乱数jを生成することです。この数jが次の場合：

1 =>次に、番号1が生成されます

2または3=>num 2

4または5または6=>num 3

7または8または9または10=>num 4

11または12または13または14または15=>num 5

次に、これを1〜10、1〜100、1〜1000を生成するようにスケーリングします。これは私が意図したとおりに機能しますか？数値を生成する必要があるたびにこれをほぼ実行するループを構築しました。いずれかの範囲で生成されたj数値が見つかるまで上昇するため、おそらく非効率的だと思います...より良い方法は何でしょうか。これをする？

編集：または多分適切な番号で一度配列を作成し、次にrand（）でより良い解決策を引き出しますか？

4

3 に答える 3

14

あなたは正しい方向に進んでいるようですが、C++にはすでにそのための特殊な乱数分布があります。std::discrete_distribution

#include <iostream>
#include <vector>
#include <map>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());

    // list of probabilities    
    std::vector<double> p = {0, 1.0/15, 2.0/15, 3.0/15, 4.0/15, 5.0/15};
    // could also be min, max, and a generating function (n/15 in your case?)
    std::discrete_distribution<> d(p.begin(), p.end());

    // some statistics
    std::map<int, int> m;
    for(int n=0; n<10000; ++n) {
        ++m[d(gen)];
    }
    for(auto p : m) {
        std::cout << p.first << " generated " << p.second << " times\n";
    }
}

オンラインデモ： http： //ideone.com/jU1ll

于 2012-06-08T02:32:51.030 に答える
10

s1からまでの整数の合計がでnあると考えてくださいs = n * (n + 1) / 2。を取得するために解決nしますn = (± sqrt(8*s + 1) - 1) / 2。正であることがわかっているので、負の平方根は無視できnます。したがってn = (sqrt(8*s + 1) - 1) / 2。

したがって、1〜15の整数をプラグインしますs。

s  n
01 1.000000
02 1.561553
03 2.000000
04 2.372281
05 2.701562
06 3.000000
07 3.274917
08 3.531129
09 3.772002
10 4.000000
11 4.216991
12 4.424429
13 4.623475
14 4.815073
15 5.000000

計算されたそれぞれの上限n（以上の最小の整数n）を取ると、次のようになります。

s  n
01 1
02 2
03 2
04 3
05 3
06 3
07 4
08 4
09 4
10 4
11 5
12 5
13 5
14 5
15 5

したがって、一様分布から一定の空間と一定の時間での分布に移行できます（反復や事前計算されたテーブルはありません）。

double my_distribution_from_uniform_distribution(double s) {
    return ceil((sqrt(8*s + 1) - 1) / 2);
}

注意：これは、完全な正方形に対して正確な結果を与えることに依存していますsqrt（たとえば、正確に49を指定すると正確に7を返します）。IEEE 754では平方根を正確に丸める必要があるため、これは通常、安全な仮定です。

IEEE 754 doubleは、1から2 ^ 53までのすべての整数を表すことができます（さらに多くの大きな整数ですが、2 ^ 53以降は連続していません）。sしたがって、この関数は1からまでのすべてで正しく機能するはずfloor((2^53 - 1) / 8) = 1125899906842623です。

于 2012-06-08T02:36:55.620 に答える
0

次のような奇妙な算術的事実を利用できます。

S(n) = 1 + 2 + 3 + ... + (n - 1) + n

または簡体字：

S(n) = n * (n + 1) / 2

これにより、配列の保存を回避できます。

于 2012-06-08T02:32:43.337 に答える