Cel

Wygeneruj ( N) losowe segmenty linii o jednakowej długości ( l), sprawdź, czy przecinają tró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 li upuść go Nrazy 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, lwszystkich dodatnich liczb całkowitych będących
• Wykonaj następujące Nczasy:
  • Wygeneruj jednolicie losową współrzędną całkowitą x,y
  • Z 1 <= x, y <= 10^6
  • x,y jest środkiem odcinka linii l
  • Wygeneruj jednolicie losową liczbę całkowitą a
  • Z 1 <= a <= 180
  • Niech Pbędzie punktem, w którym odcinek linii przecinałby oś x
  • To ajest kąt(x,y), P, (inf,0)
• Policz liczbę csegmentów linii, które przecinają linię x = i*tdla 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ń .

R, 113 100 75 70 68 67 65 59 63 57 bajtów

Jako 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ć Niteracje, po prostu omijamy wektory wielkości N. 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 przypadkach t > l, w których jest to teraz naprawione.

pryr::f(2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t)))

Wypróbuj online!

Przykładowe dane wyjściowe:

N=1000, t=1000, l=500
3.037975

N=10000, t=1000, l=700
3.11943

N=100000, t=1000, l=700
3.140351

Wyjaśnienie

Problem sprowadza się do ustalenia, czy dwie xwartości igły znajdują się po obu stronach równoległej linii. Ma to ważne konsekwencje:

1. y-wartości są nieistotne
2. Bezwzględne położenie na xosi 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ąt aokreśla tę długość), a następnie sprawdzamy, ile razy ta długość przekracza t. Algorytm wstępny to:

1. Przykładowe x1wartości z [0, 1000000]. Ponieważ linie równoległe występują w każdym tpunkcie wzdłuż xosi, relatywna xpozycja jest xmodulo t.
2. Próbuj kąt a.
3. Oblicz x2pozycję na podstawie a.
4. Sprawdź, ile razy x1+x2pasuje t, tzn. Zabierz głos (x1+x2)/t.

NLiczby próbkowania w module [0, 1e6] todpowiadają po prostu Nliczbom próbkowania w [0, t]. Ponieważ (x1+x2)/tjest to równoważne x1/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 dla runiffunkcji R , która zwraca Nliczby rzeczywiste od 0 do 1 z jednolitego rozkładu.

                          runif(N)

Powtarzamy ten krok, aby wygenerować akąt igły.

                                         runif(N)

Liczby te są interpretowane jako pół obrotu (tj. .590 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 przez lto daje nam xlokalizację końca igły.

                                   sinpi(runif(N))*l

Teraz dzielimy przez ti dodajemy x1wartość. Daje (x1+x2)/tto, jak daleko wystaje igła x1, pod względem liczby równoległych linii. Aby uzyskać liczbę całkowitą liczby skrzyżowanych linii, bierzemy wartość floor.

                    floor(runif(N)+sinpi(runif(N))*l/t)

Obliczamy sumę, dając nam liczbę, cile linii przecinają igły.

                sum(floor(runif(N)+sinpi(runif(N))*l/t))

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:

        2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t))

A całość jest zapakowana w anonimową funkcję:

pryr::f(2*l*N/t/sum(floor(runif(N)+sinpi(runif(N))*l/t)))

Perl, 97 bajtów

#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=(1+~~rand 1e6)/$&)-$a..$x+($a=$'/$&/2*sin~~rand(180)*71/4068)-1}1..$_

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

$ echo 1000000 1000 70000 | perl pi-sand.pl
3.14115345174061

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

#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=(1+~~rand 1e6)/$&)..$x+($'/$&*sin~~rand(180)*71/4068)-1}1..$_

Problem określa, że xpróbka ma być pobierana jako losowa liczba całkowita. Jeśli rzutujemy odstępy między wierszami na jeden, to otrzymamy wartości formularza n/to 0 <= n < tniekoniecznie równomiernej, jeśli tnie zostaną równo podzielone 1e6. Zakładając, że jednakowy rozkład jest akceptowalny:

76 bajtów

#!perl -p
/ \d+/;$_*=2*$'/$&/map{($x=rand)..$x+($'/$&*sin~~rand(180)*71/4068)-1}1..$_

Pamiętaj, że ponieważ randzawsze będzie mniejsza niż jeden (a zatem obcięty do zera), nie jest konieczne na początku zakresu:

70 bajtów

#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+($'/$&*sin~~rand(180)*71/4068)}1..$_

Zakładając, że kąt igły nie musi być liczbą całkowitą, ale tylko równomiernie losowy:

59 bajtów

#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+abs$'/$&*sin rand$`}1..$_

Zakładając, że kąt może być dowolnym rozkładem równomiernym:

52 bajty

#!perl -p
/ \d+/;$_*=2*$'/$&/map{1..(rand)+abs$'/$&*sin}1..$_

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

#!perl -p
/ \d+/;$_*=$'/$&/map{1..(rand)+$'/$&*sin}1..$_

Zauważ, że wartości ti nie lmają znaczenia dla wyników eksperymentu. Możemy po prostu je zignorować (domyślnie zakładając, że są równe):

28 bajtów

#!perl -p
$_/=map{1..(rand)+sin}1..$_

Oczywiście nie konkuruje, ale trzeba przyznać, że ma w sobie pewną elegancję.

Python 2, 141 bajtów

bezwstydny port rtumbull, już przeskakuje, yponieważ zupełnie nie jest potrzebny.

from math import*
from random import*
lambda N,t,l:(2.*l*N)/(t*sum(randint(1,1e6)%t+abs(cos(randint(1,180)*pi/180))*l>t for _ in range(N)))

Problem w tym, że pi jest już znane w programie.

Tutaj jest (gra w golfa) z nieznanym pi i bez funkcji trygonometrycznych

def g(N,t,l):
 c=0
 for _ in range(N):
    x,y=gauss(0,1),gauss(0,1);c+=randint(1,1e6)%t+abs(x/sqrt(x*x+y*y))*l>t
 return(2.*l*N)/(t*c)

x,yw gjest tylko dla kierunku.