Lorsque vous convertissez une fraction en nombre décimal et que vous souhaitez stocker ce nombre, vous devez souvent l'arrondir, car vous ne souhaitez utiliser qu'une certaine quantité de mémoire. Disons que vous ne pouvez stocker que 5 chiffres décimaux, puis 5/3 devient 1,6667. Si vous ne pouvez stocker que 2 chiffres décimaux, ce sera 1,7 (en supposant maintenant qu'il est toujours compris entre 0 et 9,99 ...).

Si vous essayez maintenant d'inverser ce processus avec 1.7 et que vous souhaitez récupérer votre fraction, cela peut être difficile, car vous savez que 1.7 n'est qu'un nombre arrondi. Bien sûr, vous pouvez essayer le 17/10 mais c'est plutôt une fraction "moche" par rapport au 5/3 "élégant".

Le but est donc maintenant de trouver la fraction a / b avec le plus petit dénominateur b, ce qui donne le nombre décimal arrondi lorsqu'il est correctement arrondi.

Détails

L'entrée contient une chaîne avec un nombre de 1 à 5 chiffres compris entre 0 (y compris) et 10 (non compris) avec un '.' après le premier chiffre. Disons que ndénote le nombre de chiffres. La sortie doit être une liste / un tableau de deux nombres entiers [numerator, denominator]ou un type de données rationnel (vous pouvez créer le vôtre ou utiliser la fonction intégrée) où le numérateur est non négatif et le dénominateur est positif. Le numérateur / dénominateur de fraction doit être égal à l'entrée lorsqu'il est correctement arrondi à des nchiffres (ce qui signifie des n-1chiffres après la virgule décimale).

Restriction: une seule instruction de boucle autorisée. Cela signifie que vous ne pouvez utiliser qu'une seule instruction de bouclage (comme forou whileou gotoetc. ainsi que des boucles fonctionnelles comme mapou foldqui appliquent du code à chaque élément d'une liste / tableau) dans tout votre code, mais vous êtes libre d'en abuser ou utiliser la récursivité, etc.

Vous devez écrire une fonction. Si votre langue n'a pas de fonctions (ou même si c'est le cas), vous pouvez également supposer que l'entrée est stockée dans une variable (ou entrée via stdin) et imprimer le résultat ou l'écrire dans un fichier. Le plus petit nombre d'octets gagne.

Arrondi

L'arrondi doit suivre les règles d'arrondi «conventionnelles», c'est-à-dire que si le dernier chiffre qui sera coupé est 5 ou plus, vous arrondirez et vous arrondirez vers le bas pour tous les autres cas, par exemple:

4,5494 résultera de l'arrondi à

• 1 chiffre: 5
• 2 chiffres: 4,5
• 3 chiffres: 4,55
• 4 chiffres: 4.549

Exemples

Veuillez inclure les cas de test suivants et d'autres cas «intéressants»:

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 octets

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

Suppose que la chaîne d'entrée est stockée dans Q, ce qui est explicitement autorisé par la question. Essayez-le en ligne.

Cas de test

$ 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

Comment ça marche

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

Bien que T-SQL ne soit pas vraiment adapté à ce genre de choses, il est amusant d'essayer. La performance devient vraiment mauvaise plus le dénominateur est élevé. Il est limité à un dénominateur de 1000.

L'entrée est une variable flottante @

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

Une ventilation de la requête

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

si seulement les noms n'étaient pas si longs ...

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

il s'agit d'une fonction renvoyant une Rationalvaleur.

explication: la fonction approxRationalest une fonction qui prend un nombre flottant et un flottant epsilon et renvoie le rationnel le plus simple qui est en distance epsilon de l'entrée. fondamentalement, renvoie l'approximation la plus simple du flotteur à un rationnel dans une distance "d'erreur pardonnable".

exploitons cette fonction pour notre usage. pour cela, nous devrons déterminer quelle est la surface des flotteurs qui arrondissent au nombre donné. puis obtenir ceci dans la approxRationalfonction nous obtiendra la réponse.

