Cel
Utwórz program / funkcję, która pobiera dane wejściowe N
, sprawdź, czy N
losowe pary liczb całkowitych są względnie pierwsze, i zwraca sqrt(6 * N / #coprime)
.
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 ! Przed nami jeszcze osiem wyzwań. Zapoznaj się z postem w piaskownicy, aby uzyskać rekomendacje.
Symulacja
Co symulujemy? Prawdopodobieństwo, że dwie losowe liczby całkowite są względnie pierwsze (tj. Coprime lub gcd == 1), jest 6/Pi/Pi
więc naturalnym sposobem obliczenia Pi byłoby zgarnięcie dwóch wiader (lub garści) kamieni; Policz je; sprawdź, czy ich gcd wynosi 1; powtarzać. Po zrobieniu tego kilka razy, sqrt(6.0 * total / num_coprimes)
będzie dążył do Pi
. Jeśli obliczanie pierwiastka kwadratowego w postapokaliptycznym świecie wywołuje niepokój, nie martw się! Jest na to Metoda Newtona .
Jak to symulujemy?
- Weź wkład
N
- Wykonaj następujące
N
czasy:- Jednolicie generują losowe liczby całkowite dodatnie,
i
orazj
- Z
1 <= i , j <= 10^6
- Jeżeli
gcd(i , j) == 1
:result = 1
- Jeszcze:
result = 0
- Jednolicie generują losowe liczby całkowite dodatnie,
- Weź sumę
N
wyników,S
- Powrót
sqrt(6 * N / S)
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)
- Wydajność
- 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
.
Input -> Output
----- ------
100 -> 3.????
10000 -> 3.1???
1000000 -> 3.14??
źródło
N = 1000000
czy jest w porządku, jeśli program zwróci np. Przepełnienie stosu, jeśliN
jest zbyt duże?N=10^6
.Odpowiedzi:
APL, 23 bajty
Wyjaśnienie:
?⍵2⍴1e6
: wygeneruj macierz losowych liczb 2 na ⍵ w zakresie [1..10 6 ]1+.=∨/
: pobierz GCD każdej pary i zobacz, ile jest równych 1. To oblicza S..5*⍨6×⍵÷
: (6 × ⍵ ÷ S) 0,5źródło
Galaretka ,
20 1816 bajtów-2 bajty dzięki @ Pietu1998 (łańcuch i użycie zliczają 1 s,
ċ1
zamiast mniej niż dwóch zsumowanych<2S
)-2 bajty dzięki @Dennis (powtórz 1e6 wiele razy przed próbkowaniem, aby uniknąć łączenia)
(Niezwykle wolny z powodu funkcji losowej)
W jaki sposób?
TryItOnline
źródło
ḤRµȷ6Xµ€g2/ċ1÷³6÷½
oszczędza 2 bajty. (ȷ6
ma 10 ^ 6 w jednym niladzie,ċ1
liczy się jeden)ȷ²
jest trochę trochę szybszy niżȷ6
)ȷ²
bycie dwoma linkami nie szkodzi tutaj, ale wymagałoby dodatkowego linku lub¤
w niektórych przypadkachḤȷ6xX€
powinien działać dla losowego próbkowania.Python 2,
143140132124122124122 bajtówMinęło sporo czasu, odkąd próbowałem grać w golfa, więc mogłem coś przegapić! Będę aktualizować w miarę skracania tego.
Przetestuj mnie tutaj!
dzięki Jonathanowi Allanowi za dwubajtowe zapisanie :)
źródło
1 <= i , j <= 10^6
więc musisz użyćrandrange(1,1e6+1)
.k=lambda:r.randrange(1e6)+1
oszczędza dwa bajtyMathematica,
494851 bajtówZapisano jeden bajt i naprawiono jeden błąd dzięki @ LegionMammal978 .
źródło
(6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&
1*^6
powinny zostać zastąpione{1,1*^6}
, aby upewnić się, że ja , j ≠ 0.R,
1039995999894 bajtówPrawdopodobnie można go trochę pograć w golfa. Zmniejsz 4 bajty z powodu @ antoine-sac i kolejne 4 bajty, definiując alias dla
sample
, używając^.5
zamiastsqrt
, i1e6
zamiast10^6
. Dodano 4 bajty, aby zapewnić, że próbkowaniei
ij
jest naprawdę jednolite. Usunięto jeden bajt po tym, jak zorientowałem się, że6*N/sum(x)
jest taki sam jak6/mean(x)
. Używanypryr::f
zamiastfunction(x,y)
do zapisania 4 bajtów.Przykładowe dane wyjściowe:
źródło
sample(10^6,N)
. Jest nie tylko krótszy, ale także znacznie bardziej wydajny.sample(10,10)
gwarantowane jest zwrócenie wszystkich liczb w skali 1:10, podczas gdysample(10,10,T)
spowoduje losowy wybór, w którym liczby mogą się powtarzać.Właściwie 19 bajtów
Wypróbuj online!
Wyjaśnienie:
źródło
MATL , 22 bajty
Wypróbuj online!
źródło
Pyth, 21 bajtów
Wypróbuj online.
Wyjaśnienie
źródło
Scala,
149126 bajtówWyjaśnienie:
źródło
6f
,Seq.fill
imath.random
.Rakieta 92 bajty
Nie golfowany:
Testowanie:
Wynik:
źródło
JavaScript (ES7),
1079594 bajtówWersja ES6 ma dokładnie 99 bajtów, ale operator potęgowania ES7
**
oszczędza 5 bajtówMath.sqrt
.Bez golfa
źródło
gcd
wywołuje funkcjęg
r=_=>
czy to kod czy rysunek?n=>(n*6/(r=_=>Math.random()*1e6,g=(a,b)=>b?g(b,a%b):a>-2,q=n=>n&&g(~r(),~r())+q(n-1))(n))**.5
1B krótszyn=>(n*6/(q=_=>n--&&q(r=_=>Math.random()*1e6)+g(~r(),~r()))(g=(a,b)=>b?g(b,a%b):a>-2))**.5
PHP,
827774 bajtyUruchom tak:
Wyjaśnienie
Robi to, co jest napisane na puszce. Wymaga PHP_GMP dla
gcd
.Poprawki
$argn
źródło
Perl, 64 bajty
Wymaga opcji wiersza poleceń
-pMntheory=gcd
, liczonej jako 13. Dane wejściowe są pobierane ze standardowego wejścia.Przykładowe użycie
źródło
R, 94 bajty
Stosunkowo wolny, ale nadal działa. Replikuj N razy funkcję, która pobiera 2 liczby losowe (od 1 do 1e6) i sprawdza, czy ich gcd jest mniejsza niż 2 (przy użyciu mojej starej funkcji gcd ).
źródło
1:x
zadziała.PowerShell v2 +,
118114 bajtówPobiera dane wejściowe
$n
, uruchamiafor
pętlę, aż będzie$k
równa$n
(domyślna$k=0
przy pierwszym wejściu do pętli). Każda iteracja, otrzymuj noweRandom
liczby$i
i$j
( flaga-mi
nimum1
gwarantuje, że jesteśmy>=1
i żadna maksymalna flaga nie pozwala na[int]::MaxValue
, co jest dozwolone przez PO, ponieważ jest większe niż10e6
).Następnie wchodzimy w pętlę GCD
while
. Następnie, tak długo jak GCD jest1
,$o
zwiększa się. Na końcufor
pętli wykonujemy proste[math]::Sqrt()
wywołanie, które zostaje w potoku, a dane wyjściowe są niejawne.Uruchomienie z wejściem
10000
na moim ~ 1-letnim laptopie Core i5 zajmuje około 15 minut .Przykłady
źródło
Java 8,
164151 bajtówWyjaśnienie
Uprząż testowa
Aktualizacja
źródło
n
,t+=1
może staćt++
, można skondensowaćint
deklaracji w jednej linii, to znaczyint c=n,t=0,x,y;
, i!=0
(chyba) może stać>0
. To powinno zaoszczędzić 12 bajtów ogółem. Jest to jednak fajny sposób na znalezienie GCD xiy.Perl 6 ,
5653 bajtówWypróbuj online!
źródło
Frink,
8489Mam szczęście: g = n = ... zapisuje bajt nad g = 0 n = ... ; a 1% gcd () daje (0,1) vs (1,0), więc mogę odjąć. I pecha: n jest wstępnie przypisane i stosowane, ponieważ zmienne pętlowe i ich granice są lokalne i niezdefiniowana poza pętlą.
Gadatliwy
źródło
AWK , 109 bajtów
Wypróbuj online!
Dziwi mnie, że działa w rozsądnym czasie na 1000000.
źródło
Pyt ,
3735 bajtówWyjaśnienie:
źródło
J, 27 bajtów
Wyjaśnienie:
Dostaliśmy bardzo szczęśliwy z
3.14157
zaN = 10000000
, które odbyło2.44
sekund.źródło
Japt , 23 bajty
Spróbuj
źródło