Frações contínuas são expressões que descrevem frações iterativamente. Eles podem ser representados graficamente:
Ou eles podem ser representados como uma lista de valores: [a0; a1, a2, a3, ... an]
O desafio:
pegue um número base: e uma lista de valores do denominador: e simplifique a fração continuada para uma fração racional simplificada: retorne ou imprima numerador e denominador separadamente.a0
[a1, a2, a3, ... an]
Exemplos:
√19 : [4;2,1,3,1,2]: 170/39
ℯ: [1;0,1,1,2,1,1]: 19/7
π: [3;7,15,1,292,1]: 104348/33215
ϕ: [1;1,1,1,1,1]: 13/8
Exemplo de implementação: (python)
def foo(base, sequence):
numerator = 1
denominator = sequence[-1]
for d in sequence[-2::-1]:
temp = denominator
denominator = d * denominator + numerator
numerator = temp
return numerator + base * denominator, denominator
Ganhando:
código mais curto em bytes: --no builtins que fazem todo o problema permitido--
code-golf
math
rational-numbers
Aaron
fonte
fonte
2.002
possa ser expressa como2002/1000
. Tecnicamente, é uma "fração única", você provavelmente quer dizer "uma fração única, na sua forma mais simples".Respostas:
J,
85 bytesO mesmo que esse , mas usa um build-in para racionals.
O argumento é {a0, a1, a2, a3, ...} como uma lista de J números racionais de precisão estendida. O resultado é a fração como um número racional de precisão estendida J.
(+%)
o mais-recíproco de/
redução ao longoExperimente online!
-3 graças a milhas .
fonte
∘
.Haskell,
373618 bytesEsta função espera o
Ratio
tipo de Haskell como entrada. Exemplo de uso:Nota: um explícito
Ratio
na lista de entrada (4%1
) é suficiente, os sistemas de tipos determinam que os outros também devem serRatio
s.Editar: @Lynn salvou um byte. Obrigado!
Edit II: removeu o
import
(veja esta discussão na meta ).fonte
import
. No entanto, para chamá-lo, você precisa alimentarRatio
s que precisam doimport
. Devo adicionarimport
ou não à contagem de bytes?from fractions import Fraction
para fazer operações comFraction
objetos, a declaração de importação também é contada.Ratio
que só podem ser construídos via%
, o que requer a importação. Normalmente, não contamos bytes para a sobrecarga de chamada, apenas para a própria função.GolfScript , 13 bytes
Experimente online!
Yay pelas razões ocultas do GolfScript . :)
Explicação
O único tipo de número "oficial" do GolfScript é números inteiros. Mas o operador de exponenciação não converte seu resultado para inteiro e, convenientemente, o resultado nativo de uma exponenciação inteira em Ruby (a linguagem do intérprete do GolfScript) é um número racional. Assim, podemos facilmente obter frações elevando algo ao poder de -1. Convenientemente, queremos recíprocos de qualquer maneira ...
fonte
Mathematica,
2322 bytesEssencialmente uma porta da minha resposta GolfScript . Aqui estão algumas alternativas:
Para 24 bytes, podemos escrever uma função variável recursiva:
Por 21 bytes, podemos até definir um "operador variável", mas sua convenção de chamada seria tão estranha que relutarei em contar esta:
Você teria que chamar isso com uma sequência dos valores de entrada, por exemplo,
±Sequence[3, 7, 15, 1, 292, 1]
ou±##&[3, 7, 15, 1, 292, 1]
.E também para 21 bytes, haveria o (proibido) interno:
fonte
LabVIEW, 36 bytes equivalentes
Implementação ingênua e bastante direta, usando o algoritmo do OP. Existe uma maneira melhor de fazer isso?
fonte
Dyalog APL , 10 bytes
Nem usa um build-in para fins racionais.
Pega {a 0 , a 1 , a 2 , a 3 , ...} como argumento, retorna {denominador, numerador}.
1(,÷∨)
1-anexado a dividido pelo GCD de 1 e+∘÷
mais o recíproco de/
redução ao longoTryAPL online!
fonte
Python 2, 62 bytes
Infelizmente, não é tão bom assim (veja a resposta do @ xnor para abreviar), mas calcula a fração sem precisar reverter a entrada. Isso usa a abordagem "tabela mágica" para convergentes - dadas as duas últimas frações
a/c
eb/d
, a próxima fração é(n*b+a)/(n*c+d)
.Por exemplo, para pi:
Podemos ver que
15*22 + 3 = 333
,15*7 + 1 = 106
,1*333 + 22 = 355
,1*106 + 7 = 113
, etc.fonte
M, 5 bytes
A entrada é uma lista dos valores
[a0, a1, ..., aN]
e gera um número racional.Experimente online! ou Verifique todos os casos de teste.
Explicação
fonte
Haskell, 30 bytes
Adiciona recursivamente cada camada que sai, atualizando
n/d
parah+(1/(n/d))
, que é igual ah+d/n
ou(h*n+d)/n
. A fração é armazenada como uma tupla de(num,denom)
. A fração inicial de(1,0)
inversões para a0/1
qual é0
.fonte
Python, 50 bytes
Constrói a fração contínua a partir do final da lista indo para trás, repetidamente atualizar a fração
n/d
sobre o último elementox
comon/d -> 1+1/(n/d) == (x*n+d)/n
.fonte
Lisp comum, 54
Uma dobra um pouco detalhada à direita:
Testes
fonte
Julia (53 bytes)
Esta é minha primeira vez em Julia, se eu esquecesse um iterador que poderia ter perdido mais bytes, avise-me. Aqui está uma dica para quem não sabe qual idioma escolher para este desafio específico: https://en.wikipedia.org/wiki/Rational_data_type
fonte
∘
) em vez de uma função dex∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
x->foldr((x,y)->x+1//y,x)
(o mesmo que a solução Haskell). uso:(x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2])
Javascript (ES6), 55 bytes
Casos de teste
fonte
CJam ,
1816 bytesIntérprete online .
fonte
05AB1E ,
1917 bytesExplicação
Entrada tomada como uma lista de números
Experimente online!
fonte
JavaScript (ES6), 44 bytes
fonte
Javascript (ES6), 50 bytes
É graças à resposta de Arnauld, antes de vê-lo, fiquei preso a 66 bytes:
Exemplo:
Chamada:
f([1, 0, 1, 1, 2, 1, 1])
Saída:
Array [ 19, 7 ]
fonte
Perl 6 , 24 bytes
Explicação:
1 / * + *
é um lambda com dois parâmetros (*
) que pega o inverso do primeiro e adiciona o segundo. (retorna um rato )R[&(…)]
usa isso como se fosse um operador infix e o inverte.(incluindo torná-lo associativo certo)
[…](@_)
pega isso e usa para reduzir a entrada.… .nude
retorna a nu merator e de nominator do Rato .{ … }
torne-o um bloco nu lambda com parâmetro implícito@_
.Uso:
fonte
Zephyr , 145 bytes
Zephyr é a primeira linguagem de programação que eu já criei. Ele foi projetado para ser intuitivo e ter sintaxe limpa - ao invés de custas de concisão. Por que estou jogando golfe, você pergunta? Porque, diferente de qualquer idioma que eu escrevi desde então, ele tem um
Fraction
tipo embutido . Você pode até usar o operador de divisão/
como um operador unário para "inverso" (um recurso que eu emprestei para o Pip).Agora, existem limitações significativas. O maior problema para esse desafio é que as matrizes devem ser definidas com tamanho fixo, o que significa que o programa começa lendo o tamanho da matriz do usuário. (Espero que esteja tudo bem; a alternativa é codificar o tamanho.) Há também o pequeno problema de que a precedência do operador não existe, o que significa que as expressões multioperador precisam ter parênteses.
Aqui está um exemplo de execução:
fonte
Ruby, 34 bytes
Isso realiza uma dobra à direita (invertendo e depois à esquerda), adicionando cada elemento a 1 sobre o total atual (os elementos à direita). Ruby tem o tipo Rational, o que é muito bom. E racionais literais são um número com o sufixo
r
.fonte
Stax , 4 bytes
Execute e depure
Por menor que seja, não é um built-in. Os racionais incorporados ajudam bastante. Descompactado para ascii, o programa é
rksu+
.(a, b) => (a + 1/b)
.fonte
APL (NARS), 15 + 1 caracteres, 30 + 2 bytes
Tradução em Apl (Nars) da solução Adam J ... a entrada permitida para essa função será toda a lista de números inteiros, onde o primeiro elemento será do tipo racional. Teste:
então seriam 15 caracteres como comprimento da função e 1 caractere para "x" para inserir o tipo de entrada que eu quero e sair do tipo que eu quero ...
fonte