Simplifique uma fração continuada

21

Frações contínuas são expressões que descrevem frações iterativamente. Eles podem ser representados graficamente:

insira a descrição da imagem aqui

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

Aaron
fonte
Você deve deixar essa frase mais clara "e simplificar a fração continuada em uma única fração"; a menos que você pretenda que a expressão signifique um resultado 2.002possa ser expressa como 2002/1000. Tecnicamente, é uma "fração única", você provavelmente quer dizer "uma fração única, na sua forma mais simples".
Magic Octopus Urn
ponto @carusocomputing tomada .. embora eu não me sentiria muito ruim sobre 2/4 (ou similar) como ainda simplificou a estrutura fração múltiplos a uma única fração
Aaron
Hmm ... acho que há uma maneira de explorar isso, mas com a resposta de 13 bytes do golfscript, eu provavelmente teria que usar o MATL para vencer.
Magic Octopus Urn
@carusocomputing Eu diria que ir para ela ... Se você pode bater a resposta 13 byte, que seria incrível
Aaron
Você pode fazer o pi parar mais cedo - 355/113.
Thorbjørn Ravn Andersen

Respostas:

15

J, 8 5 bytes

O 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 longo

Experimente online!

-3 graças a milhas .

Adão
fonte
Se você considerar a entrada como uma lista de números inteiros estendidos, poderá salvar 3 bytes. Você também usou a divisão APL na explicação.
miles
@miles Obrigado. Não é possível chegar mais perto da proibição interna do que isso. Pena que J não tem um caractere de composição de gancho como o Dyalog APL .
Adám 14/09/16
O link do try J online está quebrado
Chiel ten Brinke 27/02
@ChieltenBrinke Thanks. Fixo.
Adám 27/02/18
12

Haskell, 37 36 18 bytes

foldr1$(.(1/)).(+)

Esta função espera o Ratiotipo de Haskell como entrada. Exemplo de uso:

Prelude Data.Ratio> ( foldr1$(.(1/)).(+) )  [4%1,2,1,3,1,2] 
170 % 39

Nota: um explícito Rationa lista de entrada ( 4%1) é suficiente, os sistemas de tipos determinam que os outros também devem ser Ratios.

Editar: @Lynn salvou um byte. Obrigado!

Edit II: removeu o import(veja esta discussão na meta ).

nimi
fonte
11
Oooh, bom caso de ponta. A função em si é polimórfica, portanto não precisa do import. No entanto, para chamá-lo, você precisa alimentar Ratios que precisam do import. Devo adicionar importou não à contagem de bytes?
nimi
11
Parece uma boa pergunta para a meta.
Martin Ender
Eu nunca usei Haskell, então me corrija se estiver errado, mas se o equivalente em python for: from fractions import Fractionpara fazer operações com Fractionobjetos, a declaração de importação também é contada.
Aaron
.. nós tivemos isso antes .
nimi
@ Aaron: o problema é: a definição da função não precisa da importação, porque é polimórfica. Quando você deseja chamá-lo, é necessário fornecer números do tipo Ratioque 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.
nimi
11

GolfScript , 13 bytes

~]-1%{\-1?+}*

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

~]     # Evaluate input and wrap all a_i in a list.
-1%    # Reverse the list so that a_n is at the start and a_0 at the end.
{      # Fold... (apply this block to each element from a_n-1 down to a_0, with
       # the previous result on the stack)
  \    #   Swap previous result with current a_i.
  -1?  #   Raise previous result to the power of -1, computing its reciprocal
       #   as a rational number.
  +    #   Add a_i.
}*
Martin Ender
fonte
11

Mathematica, 23 22 bytes

