Mój lokalny rozdział ACM rozdaje nagrody drzwiowe osobom, które przychodzą na spotkania. Masz jednak większą szansę na wygraną, jeśli rozwiążesz zagadkę programistyczną (ale ja zawsze rozwiązuję tę zagadkę). Dlatego niektórzy mają 1 wpis, a inni 2. Ale czekaj! Program loterii nie polega na dodawaniu innego wpisu, gdy ktoś rozwiązuje zagadkę. Zamiast tego śledzi liczbę „żyć” danej osoby, zmniejszając to, że jeśli ta osoba jest wybierana w każdym przebiegu swojego losowego algorytmu próbkowania. Działa to tak:
Doorknob: 1. xnor: 2. Justin: 2. Alex: 1. Dennis: 2.
Następnie program losowo wybiera jeden [Doorknob, xnor, Justin, Alex, Dennis]
, zmniejsza liczbę (powiedz, że wybiera Justin
):
Doorknob: 1. xnor: 2. Justin: 1. Alex: 1. Dennis: 2.
I powtarza się. Jeśli liczba „żyć” kogoś trafi do 0
(wybierzmy Justin
ponownie), zostanie usunięta z listy:
Doorknob: 1. xnor: 2. Alex: 1. Dennis: 2.
Trwa to, dopóki nie pozostanie jedna osoba; ta osoba jest zwycięzcą.
Teraz prawdziwe pytanie brzmi: jakie jest prawdopodobieństwo, że wygrałbym?
Otrzymasz dwa dane wejściowe:
n
. Jest to liczba osób biorących udział w wyzwaniuk
. Jest to liczba osób (spośródn
), które mają 2 życia. Ten numer zawsze obejmuje ciebie.
Więc gdybym miał funkcję p
i zadzwonił p(10, 5)
, to byłoby prawdopodobieństwo wygrania nagrody, w której łącznie jest 10 osób, z których 5 ma tylko 1 życie, a 5 (łącznie z tobą) ma 2 życia.
Oczekuje się, że podasz prawdopodobieństwo wygranej dokładnie lub w postaci dziesiętnej. W każdym razie, odpowiedzi muszą być dokładne do i włącznie z 4 -tego miejsca po przecinku po przecinku. To, czy zaokrąglisz tę cyfrę, zależy od ciebie.
Twoje rozwiązanie może być randomizowanym rozwiązanie, które wysyła odpowiedź do 4 -tego miejsca po przecinku z wysokim prawdopodobieństwem . Możesz założyć, że wbudowany RNG, którego używasz, jest naprawdę losowy i musi dać poprawną odpowiedź z prawdopodobieństwem co najmniej 90%.
Co więcej, twój kod musi tylko działać n, k <= 1000
, chociaż zapewniłem przypadki testowe większe niż te dla ciekawskich.
Przypadki testowe
Uwaga: niektóre z nich są formułami ogólnymi.
n, k | output
----------+---------
1, 1 | 1
2, 2 | 0.5
2, 1 | 0.75
3, 1 | 11/18 = 0.611111111
1000, 1 | 0.007485470860550352
4, 3 | 0.3052662037037037
k, k | 1/k
n, 1 | (EulerGamma + PolyGamma[1 + n])/n (* Mathematica code *)
| (γ + ψ(1 + n))/n
10, 6 | 0.14424629234373537
300, 100 | 0.007871966408910648
500, 200 | 0.004218184180294532
1000, 500 | 0.0018008560286627948
---------------------------------- Extra (not needed to be a valid answer)
5000, 601 | 0.0009518052922680399
5000, 901 | 0.0007632938197806958
W przypadku kilku kolejnych kontroli wykonaj p(n, 1) * n
następujące czynności:
n | output
------+---------
1 | 1
2 | 1.5
3 | 1.8333333333333335
10 | 2.928968253968254
100 | 5.1873775176396215
-------------------------- Extra (not needed to be a valid answer)
100000| 12.090146129863305
źródło
k
jest wyłączony o jeden)Odpowiedzi:
MATL , 42 bajty
Wykorzystuje to podejście probabilistyczne (Monte Carlo). Eksperyment jest przeprowadzany wiele razy, na podstawie których szacowane jest prawdopodobieństwo. Liczba realizacji jest wybierana w celu zapewnienia poprawności wyniku do czwartego miejsca po przecinku z prawdopodobieństwem co najmniej 90%. Jednak zajmuje to bardzo dużo czasu i dużo pamięci. W linku poniżej liczby realizacjach została zmniejszona o współczynnik 10 6 tak, że kończy się program w rozsądnym amout czasu; i gwarantowana jest dokładność tylko pierwszego miejsca po przecinku z prawdopodobieństwem co najmniej 90%.
EDYCJA (29 lipca 2016 r.): Z powodu zmian w języku
6L
należy go zastąpić3L
. Poniższy link zawiera tę modyfikację.Wypróbuj online!
tło
Niech p oznacza prawdopodobieństwo obliczenia. Eksperyment opisany w wyzwaniu zostanie uruchomiony przez liczbę N razy. Za każdym razem wygrywasz nagrodę („ sukces ”) lub nie. Niech N będzie liczbą sukcesów. Pożądane prawdopodobieństwo można oszacować na podstawie N i n . Im większa n , tym dokładniejsze będzie oszacowanie. Kluczowym pytaniem jest, jak wybrać n, aby osiągnąć pożądaną dokładność, a mianowicie, aby zapewnić, że co najmniej 90% razy błąd będzie mniejszy niż 10-4 .
Metody Monte Carlo mogą być
Wśród drugiej kategorii powszechnie stosowaną metodą jest ustalenie N (pożądanej liczby sukcesów) i kontynuowanie symulacji aż do osiągnięcia takiej liczby sukcesów . Zatem n jest losowe. Ta technika, zwana odwrotnym dwumianowym próbkowaniem lub ujemnym dwumianowym Monte Carlo , ma tę zaletę, że można ograniczyć dokładność estymatora. Z tego powodu zostanie tutaj użyty.
W szczególności, z ujemnym dwumianowym Monte Carlo x = ( N- 1) / ( n- 1) jest obiektywnym estymatorem p ; a prawdopodobieństwo, że x odbiega od p o więcej niż podany stosunek, może być ograniczone. Zgodnie z równaniem (1) w tym artykule (zauważ również, że warunki (2) są spełnione), przyjmowanie N = 2,75 · 10 8 lub więcej zapewnia, że p / x należy do przedziału [1.0001, 0.9999] z co najmniej 90% prawdopodobieństwo. W szczególności oznacza to, że x jest poprawne do czwartego miejsca po przecinku z prawdopodobieństwem co najmniej 90%, zgodnie z życzeniem.
Kod wyjaśniony
Kod używa N =,
3e8
aby zapisać jeden bajt. Pamiętaj, że wykonanie tak wielu symulacji zajęłoby dużo czasu. Kod w łączu używa N =300
, który działa w bardziej rozsądnym czasie (mniej niż 1 minuta w kompilatorze online dla pierwszych przypadków testowych); ale to tylko zapewnia, że pierwszy przecinek jest poprawny z prawdopodobieństwem co najmniej 90%.źródło
Pyth, 34 bajty
Zestaw testowy
Definiuje deterministyczną zapamiętaną funkcję rekurencyjną,
g
przyjmując jako argumenty n , k .g 1000 500
zwraca0.0018008560286627952
w ciągu około 18 sekund (nie wchodzi w skład powyższego zestawu testów, ponieważ upłynął limit czasu tłumacza online).Przybliżone tłumaczenie na Python 3 byłoby
źródło
JavaScript (ES6), 65 bajtów
Nie próbuj jednak z dużymi liczbami; nawet f (30, 10) zajmuje zauważalnie dużo czasu.
źródło