Latar Belakang

The paradoks ulang tahun adalah masalah populer dalam teori probabilitas yang menentang matematika intuisi (kebanyakan orang). Pernyataan masalah adalah:

Mengingat N orang, berapa probabilitas bahwa setidaknya dua dari mereka memiliki hari ulang tahun yang sama (mengabaikan tahun).

Masalahnya biasanya disederhanakan dengan mengabaikan hari kabisat sepenuhnya. Dalam hal ini, jawaban untuk N = 23 adalah P (23) ≈ 0,5072972 (sebagai contoh umum). Artikel Wikipedia yang terhubung menjelaskan cara mencapai kemungkinan ini. Atau, video Numberphile ini melakukan pekerjaan yang sangat baik.

Namun, untuk tantangan ini kami ingin melakukannya dengan benar dan tidak mengabaikan tahun kabisat. Ini sedikit lebih rumit, karena sekarang tanggal 29 Februari perlu ditambahkan, tetapi ulang tahun khusus ini lebih kecil daripada semua yang lainnya.

Kami juga akan menggunakan aturan tahun kabisat penuh :

• Jika satu tahun dapat dibagi 400 maka ini adalah tahun kabisat.
• Atau, jika satu tahun dapat dibagi 100, itu bukan tahun kabisat.
• Lain, jika satu tahun dapat dibagi dengan 4 itu adalah tahun kabisat.
• Lain, ini bukan tahun kabisat.

Bingung? Ini berarti bahwa tahun 1700, 1800, 1900, 2100, 2200, 2300 bukan tahun kabisat, tetapi 1600, 2000, 2400 adalah (dan juga tahun lainnya yang dapat dibagi 4). Kalender ini berulang setiap 400 tahun, dan kami akan mengasumsikan distribusi ulang tahun yang seragam selama 400 tahun tersebut.

Hasil yang dikoreksi untuk N = 23 sekarang P (23) ≈ 0,5068761 .

Tantangan

Diberikan bilangan bulat 1 ≤ N < 100, tentukan probabilitas bahwa di antara Norang setidaknya dua memiliki ulang tahun yang sama dengan pertimbangan aturan tahun kabisat. Hasilnya harus berupa angka titik mengambang atau titik tetap, akurat hingga setidaknya 6 tempat desimal. Dapat diterima untuk memotong nol yang tertinggal.

Anda dapat menulis program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan output hasilnya melalui STDOUT (atau alternatif terdekat), nilai fungsi kembali atau parameter fungsi (keluar).

Solusi Anda harus dapat menghasilkan output untuk semua 99 input dalam hitungan detik. Ini terutama untuk mengesampingkan metode Monte Carlo dengan banyak sampel, jadi jika Anda menggunakan algoritma yang terutama cepat dan tepat dalam bahasa esoterik yang sangat lambat, saya bersedia memberikan kelonggaran pada aturan ini.

Uji Kasus

Berikut adalah tabel lengkap hasil:

 1 => 0.000000
 2 => 0.002737
 3 => 0.008195
 4 => 0.016337
 5 => 0.027104
 6 => 0.040416
 7 => 0.056171
 8 => 0.074251
 9 => 0.094518
10 => 0.116818
11 => 0.140987
12 => 0.166844
13 => 0.194203
14 => 0.222869
15 => 0.252642
16 => 0.283319
17 => 0.314698
18 => 0.346578
19 => 0.378764
20 => 0.411063
21 => 0.443296
22 => 0.475287
23 => 0.506876
24 => 0.537913
25 => 0.568260
26 => 0.597796
27 => 0.626412
28 => 0.654014
29 => 0.680524
30 => 0.705877
31 => 0.730022
32 => 0.752924
33 => 0.774560
34 => 0.794917
35 => 0.813998
36 => 0.831812
37 => 0.848381
38 => 0.863732
39 => 0.877901
40 => 0.890932
41 => 0.902870
42 => 0.913767
43 => 0.923678
44 => 0.932658
45 => 0.940766
46 => 0.948060
47 => 0.954598
48 => 0.960437
49 => 0.965634
50 => 0.970242
51 => 0.974313
52 => 0.977898
53 => 0.981043
54 => 0.983792
55 => 0.986187
56 => 0.988266
57 => 0.990064
58 => 0.991614
59 => 0.992945
60 => 0.994084
61 => 0.995055
62 => 0.995880
63 => 0.996579
64 => 0.997169
65 => 0.997665
66 => 0.998080
67 => 0.998427
68 => 0.998715
69 => 0.998954
70 => 0.999152
71 => 0.999314
72 => 0.999447
73 => 0.999556
74 => 0.999645
75 => 0.999717
76 => 0.999775
77 => 0.999822
78 => 0.999859
79 => 0.999889
80 => 0.999913
81 => 0.999932
82 => 0.999947
83 => 0.999959
84 => 0.999968
85 => 0.999976
86 => 0.999981
87 => 0.999986
88 => 0.999989
89 => 0.999992
90 => 0.999994
91 => 0.999995
92 => 0.999996
93 => 0.999997
94 => 0.999998
95 => 0.999999
96 => 0.999999
97 => 0.999999
98 => 0.999999
99 => 1.000000

(Tentu saja, P (99) hanya 1,0 karena pembulatan. Probabilitasnya tidak akan mencapai 1,0 hingga P (367) .)

Pyth, 31 34 byte

Jt.2425K366-1c.xX0rK-KQ*JQ^+KJQ