essayons 1.7, par exemple. le flotteur le plus bas arrondi à 1,7 est 1,65. une valeur inférieure ne sera pas arrondie à 1,7. de même, la limite supérieure des flotteurs arrondis à 1,7 est de 1,75.
les deux limites sont les limites sont le nombre d'entrée +/- 0,05. on peut facilement montrer que cette distance est toujours5 * 10 ^ -(the length of the input - 1) (le -1 est parce qu'il y a toujours un '.' dans l'entrée). à partir d'ici, le code est assez simple.

cas de test:

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

malheureusement, cela ne fonctionne pas sur "0". parce que la fonction d'analyseur de Haskell ne reconnaît pas un .à la fin d'un flottant. cela peut être fixé pour 5 octets en remplaçant read spar read$s++"0".

Rubis, 127 125 octets

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}

Définit une fonction fqui renvoie le résultat sous la forme d'un Rational. Par exemple, si vous ajoutez ce code

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

Vous recevez

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

La boucle est au-dessus des dénominateurs. Je commence par la fraction complète, par exemple 31416/10000pour le dernier exemple. Ensuite, je décrémente le dénominateur, décrémente proportionnellement le numérateur (et l'arrondis). Si les arrondis rationnels résultants sont identiques au nombre d'entrée, je me souviens d'une nouvelle meilleure fraction.

Mathematica, 49 53 caractères

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

Usage:

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

Sortie:

5/3

Cas de test:

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

Le cas de 0,001 me semble étrange; car la fonction rationaliser n'a pas fonctionné selon sa description, quand elle n'a pas trouvé le cas 1/667. Il doit afficher le nombre avec le plus petit dénominateur qui se trouve dans les limites spécifiées.

Python 2.7+, 111 caractères

Preuve que vous pouvez écrire un code horrible dans n'importe quelle langue:

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

Sortie

>>> [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

Tant que vous ne comptez pas evalet toStringque des boucles

Explication

L'approche consiste à itérer sur 1 à 10000 comme dénominateur et à calculer le numérateur qui correspond le mieux au flottant, puis à vérifier si l'erreur se situe dans les limites. Enfin, sélectionnez la plus petite paire parmi toutes les fractions trouvées.

(⍎x←⍞)Prendre une chaîne de caractères à partir de l'écran, attribuer à xet évaluer
⍳1e5Générer un tableau de 1 à 10000
{...}¨Pour chaque élément du tableau, appeler la fonction avec lui et (⍎x←⍞)et les arguments (boucle)

⍺×⍵Multipliez les arguments
⌊.5+Arrondissez (en ajoutant 0,5 puis en arrondissant vers le bas)
n←Attribuez àn
⍺-⍵÷⍨ Diviser par l'argument de droite, puis soustrayez de l'argument de gauche
(10*⍴x)×Multipliez par 10 à la puissance de "longueur de x"
|Prenez la valeur absolue
50>Vérifiez si moins de 50 (la longueur de xest 2 de plus que le nombre de dp, utilisez donc 50 ici au lieu de 0,5)
:n ⍵⋄''Si la vérification précédente renvoie vrai, retournez le tableau de net l'argument de droite, sinon retournez une chaîne vide.

⍎⍕ toStringpuis evalpour obtenir un tableau de tous les nombres du tableau
2↑Sélectionnez uniquement les 2 premiers éléments, qui est la première paire numérateur-dénominateur trouvée

GNU dc, 72 octets

Pas de boucles - DC ne les a même pas. Au lieu de cela, le contrôle provient d'une seule macro récursive de queue - idiomatique pour dc.

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

Sortie:

$ 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
$ 

Phew. Explication partielle dans cette réponse .

Mathematica, 111 caractères

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]&

Vraiment assez simple, et je ne pense pas que cela converge nulle part aussi vite que les autres solutions, car le numérateur et le dénominateur ne font qu'un incrément. Je voulais surtout trouver la solution simple à cela. Je vais devoir voir les autres réponses et voir ce qui se passe là-bas.

Sortie

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

Quelqu'un ici célèbre-t-il le jour de l'approximation de Pi ?

Applescript,> 300 octets

Je voulais le faire dans une langue qui fait nativement le type d'arrondi requis. Il s'avère qu'Applescript correspond au projet de loi. Ensuite, j'ai vu l'énumération rounding as taught in schoolet je n'ai pas pu résister à son utilisation, malgré l'incompétence flagrante d'Applescript à des fins de golf:

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

Cela peut être joué un peu plus, mais cela n'en vaut probablement pas la peine.

Sortie:

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

BC, 151 148 octets

Edit - version plus rapide et plus courte

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}}}

