1

ランダムビットを返す関数があるとすると、一定の範囲内で一様に乱数を生成し、常に終了する関数を作成することはできますか？

私はこれを行う方法を知っているので、それは終了するはずです（そしておそらく終了するでしょう）。終了が保証されているものを書くことができるかどうか疑問に思っていました（そして、それは特に効率的である必要はありません。それはどのくらい複雑になるでしょうか？

これは、常に終了するわけではないバージョンのコードです

int random(int n)
{
  while(true)
  {
    int r = 0;
    for (int i = 0; i < ceil(log(n)); i++)
    {
      r = r<<1;
      r = r|getRandomBit();
    }

    if(r<n)
    {
      return r;
    }
  }
}
4

2 に答える 2

2

私はこれがうまくいくと思います：

範囲内の数値を生成するとします[a,b]

バイナリ基数を使用してr範囲内の分数を生成します。[0,1}つまり、ランダム関数を使用して0.x1x2x3....、すべてxが0または1のいずれかであるいくつかのフォームを生成します。

それができたら、[0,b-a]計算することで範囲内の数値を簡単に生成しceil(r*(b-a))、単純に加算aして範囲内の数値を取得できます[a,b]

于 2012-11-30T18:54:54.890 に答える
1

範囲のサイズが2の累乗でない場合、棄却サンプリングに相当するものを除いて、正確に均一な分布を取得することはできません。ただし、広い範囲から1回サンプリングし、小さい範囲を分割することで、均一に近づけることができます。

たとえば、1〜10を均一にサンプリングすることはできませんが、10個のランダムビットを選択することで1〜1024を非常に簡単にサンプリングし、それをほぼ同じサイズの10個の間隔に均等に分割する方法を見つけることができます。

追加のビットを選択すると、選択で確認する必要のある最大のエラー（真の均一性から）が半分になります。したがって、より多くのビットを選択すると、エラーは指数関数的に減少します。

于 2012-11-30T21:13:03.677 に答える