0

私は CLRS を読んでいて、50% の確率で 0 または 1 を生成するプロシージャ Rand(0,1) を使用して、a から b の間の乱数を一様ランダムに生成するプロシージャ Rand(a,b) を作成するという問題に遭遇しました。 .

私は次の解決策を考えました。これは時間的に O(b) です。

int Rand_a_b(int a,int b)
{
    int i,k=0;
    for(i=0;i<b-a;i++)
    {
         k+=Rand(0,1);
    }
    return a+k;
}

これに対するより良いアプローチを提案してください。

4

3 に答える 3

1

ここにアルゴリズムがあります: a と b の差を計算し、次のk = abs(a-b)ように二分探索を開始します:

数字をn = 0キープ .コインをひっくり返す -Rand(0,1)結果が 1 の場合はk/2自分に追加し、そうでない場合はn何も追加しません。もう一度反転してが 0 になるk/4まで繰り返します。k/i

于 2014-02-16T12:25:23.610 に答える
1

ここでは、log(n) でそれを行う必要があります。(私は境界をチェックしませんでした、それはテストされていません!) それよりも速くすることはできません - 一度に 1 ビットしか発行しない場合、間隔のために少なくとも log(ba) ラウンドが必要です。

function Rand_a_b(int a, int b) {
   if (a == b) return a;
   int middle = (b-a)/2;
   if (Rand(0,1)) {
      return Rand_a_b(middle + 1, b);
   } else {
      return Rand_a_b(a, middle);
   }
}
于 2014-02-16T12:26:01.550 に答える