2

インターネット上には、有名な誕生日のパラドックスについて論じている膨大なリソースがあります。2 人の誕生日が同じである確率を計算する方法は明らかですP(same) = 1 - P(different)。しかし、明らかにもっと単純なことを自問自答すると、失速してしまいます。まず、2 つのランダムな誕生日を生成するとします。同じ誕生日を迎えることは、コインを投げるようなものです。2 人の誕生日が同じ (Heads) か、誕生日が同じでない (Tail) かのいずれかです。これを 500 回実行すると、最終結果 (#Heads/500) は何とか 0.5 に近くなります。

  • Q1) しかし、3 つのランダムな誕生日を生成した場合、これについてどのように考えればよいでしょうか? ではどうすれば確率を見積もることができるでしょうか？明らかに、私のコインの類推は当てはまりません。

  • Q2) 上記を理解したら、スケールアップして 30 または 50 の誕生日を生成する必要があります。大きなセットから同一の誕生日を分離するための推奨される手法またはアルゴリズムはありますか? それらを配列に入れてループする必要がありますか?

これが私が必要だと思うものです：

Q1)

r = 25 i.e. each trial run generates 25 birthdays

Trial 1 >
3 duplicates: 0

Trial 2 >
3 duplicates: 0

Trial 3 >
3 duplicates: 2

Trial 4 >
3 duplicates: 1

...

T100 >
3 duplicates: 2

estimated probability of 3 persons sharing a birthday in a room of 25 = (0+0+2+1+...+2)/100

Q2)

  • 2 つの複製用の配列、3 つの複製用の配列、および 3 つ以上の複製用の配列を作成します。
  • 生成された各誕生日を 1 つずつ最初の配列に追加します。ただし、そうする前に、配列をループして、既にそこにあるかどうかを確認してください。その場合、それを 2 番目の配列に追加しますが、その前に上記のプロセスを繰り返します。
  • しかし、それは非常に効率的なアルゴリズムではないようです :) ここで Big O を改善するための提案はありますか?
4

3 に答える 3

2

0 に初期化された長さ 365 の整数配列を作成します。次に、1 ～ 365 の間の N 個 (この場合は 25 個) の乱数を生成し、配列内でその数を増やします (つまり、bdays[random_value]++)。衝突の発生のみに関心があるため、配列内の数値を増やした直後に、それが 2 より大きいかどうかを確認します (2 より大きい場合は、2 回目の衝突があり、同じ誕生日の人が 3 人いることを意味します)。衝突を追跡し、これを必要な回数 (1000) 実行します。

最終的に、衝突/1000 の比率が要求された値になります。

そして、コイン投げの類推は間違っていません。

于 2011-02-15T11:21:46.227 に答える
0

最初のタスクは、ランダムな誕生日を生成するメソッドを作成することになるようです。簡単にするために、1 ～ 365 の数字を使用して一意の誕生日を表すことができます。

ただし、ランダムな誕生日 (最初のケースでは 2 つ以上) を ArrayList に文字列として格納します。ループを使用して乱数関数を呼び出し、値をリストに格納する必要があります。

次に、ArrayList で重複を検索する関数を作成します。重複がある場合 (いくつであっても)、それは Heads の結果です。一致がない場合は、Tails です。

20 程度になるまで、確率は 50/50 とは大きく異なります。

于 2011-02-14T22:39:02.190 に答える