[To jest pytanie partnera, aby dokładnie obliczyć prawdopodobieństwo ]
To zadanie dotyczy pisania kodu w celu dokładnego i szybkiego obliczenia prawdopodobieństwa . Wynik powinien być precyzyjnym prawdopodobieństwem zapisanym jako ułamek w najbardziej zredukowanej formie. Oznacza to, że nigdy nie powinien generować, 4/8
ale raczej 1/2
.
Dla pewnej dodatniej liczby całkowitej n
, rozważ jednolicie losowy ciąg 1s i -1s długości n
i nazwij ją A. Teraz połączmy się do A
jej pierwszej wartości. To znaczy, A[1] = A[n+1]
jeśli indeksowanie od 1. A
ma teraz długość n+1
. Teraz rozważ także drugi losowy ciąg długości, n
którego pierwsze n
wartości to -1, 0 lub 1 z prawdopodobieństwem 1 / 4,1 / 2, 1/4 każdy i nazwij go B.
Rozważmy teraz wewnętrzną produkt A[1,...,n]
oraz B
i wewnętrzną produkt A[2,...,n+1]
i B
.
Rozważmy na przykład n=3
. Możliwe wartości A
i B
mogą być A = [-1,1,1,-1]
i B=[0,1,-1]
. W tym przypadku dwoma produktami wewnętrznymi są 0
i 2
.
Twój kod musi przedstawiać prawdopodobieństwo, że oba produkty wewnętrzne są równe zero.
Kopiując tabelę wyprodukowaną przez Martina Büttnera otrzymaliśmy następujące przykładowe wyniki.
n P(n)
1 1/2
2 3/8
3 7/32
4 89/512
5 269/2048
6 903/8192
7 3035/32768
8 169801/2097152
Języki i biblioteki
Możesz korzystać z dowolnego darmowego języka i bibliotek, które ci się podobają. Muszę być w stanie uruchomić Twój kod, więc proszę podać pełne wyjaśnienie, jak uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe.
Zadanie
Twój kod musi zaczynać się od n=1
i dawać poprawne dane wyjściowe dla każdego rosnącego nw osobnej linii. Powinno się zatrzymać po 10 sekundach.
Wynik
Wynik jest po prostu najwyższy n
osiągnięty, zanim kod przestanie działać po 10 sekundach od uruchomienia na moim komputerze. W przypadku remisu zwycięzca najszybciej zdobędzie najwyższy wynik.
Tabela wpisów
n = 64
w Pythonie . Wersja 1 autorstwa Mitcha Schwartzan = 106
w Pythonie . Wersja z 11 czerwca 2015 r. Autor: Mitch Schwartzn = 151
w C ++ . Odpowiedź Port of Mitch Schwartz autorstwa kirbyfan64sosn = 165
w Pythonie . Wersja 11 czerwca 2015 r. W wersji „przycinanie” autorstwa Mitcha Schwartza zN_MAX = 165
.n = 945
w Pythonie przez Min_25 przy użyciu dokładnej formuły. Niesamowity!n = 1228
w Pythonie autorstwa Mitcha Schwartza przy użyciu innej dokładnej formuły (na podstawie poprzedniej odpowiedzi Min_25).n = 2761
w Pythonie autorstwa Mitcha Schwartza przy użyciu szybszej implementacji tej samej dokładnej formuły.n = 3250
w Pythonie przy użyciu Pypy autorstwa Mitcha Schwartza przy użyciu tej samej implementacji. Ten wynik musipypy MitchSchwartz-faster.py |tail
unikać przewijania konsoli nad głową.
źródło
Odpowiedzi:
Pyton
Formuła zamknięta
p(n)
toWykładnicza funkcja generująca
p(n)
jestgdzie
I_0(x)
jest zmodyfikowana funkcja Bessela pierwszego rodzaju.Edytuj w dniu 2015-06-11:
- zaktualizowałem kod Python.
Edytuj w dniu 13.06.2015 r .:
- dodano dowód powyższej formuły.
- naprawiono
time_limit
.- dodano kod PARI / GP.
Pyton
PARI / GP
Dowód:
ten problem jest podobny do problemu dwuwymiarowego (ograniczonego) losowego chodzenia.
Jeśli
A[i] = A[i+1]
można przejść od(x, y)
się(x+1, y+1)
[1], sposobem(x, y)
[2] lub sposoby(x-1, y-1)
[1] sposobem.Jeśli
A[i] != A[i+1]
można przejść od(x, y)
się(x-1, y+1)
[1], sposobem(x, y)
[2] lub sposoby(x+1, y-1)
[1] sposobem.Pozwól
a(n, m) = [x^m]((x+1)^n + (x-1)^n)
,b(n) = [x^n](1+x)^{2n}
ic(n)
jest wiele sposobów, aby przejść od(0, 0)
do(0, 0)
zn
etapów.Następnie,
c(n) = \sum_{i=0}^n a(n, i) * b(i) * b(n-i).
Ponieważ
p(n) = c(n) / 8^n
możemy uzyskać powyższą formułę zamkniętą.źródło
Pyton
Uwaga: gratulacje dla Min_25 za znalezienie rozwiązania w formie zamkniętej!
Dzięki za interesujący problem! Można to rozwiązać za pomocą DP, chociaż nie mam obecnie dużej motywacji do optymalizacji prędkości, aby uzyskać wyższy wynik. Przydałoby się golfa.
Kod osiągnął
N=39
w ciągu 10 sekund na starym laptopie z Pythonem 2.7.5.Dla krotki
(a,b,s,t)
:a
jest pierwszym elementemA
,b
jest ostatnim elementemB
,s
jest wewnętrznym produktemA[:-1]
iB
, it
jest wewnętrznym produktemA[1:-1]
iB[:-1]
przy użyciu notacji plastra Python. Mój kod nie przechowuje tablicA
aniB
nigdzie, więc używam tych liter, aby odwoływać się odpowiednio do kolejnych elementów, które zostaną dodane doA
iB
. Ten wybór nazw zmiennych sprawia, że wyjaśnienie jest trochę niewygodne, ale pozwala na ładny wyglądA*b+a*B
samego kodu. Zauważ, że dodawany elementA
jest przedostatni, ponieważ ostatni element jest zawsze taki sam jak pierwszy. Wykorzystałem sztuczkę Martina Büttnera polegającą na włączeniu się0
dwukrotnieB
kandydaci w celu uzyskania właściwego rozkładu prawdopodobieństwa. SłownikX
(który został nazwanyY
przezN+1
) śledzi liczby wszystkich możliwych tablic według wartości krotki. Zmiennen
id
oznaczają licznik i mianownik, dlatego przemianowałem nazwęn
zadania na asN
.Kluczową częścią logiki jest to, że można zaktualizować z
N
doN+1
korzystania tylko wartości w krotce. Dwa wewnętrzne produkty określone w pytaniu są podane przezs+A*B
it+A*b+a*B
. Jest to jasne, jeśli przyjrzysz się nieco definicjom; pamiętać, że[A,a]
i[b,B]
są dwa ostatnie elementy tablicA
iB
odpowiednio.Zauważ, że
s
it
są małe i ograniczone zgodnie zN
, a dla szybkiej implementacji w szybkim języku możemy uniknąć słowników na korzyść tablic.Możliwe jest wykorzystanie symetrii, biorąc pod uwagę wartości różniące się tylko znakiem; Nie przyjrzałem się temu.
Uwaga 1 : Rozmiar słownika rośnie kwadratowo
N
, gdzie rozmiar oznacza liczbę par klucz-wartość.Uwaga 2 : Jeśli ustawimy górną granicę
N
, możemy przycinać krotki dla którychN_MAX - N <= |s|
i podobnie dlat
. Można tego dokonać, określając stan pochłaniania lub pośrednio za pomocą zmiennej, która przechowuje liczbę przyciętych stanów (które trzeba będzie pomnożyć przez 8 przy każdej iteracji).Aktualizacja : ta wersja jest szybsza:
Wdrożone optymalizacje:
main()
- dostęp do zmiennych lokalnych jest szybszy niż globalnyN=1
jawnie obsługuj, aby uniknąć sprawdzania(1,-1) if N else [a]
(co wymusza spójność pierwszego elementu w krotce podczas dodawania elementów doA
rozpoczynania od pustej listy)c
dodawania0
doB
zamiast wykonywania tych operacji dwukrotnie8^N
więc nie musimy go śledzićA
, jak1
i podzielić przez mianownik2
, ponieważ prawidłowych połączeń(A,B)
zA[1]=1
i teA[1]=-1
mogą być wprowadzane do korespondencji jeden-do-jednego przez zaprzeczenieA
. Podobnie możemy naprawić pierwszy elementB
jako nieujemny.N_MAX
aby zobaczyć, jaki wynik może uzyskać na twoim komputerze. Może być przepisany, aby znaleźć odpowiedniN_MAX
automatycznie przez wyszukiwanie binarne, ale wydaje się niepotrzebny? Uwaga: nie musimy sprawdzać stanu przycinania przed dotarciem dookołaN_MAX / 2
, więc możemy uzyskać niewielkie przyspieszenie poprzez iterację w dwóch fazach, ale zdecydowałem się tego nie robić dla uproszczenia i czystości kodu.źródło
N=57
pierwszą wersję iN=75
drugą.Pyton
Korzystając z pomysłu losowego marszu Min_25, udało mi się dojść do innej formuły:
Oto implementacja Pythona oparta na Min_25:
Wyjaśnienie / dowód:
Najpierw rozwiązujemy powiązany problem liczenia, na który zezwalamy
A[n+1] = -A[1]
; to znaczy dodatkowy element połączonyA
może być1
lub-1
niezależnie od pierwszego elementu. Nie musimy więc śledzić, ile razyA[i] = A[i+1]
ma miejsce. Mamy następujący losowy spacer:Z
(x,y)
możemy przejść do(x+1,y+1)
[1 sposób],(x+1,y-1)
[1 sposób],(x-1,y+1)
[1 sposób],(x-1,y-1)
[1 sposób],(x,y)
[4 sposoby]gdzie
x
iy
stanąć na dwóch iloczyn skalarny i liczymy ilość sposobów, aby przejść od(0,0)
do(0,0)
wn
krokach. Liczba ta zostanie następnie pomnożona przez,2
aby uwzględnić fakt, żeA
można zacząć od1
lub-1
.Odnosimy się do pobytu w
(x,y)
postaci zerowym ruchu .Powtarzamy liczbę niezerowych ruchów
i
, które muszą być równe, aby wrócić do(0,0)
. Ruchy poziome i pionowe tworzą dwa niezależne jednowymiarowe losowe spacery, które można policzyćC(i,i/2)^2
, gdzieC(n,k)
jest współczynnikiem dwumianowym. (W przypadku marszu zk
krokami w lewo ik
krokami w prawo istniejąC(2k,k)
sposoby wyboru kolejności kroków.) Ponadto istniejąC(n,i)
sposoby umieszczania ruchów i4^(n-i)
sposoby wybierania ruchów zerowych. Otrzymujemy więc:Teraz musimy wrócić do pierwotnego problemu. Zdefiniuj dopuszczalną parę,
(A,B)
która ma być zamieniana, jeśliB
zawiera zero. Zdefiniuj parę,(A,B)
która będzie prawie dopuszczalna, jeśliA[n+1] = -A[1]
i dwa produkty kropkowe są równe zero.Lemat: W danym
n
przypadku prawie dopuszczalne pary są w korespondencji jeden-do-jednego z parami wymiennymi.Możemy (odwracalnie) przekonwertować parę konwertowalną
(A,B)
na prawie dopuszczalną parę(A',B')
, negującA[m+1:]
iB[m+1:]
, gdziem
jest indeks ostatniego zera wB
. Sprawdzenie tego jest proste: jeśli ostatnim elementemB
jest zero, nie musimy nic robić. W przeciwnym razie, gdy negujemy ostatni elementA
, możemy zanegować ostatni elementB
, aby zachować ostatni składnik iloczynu z przesuniętą kropką. Ale to neguje ostatnią wartość nie przesuniętego produktu kropkowego, więc naprawiamy to, negując element przedostatniA
. Ale wtedy to odrzuca ostatnią wartość przesuniętego produktu, więc negujemy element przedostatniB
. I tak dalej, aż do osiągnięcia zerowego elementu wB
.Teraz musimy tylko pokazać, że nie ma prawie dopuszczalnych par, dla których
B
nie ma zera. Aby iloczyn punktowy był równy zeru, musimy mieć taką samą liczbę1
i-1
warunki do anulowania. Każdy-1
termin składa się z(1,-1)
lub(-1,1)
. Zatem parzystość liczby takich-1
zdarzeń jest ustalona zgodnie zn
. Jeśli pierwszy i ostatni elementA
mają różne znaki, zmieniamy parzystość, więc jest to niemożliwe.Więc rozumiemy
co daje powyższą formułę (ponowne indeksowanie za pomocą
i' = i/2
).Aktualizacja: Oto szybsza wersja korzystająca z tej samej formuły:
Wdrożone optymalizacje:
p(n)
C(n,k)
zk <= n/2
źródło
p(n)
że nie musi to być funkcja fragmentaryczna. Ogólnie rzecz biorąc, jeślif(n) == {g(n) : n is odd; h(n) : n is even}
możesz napisaćf(n) == (n-2*floor(n/2))*g(n) + ((n+1)-2*(floor((n+1)/2)))*h(n)
lub użyćn mod 2
zamiast(n-2*floor(n/2))
. Zobacz tutajWyjaśnienie wzoru Min_25
Min_25 opublikował świetny dowód, ale jego wykonanie zajęło trochę czasu. To jest trochę wyjaśnienia do wypełnienia między wierszami.
a (n, m) reprezentuje liczbę sposobów wyboru A, tak że A [i] = A [i + 1] m razy. Wzór na a (n, m) jest równoważny a (n, m) = {2 * (n wybierz m) dla nm nawet; 0 dla nm nieparzyste.} Dopuszczalna jest tylko jedna parzystość, ponieważ A [i]! = A [i + 1] musi wystąpić parzystą liczbę razy, aby A [0] = A [n]. Współczynnik 2 wynika z początkowego wyboru A [0] = 1 lub A [0] = -1.
Po ustaleniu liczby (A [i]! = A [i + 1]) na q (nazwanej i we wzorze c (n)), dzieli się ona na dwa losowe spacery 1D o długości q i nq. b (m) to liczba sposobów na wykonanie jednowymiarowego losowego spaceru m kroków, który kończy się w tym samym miejscu, w którym zaczął, i ma 25% szansy na ruch w lewo, 50% szansy na pozostanie w bezruchu i 25% szansy na poruszać się w prawo. Bardziej oczywistym sposobem określenia funkcji generowania jest [x ^ m] (1 + 2x + x ^ 2) ^ n, gdzie 1, 2x i x ^ 2 oznaczają odpowiednio lewą, brak ruchu i prawą. Ale potem 1 + 2x + x ^ 2 = (x + 1) ^ 2.
źródło
C ++
Tylko część (doskonałej) odpowiedzi Pythona autorstwa Mitcha Schwartza. Podstawową różnicą jest to, że użyłem
2
do reprezentowania-1
dlaa
zmiennej i zrobił coś podobnego dob
, który pozwolił mi używać tablicy.-O3
Używam Intel C ++ z , mamN=141
! Moja pierwsza wersja maN=140
.To używa wzmocnienia. Próbowałem wersji równoległej, ale miałem problemy.
źródło
g++ -O3 kirbyfan64sos.cpp -o kirbyfan64sos -lboost_system -lboost_timer -lboost_chrono -lrt -lgmp
się skompilować. (Dzięki aditsu.)