Tor
Erstellen Sie ein Programm / eine Funktion, die eine Eingabe akzeptiert N
, prüfen Sie, ob N
zufällige Paare von Ganzzahlen relativ prim sind, und geben Sie zurück sqrt(6 * N / #coprime)
.
TL; DR
Diese Herausforderungen sind Simulationen von Algorithmen, für die nur die Natur und Ihr Gehirn (und möglicherweise einige wiederverwendbare Ressourcen) erforderlich sind, um sich dem Pi anzunähern. Wenn Sie Pi während der Zombie-Apokalypse wirklich brauchen, verschwenden diese Methoden keine Munition ! Es gibt noch acht weitere Herausforderungen. Überprüfen Sie den Sandbox-Post , um Empfehlungen abzugeben .
Simulation
Was simulieren wir? Nun, die Wahrscheinlichkeit, dass zwei zufällige ganze Zahlen relativ prim (dh coprime oder gcd == 1) sind 6/Pi/Pi
, ist so, dass ein natürlicher Weg, um Pi zu berechnen, darin besteht, zwei Eimer (oder eine Handvoll) Steine zu schöpfen; zähle sie; sehen, ob ihr gcd 1 ist; wiederholen. Nachdem Sie dies einige Male getan haben, sqrt(6.0 * total / num_coprimes)
tendieren Sie dazu Pi
. Wenn die Berechnung der Quadratwurzel in der postapokalyptischen Welt Sie nervös macht, machen Sie sich keine Sorgen! Dafür gibt es Newtons Methode .
Wie simulieren wir das?
- Eingaben übernehmen
N
- Mach die folgenden
N
Zeiten:- Einheitlich zufällige positive ganze Zahlen erzeugen,
i
undj
- Mit
1 <= i , j <= 10^6
- Wenn
gcd(i , j) == 1
:result = 1
- Sonst:
result = 0
- Einheitlich zufällige positive ganze Zahlen erzeugen,
- Nehmen Sie die Summe der
N
Ergebnisse,S
- Rückkehr
sqrt(6 * N / S)
Spezifikation
- Eingang
- Flexibel, Eingaben auf eine der Standardarten (zB Funktionsparameter, STDIN) und in einem beliebigen Standardformat (zB String, Binary)
- Ausgabe
- Flexibel, Ausgabe auf eine der Standardarten (z. B. Rückgabe, Druck)
- Leerzeichen, nachfolgende und führende Leerzeichen sind zulässig
- Genauigkeit, geben Sie bitte mindestens 4 Dezimalstellen Genauigkeit (dh
3.1416
)
- Wertung
- Kürzester Code gewinnt!
Testfälle
Ihre Ausgabe stimmt möglicherweise nicht mit diesen überein, weil zufällige Zufälle vorliegen. Aber im Durchschnitt sollte man für den gegebenen Wert von ungefähr so viel Genauigkeit bekommen N
.
Input -> Output
----- ------
100 -> 3.????
10000 -> 3.1???
1000000 -> 3.14??
quelle
N = 1000000
oder ist es in Ordnung, wenn das Programm z. B. einen Stapelüberlauf zurückgibt, wenn erN
zu groß ist?N=10^6
.Antworten:
APL, 23 Bytes
Erläuterung:
?⍵2⍴1e6
: Erzeuge eine 2-mal-⍵-Matrix von Zufallszahlen im Bereich [1..10 6 ]1+.=∨/
: Ermitteln Sie die GCD jedes Paares und sehen Sie, wie viele gleich 1 sind. Dies berechnet S..5*⍨6×⍵÷
: (6 × ≤ S) 0,5quelle
Jelly ,
20 1816 Bytes-2 Bytes dank @ Pietu1998 (chain & use count 1s,
ċ1
anstelle von weniger als zwei summierten<2S
)-2 Bytes dank @Dennis (1e6 vor dem Sampling mehrmals wiederholen, um Verkettung zu vermeiden)
(Extrem langsam aufgrund der Zufallsfunktion)
Wie?
TryItOnline
quelle
ḤRµȷ6Xµ€g2/ċ1÷³6÷½
Spart 2 Bytes. (ȷ6
ist 10 ^ 6 in einem einzigen Nilad,ċ1
zählt diejenigen)ȷ²
ist ein winziges bisschen schneller alsȷ6
)ȷ²
tut es hier nicht weh, zwei Links zu haben, sondern würde einen zusätzlichen Link oder¤
für einige Anwendungsfälle erfordernḤȷ6xX€
sollte für die Stichprobe arbeiten.Python 2,
143140132124122124122 BytesEs ist schon eine Weile her, dass ich Golf gespielt habe, also habe ich hier vielleicht etwas verpasst! Wird aktualisiert, wenn ich dies verkürze.
Teste mich hier!
danke an Jonathan Allan für die Zwei-Byte-Speicherung :)
quelle
1 <= i , j <= 10^6
Sie also verwendenrandrange(1,1e6+1)
.k=lambda:r.randrange(1e6)+1
spart zwei BytesMathematica,
494851 BytesEin Byte gespeichert und ein Fehler behoben dank @ LegionMammal978 .
quelle
(6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&
1*^6
sollte mit ersetzt werden,{1,1*^6}
um sicherzustellen, dass i , j ≠ 0.R
1039995999894 BytesKann wahrscheinlich ein bisschen runtergolfen werden. Reduzieren Sie 4 Bytes aufgrund von @ antoine-sac und weitere 4 Bytes, indem Sie einen Alias für
sample
, using^.5
anstelle vonsqrt
und1e6
anstelle von definieren10^6
. Es wurden 4 Bytes hinzugefügt, um sicherzustellen, dass die Abtastung voni
undj
wirklich einheitlich ist. Ein Byte wurde entfernt, nachdem mir klar wurde, dass6*N/sum(x)
es dasselbe ist wie6/mean(x)
. Wirdpryr::f
verwendetfunction(x,y)
, um 4 Bytes zu speichern.Beispielausgabe:
quelle
sample(10^6,N)
. Es ist nicht nur kürzer, sondern auch effizienter.sample(10,10)
werden garantiert alle Zahlen in 1:10 zurückgegeben, währendsample(10,10,T)
eine zufällige Auswahl erstellt wird, bei der Zahlen wiederholt werden können.Eigentlich 19 Bytes
Probieren Sie es online!
Erläuterung:
quelle
MATL , 22 Bytes
Probieren Sie es online!
quelle
Pyth, 21 Bytes
Probieren Sie es online aus.
Erläuterung
quelle
Scala,
149126 BytesErläuterung:
quelle
6f
,Seq.fill
undmath.random
.Schläger 92 Bytes
Ungolfed:
Testen:
Ausgabe:
quelle
JavaScript (ES7),
1079594 ByteDie ES6-Version hat genau 99 Byte, aber der ES7-Exponentiationsoperator
**
spart 5 Byte mehrMath.sqrt
.Ungolfed
quelle
gcd
nennt sich die Funktiong
r=_=>
ist das ein Code oder eine Zeichnung?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 kürzern=>(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 BytesLaufen Sie wie folgt:
Erläuterung
Tut was es verspricht. Benötigt PHP_GMP für
gcd
.Optimierungen
$argn
quelle
Perl, 64 Bytes
Erfordert die Befehlszeilenoption
-pMntheory=gcd
, die als 13 gezählt wird. Die Eingabe erfolgt über stdin.Beispielnutzung
quelle
R, 94 Bytes
Relativ langsam, funktioniert aber immer noch. Repliziere N-mal eine Funktion, die 2 Zufallszahlen (von 1 bis 1e6) akzeptiert und prüfe, ob ihr gcd kleiner als 2 ist (unter Verwendung einer alten gcd-Funktion von mir ).
quelle
1:x
wird funktionieren.PowerShell v2 +,
118 bis114 ByteÜbernimmt die Eingabe
$n
, startet einefor
Schleife, bis sie$k
gleich ist$n
(impliziert$k=0
beim ersten Betreten der Schleife). Bei jeder Iteration erhalten Sie neueRandom
Zahlen$i
und$j
(das-mi
Nimum-1
Flag stellt sicher, dass wir>=1
und kein Maximum-Flag bis zu[int]::MaxValue
zulassen sind, was vom OP zulässig ist, da es größer als ist10e6
).Wir gehen dann in eine GCD-
while
Schleife . Dann wird, solange der GCD ist1
,$o
inkrementiert. Am Ende derfor
Schleife führen wir einen einfachen[math]::Sqrt()
Aufruf durch, der in der Pipeline verbleibt und dessen Ausgabe implizit ist.Die Ausführung mit Eingaben
10000
auf meinem ~ 1 Jahr alten Core i5-Laptop dauert ungefähr 15 Minuten .Beispiele
quelle
Java 8,
164151 BytesErläuterung
Testgeschirr
Aktualisieren
quelle
n
,t+=1
können werdent++
, Sie können Ihreint
Deklarationen in einer Zeile zusammenfassen, dhint c=n,t=0,x,y;
und!=0
(ich denke) können werden>0
. Das sollte insgesamt 12 Bytes einsparen. Dies ist jedoch eine gute Methode, um die GCD von x und y zu ermitteln.Perl 6 ,
5653 BytesProbieren Sie es online!
quelle
Frink,
8489Ich hatte Glück: g = n = ... speichert ein Byte über g = 0 n = ... ; und 1% gcd () ergibt (0,1) vs (1,0), so dass ich subtrahieren kann. Und Pech: n ist vorbelegt und ein verwendet , da Schleifenvariablen und ihre Grenzen sind lokal und außerhalb der Schleife nicht definiert.
Ausführlich
quelle
AWK , 109 Bytes
Probieren Sie es online!
Ich bin überrascht, dass es für 1000000 in angemessener Zeit läuft.
quelle
Pyt ,
3735 BytesErläuterung:
quelle
J, 27 Bytes
Erläuterung:
Ich hatte ziemlich viel Glück mit einem
3.14157
fürN = 10000000
, was2.44
Sekunden dauerte .quelle
Japt , 23 Bytes
Versuch es
quelle