Frações não arredondadas

22

Quando você converte uma fração em um número decimal e deseja armazenar esse número, geralmente precisa arredondá-lo, porque deseja usar apenas uma certa quantidade de memória. Digamos que você possa armazenar apenas 5 dígitos decimais e 5/3 se tornará 1,6667. Se você puder armazenar apenas 2 dígitos decimais, será 1,7 (agora assumindo que esteja sempre entre 0 e 9,99 ...).

Se agora você tenta reverter esse processo com 1.7 e deseja recuperar sua fração, isso pode ser difícil, pois você sabe que 1.7 é apenas um número arredondado. Claro que você pode tentar 17/10, mas essa é uma fração 'feia' em comparação com a 'elegante' 5/3.

Portanto, o objetivo agora é encontrar a fração a / b com o mínimo denominador b, que resulta no número decimal arredondado quando corretamente arredondado.

Detalhes

A entrada contém uma sequência com um número de 1 a 5 dígitos que está entre 0 (inclusive) e 10 (não incluindo) com um '.' após o primeiro dígito. Digamos que ndenota o número de dígitos. A saída deve ser uma lista / matriz de dois números inteiros [numerator, denominator]ou um tipo de dados racional (você pode criar o seu próprio ou usar interno) em que o numerador não é negativo e o denominador é positivo. O numerador / denominador da fração deve ser igual à entrada quando arredondado corretamente para ndígitos (o que significa n-1dígitos após o ponto decimal).

Restrição: apenas uma instrução de loop é permitida. Isso significa que você pode usar apenas uma única instrução de loop (como forou whileou gotoetc., bem como loops funcionais como mapou foldque aplicam código a todos os elementos de uma lista / matriz) em todo o código, mas você pode 'abusar' dela ou use recursão etc.

Você deve escrever uma função. Se o seu idioma não possuir funções (ou mesmo se houver), você poderá assumir como alternativa que a entrada está armazenada em uma variável (ou entrada via stdin) e imprimir o resultado ou gravá-lo em um arquivo. O menor número de bytes vence.

Arredondamento

O arredondamento deve seguir as regras de arredondamento "convencionais", ou seja, se o último dígito a ser cortado for 5 ou superior, você arredondará para cima e arredondará para outros casos, por exemplo:

4.5494 resultará ao arredondar para

  • 1 dígito: 5
  • 2 dígitos: 4,5
  • 3 dígitos: 4,55
  • 4 dígitos: 4.549

Exemplos

Inclua os seguintes casos de teste e outros 'interessantes':

Input 1.7     Output 5/3
Input 0.      Output 0/1
Input 0.001   Output 1/667
Input 3.1416  Output 355/113
flawr
fonte
1
Mas nas linguagens funcionais não existe um loop. Um exemplo de inimigo em haskell repeatcria uma lista infinita de seus argumentos. Parece que faz um loop, mas na verdade tem complexidade de tempo de O (1). Mas acho que classificar cada caso individualmente é melhor do que não permitir linguagens funcionais.
proud haskeller,
3
Não gosto da definição atual de "loop". Em Python, por exemplo, for n in numbers: f(g(n))é equivalente a map(f, map(g, numbers)). A versão funcional usa mapduas vezes, isso realmente deve ser proibido?
Flornquake 23/09/14
1
@ MartinBüttner eu falei sobre o caso que linguagens funcionais seria anulado por causa da ambigüidade
haskeller orgulhoso
1
Lamento não poder realmente contribuir para essa discussão, pois meu conhecimento sobre programação funcional é basicamente zero. Se você tem uma solução da qual não tem certeza se está em conformidade com as 'regras', envie-a assim mesmo! No final, é suposto ser um desafio divertido e educacional!
flawr
2
@ Dennis Não, isso foi lamentável, você pode enviá-lo da forma que quiser, a principal idéia por trás desse parágrafo era que você não deveria ter uma desvantagem se o seu idioma usar mais bytes para 'ler' o número de entrada.
flawr

Respostas:

4

CJam, 41 40 36 bytes

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

Supõe que a sequência de entrada seja armazenada em Q, o que é explicitamente permitido pela pergunta. Experimente online.

Casos de teste

$ 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

Como funciona

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
fonte
15

T-SQL 254

Embora o T-SQL não seja realmente adequado para esse tipo de coisa, é divertido tentar. O desempenho fica muito ruim quanto maior o denominador. É limitado a um denominador de 1000.

Input é uma variável flutuante @

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

Um detalhamento da consulta

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
fonte
+1. Eu amo isso. Eu coloquei em 3.14159e devidamente me deu355/113
Tom Chantler
1
+1 Eu nunca esperava ver uma linguagem SQL aqui !!!
flawr
@TomChantler eu suspeito que você quer dizer, eventualmente :)
MickyT
@ flawr Para ser sincero, não achei que fosse dar certo .. método de força muito bruta.
MickyT
12

Haskell, 62 59

se apenas os nomes não fossem tão longos ...

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

esta é uma função retornando um Rationalvalor.

