Cel
Wygeneruj ( N
) losowe segmenty linii o jednakowej długości ( l
), sprawdź, czy przecinają t
równoległe linie równoodległe ( ).
Symulacja
Co symulujemy? Igła Buffona . Wygładź piasek w piaskownicy, narysuj zestaw równomiernie rozmieszczonych równoległych linii (nazwij odległość między nimi t
). Weź prosty kij długości l
i upuść go N
razy w piaskownicy. Niech liczba razy przekroczy linię c
. To Pi = (2 * l * n) / (t * c)
!
Jak to symulujemy?
- Weź wkład
N,t,l
- Z
N, t, l
wszystkich dodatnich liczb całkowitych będących - Wykonaj następujące
N
czasy:- Wygeneruj jednolicie losową współrzędną całkowitą
x,y
- Z
1 <= x, y <= 10^6
x,y
jest środkiem odcinka liniil
- Wygeneruj jednolicie losową liczbę całkowitą
a
- Z
1 <= a <= 180
- Niech
P
będzie punktem, w którym odcinek linii przecinałby oś x - To
a
jest kąt(x,y), P, (inf,0)
- Wygeneruj jednolicie losową współrzędną całkowitą
- Policz liczbę
c
segmentów linii, które przecinają linięx = i*t
dla dowolnej liczby całkowiteji
- Powrót
(2 * l * N) / (t * c)
Specyfikacja
- Wejście
- Elastyczny, przyjmuj dane wejściowe na dowolny ze standardowych sposobów (np. Parametr funkcji, STDIN) i w dowolnym standardowym formacie (np. Ciąg, Binarny)
- Wynik
- Elastyczny, daje wydruk w dowolny ze standardowych sposobów (np. Zwrot, wydruk)
- Dopuszczalne są białe pola, końcowe i białe znaki wiodące
- Dokładność, proszę podać co najmniej 4 miejsca dziesiętne dokładności (tj.
3.1416
)
- Punktacja
- Najkrótszy kod wygrywa!
Przypadki testowe
Twój wynik może się nie zgadzać z powodu losowej szansy. Ale średnio powinieneś uzyskać taką dokładność dla danej wartości N, t, l
.
Input (N,t,l) -> Output
----------- ------
10,10,5 -> ?.????
10,100,50 -> ?.????
1000,1000,600 -> 3.????
10000,1000,700 -> 3.1???
100000,1000,700 -> 3.14??
TL; DR
Wyzwania te są symulacjami algorytmów, które wymagają jedynie natury i twojego mózgu (i być może pewnych zasobów wielokrotnego użytku) do przybliżenia Pi. Jeśli naprawdę potrzebujesz Pi podczas apokalipsy zombie, te metody nie marnują amunicji ! Łącznie jest dziewięć wyzwań .
a
można również utworzyć inną metodą, jeśli jest on jednolity? (myślenie o 2D Gaussa Bubble)t > l
? Dwa poniższe rozwiązania potwierdzają to założenie, co znacznie upraszcza sprawdzanie skrzyżowania.Odpowiedzi:
R,
1131007570686765596357 bajtówJako statystyczny, funkcjonalny język programowania, nic dziwnego, że R jest dość dobrze przystosowany do tego rodzaju zadań. Fakt, że większość funkcji może przyjmować wektoryzowane dane wejściowe, jest naprawdę pomocny w tym problemie, ponieważ zamiast zapętlać
N
iteracje, po prostu omijamy wektory wielkościN
. Dzięki @Billywob za sugestie, które prowadzą do odcięcia 4 bajtów. Ogromne podziękowania dla @Primo za cierpliwe wyjaśnienie mi, w jaki sposób mój kod nie działał w przypadkacht > l
, w których jest to teraz naprawione.Wypróbuj online!
Przykładowe dane wyjściowe:
Wyjaśnienie
Problem sprowadza się do ustalenia, czy dwie
x
wartości igły znajdują się po obu stronach równoległej linii. Ma to ważne konsekwencje:y
-wartości są nieistotnex
osi jest nieistotne, jedynie położenie względem najbliższych równoległych linii.Zasadniczo jest to zadanie w przestrzeni 1-wymiarowej, w której generujemy linię o długości w [0,
l
] (kąta
określa tę długość), a następnie sprawdzamy, ile razy ta długość przekraczat
. Algorytm wstępny to:x1
wartości z [0, 1000000]. Ponieważ linie równoległe występują w każdymt
punkcie wzdłużx
osi, relatywnax
pozycja jestx
modulot
.a
.x2
pozycję na podstawiea
.x1+x2
pasujet
, tzn. Zabierz głos(x1+x2)/t
.N
Liczby próbkowania w module [0, 1e6]t
odpowiadają po prostuN
liczbom próbkowania w [0,t
]. Ponieważ(x1+x2)/t
jest to równoważnex1/t + x2/t
, pierwszy krok staje się próbkowaniem z [0,t
] /t
, tj. [0, 1]. Na szczęście dla nas jest to domyślny zakres dlarunif
funkcji R , która zwracaN
liczby rzeczywiste od 0 do 1 z jednolitego rozkładu.Powtarzamy ten krok, aby wygenerować
a
kąt igły.Liczby te są interpretowane jako pół obrotu (tj.
.5
90 stopni). (PO prosi stopni od 1 do 180, ale w komentarzach to wyjaśnić, że każdy sposób jest niedozwolone, jeśli to samo lub bardziej precyzyjnie.) Dla kątaθ
,sin(θ)
daje odległość osi x końcach igły. (Normalnie byłoby użyć cosinus na coś takiego, ale w naszym przypadku rozważamy kątθ
jako względem osi y, a nie na osi x (czyli wartość 0 stopni idzie w górę , a nie po prawej ) i dlatego używamy sinusa, który zasadniczo przesuwa fazę liczb.) Pomnożony przezl
to daje namx
lokalizację końca igły.Teraz dzielimy przez
t
i dodajemyx1
wartość. Daje(x1+x2)/t
to, jak daleko wystaje igłax1
, pod względem liczby równoległych linii. Aby uzyskać liczbę całkowitą liczby skrzyżowanych linii, bierzemy wartośćfloor
.Obliczamy sumę, dając nam liczbę,
c
ile linii przecinają igły.Reszta kodu po prostu implementuje formułę aproksymacji pi, czyli
(2*l*N)/(t*c)
. Oszczędzamy niektóre bajty w nawiasach, wykorzystując fakt, że(2*l*N)/(t*c) == 2*l*N/t/c
:A całość jest zapakowana w anonimową funkcję:
źródło
(2*l*N) => 2*l*N
?(2*l*N)/(t*c) = 2*l*N/t/c
abyś mógł zapisać kolejne dwa bajty, pomijając nawiasy również w ostatniej części.Perl, 97 bajtów
Licząc shebang jako jeden, dane wejściowe są pobierane ze standardowego wejścia, oddzielone spacją. Gdyby dozwolone były wartości losowe inne niż całkowite, mogłoby to być nieco krótsze.
Wziąłem jedną swobodę, zbliżoną do π / 180 jako 71/4068 , co odpowiada dokładności w granicach 1,48 · 10 -9 .
Przykładowe użycie
Podstawienia mniej więcej równoważne matematycznie
Zakładając, że współrzędna x reprezentuje najbardziej lewy punkt igły, a nie jej środek, jak określono w opisie problemu:
89 bajtów
Problem określa, że
x
próbka ma być pobierana jako losowa liczba całkowita. Jeśli rzutujemy odstępy między wierszami na jeden, to otrzymamy wartości formularzan/t
o0 <= n < t
niekoniecznie równomiernej, jeślit
nie zostaną równo podzielone1e6
. Zakładając, że jednakowy rozkład jest akceptowalny:76 bajtów
Pamiętaj, że ponieważ
rand
zawsze będzie mniejsza niż jeden (a zatem obcięty do zera), nie jest konieczne na początku zakresu:70 bajtów
Zakładając, że kąt igły nie musi być liczbą całkowitą, ale tylko równomiernie losowy:
59 bajtów
Zakładając, że kąt może być dowolnym rozkładem równomiernym:
52 bajty
Powyżej jest matematycznie poprawna symulacja Igła Buffona. Jednak w tym momencie myślę, że większość ludzi zgodziłaby się z tym, że nie o to właściwie pytano.
Naprawdę to popycham
Możemy po prostu wyrzucić połowę przypadków testowych, ilekroć drugi punkt końcowy znajduje się na lewo od pierwszego (zamiast zamiany):
47 bajtów
Zauważ, że wartości
t
i niel
mają znaczenia dla wyników eksperymentu. Możemy po prostu je zignorować (domyślnie zakładając, że są równe):28 bajtów
Oczywiście nie konkuruje, ale trzeba przyznać, że ma w sobie pewną elegancję.
źródło
Python 2, 141 bajtów
bezwstydny port rtumbull, już przeskakuje,
y
ponieważ zupełnie nie jest potrzebny.Problem w tym, że pi jest już znane w programie.
Tutaj jest (gra w golfa) z nieznanym pi i bez funkcji trygonometrycznych
x,y
wg
jest tylko dla kierunku.źródło
from random import randint;from math import cos,pi
. Nie powiedzie sięt < l
np1000000,1000,70000
.