Prawdopodobieństwa nokautowe

Knockout to gra w koszykówkę, w której gracze na zmianę strzelają. Rozgrywka jest sekwencją dwóch graczy, z których każdy ma możliwość „znokautowania” jednego z tych graczy.

Załóżmy, że gracze mają odpowiednio A B C Dswoje szanse na strzelanie i zrobienie kosza 0.1 0.2 0.3 0.4, niezależnie od drugiego gracza biorącego udział w konkursie. Dwóch graczy z przodu linii Ai B„walczyć”. Ponieważ Aidzie pierwszy, jest on obrońcą , grozi wyeliminowane, a Bto napastnik , a nie w niebezpieczeństwie natychmiastowej eliminacji. Anajpierw strzela. Jeśli Ato zrobi, Askutecznie się bronił i idzie na koniec linii. Linia zmieni się na B C D A. Jeśli się Anie uda , to Bstrzela. Jeśli Bto zrobi, wtedy Ajest na zewnątrz i Bprzechodzi na koniec linii, więc linia staje się C D B. Jeśli nieAnie Bczyni go powtórzenia procesu, ze Astrzelanie ponownie, dopóki albo Aczy Bsprawia kosz.

Załóżmy, że linia zmieniła się na B C D A( Audało się obronić). Teraz Bi C„walcz”, Bbędąc obrońcą i Catakującym. Ten proces powtarza się, aż pozostanie tylko jedna osoba. Ta osoba jest zwycięzcą.

Twoim zadaniem jest obliczenie prawdopodobieństwa wygranej przez każdą osobę, biorąc pod uwagę szansę, że zrobi ona koszyk.

Wejście :

Lista liczb, takich jak 0.1 0.2lub 0.5 0.5 0.5 0.5, gdzie n- ta liczba to szansa, że n- ty gracz zrobi koszyk. Możesz wziąć to wejście w dowolnym formacie, w tym jako parametrach funkcji.

Wyjście :

Lista liczb, gdzie n- ta liczba to szansa, że n- ty gracz wygra grę. Twoje liczby muszą być dokładne z dokładnością do co najmniej dwóch miejsc po przecinku przez co najmniej 90% czasu. Oznacza to, że możesz zastosować podejście oparte na symulacji. Jeśli jednak kod nie jest oparty na symulacji ( gwarantuje poprawną odpowiedź co najmniej 6 miejsc po przecinku), odejmij 30% od wyniku.

Przykład pomiędzy 0.5 0.5: Zadzwoń do graczy Ai B. Niech pbędzie prawdopodobieństwo wygranej A. Ama 2/3szansę na skuteczną obronę (ponieważ istnieje 1/2szansa, że Azdobędzie punkty, 1/4szansa, że Anie trafi i Bzdobędzie punkty, a także 1/4szansa, że ​​zarówno nie trafi , jak i proces się powtórzy). Jeśli się Anie obroni, zostaje znokautowany i Bwygrywa. Jeśli się Abroni, linia staje się B A. Ponieważ sytuacja jest symetryczna, prawdopodobieństwo Awygranej jest (1 - p). Otrzymujemy:

p = 2/3 * (1 - p) + 1/3 * 0. Dostajemy rozwiązanie p = 2/5. Dane wyjściowe powinny być 2/5 3/5lub 0.4 0.6.

Z prawdopodobieństwem nie jestem w stanie zrobić bardziej złożonych przykładów.

Jeśli potrzebujesz więcej przypadków testowych, oto kilka:

0.1 0.2 0.3 0.4 --> 0.01 0.12 0.25 0.62
0.99 0.99 --> 0.5 0.5 (it's not exact, but if you round to two decimal places, you get 0.5 and 0.5)

CJam ( 84 80 znaków * 0,7 = 56)

{_,({_,,{_2$m<(;(+Q0\)\++m>\}%)_(+.{X2$-*_@+/}1\{1$*\1$-}%)1\-f/.f*:.+}{,da}?}:Q

Demo online . Jest to funkcja rekurencyjna, która pobiera tablicę podwójnych i zwraca tablicę podwójnych. Demo online zawiera niewielką ilość rusztowań, aby wykonać funkcję i sformatować dane wyjściowe do wyświetlenia.

Sekcja

Podstawową zasadą jest to, że jeśli n > 1pozostali gracze, jeden z nich musi być kolejnym, który zostanie znokautowany. Co więcej, kolejność kolejki po tym zdarzeniu zależy tylko od początkowej kolejności kolejki i od tego, kto zostanie znokautowany. Możemy więc wykonywać nrekurencyjne połączenia, obliczyć prawdopodobieństwo wygranej dla każdego gracza w każdym przypadku, a następnie musimy odpowiednio odpowiednio zważyć i dodać.

Oznaczę prawdopodobieństwa wejściowe jako [p_0 p_1 ... p_{n-1}]. Niech f(a,b)oznacza prawdopodobieństwo, przed którym się anie obroni b. W każdej rundzie, prawdopodobieństwo, że abroni sukcesem jest p_a, że prawdopodobieństwo buderzenia aOUT (1-p_a)*p_b, a prawdopodobieństwo, że udaje się do innego rundy (1-p_a)*(1-p_b). Możemy albo dokonać wyraźnej sumy postępu geometrycznego, albo możemy argumentować, że dwa postępy geometryczne są proporcjonalne względem siebie, aby to uzasadnić f(a,b) = (1-p_a)*p_b / (p_a + (1-p_a)*p_b).

Następnie możemy zwiększyć poziom do pełnych rund linii. Prawdopodobieństwo, że pierwszy gracz zostanie powalony, jest f(0,1); prawdopodobieństwo, że drugi gracz zostanie powalony, jest (1-f(0,1)) * f(1,2); trzecim graczem jest (1-f(0,1)) * (1-f(1,2)) * f(2,3); itd., aż ostatni zostanie znokautowany z prawdopodobieństwem \prod_i (1-f(i,i+1)) * f(n-1,0). Ten sam argument na temat postępów geometrycznych pozwala nam wykorzystywać te prawdopodobieństwa jako wagi, z normalizacją współczynnik 1 / \prod_i f(i, i+1 mod n).

{                   e# Define a recursive function Q
  _,({              e# If we have more than one person left in the line...
    _,,{            e#   Map each i from 0 to n-1...
      _2$m<         e#     Rotate a copy of the probabilities left i times to get [p_i p_{i+1} ... p_{n-1} p_0 ... p_{i-1}]
      (;(+          e#     i fails to defend, leaving the line as [p_{i+2} ... p_{n-1} p_0 ... p_{i-1} p_{i+1}]
      Q             e#     Recursive call
      0\)\++        e#     Insert 0 for the probability of i winning and fix up the order
      m>\           e#     Rotate right i times and push under the list of probabilities
    }%
    )               e#   Stack: [probs if 0 knocked out, probs if 1 knocked out, ...] [p_0 p_1 ...]
    _(+.{           e#   Duplicate probs, rotate 1, and pointwise map block which calculates f(a,b)
      X2$-*_@+/     e#     f(a,b) = (1-p_a)*p_b / (p_a + (1-p_a)*p_b)  TODO is the d necessary?
    }
    1\{1$*\1$-}%    e#   Lift over the list of f(a,b) a cumulative product to get the weights  TODO is the d necessary?
    )1\-f/          e#   Normalise the weights
    .f*             e#   Pointwise map a multiplication of the probabilities for each case with the corresponding weight
    :.+             e#   Add the weights across the cases
  }{,da}?           e# ...else only one left, so return [1.0]
}:Q