explicação: a função approxRationalé uma função que pega um número flutuante e um epsilon flutuante e retorna o racional mais simples que está na distância epsilon da entrada. basicamente, retorna a aproximação mais simples do flutuador para uma racional em uma distância de "erro perdoável".

vamos explorar esta função para nosso uso. para isso, precisaremos descobrir qual é a área dos carros alegóricos que arredondam para o número especificado. colocar isso na approxRationalfunção nos dará a resposta.

vamos tentar 1.7, por exemplo. o flutuador mais baixo que chega a 1,7 é 1,65. qualquer valor mais baixo não arredondará para 1,7. da mesma forma, o limite superior dos carros alegóricos que arredondam para 1,7 é 1,75.
ambos os limites são os limites são o número de entrada +/- 0,05. pode-se facilmente mostrar que essa distância é sempre 5 * 10 ^ -(the length of the input - 1)(o -1 é porque sempre existe um '.' na entrada). daqui o código é bem simples.

casos de teste:

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

infelizmente não funciona em "0". porque a função do analisador de Haskell não reconhece a .no final de um float. isso pode ser corrigido por 5 bytes substituindo read spor read$s++"0".

orgulhoso haskeller
fonte
É uma função interessante de ter. Normalmente, essas funções existem com o objetivo de encontrar a melhor aproximação racional de um número nas poucas etapas, o que é comprovadamente realizado usando representações de frações contínuas truncadas. Como alternativa, encontrar uma fração com o menor denominador é mais uma curiosidade acadêmica. Normalmente, não se espera encontrá-lo como uma função de biblioteca padrão.
COTO 23/09
4
@COTO Bem, este é Haskell, está cheio de pesquisas acadêmicas.
proud 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}

Define uma função fque retorna o resultado como a Rational. Por exemplo, se você anexar este código

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

Você recebe

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

O loop está sobre denominadores. Estou começando com a fração completa, por exemplo, 31416/10000para o último exemplo. Então, eu estou diminuindo o denominador, diminuindo proporcionalmente o numerador (e arredondando-o). Se o racional resultante arredondar para o mesmo que o número de entrada, estou lembrando de uma nova melhor fração.

Martin Ender
fonte
4

Mathematica, 49 53 caracteres

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

Uso:

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

Saída:

5/3

Casos de teste:

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

O caso 0,001 me parece estranho; como a função racionalizar não funcionava de acordo com sua descrição, quando não encontrou o caso 1/667. Ele deve gerar o número com o menor denominador dentro dos limites especificados.

Tally
fonte
2
haha eu usei exatamente a mesma solução. muito ruim em Haskell, é mais longo. Aliás, não parece que sua solução usa uma string como entrada, conforme exigido pelas especificações.
proud haskeller
Espere, a entrada era uma string? Caramba, isso significa que posso extrair algumas coisas do código.
Tally
Sua saída para 0.001não corresponde ao OP porque Rationalizenão está sob a restrição de minimizar o denominador. Como mencionei ao orgulhoso haskeller, uma função de aproximação racional sujeita a minimizar o denominador é altamente esotérica (em suma, porque é uma maneira péssima e ineficiente de aproximar números). Normalmente, eu não esperava que fosse uma função de biblioteca padrão.
COTO 23/09
@COTO De acordo com os documentos que não minimizar o denominador embora.
Martin Ender
@ MartinBüttner: É meio interessante o resultado 1/999. 999 torna-se o denominador mais baixo (aceitável) apenas para um erro entre aproximadamente 1e-6 e 2e-6. O erro vinculado é claramente 5e-4. Portanto, o que quer que o Mathematica esteja fazendo nesse caso, definitivamente não está funcionando conforme as especificações. : P
COTO 23/09
4

Python 2.7+, 111 caracteres

Prova de que você pode escrever código horrível em qualquer idioma:

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

Saída

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

APL, 50

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

Contanto que você não conte evale toStringcomo loops

Explicação

A abordagem é iterar mais de 1 a 10000 como denominador e calcular o numerador que mais se aproxima do flutuador, e depois verificar se o erro está dentro dos limites. Por fim, selecione o menor par de todas as frações encontradas.

(⍎x←⍞)Pegue a entrada de string da tela, atribua a xe avalie
⍳1e5Gerar array de 1 a 10000
{...}¨Para cada elemento do array, chame a função com ele (⍎x←⍞)ee argumentos (loop)

⍺×⍵Multiplique os argumentos
⌊.5+Arredondar (adicionando 0,5 e arredondando para baixo)
n←Atribua a n
⍺-⍵÷⍨Dividir pelo argumento da direita e subtraia do argumento da esquerda
(10*⍴x)×Multiplique por 10 à potência de "comprimento de x"
|Obter valor absoluto
50>Verifique se menos de 50 (comprimento de x2 é mais que o número de dp, use 50 aqui em vez de 0,5)
:n ⍵⋄''Se a verificação anterior retornar true, retorne a matriz de ne o argumento correto, caso contrário, retorne uma string vazia.

⍎⍕ toStringe, em seguida, evalpara obter uma matriz de todos os números da matriz
2↑Selecione apenas os 2 primeiros elementos, que é o primeiro par numerador-denominador encontrado

TwiNight
fonte
2

GNU dc, 72 bytes

