Wenn Sie einen Bruch in eine Dezimalzahl umwandeln und diese Zahl speichern möchten, müssen Sie sie häufig runden, da Sie nur eine bestimmte Menge an Speicher verwenden möchten. Angenommen, Sie können nur 5 Dezimalstellen speichern, dann wird 5/3 zu 1,6667. Wenn Sie nur 2 Dezimalstellen speichern können, beträgt diese 1,7 (jetzt wird angenommen, dass sie immer zwischen 0 und 9,99 liegt ...).

Wenn Sie nun versuchen, diesen Prozess mit 1.7 umzukehren und Ihren Bruch wieder herzustellen, kann dies schwierig sein, da Sie wissen, dass 1.7 nur eine gerundete Zahl ist. Natürlich können Sie 17/10 probieren, aber das ist eher ein "hässlicher" Bruchteil im Vergleich zum "eleganten" 5/3.

Das Ziel ist es nun, den Bruch a / b mit dem kleinsten Nenner b zu finden, der bei richtiger Rundung die gerundete Dezimalzahl ergibt.

Einzelheiten

Die Eingabe enthält eine Zeichenfolge mit einer Zahl von 1 bis 5 Ziffern, die zwischen 0 (einschließlich) und 10 (nicht einschließlich) mit einem '.' nach der ersten Ziffer. Angenommen, ndie Anzahl der Stellen. Die Ausgabe muss eine Liste / ein Array mit zwei Ganzzahlen [numerator, denominator]oder ein rationaler Datentyp sein (Sie können einen eigenen Datentyp erstellen oder einen integrierten Datentyp verwenden), bei dem der Zähler nicht negativ und der Nenner positiv ist. Der Bruchzähler / Nenner muss der Eingabe entsprechen, wenn er korrekt auf nZiffern gerundet ist (dh n-1Ziffern nach dem Komma).

Einschränkung: Es ist nur eine Schleifenanweisung zulässig. Dies bedeutet, dass Sie nur eine einzige Schleifenanweisung (wie foroder whileoder gotousw.) sowie funktionale Schleifen wie mapoder fold, die Code auf jedes Element einer Liste / eines Arrays anwenden) in Ihrem gesamten Code verwenden können, aber Sie können ihn "missbrauchen" oder benutze Rekursion etc.

Sie sollten eine Funktion schreiben. Wenn Ihre Sprache keine Funktionen hat (oder auch nicht), können Sie alternativ davon ausgehen, dass die Eingabe in einer Variablen gespeichert ist (oder über stdin eingegeben wird), und das Ergebnis ausdrucken oder in eine Datei schreiben. Die niedrigste Anzahl von Bytes gewinnt.

Runden

Die Rundung sollte nach den „herkömmlichen“ Rundungsregeln erfolgen. Wenn also die letzte Stelle, die abgeschnitten wird, 5 oder mehr beträgt, runden Sie auf und runden für alle anderen Fälle ab. Beispiel:

Beim Runden auf ergibt sich 4.5494

• 1 Ziffer: 5
• 2 Stellen: 4.5
• 3 Stellen: 4,55
• 4 Stellen: 4,549

Beispiele

Bitte geben Sie folgende und andere 'interessante' Testfälle an:

Input 1.7     Output 5/3
Input 0.      Output 0/1
Input 0.001   Output 1/667
Input 3.1416  Output 355/113

CJam, 41 40 36 Bytes

Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@

Als nächstes wird die Eingabezeichenfolge in Q gespeichert, was in der Frage ausdrücklich erlaubt ist. Probieren Sie es online aus.

Testfälle

$ for d in 1.7 0. 0.001 3.1416; do cjam <(echo "\"$d\":Q;
> Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@
> "); echo; done
5/3
0/1
1/667
355/113

Wie es funktioniert

Q'./1=,:L  " Count the number of characters after the dot and store it in L.     ";
0\         " Push 0 (denominator) and swap it with L (dummy value).              ";
{          "                                                                     ";
  ;        " Discard the topmost item from the stack (numerator or dummy value). ";
  )        " Increment the denominator.                                          ";
  _Qd*mo   " Multiply a copy by Double(Q) and round.                             ";
  _d2$/    " Cast a copy to Double and it divide it by the denominator.          ";
  LmO      " Round to L digits.                                                  ";
  Qd       " If the result is not Double(Q),                                     ";
}g         " repeat the loop.                                                    ";
./@        " Push a slash and rotate the denominator on top of it.               ";