Fold[#2+1/#&]@*Reverse

Essencialmente uma porta da minha resposta GolfScript . Aqui estão algumas alternativas:

Para 24 bytes, podemos escrever uma função variável recursiva:

f@n_=n
n_~f~m__:=n+1/f@m

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:

±n_=n
n_ ±m__:=n+1/±m

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:

FromContinuedFraction
Martin Ender
fonte
10

LabVIEW, 36 bytes equivalentes

Implementação ingênua e bastante direta, usando o algoritmo do OP. Existe uma maneira melhor de fazer isso?

insira a descrição da imagem aqui

ijustlovemath
fonte
5
Seu diploma de engenharia elétrica está aparecendo.
Magic Octopus Urn
11
@ijustlovemath Props, mas ..... relevante
Aaron
Sim, é uma linguagem controversa, com certeza. Eu vejo o LabVIEW como o "Eu odeio a matemática" do mundo dos programadores. O problema não é a matemática em si, mas como é ensinada (ou muitas vezes a falta de ensino).
ijustlovemath
6

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(,÷∨) 1-anexado a dividido pelo GCD de 1 e

+∘÷ mais o recíproco de

/ redução ao longo

TryAPL online!

Adão
fonte
6

Python 2, 62 bytes

a=d=0
b=c=1
for n in input():a,b=b,n*b+a;c,d=d,n*d+c
print b,d

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/ce b/d, a próxima fração é (n*b+a)/(n*c+d).

Por exemplo, para pi:

          3    7    15     1      292        1

  0   1   3   22   333   355   103993   104348
  1   0   1    7   106   113    33102    33215

Podemos ver que 15*22 + 3 = 333, 15*7 + 1 = 106, 1*333 + 22 = 355, 1*106 + 7 = 113, etc.

Sp3000
fonte
4

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

Ṛİ+¥/  Input: list A
Ṛ      Reverse A
    /  Reduce A from left to right using
   ¥     A dyadic chain
 İ         Take the reciprocal of the left value
  +        Add the reciprocal to the right value
       Return and print implicitly
milhas
fonte
11
O que é isso? Algum novo dialeto da Jelly?
Adám 15/09/16
@miles na verdade 9 bytes sorry :(
Aaron
@ Adám É um velho garfo de geléia feito para matemática e simbologia. Aqui está o repositório do Github .
milhas
11
O @Aaron M usa a mesma página de código do Jelly e pode ser codificado usando um byte para cada caractere.
miles
@miles OK, adicionado .
Adám 15/09/16
4

Haskell, 30 bytes

foldr(\h(n,d)->(h*n+d,n))(1,0)

Adiciona recursivamente cada camada que sai, atualizando n/dpara h+(1/(n/d)), que é igual a h+d/nou (h*n+d)/n. A fração é armazenada como uma tupla de (num,denom). A fração inicial de (1,0)inversões para a 0/1qual é 0.

xnor
fonte
3

Python, 50 bytes

f=lambda l,n=1,d=0:l and f(l,l.pop()*n+d,n)or(n,d)

Constrói a fração contínua a partir do final da lista indo para trás, repetidamente atualizar a fração n/dsobre o último elemento xcomo n/d -> 1+1/(n/d) == (x*n+d)/n.

xnor
fonte
3

 Lisp comum, 54

Uma dobra um pouco detalhada à direita:

(lambda(s)(reduce(lambda(a r)(+(/ r)a))s :from-end t))

Testes

PASS  NAME  ACTUAL               EXPECTED
===============================================
T     √19   170/39               170/39              
T     ℯ     19/7                 19/7                
T     π     104348/33215         104348/33215        
T     ϕ     13/8                 13/8                
coredump
fonte
2

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

f(x,c)=(a=0;for b in x[end:-1:1];a=1//(b+a);end;a+c;)
  • Inverta a matriz de entrada.
  • Itere através dele com divisão racional.
  • Adicione c ao resultado decimal.
Urna de polvo mágico
fonte
pode guardar dois bytes pela definição de um operador (por exemplo ) em vez de uma função de
Tasos Papastylianou
também, alterar o loop for por um tempo e pop:x∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
Tasos Papastylianou
11
25: 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])
Fengyang Wang
Ooo ... Uma função de dobra reversa? Isso é bonito! Eu não mereço receber crédito por isso, haha.
Magic Octopus Urn
2

Javascript (ES6), 55 bytes

s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

Casos de teste

var f =
s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

console.log(f([4, 2, 1, 3, 1, 2]));
console.log(f([1, 0, 1, 1, 2, 1, 1]));
console.log(f([3, 7, 15, 1, 292, 1]));
console.log(f([1, 1, 1, 1, 1, 1]));

Arnauld
fonte
2

CJam , 18 16 bytes

XUq~W%{2$*+\}/]p

