Unrunde Brüche

22

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
fehlerhaft
quelle
1
Aber in funktionalen Sprachen gibt es keine Schleife. Das feindliche Beispiel in haskell repeaterstellt eine unendliche Liste seines Arguments. Es scheint sich zu wiederholen, aber es hat tatsächlich die zeitliche Komplexität von O (1). Aber ich denke, es ist besser, jeden Fall einzeln zu sortieren, als keine funktionalen Sprachen zuzulassen.
stolzer Haskeller
3
Ich mag die aktuelle Definition von "Schleife" nicht. In Python ist zum Beispiel for n in numbers: f(g(n))äquivalent zu map(f, map(g, numbers)). Die Funktionsversion verwendet mapzweimal, sollte das wirklich verboten sein?
Flornquake
1
@ MartinBüttner Ich sprach über den Fall, dass funktionale Sprachen wegen Zweideutigkeit nicht zugelassen würden
stolzer Haskeller
1
Es tut mir leid, dass ich nicht wirklich zu dieser Diskussion beitragen kann, da mein Wissen über funktionale Programmierung im Grunde Null ist. Wenn Sie eine Lösung haben, bei der Sie sich nicht sicher sind, ob sie den "Regeln" entspricht, reichen Sie sie trotzdem ein! Am Ende soll es eine unterhaltsame und lehrreiche Herausforderung sein!
Fehler
2
@Dennis Nein, das war eine unglückliche Formulierung. Sie können sie in jeder beliebigen Form einreichen. Der Grundgedanke hinter diesem Absatz war, dass Sie keinen Nachteil haben sollten, wenn Ihre Sprache mehr Bytes zum "Lesen" der eingegebenen Nummer benötigt.
Fehler

Antworten:

4

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.               ";
Dennis
quelle
15

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
MickyT
quelle
+1. Ich liebe es. Ich legte in 3.14159und es gab mir ordnungsgemäß355/113
Tom Chantler
1
+1 Ich hätte nie gedacht, dass hier eine SQL-Sprache vorkommt !!!
Fehler
@ TomChantler Ich vermute, Sie meinen schließlich :)
MickyT
@flawr Um ehrlich zu sein, ich hätte nicht gedacht, dass es funktionieren würde. Sehr brachiale Methode.
MickyT
12

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".

stolzer haskeller
quelle
Es ist eine interessante Funktion. Normalerweise existieren solche Funktionen, um die beste rationale Annäherung an eine Zahl in den wenigsten Schritten zu finden, was nachweislich unter Verwendung von abgeschnittenen fortgesetzten Bruchsignalen erreicht wird. Alternativ ist es eher eine akademische Neugier, einen Bruch mit dem niedrigsten Nenner zu finden. Normalerweise würde man nicht erwarten, dass es sich um eine Standardbibliotheksfunktion handelt.
COTO
4
@ COTO Nun, das ist Haskell, es steckt voller akademischer Forschung.
stolzer Haskeller
7

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.

Martin Ender
quelle
4

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.

Übereinstimmen
quelle
2
haha ich habe genau die selbe lösung benutzt. Schade, in Haskell ist es länger. Übrigens sieht es nicht so aus, als würde Ihre Lösung eine Zeichenfolge als Eingabe verwenden, wie es die Spezifikation erfordert.
stolzer Haskeller
Warten Sie, die Eingabe war eine Zeichenfolge? Dang, das heißt, ich kann ein paar Sachen aus dem Code ziehen.
Tally
Ihre Ausgabe für 0.001stimmt nicht mit dem OP überein, da Rationalizenicht die Einschränkung besteht, den Nenner zu minimieren. Wie ich dem stolzen Haskeller bereits sagte, ist eine rationale Approximationsfunktion zur Minimierung des Nenners hochgradig esoterisch (kurz gesagt, weil sie eine miese und ineffiziente Methode zur Approximation von Zahlen ist). Normalerweise würde ich nicht erwarten, dass es sich um eine Standardbibliotheksfunktion handelt.
COTO
@COTO Laut Dokumentation wird der Nenner jedoch minimiert.
Martin Ender
@ MartinBüttner: Es ist schon interessant, dass es ausgibt 1/999. 999 wird der (akzeptable) kleinste Nenner nur für einen Fehler zwischen ungefähr 1e-6 und 2e-6. Die Fehlergrenze liegt eindeutig bei 5e-4. Was auch immer Mathematica in diesem Fall tut, es funktioniert definitiv nicht nach Spezifikation. : P
COTO
4

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)]
Steve
quelle
3

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

TwiNight
quelle
2

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 .

Digitales Trauma
quelle
2

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 ?

krs013
quelle
Nein, ich feiere nur den Tag der Annäherung. = P Aber ich habe gerade bemerkt, dass | 355/113 - pi | <10 ^ -6 =)
Fehler
2

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*)
Digitales Trauma
quelle
2

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.

Franki
quelle
1
Sie sollten wahrscheinlich die neue Version auf der Vorderseite der Post bewegen
stolz haskeller
@ proudhaskeller erledigt
Franki
1

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;}}}
RT
quelle
Tatsächlich hat die Definition von in der Haskell-Bibliotheksimplementierung ( hackage.haskell.org/package/base-4.7.0.1/docs/src/… ) approxRationalnur eine rekursive Hilfsfunktion und keine Schleife mehr.
stolzer Haskeller
Nun
Ich wollte nicht sagen, dass die Lösungen von irgendjemandem ungültig sind, sondern nur eine ohne eingebaute Rationalisierung posten :)
RT
Natürlich, aber die Tatsache, dass die Definition selbst keine Schleifen hat, ist nett und genau, Sie haben in Ihrem Beitrag geschrieben: "Soweit wir wissen, haben die internen rationalize () -Funktionen moderner Sprachen viele interne Schleifen." also habe ich es überprüft.
stolzer Haskeller
Wie funktioniert die Lösung überhaupt?
stolzer Haskeller
1

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
$ 
Digitales Trauma
quelle
Sollte eine ziemlich einfache intPortierung auf c
Digital Trauma
1

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]
edc65
quelle