Wir haben eine Gleitkommazahl r
zwischen 0 und 1 und eine ganze Zahl p
.
Finden Sie den Anteil der ganzen Zahlen mit dem kleinsten Nenner, der sich r
mit p
einer Genauigkeit von mindestens einer Ziffer annähert.
- Eingaben:
r
(eine Gleitkommazahl) undp
(Ganzzahl). - Ausgaben:
a
undb
ganze Zahlen, woa/b
(als float) ungefährr
bis zu denp
Ziffern.b
ist die mögliche kleinste solche positive ganze Zahl.
Beispielsweise:
- wenn
r=0.14159265358979
undp=9
, - dann ist das Ergebnis
a=4687
undb=33102
, - weil
4687/33102=0.1415926530119026
.
Jede Lösung muss theoretisch mit Typen mit beliebiger Genauigkeit funktionieren, aber Einschränkungen, die durch Typen mit fester Genauigkeit der Implementierungen verursacht werden, spielen keine Rolle.
Präzision bedeutet die Anzahl der Stellen nach " 0.
" in r
. Also, wenn r=0.0123
und p=3
, dann a/b
sollte mit beginnen 0.012
. Wenn die ersten p
Ziffern des Bruchteils von r
0 sind, ist undefiniertes Verhalten akzeptabel.
Gewinnkriterien:
- Der algorithmisch schnellste Algorithmus gewinnt. Die Geschwindigkeit wird in O (p) gemessen.
- Wenn es mehrere schnellste Algorithmen gibt, gewinnt der kürzeste.
- Meine eigene Antwort ist aus dem Satz der möglichen Gewinner ausgeschlossen.
Ps der mathematische Teil ist eigentlich viel einfacher, wie es scheint, ich schlage vor, diesen Beitrag zu lesen .
quelle
padEnd
und herummatch
? Können Sie nicht einfachslice
jede Zeichenfolge auf die richtige Länge bringen und sie dann subtrahieren?padEnd
wird für Testfallf(0.001,2)
und verwendetf(0.3,2)
.(r,p)=>{for(a=0,b=1;`${a/b}`.slice(0,p+2)-`${r}`.slice(0,p+2);a/b<r?a++:b++);return[a,b]}
(nicht vollständig Golf) vereinfachen.Haskell , O (10 p ) im schlimmsten Fall
121119 BytesProbieren Sie es online aus!
2 Bytes dank Laikoni gespeichert
Ich habe den Algorithmus von /math/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i verwendet .
Bei jedem Schritt ist das neue Intervall die Hälfte des vorherigen Intervalls. Somit ist die Intervallgröße
2**-n
, won
der aktuelle Schritt ist. Wann2**-n < 10**-p
sind wir sicher, die richtige Annäherung zu haben. Doch wennn > 4*p
dann2**-n < 2**-(4*p) == 16**-p < 10**-p
. Die Schlussfolgerung ist, dass der Algorithmus istO(p)
.BEARBEITEN Wie von orlp in einem Kommentar ausgeführt, ist die obige Behauptung falsch. Im schlimmsten Fall
r = 1/10**p
(r= 1-1/10**p
ist ähnlich) gibt es10**p
Schritte :1/2, 1/3, 1/4, ...
. Es gibt eine bessere Lösung, aber ich habe momentan nicht die Zeit, dies zu beheben.quelle
f=
und zwei Bytes mit sparenz<-floor.(*10^p),u<-a+c,v<-b+d
.f=
TIO im Haskell-Code entfernen soll .-cpp
Compiler-Flag hinzufügen undf=\
in die Kopfzeile schreiben : Probieren Sie es online aus!C, 473 Bytes (ohne Kontext), O (p), nicht konkurrierend
Diese Lösung verwendet den in diesem ausgezeichneten Beitrag beschriebenen mathematischen Teil . Ich habe nur
calc()
die Antwortgröße berechnet .quelle