1

最初に、これは不自然な例であり、現実の問題ではないことを明確にしておきます。

0〜10の乱数を作成する際に問題が発生した場合は、これを11回行い、以前に発生した番号が再度描画されないようにします。繰り返し番号を取得した場合は、別の乱数を作成して、以前は見られませんでした。したがって、基本的に、0から10までの一意の番号のシーケンスをランダムな順序で取得します（例：3 1 2 0 5 9 4 8 10 6 7など）。

ここで、乱数が一意であり、以前に描画したものではないことを確認するロジックを考え出すために、多くのアプローチを使用できます。

C ++std::bitsetを使用して、インデックスに対応するビットを各ランダム番号の値に等しく設定します。次回、新しい乱数が描画されたときに確認します。

または

aを使用しstd::map<int,int>て、回数をカウントするか、その配列にいくつかの番兵値が格納されている単純なC配列でさえ、その数が発生したかどうかを示します。

上記の方法を避け、数学的/論理的/ビット単位の演算を使用して、以前に乱数が描画されたかどうかを確認する必要がある場合、方法はありますか？

4

5 に答える 5

3

あなたはあなたが提案するようにそれをしたくありません。11個のアイテムのうち10個をすでに選択した場合に何が起こるかを考えてみてください。乱数ジェネレーターは、欠落している番号が見つかるまで循環します。これは、乱数ジェネレーターによっては、検出されない場合があります。

より良い解決策は、0から10までの番号のリストを順番に作成してから、リストをランダムな順序にシャッフルすることです。これを行うための通常のアルゴリズムは、Knuth、Fisher、およびYatesによるものです。最初の要素から開始して、各要素を配列内の現在の要素よりも大きい位置にある要素と交換します。

function shuffle(a, n)
    for i from n-1 to 1 step -1
        j = randint(i)
        swap(a[i], a[j])

インデックスが0からn-1の配列と、jを0 <= j<=iの範囲に設定するrandint関数を想定しています。

于 2012-12-10T13:59:44.477 に答える
1

配列を使用して、可能なすべての値を配列に追加します。次に、アレイから1つを選び、それを削除します。次回は、配列が空になるまでもう一度選択します。

于 2012-12-10T13:26:16.283 に答える
1

はい、それを行うには数学的な方法がありますが、それは少し広大です。

配列があります：primes[]ここでprimes[i] = the i'th prime number。したがって、その始まりはになります[2,3,5,7,11,...]。

また、数字を保存しmultます。ここで、数字を描画したら（そのままにしますi）、そうである場合は、以前に描画された数字であるかどうかを確認します。そうmult % primes[i] == 0でない場合は、数字はそうではありませんでした。それを選んでやるmult = mult * primes[i]。

ただし、範囲が広い場合は多くのスペースが必要になる可能性があるため、拡張性があります（可能な値はmult指数関数的に増加します）

（これは優れた数学的アプローチです。実際には素数のセットを調べているため、素数p_iの配列は抽象的な素数のセットの実装にすぎません）。

小さな値のビット操作の代替手段は、intまたはをビットlongセットとして使用することです。

このアプローチでは、候補者をチェックするためにあなたがチェックする必要がiあるのはあなただけではありませんset：

if (pow(2,i) & set == 0) // not in the set
else //already in the set

セットに要素を入力するiには：

set = set | pow(2,i)

より良いアプローチはlist、すべての数値を入力し、フィッシャーイェーツシャッフルでシャッフルし、それを繰り返して新しい乱数を生成することです。

于 2012-12-10T13:37:26.713 に答える
0

上記の方法を避け、数学的/論理的/ビット単位の演算を使用して、以前に乱数が描画されたかどうかを確認する必要がある場合、方法はありますか？

はい、不自然な制約を条件として、ビット単位の演算を使用して小さなビットセットを模倣できます。

必要なサイズに応じて、右側でさまざまな整数タイプを選択できます。

bitset code                    bitwise code

std::bitset<32> x;             unsigned long x = 0;
if (x[i]) { ... }              if (x & (1UL << i)) { ... }
// assuming v is 0 or 1
x[i] = v;                      x = (x & ~(1UL << i)) | ((unsigned long)v << i);
x[i] = true;                   x |= (1UL << i);
x[i] = false;                  x &= ~(1UL << i);

より大きなセット（ビット単位のサイズを超えるunsigned long long）の場合は、選択した整数型の配列が必要になります。インデックスを各値の幅で除算して、配列で検索するインデックスを確認し、ビットシフトのモジュラスを使用します。これは基本的に何をするかbitsetです。

私は、10の数字をシャッフルする最善の方法を示すさまざまな答えが完全にポイントを失っていると思います。実際には、10の数字をシャッフルする最善の方法を知りたくない、または知る必要がないため、考案された制約があります:-)

于 2012-12-10T14:11:43.393 に答える
0

変数を保持し、描画された数値をマップします。数値が以前に描画された場合、その変数のi番目のビットは1になります。

int mapNumbers = 0;

int generateRand() {        
    if (mapNumbers & ((1 << 11) - 1) == ((1 << 11) - 1)) return; // return if all numbers have been generated
    int x;  
    do {
        x = newVal();
    } while (!x & mapNumbers);
    mapNumbers |= (1 << x);
    return x;
}
于 2012-12-10T14:18:25.127 に答える