birthday paradox

Dzień dobry,
mam problem z paradoksem z tytułu, wynik powinien być 23 a wychodzi 24-25, wie ktoś może w czym może być problem? Pętelka:

int main()
{
    srand(time(0));
    int licznik = 0;
    for (int i = 0; i < 100000; i++)
    {
        bool dzienUrodzin[365] = { 0 };
        while (true)
        {
            licznik++;
            int los = ((rand() % 364));
            if (dzienUrodzin[los])
                break;
            dzienUrodzin[los] = true;
        }
    }
    std::cout << licznik / 100000.0;
}

informacje o paradoksie: https://pl.wikipedia.org/wiki/Paradoks_dnia_urodzin

Wydaje mi się że nie ma nigdzie błędu ( prosty kod ) ale wynik nie jest taki jak powinien być : d Z góry dziękuję za pomoc : D

Nie patrząc na sam algorytm, powinieneś raczej mieć rand() % 365.

Uwielbiam jak ludzie nadają nazwę paradoks, czemuś co wcale paradoksem nie jest.

Nie ja wymyślałem nazwę : D, losujemy od 0 do 364 czyli 365 wartości dlatego jest 365 : ), jak wkleicie ten kod to też wychodzi Wam ~25? Nie wiedzę w nim błędu a powinno wyjść 23 : d

@Samiec Alfa: ile Twoim zdaniem wynosi 364 % 364? ;-)
Albo inaczej: dla jakiego n spełnione będzie n % 364 = 364? (podpowiedź: dla żadnego, czyli obcinasz sobie jeden dzień z obliczeń)

Dobra przekonałeś mnie : D ale to nie rozwiązuję problemu, nadal jest błędna wartość, może coś przeoczyłem ?

Zmień inta na double.

przy wyświetlaniu mam zmiane:

std::cout << licznik / 100000.0;
 

Ktoś ma jakiś pomysł dlaczego wynik jest błędny ?

