Tor
Generieren Sie ( N
) zufällige Liniensegmente mit einheitlicher Länge ( l
) und prüfen Sie, ob sie die äquidistanten ( t
) parallelen Linien kreuzen .
Simulation
Was simulieren wir? Buffons Nadel . Glätten Sie den Sand in Ihrem Sandkasten und zeichnen Sie einen Satz gleichmäßig verteilter paralleler Linien (nennen Sie den Abstand dazwischen t
). Nehmen Sie einen geraden Stock der Länge l
und lassen Sie ihn N
mal in den Sandkasten fallen. Lassen Sie die Häufigkeit sein, mit der eine Linie überschritten wurde c
. Dann Pi = (2 * l * n) / (t * c)
!
Wie simulieren wir das?
- Nehmen Sie Eingabe
N,t,l
- Mit
N, t, l
allen positiven ganzen Zahlen - Gehen Sie wie folgt vor
N
:- Generieren Sie eine gleichmäßig zufällige Ganzzahlkoordinate
x,y
- Mit
1 <= x, y <= 10^6
x,y
ist der Mittelpunkt eines Liniensegments der Längel
- Generieren Sie eine einheitlich zufällige Ganzzahl
a
- Mit
1 <= a <= 180
- Sei
P
der Punkt, an dem das Liniensegment die x-Achse kreuzen würde - Dann
a
ist der Winkel(x,y), P, (inf,0)
- Generieren Sie eine gleichmäßig zufällige Ganzzahlkoordinate
- Zählen Sie die Anzahl
c
der Liniensegmente, die die Liniex = i*t
für eine beliebige Ganzzahl kreuzeni
- Rückkehr
(2 * l * N) / (t * c)
Spezifikation
- Eingang
- Flexibel, Eingabe auf eine der Standardmethoden (z. B. Funktionsparameter, STDIN) und in einem beliebigen Standardformat (z. B. String, Binär)
- Ausgabe
- Flexibel, Ausgabe auf eine der Standardmethoden (z. B. Rückgabe, Druck)
- Leerzeichen, nachgestellte und führende Leerzeichen sind akzeptabel
- Genauigkeit, bitte geben Sie mindestens 4 Dezimalstellen Genauigkeit an (dh
3.1416
)
- Wertung
- Der kürzeste Code gewinnt!
Testfälle
Ihre Ausgabe stimmt möglicherweise aufgrund zufälliger Zufälle nicht mit diesen überein. Aber im Durchschnitt sollten Sie ungefähr so viel Genauigkeit für den gegebenen Wert von erhalten 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
Diese Herausforderungen sind Simulationen von Algorithmen, die nur die Natur und Ihr Gehirn (und möglicherweise einige wiederverwendbare Ressourcen) benötigen, um Pi zu approximieren. Wenn Sie Pi während der Zombie-Apokalypse wirklich brauchen, verschwenden diese Methoden keine Munition ! Insgesamt gibt es neun Herausforderungen .
a
auch mit einer anderen Methode erstellt werden, wenn sie einheitlich ist? (Denken an eine 2D-Gauß-Blase)t > l
? Zwei der folgenden Lösungen gehen von dieser Annahme aus, die die Überprüfung auf Schnittpunkte erheblich vereinfacht.Antworten:
R,
1131007570686765596357 BytesAls statistische, funktionale Programmiersprache ist es nicht verwunderlich, dass R für diese Art von Aufgabe ziemlich gut geeignet ist. Die Tatsache, dass die meisten Funktionen vektorisierte Eingaben annehmen können, ist für dieses Problem sehr hilfreich, da
N
wir nicht nur Iterationen durchlaufen, sondern nur Vektoren mit einer Größe übergebenN
. Vielen Dank an @Billywob für einige Vorschläge, die dazu führen, dass 4 Bytes abgeschnitten werden. Vielen Dank an @Primo für die geduldige Erklärung, dass mein Code in Fällent > l
, in denen dies behoben wurde, nicht funktioniert hat .Probieren Sie es online aus!
Beispielausgabe:
Erläuterung
Das Problem besteht darin, festzustellen, ob sich die beiden
x
Werte der Nadel auf beiden Seiten einer parallelen Linie befinden. Dies hat einige wichtige Konsequenzen:y
-Werte sind irrelevantx
Achse ist irrelevant, nur die Position relativ zu den nächsten parallelen Linien.Im Wesentlichen ist dies eine Aufgabe in einem eindimensionalen Raum, in dem wir eine Linie mit der Länge in [0,
l
] erzeugen (der Winkela
bestimmt diese Länge) und dann prüfen, wie oft diese Länge überschritten wirdt
. Der grobe Algorithmus lautet dann:x1
von [0, 1000000]. Da an jedemt
Punkt entlang derx
Achse parallele Linien auftreten , ist die relativex
Positionx
modulot
.a
.x2
Position basierend aufa
.x1+x2
passtt
, dh das Wort ergreifen(x1+x2)/t
.Abtasten
N
Zahlen in [0, 1E6] modulot
entspricht einfaches AbtastenN
Zahlen in [0,t
]. Da dies(x1+x2)/t
äquivalent zu istx1/t + x2/t
, wird der erste Schritt zur Abtastung von [0,t
] /t
, dh [0, 1]. Glücklicherweise ist dies der Standardbereich für dierunif
Funktion von R , dieN
reelle Zahlen von 0 bis 1 aus einer gleichmäßigen Verteilung zurückgibt .Wir wiederholen diesen Schritt, um
a
den Winkel der Nadel zu erzeugen .Diese Zahlen werden als halbe Umdrehung interpretiert (dh
.5
90 Grad). (Die OP fragen nach Grad von 1 bis 180, aber in den Kommentaren es ist klar , dass jedes Verfahren erlaubt, wenn sie als oder genauer ist.) Bei einem Winkelθ
,sin(θ)
gibt uns den x-Achsen - Abstand zwischen den Enden der Nadel. (Normalerweise würde man den Kosinus für so etwas wie diese verwendet, aber in unserem Fall betrachten wir den Winkelθ
in Bezug auf die y-Achse relativ zu sein, nicht die x-Achse (das heißt, ein Wert von 0 Grad geht nach oben , nicht rechts ), und deshalb verwenden wir den Sinus, der die Zahlen im Grunde phasenverschiebt.) Multipliziertl
damit ergibt sich diex
Position des Nadelendes.Jetzt teilen wir durch
t
und addieren denx1
Wert. Dies ergibt(x1+x2)/t
, wie weit die Nadelx1
in Bezug auf die Anzahl der parallelen Linien herausragt . Um die ganze Zahl zu erhalten, wie viele Linien gekreuzt wurden, nehmen wir diefloor
.Wir berechnen die Summe und geben an,
c
wie viele Linien von Nadeln gekreuzt werden.Der Rest des Codes implementiert nur die Formel zur Approximation von pi, d
(2*l*N)/(t*c)
. H. Wir sparen einige Bytes in Klammern, indem wir die Tatsache ausnutzen, dass(2*l*N)/(t*c) == 2*l*N/t/c
:Und das Ganze ist in eine anonyme Funktion verpackt:
quelle
(2*l*N) => 2*l*N
?(2*l*N)/(t*c) = 2*l*N/t/c
Sie können also zwei weitere Bytes speichern, indem Sie auch die Klammern im letzten Teil überspringen.Perl, 97 Bytes
Wenn man den Shebang als eins zählt, wird die Eingabe von stdin übernommen, wobei der Raum getrennt ist. Wenn nicht ganzzahlige Zufallswerte zulässig wären, könnte dies etwas kürzer sein.
Ich habe mir eine Freiheit genommen und π / 180 als 71/4068 angenähert , was innerhalb von 1,48 · 10 -9 genau ist .
Beispielnutzung
Mehr oder weniger mathematisch äquivalente Substitutionen
Angenommen, die x-Koordinate repräsentiert den am weitesten links liegenden Punkt der Nadel und nicht ihre Mitte, wie in der Problembeschreibung angegeben:
89 Bytes
Das Problem gibt an, dass
x
als zufällige Ganzzahl abgetastet werden soll. Wenn wir den Zeilenabstand auf eine Lücke von eins projizieren, erhalten wir Werte der Formn/t
mit0 <= n < t
, die nicht unbedingt einheitlich sind, wenn siet
sich nicht gleichmäßig teilen1e6
. Unter der Annahme, dass eine gleichmäßige Verteilung dennoch akzeptabel ist:76 Bytes
Beachten Sie, dass
rand
es am Anfang des Bereichs nicht erforderlich ist , da immer kleiner als eins ist (und daher auf Null abgeschnitten wird):70 Bytes
Angenommen, der Winkel der Nadel muss kein ganzzahliger Grad sein, sondern nur gleichmäßig zufällig:
59 Bytes
Angenommen, der Winkel kann eine gleichmäßige Verteilung sein:
52 Bytes
Das Obige ist eine mathematisch korrekte Simulation von Buffons Nadel. An diesem Punkt denke ich jedoch, dass die meisten Leute zustimmen würden, dass dies nicht das ist, wonach die Frage gestellt wurde.
Wirklich pushen
Wir könnten einfach die Hälfte der Testfälle wegwerfen, wenn der zweite Endpunkt links vom ersten liegt (anstatt sie auszutauschen):
47 Bytes
Beachten Sie, dass die Werte von
t
undl
für die Ergebnisse des Experiments keine Rolle spielen. Wir könnten sie einfach ignorieren (implizit davon ausgehen, dass sie gleich sind):28 Bytes
Offensichtlich nicht konkurrierend, aber Sie müssen zugeben, dass es eine gewisse Eleganz hat.
quelle
Python 2, 141 Bytes
schamloser Hafen von rtumbull, der schon überspringt,
y
weil er überhaupt nicht benötigt wird.Das Problem ist nur, dass pi bereits im Programm bekannt ist.
Hier ist es (golfbar) mit unbekanntem pi und ohne trigonometrische Funktionen
x,y
ing
ist nur für die Richtung.quelle
from random import randint;from math import cos,pi
. Schlägtt < l
z1000000,1000,70000
.