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/8ale raczej 1/2.

Dla pewnej dodatniej liczby całkowitej n, rozważ jednolicie losowy ciąg 1s i -1s długości ni nazwij ją A. Teraz połączmy się do Ajej pierwszej wartości. To znaczy, A[1] = A[n+1]jeśli indeksowanie od 1. Ama teraz długość n+1. Teraz rozważ także drugi losowy ciąg długości, nktórego pierwsze nwartoś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 Ai Bmogą być A = [-1,1,1,-1]i B=[0,1,-1]. W tym przypadku dwoma produktami wewnętrznymi są 0i 2.

Rozważmy teraz wewnętrzną produkt A[1,...,n]oraz Bi 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=1to prawdopodobieństwo jest wyraźnie 1/2.

Nie przeszkadza mi to, jak nokreś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.

Pyth, 48 47 46 44 bajtów

K,smlf!|Fms*Vd.>Tk2^,1_1Q^+0tM3Q^8Qj\//RiFKK

Wypró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:

smlf!|Fms*Vd.>Tk2^,1_1Q^+0tM3Q   implicit: Q = input number
                          tM3    the list [-1, 0, 1]
                        +0       add zero, results in [0, -1, 0, 1]
                       ^     Q   all possible lists of length Q using these elements
 m                               map each list d (B in Lembik's notation) to:
                  ,1_1              the list [1, -1]
                 ^    Q             all possible lists of length Q
   f                                filter for lists T (A in Lembik's notation),
                                    which satisfy:
       m        2                      map each k in [0, 1] to:
        s*Vd.>Tk                          scalar-product d*(shifted T by k)
    !|F                                not or (True if both scalar-products are 0)      
  l                                 determine the length                
s                                add all possibilities at the end

K,...^8QQj\//RiFKK   
 ,...^8Q             the list [result of above, 8^Q]
K                    store it in K
              iFK    determine the gcd of the numbers in K
            /R   K   divide the numbers in K by the gcd
         j\/         join the two numbers by "/" and print

Mathematica, 159 100 87 86 85 bajtów

n=3;1-Mean@Sign[##&@@Norm/@({1,0,0,-1}~t~n.Partition[#,2,1,1])&/@{1,-1}~(t=Tuples)~n]

Aby zmienić, npo prostu zmień definicję zmiennej na początku.

Ponieważ jest brutalna, działa dość wolno, ale oto pierwsze osiem wyników:

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

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 Ai Bobliczam 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:

{1,-1}~(t=Tuples)~n

Generuje to wszystkie n-krotki zawierające 1lub -1, tj. Wszystkie możliwe A. Bo n = 3to jest:

{{1, 1, 1}, 
 {1, 1, -1}, 
 {1, -1, 1}, 
 {1, -1, -1}, 
 {-1, 1, 1}, 
 {-1, 1, -1}, 
 {-1, -1, 1}, 
 {-1, -1, -1}}

Aby obliczyć B, robimy prawie to samo:

{1,0,0,-1}~t~n

Powtarzając 0, duplikujemy każdą krotkę dla każdej 0jej zawartości, dzięki czemu 0prawdopodobieństwo jest dwukrotnie większe niż 1lub -1. Ponownie używając n = 3jako przykładu:

{{-1, -1, -1},
 {-1, -1, 0}, {-1, -1, 0},
 {-1, -1, 1},
 {-1, 0, -1}, {-1, 0, -1},
 {-1, 0, 0}, {-1, 0, 0}, {-1, 0, 0}, {-1, 0, 0},
 {-1, 0, 1}, {-1, 0, 1},
 {-1, 1, -1},
 {-1, 1, 0}, {-1, 1, 0},
 {-1, 1, 1},
 {0, -1, -1}, {0, -1, -1},
 {0, -1, 0}, {0, -1, 0}, {0, -1, 0}, {0, -1, 0},
 {0, -1, 1}, {0, -1, 1},
 {0, 0, -1}, {0, 0, -1}, {0, 0, -1}, {0, 0, -1},
 {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0},
 {0, 0, 1}, {0, 0, 1}, {0, 0, 1}, {0, 0, 1},
 {0, 1, -1}, {0, 1, -1},
 {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0},
 {0, 1, 1}, {0, 1, 1},
 {1, -1, -1},
 {1, -1, 0}, {1, -1, 0},
 {1, -1, 1},
 {1, 0, -1}, {1, 0, -1},
 {1, 0, 0}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0},
 {1, 0, 1}, {1, 0, 1},
 {1, 1, -1},
 {1, 1, 0}, {1, 1, 0},
 {1, 1, 1}}

Teraz, dla każdego możliwego A, chcemy iloczynu kropkowego każdego z tych możliwych B, zarówno z, jak A[1 .. n]i A[2 .. n+1]. Np. Jeśli nasz prąd Ajest {1, 1, -1}, chcemy produktu kropkowego zarówno z, jak {1, 1, -1}i z {1, -1, 1}. Ponieważ wszystkie nasze Bsą już wygodnie rzędami macierzy, chcemy, aby dwie podlisty Abył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ędnych A. Tak to działa:

Partition[#,2,1,1]

Obliczamy to i bierzemy produkt kropkowy z naszą listą B. Ponieważ otrzymujemy teraz listę zagnieżdżoną (ponieważ każdy możliwy Adaje osobny wektor), spłaszczamy je za pomocą ##&@@.

Aby dowiedzieć się, czy dana para {x, y}jest {0, 0}obliczana, Sign[Norm[{x,y}]] gdzie Normdaje √(x²+y²). To daje 0lub 1.

Wreszcie, ponieważ teraz po prostu chcesz wiedzieć, ułamki 1sekund na liście 0s, a 1wszystko, 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, 1aby uzyskać pożądany wynik.

Pyth - 65 55 bajtów

Naprawiono 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

*F-KP/Jmms*Vked,thdPhd*makhk^,1_1Q^[1ZZ_1)Q,ZZ2/lJ^2/K2

Używa produktów kartezjańskich do generowania obu Ai B, wykonując zmienne prawdopodobieństwa, 0wyświetlając się dwukrotnie na liście źródeł, a następnie zliczając te wewnętrzne iloczyny do zera. Produkt wewnętrzny ułatwia Vcukier syntaktyczny ectorization. Uproszczenie frakcji początkowo mnie przerażało, ale było to dość łatwe dzięki Pfunkcji faktoryzacji rymu i uświadomieniu sobie, że musimy zmniejszyć tylko o 2.

Wypróbuj online tutaj .

CJam, 58 57 54 51 46 bajtów

WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__~)&:T/'/@,T/

Aby go uruchomić, wstaw żądaną liczbę całkowitą pomiędzy WX]i m*.

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} ⁿ ze wszystkimi wektorami {-1, 0, 1} ^nz pożądanymi prawdopodobieństwami, rozważa zliczanie liczby trojaczków wektorów w {-1, 1} ⁿ które spełniają pewien warunek.

  Jeśli dodamy dwa ostatnie wektory tripletu, wynikiem będzie wektor {-2, 0, 2} ⁿ .

  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

WX]    e# Push the array [-1 1].
       e# Insert N here.
m*     e# Cartesian product: Push the array of all vectors of {-1,1}^N.
Zm*    e# Cartesian product: Push the array of all triplets of these vectors.
_      e# Copy the array.
{      e# Filter; for each triplet of vectors U, V and W in {-1,1}^N:
  ~    e#   Dump U, V and W on the stack.
  .+   e#   Compute X := V + W, a vector of {-2,0,2}^N, where each component is
       e#   zero with probability 1/2.
  2,@  e#   Push [0 1]. Rotate U on top of it.
  fm<  e#   Push [U U'], where U' is U rotated one dimension to the left.
  \f.* e#   Push [U*X and U'*X], where * denotes the vectorized product.
  ::+  e#   Add the components of both products.
  0-   e#   Remove zeroes.
       e#   Push the logical NOT of the array.
},     e#   If the array was empty, keep the triplet.
,      e# Push X, the length of the filtered array.
__~)&  e# Push X & ~X + 1.
:T     e# Save the result in T and divide X by T.
'/     e# Push a slash.
@,T/   e# Dividet he length of the unfiltered array by T.