Sem loops - o dc nem os possui. Em vez disso, o controle vem de uma única macro recursiva de cauda - idiomática para dc.

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

Saída:

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

Ufa. Explicação parcial nesta resposta .

Trauma Digital
fonte
2

Mathematica, 111 caracteres

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

Bem simples, na verdade, e não acho que converja para lugar algum tão rápido quanto as outras soluções, pois o numerador e o denominador apenas aumentam em uma. Eu queria principalmente encontrar a solução simples para isso. Vou ter que ver as outras respostas e ver que coisas inteligentes acontecem lá.

Saída

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

Alguém aqui celebra o Dia da Aproximação do Pi ?

krs013
fonte
Não, eu só estou comemorando dia tau aproximação = P Mas eu só notei que |. 355/113 - pi | <10 ^ -6 =)
flawr
2

Applescript,> 300 bytes

Eu queria fazer isso em um idioma que nativamente faça o tipo de arredondamento necessário. Acontece que o Applescript se encaixa na conta. Então vi o enum rounding as taught in schoole não pude resistir ao seu uso, apesar da flagrante falta de competitividade do Applescript para fins de golfe:

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

Isso pode ser jogado um pouco mais, mas provavelmente não vale a pena.

Saída:

(*5, 3*)
(*0, 1*)
(*1, 667*)
(*355, 113*)
Trauma Digital
fonte
2

BC, 151 148 bytes

Editar - versão mais rápida e mais curta

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

mesmo caso de teste.

Muito é semelhante à versão anterior, mas, em vez de tentar todas as combinações possíveis de n / d, subimos os resíduos de v e quocientes inversos de múltiplos m == v * de denominadores d. Novamente, a precisão do cálculo é a mesma.

Aqui está desembaraçado:

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

Esta versão realmente tem um mero loop único e faz apenas operações aritméticas $ \ Theta \ left (\ operatorname {fractal_decimals} (v) \ right) $.

Original - versão lenta

Essa função calcula o menor nominador n e denominador d, de modo que a fração n / d arredondada para dígitos fracionários_decimais (v) seja igual a um determinado valor decimal 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}

caso de teste:

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

E aqui está desembaraçado:

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
}

Admito que trapacei um pouco imitando um segundo loop interno dentro de um único loop externo, mas sem usar mais nenhuma instrução de loop. E é por isso que ele realmente faz operações aritméticas $ \ Theta \ left (v \ nome do operador {decimal_de_frações} (v) ^ 2 \ right) $.

Franki
fonte
1
você provavelmente deve mover a nova versão para a frente do pós
haskeller orgulhoso
@proudhaskeller done
Franki
1

C, 233

Isso funciona chamando uma função de racionalização r () com um denominador inicial de 1. A função começa a incrementar um numerador e verifica a cada incremento se o número resultante, quando arredondado para o mesmo número de dígitos que o original, tem a mesma string representação como o original. Depois que o numerador é incrementado tanto que o resultado é maior que o original, a função incrementa o denominador e chama a si mesma.

É claro que isso usa muito mais código, mas acho que o espírito do problema exonera essa abordagem básica; pelo que sabemos, as funções internas racionalize () das linguagens modernas têm muitos loops internos.

Observe que isso não funciona para uma entrada "0". porque essa não é uma maneira padrão de escrever um float, portanto, quando ele reescreve o float em string, o resultado nunca será um "0".

As especificações querem uma função que retorne valores, em vez de apenas imprimir na tela, daí a passagem de argumentos.

Código (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;
        }
    }
}

Uso:

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

Código de golfe:

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
fonte
na verdade, na implementação da biblioteca Haskell ( hackage.haskell.org/package/base-4.7.0.1/docs/src/… ), a definição de approxRationalpossui Apenas uma função auxiliar recursiva, e não há mais looping que isso.
proud haskeller
Bem, eu estava errado, ele realmente tem duas funções auxiliares recursiva, mas pela especificação é bom
haskeller orgulhoso
Eu não estava tentando dizer soluções que de ninguém eram inválidos, só queria postar um sem built-in racionalização :)
RT
é claro, mas o fato de a definição em si não ter loops é agradável e, de fato, você escreveu em seu post "pelo que sabemos, as funções internalize () internas das linguagens modernas têm muitos loops internos". então eu verifiquei.
proud haskeller
enfim, como a solução funciona?
proud haskeller,
1

Pure Bash, 92 bytes

Como explicação parcial para esta resposta , aqui é portado para o 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

Notavelmente:

  • O bash possui aritmética de número inteiro. Então, escalamos tudo de forma adequada em 2 * 10 ^ (número de dígitos fracionários).
  • bash arredonda para baixo para o número inteiro mais próximo; o 2 na expressão acima é para que possamos arredondar para o número inteiro mais próximo (para cima ou para baixo ).
  • Apenas um loop
  • verificamos se o racional ultrapassa ou ultrapassa o decimal e incrementamos o denominador ou numerador de acordo.

Saída:

$ 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
$ 
Trauma Digital
fonte
Deve ser uma intporta bastante simples para 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]
}

Teste no console do FireFox / FireBug

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

Saída

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