même cas de test.

Beaucoup de choses sont similaires à la version précédente, mais au lieu d'essayer toutes les combinaisons n / d possibles, nous escaladons les résidus de v et les quotients arrières des multiples m == v * d et des dénominateurs d. Encore une fois, la précision du calcul est la même.

Le voici démêlé:

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
        }
    }
}

Cette version n'a vraiment qu'une seule boucle et ne fait que $ \ Theta \ left (\ operatorname {fractional_decimals} (v) \ right) $ opérations arithmétiques.

Original - version lente

Cette fonction calcule le plus petit nominateur n et le plus petit dénominateur d de sorte que la fraction n / d arrondie aux chiffres fractionnaires_décimaux (v) soit égale à une valeur décimale donnée v.

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}

cas de test:

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

Et le voici démêlé:

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
}

J'avoue que j'ai un peu triché en émulant une deuxième boucle interne à l'intérieur d'une seule boucle externe, mais sans utiliser d'autres instructions de boucle. Et c'est pourquoi il effectue en réalité $ \ Theta \ left (v \ operatorname {fractional_decimals} (v) ^ 2 \ right) $ des opérations arithmétiques.

C, 233

Cela fonctionne en appelant une fonction de rationalisation r () avec un dénominateur de départ de 1. La fonction commence à incrémenter un numérateur et à vérifier à chaque incrément si le nombre résultant, lorsqu'il est arrondi au même nombre de chiffres que l'original, a la même chaîne représentation comme l'original. Une fois que le numérateur a été tellement incrémenté que le résultat est supérieur à l'original, la fonction incrémente le dénominateur et s'appelle.

Bien sûr, cela utilise beaucoup plus de code, mais je pense que l'esprit du problème exonère cette approche à nu; pour tout ce que nous savons, les fonctions rationalize () internes des langages modernes ont beaucoup de boucles internes.

Notez que cela ne fonctionne pas pour une entrée de "0". car ce n'est pas une façon standard d'écrire un flottant, donc quand il réécrit le flottant dans la chaîne, le résultat ne sera jamais un "0".

Les spécifications veulent une fonction qui renvoie des valeurs au lieu de simplement imprimer à l'écran, d'où le passage d'arguments.

Code (non golfé):

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;
        }
    }
}

Usage:

#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;
}

Code golf:

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 octets

Comme explication partielle de cette réponse , elle est ici portée à bash:

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

Notamment:

• bash a une arithmétique entière uniquement. Nous avons donc tout mis à l'échelle de manière appropriée par 2 * 10 ^ (nombre de chiffres fractionnaires).
• tours bash vers le bas à l' entier le plus proche; le 2 dans l'expression ci-dessus est donc nous pouvons plutôt arrondir à l'entier le plus proche ( vers le haut ou vers le bas ).
• Une seule boucle
• nous vérifions si le dépassement ou le dépassement rationnel de la décimale et incrémentons le dénominateur ou le numérateur en conséquence.

Sortie:

$ 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]

Non golfé

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]
}

Tester dans la console FireFox / FireBug

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

Sortie

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