Mam wrażenie, że nie to liczysz co chcesz. Napisałem dwa programy:
Pierwszy program liczy przy której wylosowanej dacie następuje pierwsze powtórzenie, robiłem 10000 testów, wyniki były zawsze między 24 a 25, przypuszczam, że Twój program (którego nie chcę mi się analizować) liczy to samo.
Drugi program losuje 1000 razy i dat (15<=i<=30) i wyświetla stosunek w_ilu_losowaniach_się_powtórzyło/1000. Wyniki są zgodne z teorią.

        int tests = 1000;
        int duplicate = 0;
        HashSet<Integer> days = new HashSet<Integer>();
        for(int i=15;i<=30;i++)
        {
            duplicate = 0;
            for(int j=0;j<tests;j++)
            {
                days.clear();
                for(int k=0;k<i;k++)
                {
                    days.add(r.nextInt(365));
                }
                if(days.size() < i)
                {
                    duplicate++;
                }
            }
            System.out.println("i = " + i + " frequency = " + duplicate/(float)tests);
    `code>`
i = 15 frequency = 0.246
i = 16 frequency = 0.273
i = 17 frequency = 0.325
i = 18 frequency = 0.372
i = 19 frequency = 0.386
i = 20 frequency = 0.393
i = 21 frequency = 0.463
i = 22 frequency = 0.481
i = 23 frequency = 0.513
i = 24 frequency = 0.536
i = 25 frequency = 0.549
i = 26 frequency = 0.602
i = 27 frequency = 0.642
i = 28 frequency = 0.641
i = 29 frequency = 0.705
i = 30 frequency = 0.709

bogdans napisał(a):

Mam wrażenie, że nie to liczysz co chcesz. Napisałem dwa programy:
Pierwszy program liczy przy której wylosowanej dacie następuje pierwsze powtórzenie, robiłem 10000 testów, wyniki były zawsze między 24 a 25, przypuszczam, że Twój program (którego nie chcę mi się analizować) liczy to samo.
Drugi program losuje 1000 razy i dat (15<=i<=30) i wyświetla stosunek w_ilu_losowaniach_się_powtórzyło/1000. Wyniki są zgodne z teorią.

        int tests = 1000;
        int duplicate = 0;
        HashSet<Integer> days = new HashSet<Integer>();
        for(int i=15;i<=30;i++)
        {
            duplicate = 0;
            for(int j=0;j<tests;j++)
            {
                days.clear();
                for(int k=0;k<i;k++)
                {
                    days.add(r.nextInt(365));
                }
                if(days.size() < i)
                {
                    duplicate++;
                }
            }
            System.out.println("i = " + i + " frequency = " + duplicate/(float)tests);
    `code>`
i = 15 frequency = 0.246
i = 16 frequency = 0.273
i = 17 frequency = 0.325
i = 18 frequency = 0.372
i = 19 frequency = 0.386
i = 20 frequency = 0.393
i = 21 frequency = 0.463
i = 22 frequency = 0.481
i = 23 frequency = 0.513
i = 24 frequency = 0.536
i = 25 frequency = 0.549
i = 26 frequency = 0.602
i = 27 frequency = 0.642
i = 28 frequency = 0.641
i = 29 frequency = 0.705
i = 30 frequency = 0.709

No to mam takie same wyniki jak Ty w tym pierwszym programie- pomiędzy 24 a 25 ale czy statystycznie nie powinno wyjść 23 ?

Przy deklaracji zmiennej bool dzienUrodzin dodałeś sobie o jeden dzień za dużo, dlatego wychodzi ci że statystycznie liczba osób o które trzeba przejść by dostać ten sam dzień urodzin wychodzi 24 z kawałkiem a nie 23 z kawałkiem, zmień linię 7 z bool dzienUrodzin[365] = { 0 }; na bool dzienUrodzin[364] = {0}. Ogólnie były dwa błędy z nietrzymaniem się prawidłowej ilości dni, jeden zauważył patryk27 a drugi to ten zauważony przeze mnie. Powinno działać, sprawdzałem na C::B, wychodzi coś koło 23.6.

ale czy statystycznie nie powinno wyjść 23 ?
Nie, pierwszy program liczy coś zupełnie innego. W błąd wprowadziło Cię podobieństwo wyników (23 vs. 24-25).

czaffik napisał(a):

Przy deklaracji zmiennej bool dzienUrodzin dodałeś sobie o jeden dzień za dużo, dlatego wychodzi ci że statystycznie liczba osób o które trzeba przejść by dostać ten sam dzień urodzin wychodzi 24 z kawałkiem a nie 23 z kawałkiem, zmień linię 7 z bool dzienUrodzin[365] = { 0 }; na bool dzienUrodzin[364] = {0}. Ogólnie były dwa błędy z nietrzymaniem się prawidłowej ilości dni, jeden zauważył patryk27 a drugi to ten zauważony przeze mnie. Powinno działać, sprawdzałem na C::B, wychodzi coś koło 23.6.

Dlaczego dał sobie 1 dzień za dużo? Skąd wzięło Ci się 364?

Bo tablica jest iterowana od zera, w konsekwencji zapis bool dzienUrodzin[365]oznacza że masz 366 elementów w tej tablicy.

czaffik napisał(a):

Bo tablica jest iterowana od zera, w konsekwencji zapis bool dzienUrodzin[365]oznacza że masz 366 elementów w tej tablicy.

Może doczytaj sobie o tablicach.

Dobra, pomyliło mi się, wydaje mi się jeszcze że jakbyś zwiększył liczbę iteracji z 1000000 na większą wartość to coś powinno pomóc, ale przy większych wartość komp mi się muli.

W tym wątku zostały pomieszane dwie wielkości. Losujemy ze zbioru zawierającego n elementów (np. z 365-elementowego zbioru dat).
Pierwsza wielkość, to średnia liczba losowań potrzebnych by jakaś data się powtórzyła.
Druga wielkość, to liczba osób w grupie, która gwarantuje, że z prawdopodobieństwem przekraczającym 0,5 data urodzin się powtarza.
Te wielkości można pomylić, bo są zbliżone.
''długość roku (w dniach) średnia liczba losowań wymagana liczba osób
6 3,77 4 (dni w roku można zastąpić rzutami kostki)
100 13,18 12
365 24,52 23
500 28,37 27
1000 40,58 39
5000 89,53 83
10000 126,82 118
20000 178,07 167''