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 n
denota 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 n
dígitos (o que significa n-1
dí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 for
ou while
ou goto
etc., bem como loops funcionais como map
ou fold
que 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
repeat
cria 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.for n in numbers: f(g(n))
é equivalente amap(f, map(g, numbers))
. A versão funcional usamap
duas vezes, isso realmente deve ser proibido?Respostas:
CJam,
414036 bytesSupõe que a sequência de entrada seja armazenada em Q, o que é explicitamente permitido pela pergunta. Experimente online.
Casos de teste
Como funciona
fonte
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 @
Um detalhamento da consulta
fonte
3.14159
e devidamente me deu355/113
Haskell,
6259se apenas os nomes não fossem tão longos ...
esta é uma função retornando um
Rational
valor.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
approxRational
funçã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:
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 substituindoread s
porread$s++"0"
.fonte
Ruby,
127125 bytesDefine uma função
f
que retorna o resultado como aRational
. Por exemplo, se você anexar este códigoVocê recebe
O loop está sobre denominadores. Estou começando com a fração completa, por exemplo,
31416/10000
para 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.fonte
Mathematica,
4953 caracteresUso:
Saída:
Casos de teste:
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.
fonte
0.001
não corresponde ao OP porqueRationalize
nã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.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. : PPython 2.7+, 111 caracteres
Prova de que você pode escrever código horrível em qualquer idioma:
Saída
fonte
APL, 50
Contanto que você não conte
eval
etoString
como loopsExplicaçã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 ax
e avalie⍳1e5
Gerar 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 an
⍺-⍵÷⍨
Dividir pelo argumento da direita e subtraia do argumento da esquerda(10*⍴x)×
Multiplique por 10 à potência de "comprimento dex
"|
Obter valor absoluto50>
Verifique se menos de 50 (comprimento dex
2 é 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 den
e o argumento correto, caso contrário, retorne uma string vazia.⍎⍕
toString
e, em seguida,eval
para obter uma matriz de todos os números da matriz2↑
Selecione apenas os 2 primeiros elementos, que é o primeiro par numerador-denominador encontradofonte
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.
Saída:
Ufa. Explicação parcial nesta resposta .
fonte
Mathematica, 111 caracteres
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
Alguém aqui celebra o Dia da Aproximação do Pi ?
fonte
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 school
e não pude resistir ao seu uso, apesar da flagrante falta de competitividade do Applescript para fins de golfe:Isso pode ser jogado um pouco mais, mas provavelmente não vale a pena.
Saída:
fonte
BC,
151148 bytesEditar - versão mais rápida e mais curta
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:
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.
caso de teste:
E aqui está desembaraçado:
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) $.
fonte
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):
Uso:
Código de golfe:
fonte
approxRational
possui Apenas uma função auxiliar recursiva, e não há mais looping que isso.Pure Bash, 92 bytes
Como explicação parcial para esta resposta , aqui é portado para o bash:
Notavelmente:
Saída:
fonte
int
porta bastante simples para cJavaScript (E6) 85
Ungolfed
Teste no console do FireFox / FireBug
Saída
fonte