T-SQL 254

Während T-SQL für solche Dinge nicht wirklich geeignet ist, macht es Spaß, es zu versuchen. Die Leistung wird umso schlechter, je höher der Nenner ist. Es ist auf einen Nenner von 1000 begrenzt.

Eingabe ist eine Float-Variable @

WITH e AS(SELECT *FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)),t AS(SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N FROM e a,e b,e c,e d)SELECT TOP 1concat(n.n,'/',d.n)FROM t d,t n WHERE round(n.n/(d.n+.0),len(parsename(@,1)))=@ ORDER BY d.n,n.n

Eine Aufschlüsselung der Abfrage

WITH                                      -- Start CTE(Common Table Expression)
 e AS(                                    --Create a set of 10 rows
   SELECT *
   FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)
 ),
 t AS(                                    
   SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N 
   FROM e a,e b,e c,e d                   --Cross join e to produce 1000 numbered rows
 )
SELECT 
  TOP 1                                   --Grab first result
  concat(n.n,'/',d.n)                     --Build output
FROM t d,t n                              --Cross join t against itself for denominator and numerator
WHERE round(
  n.n/(d.n+.0),                           --Force float division with +.0
  len(parsename(@,1))                     --Get rounding length
  )=@                                     --Filter where the rounded result = input
ORDER BY d.n,n.n                          --Order by denominator then numerator

Haskell, 62 59

wenn nur die Namen nicht so lang wären ...

import Data.Ratio
f s=approxRational(read s)$50/10^length s

Dies ist eine Funktion, die einen RationalWert zurückgibt.

Erklärung: Die Funktion approxRationalist eine Funktion, die eine Gleitkommazahl und ein Gleitkommazahl-Epsilon annimmt und das einfachste Rationale zurückgibt, das sich im Abstandsepsilon der Eingabe befindet. Grundsätzlich wird die einfachste Annäherung des Schwimmers an einen rationalen Fehler in einer "verzeihlichen Fehler" -Distanz zurückgegeben.

Nutzen wir diese Funktion für unsere Zwecke. Dazu müssen wir herausfinden, wie groß die Fläche der Floats ist, die sich auf die angegebene Zahl aufrunden. Wenn Sie dies in die approxRationalFunktion aufnehmen, erhalten Sie die Antwort.

Versuchen wir zum Beispiel 1.7. Der niedrigste auf 1,7 gerundete Float ist 1,65. Ein niedrigerer Wert wird nicht auf 1,7 gerundet. In ähnlicher Weise beträgt die Obergrenze der Floats, die auf 1,7 runden, 1,75.
beide grenzen sind die grenzen sind die eingabenummer +/- 0.05. es kann leicht gezeigt werden, dass dieser Abstand immer ist 5 * 10 ^ -(the length of the input - 1)(der -1 ist, weil es immer ein '.' in der Eingabe gibt). ab hier ist der code ganz einfach.

Testfälle:

*Main> map f ["1.7", "0.001", "3.1416"]
[5 % 3,1 % 667,355 % 113]

bei "0" funktioniert es leider nicht weil die Parser-Funktion von Haskell ein .am Ende eines Floats nicht erkennt . Dies kann durch Ersetzen read sdurch für 5 Bytes behoben werden read$s++"0".

Ruby, 127 125 Bytes

f=->n{b=q=r=(m=n.sub(?.,'').to_r)/d=10**p=n.count('0-9')-1
b=r if(r=(q*d-=1).round.to_r/d).round(p).to_f.to_s==n while d>1
b}

Definiert eine Funktion, fdie das Ergebnis als zurückgibt Rational. ZB wenn Sie diesen Code anhängen

p f["1.7"]
p f["0."]
p f["0.001"]
p f["3.1416"]

Du erhältst

(5/3)
(0/1)
(1/667)
(355/113)

Die Schleife ist über Nenner. Ich beginne mit dem vollen Bruch, zB 31416/10000für das letzte Beispiel. Dann dekrementiere ich den Nenner, dekrementiere den Zähler proportional (und runde ihn). Wenn das resultierende Rational auf die gleiche Zahl wie die eingegebene gerundet wird, erinnere ich mich an einen neuen besten Bruch.

Mathematica, 49 53 Zeichen

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@

Verwendung:

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@"1.7"

Ausgabe:

5/3

Testfälle:

input: 1.7     output: 5/3
input: 0.      output: 0
input: 0.001   output: 1/999
input: 3.1416  output: 355/113

Der 0,001-Fall kommt mir merkwürdig vor; da die Rationalisierungsfunktion nicht gemäß ihrer Beschreibung funktionierte, als sie den 1/667-Fall nicht fand. Sie sollte die Zahl mit dem kleinsten Nenner ausgeben, der innerhalb der angegebenen Grenzen liegt.

Python 2.7+, 111 Zeichen

Beweis, dass Sie schrecklichen Code in jeder Sprache schreiben können:

def f(s):
 t,e,y=float(s),50*10**-len(s),1;n=d=x=0
 while x|y:n,d=n+x,d+y;a=1.*n/d;x,y=a<t-e,a>t+e
 return n,d

Ausgabe

>>> [f(s) for s in ("1.7", "0.", "0.001", "3.1416")]
[(5, 3), (0, 1), (1, 667), (355, 113)]

APL, 50

2↑⍎⍕(⍎x←⍞){50>|(10*⍴x)×⍺-⍵÷⍨n←⌊.5+⍺×⍵:n ⍵⋄''}¨⍳1e5

Solange Sie nicht zählen evalund toStringals Schleifen

Erläuterung

Der Ansatz besteht darin, als Nenner über 1 bis 10000 zu iterieren und den Zähler zu berechnen, der am ehesten mit dem Gleitkomma übereinstimmt, und dann zu prüfen, ob der Fehler innerhalb der Grenzen liegt. Zuletzt wählen Sie aus allen gefundenen Brüchen das kleinste Paar aus.

(⍎x←⍞)String-Eingabe vom Bildschirm nehmen, zuweisen xund auswerten
⍳1e5 Array von 1 bis 10000 generieren
{...}¨Für jedes Element des Arrays Funktion damit aufrufen und (⍎x←⍞)und Argumente (Schleife)

⍺×⍵Multiplizieren die Argumente
⌊.5+Abrunden (um 0,5 dann Abrunden Zugabe)
n←Zuweisen zu n
⍺-⍵÷⍨Divide by rechtem Argumente, dann subtrahiert linkes Argument
(10*⍴x)×Multiplizieren mit 10 auf die Kraft der „Länge von x“
|Absolutwert Nehmen
50> Sie prüfen , ob weniger als 50 (Länge von x2 mehr ist als die Nr. von dp, verwenden Sie hier also 50 anstelle von 0,5.)
:n ⍵⋄''Wenn die vorherige Prüfung true zurückgibt, geben Sie das Array von nund das richtige Argument zurück, andernfalls wird eine leere Zeichenfolge zurückgegeben.

⍎⍕ toStringund dann eval, um ein Array aller Zahlen im Array zu erhalten
2↑ Wählen Sie nur die ersten 2 Elemente aus, bei denen es sich um das erste gefundene Zähler-Nenner-Paar handelt

GNU DC, 72 Bytes

Keine Schleifen - DC hat sie nicht einmal. Stattdessen stammt die Steuerung aus einem einzelnen rekursiven Makro - idiomatisch für DC.

?dXAr^d2*sf*sq1sd0[ld1+sd]sD[r1+r]sN[dlf*ld/1+2/dlq>Ndlq<Dlq!=m]dsmxpldp

Ausgabe:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; dc unround.dc <<< $n; done
    n = 1.7:
5
3
    n = 0.:
0
1
    n = 0.001:
1
667
    n = 3.1416:
355
113
$ 

Puh. Teilweise Erklärung in dieser Antwort .

Mathematica, 111 Zeichen

