1

範囲とその範囲内のいくつかの数値 ( exceptions ) が与えられたとします。次に、指定された例外を除く範囲で乱数を生成する必要があります。

たとえば、範囲 = [1..5] で例外 = {1, 3, 5} の場合、2 または 4 を同じ確率で生成する必要があります。

この問題を解決するには、どのロジックを使用する必要がありますか?

4

7 に答える 7

2

1簡単にするために、配列のインデックスは から始まり、範囲は から1までであると仮定しましょうk。もちろん、そうでない場合は、いつでも結果を定数でシフトできます。例外の配列を呼び出し、例外ex_arrayがあるとしましょうc。これらはソートする必要があり、しばらくするとかなり重要になるでしょう。

これで、作業に役立つ数値しかないので、 から までの範囲でk-e乱数を見つけることは意味があります。数字で終わるとしましょう。次に、配列で有効な数値を見つける必要があります。単純？それほどでもない。覚えておいてほしいのは、どの配列も単純に直線的に処理することはできないということです。これは、多数の数値がある場合に実装が非常に遅くなる可能性があるためです。たとえば、十分に高速なアルゴリズムを考え出すために、ある種の二分探索を行う必要があります。1k-err-th

では、もっと良いものを試してみましょう。例外がなければ、数値は名目上、元の配列のインデックスにあるr-thはずです。もちろん、範囲と配列インデックスが から始まるため、インデックスrの数値はです。しかし、 と の間に無効な数値がたくさんあり、どうにかして有効な数値に到達したいと考えています。では、例外の配列 に対してバイナリ検索を実行して、と の間に無効な数値が多数あるため、と等しいかそれ以下の無効な数値がいくつあるかを調べます。この数値がの場合はすべて完了ですが、そうでない場合は、もう少し作業が必要です。rr11rr-th ex_array r1r0

二分探索の間と後にn無効な数値があることがわかったとします。配列内のインデックスをインデックス に進め、 と の間にある無効な数値の数を見つけます。二分探索を使用して、 の要素が より小さいか等しいかを調べます。この数字が正確に である場合、無効な数字はこれ以上検出されず、有効な数字を見つけたことになります。それ以外の場合は、今度はインデックス について繰り返します。ここで、は と の間にある乱数の数です。1r nr+n1r+nex_arrayr+nnr-thr+n'n'1r+n

余分な例外が見つからなくなるまで繰り返します。ここで重要なことは、配列を直線的にたどる必要が一度もないということです。常に index から開始しないように、バイナリ検索を最適化する必要があります0。との間に n 個の乱数があることがわかっている1としrます。から次のバイナリ検索を開始する代わりに、in に1対応するインデックスの 1 つ後のインデックスから開始することができます。nex_array

最悪の場合、 の各要素に対してバイナリ検索を実行することになりex_arrayます。つまりc、最初は index から開始し1、次は indexから開始するというようにバイナリ検索2を実行することになり、時間計算量は になりO(log(n!))ます。さて、スターリングの近似は を教えてくれるO(ln(x!)) = O(xln(x))ので、上記のアルゴリズムの使用はcが十分に小さい場合にのみ意味があります。最初に配列から有効な要素を抽出する簡単な方法を使用して複雑さをO(cln(c)) < O(k)達成できるからです。O(k)

于 2013-09-13T19:52:26.197 に答える
1

初期範囲が [1,n] で、除外セットのサイズが x であるとします。最初に、[1, nx] から除外セット内の番号を除いた番号 [1, n] へのマップを生成します。両側に等しい数があるため、このマッピングは 1-1 です。質問に示されている例では、マッピングは次のようになります - {1->2,2->4}。

別の例として、リストが [1,10] で除外リストが [2,5,8,9] の場合、マッピングは {1->1, 2->3, 3->4, 4->6, 5->7、6->10}。このマップは、O(nlogn) の最悪の場合の時間計算量で作成できます。

[1, nx] の間の乱数を生成し、マッピングを使用して対応する番号にマッピングします。マップのルックは O(logn) で行うことができます。

于 2015-01-23T17:11:33.653 に答える
1

これが別のアプローチです...除外されない乱数が得られるまで、乱数を生成し続けます。

希望する範囲が [0,100) で、25、50、および 75 を除くとします。

高速検索のために、除外された値をハッシュテーブルまたはビット配列に入れます。

int randNum = rand(0,100);

while( excludedValues.contains(randNum) )
{
    randNum = rand(0,100);
}

rand(0,100) は毎回 25、50、または 75 を返す可能性があるため、複雑さの分析はより困難です。ただし、範囲の半分が除外されたとしても、それはほとんどありません (乱数ジェネレーターを想定)。

上記の場合、元の値の 3/100 のみのランダム値を再生成します。

つまり、3% の確率で 1 回再生します。それらの 3% のうち、再生する必要があるのは 3% だけです。

于 2013-09-20T05:58:47.473 に答える
0

列挙子または集合操作がある場合は、用途の広い方法で行うことができます。たとえば、Linq を使用すると、次のようになります。

void Main()
{
    var exceptions = new[] { 1,3,5 };
    RandomSequence(1,5).Where(n=>!exceptions.Contains(n))
                       .Take(10)
                       .Select(Console.WriteLine);
}

static Random r = new Random();

IEnumerable<int> RandomSequence(int min, int max)
{
    yield return r.Next(min, max+1);
}

現在削除されているいくつかのコメントに感謝したいと思います。

  • 有効な値を決して含まないシーケンスが存在する可能性があるため、このプログラムが終了しない可能性があります (理論的にのみ) 。公正なポイント。これはインタビュアーに説明できることだと思いますが、私の例はコンテキストに十分適していると思います.

  • 各要素が出現する可能性が同じであるため、分布は公平です。

  • このように答える利点は、インタビュアーにとって興味深いかもしれない最新の「関数型」プログラミングの理解を示すことです。

  • 他の答えも正しいです。これは、問題に対する別の見方です。

于 2013-09-13T20:03:30.353 に答える