Intérprete online .

XU                  Push 1 and 0 to the stack
  q~W%              Push input, eval and reverse it
      {     }/      For each n in the reversed input...
       2$             Copy numerator
         *+           Calculate n*denominator + numerator
           \          Swap numerator and denominator
              ]p   Wrap in array and output
Sp3000
fonte
2

05AB1E , 19 17 bytes

R¬V¦vyY*X+YUV}YX)

Explicação

Entrada tomada como uma lista de números

                     # variable X is initialized as 1
R¬V¦                 # reverse the list, remove the first item and store it in variable Y
    v        }       # for each item N left in list
     yY*X+  V        # store N*Y+X in Y
          YU         # store Y in X
              YX)    # wrap X and Y in a list

Experimente online!

Emigna
fonte
2

JavaScript (ES6), 44 bytes

a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])
Neil
fonte
1

Javascript (ES6), 50 bytes

f=(s,n=1,d=s.pop())=>s+""?f(s,d,s.pop()*d+n):[d,n]

É graças à resposta de Arnauld, antes de vê-lo, fiquei preso a 66 bytes:

f=(b,s,i=s.length-1,n=1,d=s[i])=>i?f(b,s,--i,d,s[i]*d+n):[n+b*d,d]

Exemplo:
Chamada: f([1, 0, 1, 1, 2, 1, 1])
Saída:Array [ 19, 7 ]

Hedi
fonte
1

Perl 6 , 24 bytes

{[R[&(1/*+*)]](@_).nude}

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.

  • … .nuderetorna a nu merator e de nominator do Rato .

  • { … }torne-o um bloco nu lambda com parâmetro implícito @_.

Uso:

say {[R[&(1/*+*)]](@_).nude}(3,7,15,1,292,1) #*/# (104348 33215)

my &code = {[R[&(1/*+*)]](@_).nude}; # stupid highlighter */

say code 4,2,1,3,1,2;    # (170 39)
say code 1,0,1,1,2,1,1;  # (19 7)
say code 1,1,1,1,1,1;    # (13 8)
Brad Gilbert b2gills
fonte
1

Zephyr , 145 bytes

input n as Integer
set a to Array(n)
for i from 1to n
input a[i]as Integer
next
set r to a[n]
for i from 1to n-1
set r to(/r)+a[n-i]
next
print r

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 Fractiontipo 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:

C:\Zephyr> python zephyr.py contfrac.zeph
6
1
1
1
1
1
1
13/8
DLosc
fonte
1

Ruby, 34 bytes

->a{a.reverse.inject{|b,i|i+1r/b}}

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.

IMP1
fonte
1

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

  1. Inverta a matriz.
  2. Dobre a matriz usando (a, b) => (a + 1/b).
recursivo
fonte
1

APL (NARS), 15 + 1 caracteres, 30 + 2 bytes

{1=≢⍵:↑⍵⋄+∘÷/⍵}

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:

  f←{1=≢⍵:↑⍵⋄+∘÷/⍵}      
  f 4x 2 1 3 1 2
170r39 
  f 1x 0 1 1 2 1 1
19r7 
  f 3x 7 15 1 292 1
104348r33215 
  f 1x 1 1 1 1 1
13r8 
  f 3x 89 888 999 11 222 373 7282 9272 3839 2828 
158824716824887954093160207727r52744031585005490644982548907 
  f ,0x
0 
  f ,9x
9 

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

RosLuP
fonte