f=Module[{a=0,b=1,k},While[Round[a/b,10^-(StringLength[#]-2)]!=(k=ToExpression)@#,If[N[a/b]>k@#,b++,a++]];a/b]&

Wirklich ziemlich einfach, und ich denke, es konvergiert nirgendwo so schnell wie die anderen Lösungen, da Zähler und Nenner nur um eins inkrementiert werden. Ich wollte meistens die einfache Lösung dafür finden. Ich muss die anderen Antworten sehen und sehen, was für clevere Sachen dort passieren.

Ausgabe

f/@{"1.7","0.0","0.001","3.1416","3.14"}
{5/3, 0, 1/667, 355/113, 22/7}

Feiert hier jemand den Pi Approximation Day ?

Applescript,> 300 Bytes

Ich wollte dies in einer Sprache tun, die von Haus aus die erforderliche Rundungsart bietet. Es stellt sich heraus, dass Applescript die Rechnung passt. Dann sah ich die Aufzählung rounding as taught in schoolund konnte der Verwendung nicht widerstehen, trotz der offensichtlichen Unwettbewerblichkeit von Applescript für Golfzwecke:

on u(q)
    set n to 0
    set d to 1
    set x to 0
    set AppleScript's text item delimiters to "."
    set f to 10 ^ (q's text item 2's length)
    repeat until x = q as real
        set x to (round n * f / d rounding as taught in school) / f
        if x < q then set n to n + 1
        if x > q then set d to d + 1
    end repeat
    return {n, d}
end u

log my u("1.7")
log my u("0.")
log my u("0.001")
log my u("3.1416")

Dies kann ein bisschen mehr Golf gespielt werden, aber wahrscheinlich nicht wert.

Ausgabe:

(*5, 3*)
(*0, 1*)
(*1, 667*)
(*355, 113*)

BC, 151 148 Bytes

Bearbeiten - schnellere und kürzere Version

define f(v){s=scale(x=v);for(i=r=1;i<=10^s;i+=1){t=v*i+1/2;scale=0;p=t/=1;scale=s+1;t=t/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=p;d=i}}}

gleicher Testfall.

Vieles ist ähnlich wie in der vorherigen Version, aber anstatt alle möglichen n / d-Kombinationen auszuprobieren, klettern wir über die Reste von v und Rückwärtsquotienten von Vielfachen von m == v * d und Nennern d. Auch hier ist die Genauigkeit der Berechnung gleich.

Hier ist es entwirrt:

define f(v)
{
    s= scale(x=v)
    for( i=r=1; i <= 10^s; i+=1 ){
        t= v * i +1/2
        scale=0
        m=t/=1 # this rounded multiple becomes nominator if
               # backward quotient is first closest to an integer
        scale=s+1
        t= t / i +10^-s/2 # divide multiple back by denominator, start rounding again...
        scale=s
        t= t/1 - v # ...rounding done. Signed residue of backward quotient
        if( (t*= -1^(t < 0)) < r ){
            r=t
            n=m
            d=i
        }
    }
}

Diese Version hat wirklich nur eine einzige Schleife und führt nur $ \ Theta \ left (\ operatorname {fractional_decimals} (v) \ right) $ arithmetische Operationen aus.

Original - langsame Version

Diese Funktion berechnet den kleinsten Nominator n und den kleinsten Nenner d so, dass der auf Nachkommastellen (v) gerundete Bruch n / d gleich einem gegebenen Dezimalwert v ist.

define f(v){s=scale(v);j=0;for(i=r=1;j<=v*10^s;){scale=s+1;t=j/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=j;d=i};if((i+=1)>10^s){i=1;j+=1}};v}

Testfall:

define o(){ print "Input ",x,"\tOutput ",n,"/",d,"\n" }
f(1.7); o()
> 0
> Input 1.7       Output 5/3
> 0
f(0.); o()
> 0
> Input 0 Output 0/1
> 0
f(0.001); o()
> 0
> Input .001      Output 1/667
> 0
f(3.1416); o()
> 0
> Input 3.1416    Output 355/113
> 0

Und hier ist es entwirrt:

define f(v)
{
    s=scale(x=v) # save in global for later print
    j=0
    # do a full sequential hill-climb over the residues r of v and all possible
    # fractions n / d with fractional_decimals(v) == s precision.
    for( i=r=1; j <= v * 10^s; ){
        scale=s+1
        t= j / i +10^-s/2 # start rounding...
        scale=s
        t= t/1 - v # ...rounding done. New residue, but still signed
        if( (t*= -1^(t < 0)) < r ){ # absolute residue better?
            # climb hill
            r=t
            n=j
            d=i
        }
        if( (i+=1) > 10^s ){ # next inner step. End?
            # next outer step
            i=1
            j+=1
        }
    }
    v
}

Ich gebe zu, ich habe ein wenig geschummelt, indem ich eine zweite innere Schleife innerhalb einer einzelnen äußeren Schleife emuliert habe, aber ohne weitere Schleifenanweisungen zu verwenden. Und deshalb führt es tatsächlich $ \ Theta \ left (v \ operatorname {fractional_decimals} (v) ^ 2 \ right) $ arithmetische Operationen aus.

C 233

Dies funktioniert durch Aufrufen einer Rationalisierungsfunktion r () mit einem Anfangsnenner von 1. Die Funktion beginnt mit dem Inkrementieren eines Zählers und prüft bei jedem Inkrement, ob die sich ergebende Zahl, wenn sie auf die gleiche Anzahl von Ziffern wie das Original gerundet wird, dieselbe Zeichenfolge hat Darstellung als Original. Sobald der Zähler so weit erhöht wurde, dass das Ergebnis größer als das Original ist, erhöht die Funktion den Nenner und ruft sich selbst auf.

Hier wird natürlich viel mehr Code verwendet, aber ich denke, der Geist des Problems entlastet diesen Bare-Bones-Ansatz. Soweit wir wissen, haben die internen rationalize () -Funktionen moderner Sprachen viele interne Schleifen.

Beachten Sie, dass dies bei einer Eingabe von "0" nicht funktioniert. Da dies keine Standardmethode zum Schreiben eines Floats ist, wird beim erneuten Schreiben des Floats in einen String niemals eine "0" ausgegeben.

Die Spezifikationen wollen eine Funktion, die Werte zurückgibt, anstatt nur auf dem Bildschirm zu drucken, daher die Übergabe von Argumenten.

Code (ungolfed):

void r(char* x, int* a, int* b) {
    int i = -1;
    char z[32];
    double v =atof(x);
    while(1) {
        i++;
        double y = ((double)i)/((double)(*b));
        double w;
        sprintf(z, "%.*f", strlen(strchr(x,'.'))-1, y);
        if(strcmp(x, z)==0) {
            *a = i;
            return;
        }
        w = atof(z);
        if(w > v) {
            (*b)++;
            r(x, a, b);
            return;
        }
    }
}

Verwendung:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
    int num;
    int denom = 1; // start with a denominator of 1
    r(argv[1], &num, &denom);
    printf("%d/%d\n", num, denom);
    return 0;
}

Golf Code:

typedef double D;
void r(char*x,int*a,int*b){int i=-1;char z[32];D v=atof(x);while(1){i++;D y=((D)i)/((D)(*b));D w;sprintf(z,"%.*f",strlen(strchr(x,'.'))-1,y);if(!strcmp(x,z)){*a=i;return;}w=atof(z);if(w>v){(*b)++;r(x,a,b);return;}}}

Pure Bash, 92 Bytes

Als eine teilweise Erklärung für diese Antwort wird hier portiert, um zu schlagen:

f=${1#*.}
q=${1//.}
for((n=0,d=1;x-q;x=2*10**${#f}*n/d+1>>1,n+=x<q,d+=x>q));{ :;}
echo $n/$d

Vor allem:

• Bash hat nur Ganzzahl-Arithmetik. Also skalieren wir alles entsprechend um 2 * 10 ^ (Anzahl der Nachkommastellen).
• schlag Runden unten zur nächsten ganzen Zahl; Die 2 im obigen Ausdruck ist, damit wir stattdessen auf die nächste Ganzzahl ( auf oder ab) runden können ) .
• Nur eine Schleife
• Wir prüfen, ob das Rationale die Dezimalstelle überschreitet oder unterschreitet und erhöhen den Nenner oder Zähler entsprechend.

Ausgabe:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; ./unround.sh $n; done
    n = 1.7:
5/3
    n = 0.:
0/1
    n = 0.001:
1/667
    n = 3.1416:
355/113
$ 

JavaScript (E6) 85

F=r=>(l=>{for(n=r,d=1;l&&r!=((n=r*d+1/2|0)/d).toFixed(l);d++);})(r.length-2)||[n|0,d]

Ungolfed

F=r=>{
  l = r.length-2; // decimal digits
  if (l==0) return [r|0, 1] // if no decimal return the same (conv to number) with denominator 1

  // loop for increasing denominator 
  for(d = 2; 
      r != ( // loop until find an equal result
      // given R=N/D ==> N=R*D
      (n=r*d+1/2|0) // find possible numerator, rounding (+0.5 and trunc)
      /d).toFixed(l); // calc result to given decimals
      d++);
  return [n,d]
}

Test In FireFox / Firebug - Konsole

;["1.7","0.","0.001","3.1416","9.9999"].forEach(v => console.log(v,F(v)))

Ausgabe

1.7 [5, 3]
0. [0, 1]
0.001 [1, 667]
3.1416 [355, 113]
9.9999 [66669, 6667]