0

そこで、同じ部屋にいる大勢の人が同じ誕生日になる確率を作成するプログラムを作成しようとしています...関数の作成方法がわかりません。これが私がこれまでに持っているものです

def birthday():
    mySet = set()
    x = 1
    for item in mySet:
        if item in mySet:
            return x
        else:
            mySet().append() # don't know what to do here.

編集:

さて、私が達成しようとしているのは、1 から 365 までの数字を使用して誕生日を格納するセットを使用して関数を作成することです...たとえば、30 人の部屋をランダムに選択すると、同じ誕生日ではない可能性があります。ただし、同じ部屋に双子がいる場合、同じ部屋にいるのは2人だけで同じ誕生日になります. したがって、最終的には、この関数を数回テストし、すべてを平均化するパラメーターが必要です。残念ながら、私はこれを作る方法を理解できません。x を部屋にいる人数のカウンターにしたいのですが、一致するとループが停止し、停止します。また、何を追加すればよいかわかりません。

4

1 に答える 1

1

この問題に対して閉じた形式のソリューションを使用するのではなく、これをシミュレートしようとしている理由はありますか? 高速で簡単にコーディングできる、かなりまともな近似があります。

import math
def closed_form_approx_birthday_collision_probability(num_people):
    return 1 - math.exp(-num_people * (num_people - 1) / (2 * 365.0))

非常に優れた「正確な」ソリューションを実装することもできます(フロートに変換すると忠実度が失われるため、引用符で囲みます):

import operator
import functools
import fractions
def slow_fac(n):
    return functools.reduce(operator.mul, range(2, n+1), 1)

def closed_form_exact_birthday_collision_probability(num_people):
    p_no_collision = fractions.Fraction(slow_fac(365), 365 ** num_people * slow_fac(365 - num_people))
    return float(1 - p_no_collision)

シミュレーションを行うには、次のようにします。セットではなくリストを使用しているのは、可能性の数が少なく、これにより、セットを使用する場合に発生する余分な作業が回避されるためです。

import random
def birthday_collision_simulate_once(num_people):
    s = [False] * 365
    for _ in range(num_people):
        birthday = random.randint(0, 364)
        if s[birthday]:
            return True
        else:
            s[birthday] = True
    return False

def birthday_collision_simulation(num_people, runs):
    collisions = 0
    for _ in range(runs):
        if birthday_collision_simulate_once(num_people):
            collisions += 1
    return collisions / float(runs)

シミュレーションとクローズド フォーム ソリューションから得た数値は、 http://en.wikipedia.org/wiki/Birthday_problemの表に似ています。

>>> closed_form_approx_birthday_collision_probability(20)
0.40580512747932584
>>> closed_form_exact_birthday_collision_probability(20)
0.41143838358058
>>> birthday_collision_simulation(20, 100000)
0.41108

もちろん、多くの実行を行ったシミュレーションは実際の 41.1% に近く、計算ははるかに遅くなります。必要な精度に応じて、閉じた形式のソリューションのいずれかを選択します。

于 2013-10-24T01:05:05.063 に答える