Demonstrasi , Test Harness

Ini bekerja mirip dengan versi lama, kecuali bahwa alih-alih secara terpisah menghasilkan nilai (366 + n * (.2425 - 1)) dan mengalikannya, itu dimulai dengan membuat daftar yang memanjang dari 366 hingga 365 - n + 2, kemudian memodifikasi 366 di tempat menjadi (366 + n * (.2425 - 1)), dan kemudian mengambil produk dari daftar. Juga, konstanta 366 dan -.7575 digunakan sebagai pengganti 365 dan .2425.

Versi lama:

Pyth, 34 byte

J.2425K365-1c*+hK*QtJ.xrK-hKQ^+KJQ

Ada dua cara yang memungkinkan untuk tidak ada pasangan orang dengan ulang tahun yang sama: setiap orang memiliki ulang tahun yang berbeda, dan tidak ada yang memiliki ulang tahun pada tanggal 29 Februari, dan seseorang yang memiliki ulang tahun pada tanggal 29, dan setiap orang yang berbeda memiliki ulang tahun pada hari-hari normal.

Peluang terjadinya pertama adalah (365 * 364 * ... 365 - n + 1) / (365.2425 ^ n).

Peluang terjadinya kedua adalah (365 * 364 * ... 365 - n + 2) * .2425 * n / (365.2425 ^ n)

Ini dapat ditulis bersama sebagai (365 * 364 * ... 365 - n + 2) * (365 - n + 1 + .2425 * n) / (365.2425 ^ n) = (365 * 364 * ... 365 - n + 2) * (365 + 1 + (.2425 - 1) * n) / (365.2425 ^ n).

Ini adalah probabilitas tanpa pasangan, sehingga probabilitas setidaknya satu pasangan adalah satu minus angka di atas.

J = .2425
K = 365
.xrK-hKQ = (365 * 364 * ... 365 - n + 2)
+hK*QtJ = (365 + 1 + n * (.2425 - 1))
^+KJQ = (365.2425 ^ n)

Python, 179 178 144 143 140 136 135 133

f=.2425
g=365+f
a=lambda n:(n and(365-n)*a(n-1)or 365)/g
b=lambda n:(n<2and f or(367-n)*b(n-1)+a(n-2)*f)/g
p=lambda n:1-a(n-1)-b(n)

p(n)memberikan hasilnya. Ubah .2425untuk fractions.Fraction(97,400)mendapatkan hasil yang tepat.

Python 155 153 151 142 140 bytes

d=146097
b=d/400
c=97/d
e=lambda n:n<2and 1-97/d or e(n-1)*(366-n)/b
f=lambda n:n<2and c or f(n-1)*(367-n)/b+e(n-1)*c
a=lambda n:1-e(n)-f(n)

Panggil a(n)hasilnya. Untuk hasil yang tepat, bungkus ddalam pecahan.

Tes di sini

Menggunakan teknik yang sama seperti di sini , tetapi dengan konstanta yang dimodifikasi.

80386 kode mesin, 43 byte

Hexdump kode:

68 75 6e 33 3b 68 5a eb 07 3b 8b c4 49 d9 e8 d9
e8 d8 00 d9 e8 d9 40 04 de ea d8 c9 d9 00 de eb
e2 f3 d8 ca d9 e8 d8 e1 58 58 c3

Saya mulai dari rumus berikut (untuk probabilitas komplementer):

( d = 366 * 400 - 303ini adalah jumlah hari dalam 400 tahun)

Berikut ini adalah kode c ++ yang mengimplementasikannya (sudah sedikit dioptimalkan):

double it_opt(int k)
{
    double d = 366 * 400 - 303; // number of days in 400 years
    double result = 1; // probability of no coincidences
    const float const1 = float(400 / d);
    const float const2 = float(303 / d);
    double v1 = 1 + const2;
    double v2 = 1;

    for (int i = 0; i < k - 1; ++i)
    {
        v1 -= const1;
        result *= v1;
        v2 -= const2;
    }
    result *= v2;
    return 1 - result;
}

Kode diatur sehingga memerlukan jumlah minimum konstanta - hanya dua (400 / d dan 303 / d). Saya menggunakan floattipe untuk mewakili mereka karena menempati lebih sedikit ruang (4 byte per konstan). Selain itu, saya tidak ingin mengalikan const2dengan k - 1(karena itu akan memerlukan konversi k - 1ke float); kode itu mengurangi const2berulang kali sebagai gantinya.

Berikut adalah daftar bahasa majelis:

    ; // fastcall convention - parameter k is in ecx
    ; // result must be returned in st
    push dword ptr 0x3b336e75; // const1 = [esp + 4]
    push dword ptr 0x3b07eb5a; // const2 = [esp]
    mov eax, esp;              // use [eax] instead of [esp] - 1 byte less
    dec ecx;                   // calculate k - 1
    fld1;                      // initiaze result = 1
    fld1;                      // initialize v1
    fadd [eax];
    fld1;                      // initialilze v2
myloop:
    fld dword ptr [eax + 4];
    fsubp st(2), st;            // update v1
    fmul st, st(1);             // update result
    fld dword ptr [eax];
    fsubp st(3), st;            // update v2
    loop myloop;                // loop
    fmul st, st(2);             // update result by v2
    fld1;
    fsub st, st(1);             // complement result
    pop eax;                    // restore stack
    pop eax;                    // restore stack
    ret;                        // return