3

このコードは、特定の確率で乱数を取得するために使用されますr。 が 0 ～ 0.8 の場合は 8 が返されます。rが 0.8 ～ 1 の場合は 2 が返されます。

#include<stdio.h>
#include<pthread.h>
#include<stdlib.h>

int main()
{
    srand(time(NULL));
    double r = rand() / (double)RAND_MAX;
    double sum = 8 + 2;
    if (r < 8 / sum) {
        printf("80% \n");
    } else {
        printf("20% \n");
    }  
}

しかし、2 つ以上の数 (n など) がある場合、どうすればそれを処理できますか? 複数の if-else ステートメントで処理できますか? それとも他に何ですか？

4

2 に答える 2

3

単純

  1. O(n)時間内に確率の配列を作成します (合計で 1.0)
  2. 0.0 から 1.0 の間の乱数を生成します
  3. O(n)時間 内に配列を反復処理します。
    • 乱数 < 要素の確率の場合、停止
    • それ以外の場合は、確率で乱数を減らし、次の要素に移動します
  4. 答えは、止まった要素に対応する番号です

複雑

  1. 累積確率の配列を作成し、それらを時間内に配列に保存しますO(n)(この配列には値が増加する必要があります)。
  2. 0.0 から 1.0 の間の乱数を生成します
  3. 二分探索を実行して>=、時間内に乱数である最小の要素を見つけますO(log(n))。
  4. 答えは、止まった要素に対応する番号です

対処するために必要なコーナー ケースは含めていません。私はあなたがそれを自分で行うことができると確信しています。

于 2013-08-25T01:49:20.447 に答える
1

randomstring の提案に加えて、エイリアス テーブルを作成することを検討できます-- O(n log n) を使用してテーブルを作成し、値ごとに O(1) を生成します。

于 2013-08-25T16:01:13.203 に答える