fundo
O paradoxo do aniversário é um problema popular na teoria da probabilidade que desafia a intuição matemática (da maioria das pessoas). A declaração do problema é:
Dadas as pessoas N , qual é a probabilidade de que pelo menos duas delas tenham o mesmo aniversário (independentemente do ano).
O problema geralmente é simplificado ignorando completamente os dias bissextos. Nesse caso, a resposta para N = 23 é P (23) ± 0,5072972 (como um exemplo comum). O artigo vinculado da Wikipedia explica como chegar a essa probabilidade. Como alternativa, este vídeo do Numberphile faz um bom trabalho.
No entanto, para esse desafio, queremos fazer o certo e não ignorar os anos bissextos. Isso é um pouco mais complicado, pois agora é necessário adicionar o dia 29 de fevereiro, mas esse aniversário em particular é menos provável que todos os outros.
Também usaremos as regras do ano bissexto completo :
- Se um ano é divisível por 400, é um ano bissexto.
- Senão, se um ano é divisível por 100, não é um ano bissexto.
- Senão, se um ano é divisível por 4, é um ano bissexto.
- Senão, não é um ano bissexto.
Confuso? Isso significa que os anos 1700, 1800, 1900, 2100, 2200, 2300 não são bissextos, mas 1600, 2000, 2400 são (assim como qualquer outro ano divisível por 4). Esse calendário se repete a cada 400 anos, e assumiremos uma distribuição uniforme de aniversários nesses 400 anos.
O resultado corrigido para N = 23 agora é P (23) ± 0,5068761 .
O desafio
Dado um número inteiro 1 ≤ N < 100
, determine a probabilidade de que, entre as N
pessoas, pelo menos duas tenham o mesmo aniversário, considerando as regras do ano bissexto. O resultado deve ser um número de ponto flutuante ou de ponto fixo, com precisão de pelo menos 6 casas decimais. É aceitável truncar zeros à direita.
Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e gerar o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).
Sua solução deve ser capaz de produzir saída para todas as 99 entradas em questão de segundos. Isso é principalmente para descartar os métodos de Monte Carlo com toneladas de amostras, por isso, se você estiver usando um algoritmo principalmente rápido e exato em uma linguagem esotérica excessivamente lenta, estou disposto a dar margem a essa regra.
Casos de teste
Aqui está a tabela completa de resultados:
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
(É claro que P (99) é apenas 1,0 devido ao arredondamento. A probabilidade não alcançará exatamente 1,0 até P (367) .)
fonte
Respostas:
Pitão, 31
34bytesDemonstração , Arnês de Teste
Isso funciona de maneira semelhante à versão antiga, exceto que, em vez de gerar separadamente o valor (366 + n * (.2425 - 1)) e multiplicá-lo, ele começa gerando uma lista que se estende de 366 a 365 - n + 2, depois modifica o 366 no lugar para se tornar (366 + n * (0,2425 - 1)) e, em seguida, pega o produto da lista. Além disso, as constantes 366 e -.7575 são usadas em vez de 365 e .2425.
Versão antiga:
Pitão, 34 bytes
Existem duas maneiras possíveis de não haver um par de pessoas com o mesmo aniversário: todo mundo para ter aniversários diferentes, e ninguém tem um aniversário em 29 de fevereiro, e alguém para fazer um aniversário no dia 29, e todo mundo para ter um aniversário diferente. aniversários em dias normais.
A probabilidade da primeira ocorrência é (365 * 364 * ... 365 - n + 1) / (365,2425 ^ n).
A probabilidade da segunda ocorrência é (365 * 364 * ... 365 - n + 2) * .2425 * n / (365.2425 ^ n)
Estes podem ser escritos juntos como (365 * 364 * ... 365 - n + 2) * (365 - n + 1 + .2425 * n) / (365,2425 ^ n) = (365 * 364 * ... 365 - n + 2) * (365 + 1 + (0,2425 - 1) * n) / (365,2425 ^ n).
Essa é a probabilidade de não haver pares; portanto, a probabilidade de pelo menos um par é um menos o número acima.
fonte
Python,
179178144143140136135133p(n)
dá o resultado. Mude.2425
parafractions.Fraction(97,400)
para obter um resultado exato.fonte
2
eand
.1/
parag
e dividir por ele em vez disso?e=365
e substituir 365 por e e 367 por e + 2Python
155153151142140 bytesLigue
a(n)
para o resultado. Para resultados exatos, envolvad
em uma fração.Teste aqui
Usa a mesma técnica que aqui , mas com constantes modificadas.
fonte
2
eand
.Código da máquina 80386, 43 bytes
Hexdump do código:
Comecei da seguinte fórmula (para a probabilidade complementar):
(aqui
d = 366 * 400 - 303
é o número de dias em 400 anos)Aqui está o código c ++ que o implementa (já está otimizado um pouco):
O código é organizado de forma que exija o número mínimo de constantes - apenas duas (
400 / d
e303 / d
). Eu uso ofloat
tipo para representá-los porque ocupa menos espaço (4 bytes por constante). Além disso, não queria multiplicarconst2
pork - 1
(porque isso exigiria a conversãok - 1
parafloat
); o código subtraiconst2
repetidamente.Aqui está a lista da linguagem assembly:
fonte