To zadanie dotyczy pisania kodu w celu dokładnego 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 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
.
Rozważmy teraz wewnętrzną produkt A[1,...,n]
oraz B
i wewnętrzną produkt A[2,...,n+1]
i B
.
Twój kod musi przedstawiać prawdopodobieństwo, że oba produkty wewnętrzne są równe zero.
Bo n=1
to prawdopodobieństwo jest wyraźnie 1/2
.
Nie przeszkadza mi to, jak n
określono w kodzie, ale powinno być bardzo proste i oczywiste, jak to zmienić.
Języki i biblioteki
Możesz używać dowolnego języka i bibliotek, które ci się podobają. Chciałbym 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.
n
Pomocne byłyby przypadki testowe dla pierwszych kilku osób . Może też pomóc wyraźny przykład A, B i dwóch wewnętrznych produktów.n=4
liczy się ona jako zero, dwa lub trzy bajty? Czy wynik musi być dokładnie,a/b
czy[a b]
np. Byłby dozwolony?n
? W przeciwnym razie myślę, że to niedozwolone.Odpowiedzi:
Pyth,
48474644 bajtówWypróbuj online: demonstracja
Wersja online prawdopodobnie się nie oblicza
n=6
. Na moim laptopie (wersja offline) zajmuje to około 45 sekund.Podejście brutalnej siły.
Wyjaśnienie:
źródło
+0r1_2
jest krótszy niż/R2r2_2
.Mathematica,
159100878685 bajtówAby zmienić,
n
po prostu zmień definicję zmiennej na początku.Ponieważ jest brutalna, działa dość wolno, ale oto pierwsze osiem wyników:
Ostatni z nich zajął już 231 sekund, a środowisko wykonawcze jest strasznie wykładnicze.
Wyjaśnienie
Jak powiedziałem, to brutalna siła. Zasadniczo po prostu wyliczam wszystkie możliwe
A
iB
obliczam dwa produkty kropkowe dla każdej możliwej pary, a następnie znajduję ułamek par, które się wydały{0, 0}
. Kombinatoryka Mathematiki i funkcje algebry liniowej były bardzo pomocne w grze w golfa:Generuje to wszystkie n-krotki zawierające
1
lub-1
, tj. Wszystkie możliweA
. Bon = 3
to jest:Aby obliczyć
B
, robimy prawie to samo:Powtarzając
0
, duplikujemy każdą krotkę dla każdej0
jej zawartości, dzięki czemu0
prawdopodobieństwo jest dwukrotnie większe niż1
lub-1
. Ponownie używającn = 3
jako przykładu:Teraz, dla każdego możliwego
A
, chcemy iloczynu kropkowego każdego z tych możliwychB
, zarówno z, jakA[1 .. n]
iA[2 .. n+1]
. Np. Jeśli nasz prądA
jest{1, 1, -1}
, chcemy produktu kropkowego zarówno z, jak{1, 1, -1}
i z{1, -1, 1}
. Ponieważ wszystkie naszeB
są już wygodnie rzędami macierzy, chcemy, aby dwie podlistyA
były kolumnami innej macierzy, abyśmy mogli obliczyć prosty iloczyn między nimi. Ale transpozycja{{1, 1, -1}, {1, -1, 1}}
po prostu daje,{{1, 1}, {1, -1}, {-1, 1}}
co jest tylko listą wszystkich 2-elementowych cyklicznych list podrzędnychA
. Tak to działa:Obliczamy to i bierzemy produkt kropkowy z naszą listą
B
. Ponieważ otrzymujemy teraz listę zagnieżdżoną (ponieważ każdy możliwyA
daje osobny wektor), spłaszczamy je za pomocą##&@@
.Aby dowiedzieć się, czy dana para
{x, y}
jest{0, 0}
obliczana,Sign[Norm[{x,y}]]
gdzieNorm
daje√(x²+y²)
. To daje0
lub1
.Wreszcie, ponieważ teraz po prostu chcesz wiedzieć, ułamki
1
sekund na liście0
s, a1
wszystko, czego potrzebujemy jest średnią arytmetyczną z listy. Daje to jednak prawdopodobieństwo, że zarówno co najmniej jeden iloczyn punktowy będzie niezerowy, więc odejmujemy go,1
aby uzyskać pożądany wynik.źródło
Pyth -
6555 bajtówNaprawiono błąd z redukcją frakcji kosztem jednego bajtu.
Wykorzystuje podejście brutalnej siły i można grać w golfa ogromnie, ale po prostu chciałem coś tam dostać. Bardzo wolno
Używa produktów kartezjańskich do generowania obu
A
iB
, wykonując zmienne prawdopodobieństwa,0
wyświetlając się dwukrotnie na liście źródeł, a następnie zliczając te wewnętrzne iloczyny do zera. Produkt wewnętrzny ułatwiaV
cukier syntaktyczny ectorization. Uproszczenie frakcji początkowo mnie przerażało, ale było to dość łatwe dziękiP
funkcji faktoryzacji rymu i uświadomieniu sobie, że musimy zmniejszyć tylko o 2.Wypróbuj online tutaj .
źródło
n
?CJam,
5857545146 bajtówAby go uruchomić, wstaw żądaną liczbę całkowitą pomiędzy
WX]
im*
.Dzięki @ jimmy23013 za odrobinę magii i grę w golfa 5 bajtów!
Wypróbuj online w interpretatorze CJam .
Pomysł
Większość części tych odpowiedzi jest prosta, ale wykorzystuje dwie zgrabne sztuczki:
Zamiast parowania wszystkich wektorów {-1, 1} n ze wszystkimi wektorami {-1, 0, 1} nz pożądanymi prawdopodobieństwami, rozważa zliczanie liczby trojaczków wektorów w {-1, 1} n które spełniają pewien warunek.
Jeśli dodamy dwa ostatnie wektory tripletu, wynikiem będzie wektor {-2, 0, 2} n .
Ponieważ (-1) + 1 = 0 = 1 + (-1) , 0 s wystąpi dwa razy częściej niż -2 s i 2 s.
Dzielenie każdego składnika przez 2 dałoby wektor {-1, 0, 1} nz pożądanymi prawdopodobieństwami.
Ponieważ interesuje nas tylko to, czy iloczyn skalarny ma wartość 0, czy nie, możemy pominąć podział o 2 .
Po zliczeniu wszystkich trojaczków spełniających warunek pytania i całkowitej liczby trojaczków, musimy zmniejszyć wynikowy ułamek.
Zamiast obliczać GCD obu liczb, ponieważ mianownik zawsze będzie potęgą 2, wystarczy podzielić obie liczby przez najwyższą potęgę 2, która dzieli licznik.
Aby uzyskać najwyższą potęgę 2, która dzieli x , możemy wziąć bitowe AND x i ~ x + 1 .
~ x odwraca wszystkie bity x , więc wszystkie końcowe 0 s stają się 1 s. Dodając 1 do ~ x , te 1 s zamieniają się z powrotem w 0 s, a ostatnie 1 w ~ x + 1 będzie pasować do ostatniego 1 w x .
Wszystkie pozostałe bity są albo oba 0 odrębnych, tak bitowe i powrót liczby całkowitej w ostatnim 1 o X i wszystkich 0 S, które po nim następują. Jest to najwyższa potęga 2 dzieląca x .
Kod
źródło
WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__W*&:T/'/@,T/
.