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 Justinponownie), 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 wyzwaniu
• k. Jest to liczba osób (spośród n), które mają 2 życia. Ten numer zawsze obejmuje ciebie.

Więc gdybym miał funkcję pi 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) * nnastę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

MATL , 42 bajty

:<~QXJx`J`tf1Zry0*1b(-tzq]f1=vts3e8<]6L)Ym

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 ⁶ 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 6Lnależ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ć

• Ustalony rozmiar : wartość n jest ustalana z góry (a następnie N jest losowa);
• Zmienny rozmiar : n jest w locie określany na podstawie wyników symulacji.

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 ⁸ 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 =, 3e8aby 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%.

:        % Take k implicitly. Range [1 ... k]
<~       % Take n implicitly. Determine if each element in the previous array is
         % less than or equal than n
Q        % Add 1. This gives an array [2 ... 2 1 ... 1]
XJx      % Copy to clipboard J. Delete from stack
`        % Do...while. Each iteration is a Monte Carlo realization, until the 
         % desired nunber of successes is reached
  J      %   Push previously computed array [2 ... 2 1 ... 1]
  `      %   Do...while. Each iteration picks one door and decrements it, until
         %   there is only one
    t    %     Duplicate
    f    %     Indices of non-zero elements of array
    1Zr  %     Choose one of them randomly with uniform distribution
    y0*  %     Copy of array with all values set to 0
    1b(  %     Assign 1 to chosen index
    -    %     Subtract
    tzq  %     Duplicate. Number of nonzero elements minus 1. This is falsy if
         %     there was only one nonzero value; in this case the loop is exited
  ]      %   End do...while
  f1=    %   Index of chosen door. True if it was 1 (success), 0 otherwise
  v      %   Concatenate vertically to results from previous realizations
  ts3e8< %   Duplicate. Is the sum less than 3e8? If so, the loop is exited
]        % End do...while
6L)      % Remove last value (which is always 1)
Ym       % Compute mean. This gives (N-1)/(n-1). Implicitly display

Pyth, 34 bajty

Mc|!*HJ-GHch*J+*tHgGtH*gtGHKh-GHKG

Zestaw testowy

Definiuje deterministyczną zapamiętaną funkcję rekurencyjną, gprzyjmując jako argumenty n , k . g 1000 500zwraca 0.0018008560286627952w 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

@memoized
def g(n,k):
    return (not k*(n-k) or (1+(n-k)*((k-1)*g(n,k-1)+g(n-1,k)*(n-k+1)))/(n-k+1))/n

JavaScript (ES6), 65 bajtów

f=(n,k,d=n-k)=>(!d||(f(n-1,k)*++d*--d+1+(--k&&f(n,k)*k*d))/++d)/n

Nie próbuj jednak z dużymi liczbami; nawet f (30, 10) zajmuje zauważalnie dużo czasu.