Simplifica una fracción continua

21

Las fracciones continuas son expresiones que describen fracciones iterativamente. Se pueden representar gráficamente:

ingrese la descripción de la imagen aquí

O pueden representarse como una lista de valores: [a0; a1, a2, a3, ... an]

El reto:

tome un número base: y una lista de valores de denominador: y simplifique la fracción continua a una fracción racional simplificada: devuelva o imprima numerador y denominador por separado.a0[a1, a2, a3, ... an]

Ejemplos:

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

Implementación de ejemplo: (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

Victorioso:

código más corto en bytes: --no hay incorporados que hagan todo el problema permitido--

Aaron
fuente
Debería hacer esta oración más clara, "y simplificar la fracción continua a una sola fracción"; a menos que haya querido que la redacción signifique un resultado de 2.002puede expresarse como 2002/1000. Eso es técnicamente una "fracción única", probablemente desee decir, "una fracción única, en su forma más simple".
Magic Octopus Urn
@carusocomputing point tomado ... aunque no me sentiría tan mal por 2/4 (o similar) ya que todavía ha simplificado la estructura de múltiples fracciones a una sola fracción
Aaron
Hmm ... Creo que hay una manera de explotar eso, pero con la respuesta de 13 bytes de golfscript, probablemente tendría que usar MATL para ganar.
Urna de pulpo mágico
@carusocomputing Yo diría que anímate ... Si puedes superar la respuesta de 13 bytes, sería genial
Aaron
Puede hacer que el pi se detenga antes: 355/113.
Thorbjørn Ravn Andersen

Respuestas:

15

J, 8 5 bytes

Igual que esto , pero utiliza un incorporado para racionales.

El argumento es {a0, a1, a2, a3, ...} como una lista de J números racionales de precisión extendida. El resultado es la fracción como un número racional J de precisión extendida.

(+%)/

(+%) el más el recíproco de

/ reducción sobre

Pruébalo en línea!

-3 gracias a millas .

Adán
fuente
Si toma la entrada como una lista de enteros extendidos, podría guardar 3 bytes. También usaste la división APL en la explicación.
millas
@miles Gracias. No puedo estar más cerca de la prohibición incorporada que eso. Lástima que J no tenga un personaje de composición de gancho como Dyalog APL .
Adám
El intento de enlace en línea J se rompe
Chiel ten Brinke
@ChieltenBrinke Gracias. Fijo.
Adám
12

Haskell, 37 36 18 bytes

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

Esta función espera el Ratiotipo de Haskell como entrada. Ejemplo de uso:

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

Nota: uno explícito Ratioen la lista de entrada ( 4%1) es suficiente, los sistemas de tipo calculan que los otros también deben ser Ratios.

Editar: @Lynn guardó un byte. ¡Gracias!

Editar II: eliminó el import(ver esta discusión sobre meta ).

nimi
fuente
1
Oooh, bonito caso de borde. La función en sí es polimórfica, por lo que no necesita import. Sin embargo, para llamarlo, tienes que alimentarlo, Ratiolo que sí necesita import. ¿Debo agregar el importal recuento de bytes o no?
nimi
1
Eso suena como una buena pregunta para meta.
Martin Ender
Nunca he usado Haskell, así que corrígeme si me equivoco, pero si el equivalente de Python sería: from fractions import Fractionpara hacer operaciones con Fractionobjetos, la declaración de importación también se cuenta.
Aaron
.. tuvimos eso antes .
nimi
@Aaron: el problema es: la definición de la función no necesita la importación, porque es polimórfica. Cuando desee llamarlo, debe proporcionar números de tipo Ratioque solo se pueden construir a través de %, lo que requiere la importación. Por lo general, no contamos bytes para llamar a gastos generales, solo para la función en sí.
nimi
11

GolfScript , 13 bytes

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

Pruébalo en línea!

Yay para los racionales ocultos de GolfScript . :)

Explicación

El único tipo de número "oficial" de GolfScript son los enteros. Pero el operador de exponenciación no convierte su resultado en entero y, convenientemente, el resultado nativo de una exponenciación de enteros en Ruby (el lenguaje del intérprete de GolfScript) es un número racional. Entonces podemos obtener fracciones fácilmente elevando algo a la potencia de -1. Convenientemente, queremos reciprocos de todos modos ...

~]     # 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
fuente
11

Mathematica, 23 22 bytes

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

Esencialmente un puerto de mi respuesta GolfScript . Aquí hay algunas alternativas:

Para 24 bytes, podemos escribir una función variable recursiva:

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

Para 21 bytes, incluso podemos definir un "operador variable", pero su convención de llamada sería tan extraña, que soy reacio a contar esto:

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

Tendría que llamar a esto con una secuencia de los valores de entrada, por ejemplo, ±Sequence[3, 7, 15, 1, 292, 1]o ±##&[3, 7, 15, 1, 292, 1].

Y también para 21 bytes, habría el (prohibido) incorporado:

FromContinuedFraction
Martin Ender
fuente
10

LabVIEW, 36 bytes equivalentes

Implementación bastante sencilla e ingenua utilizando el algoritmo de OP. ¿Hay una mejor manera de hacer esto?

ingrese la descripción de la imagen aquí

ijustlovemath
fuente
55
Su título de ingeniero eléctrico está demostrando.
Urna mágica de pulpo
1
@ijustlovemath Props, pero ... relevante
Aaron
Sí, es un lenguaje polémico para estar seguro. Veo LabVIEW como el "Odio las matemáticas" del mundo de los programadores. El problema no es la matemática en sí, sino cómo se enseña (o, a menudo, la falta de enseñanza).
ijustlovemath
6

Dyalog APL , 10 bytes

Ni siquiera utiliza un incorporado para racionales.

Toma {a 0 , a 1 , a 2 , a 3 , ...} como argumento, devuelve {denominador, numerador}.

1(,÷∨)+∘÷/

1(,÷∨) 1-antepuesto-dividido por el MCD de 1 y

+∘÷ más el recíproco de

/ reducción sobre

TryAPL en línea!

Adán
fuente
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

Desafortunadamente, no es tan golfoso (vea la respuesta de @ xnor para más corto), pero calcula la fracción sin necesidad de invertir la entrada. Esto utiliza el enfoque de "tabla mágica" para convergentes, dadas las dos últimas fracciones a/cy b/d, la siguiente fracción es (n*b+a)/(n*c+d).

Por ejemplo, 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
fuente
4

M, 5 bytes

Ṛİ+¥/

La entrada es una lista de los valores [a0, a1, ..., aN]y genera un número racional.

Pruébalo en línea! o Verificar todos los casos de prueba.

Explicación

Ṛİ+¥/  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
millas
fuente
1
¿Que es esto? ¿Algún nuevo dialecto de gelatina?
Adám
@miles en realidad 9 bytes lo siento :(
Aaron
@ Adám Es un viejo tenedor de gelatina destinado a las matemáticas y la simbología. Aquí está su repositorio de Github .
millas del
1
@Aaron M usa la misma página de códigos que Jelly, y se puede codificar usando un byte para cada personaje.
millas
@miles OK, agregado .
Adám
4

Haskell, 30 bytes

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

Agrega recursivamente cada capa hacia afuera, actualizando n/dah+(1/(n/d)) , lo que equivale a h+d/no (h*n+d)/n. La fracción se almacena como una tupla de (num,denom). La fracción inicial de (1,0)volteos a la 0/1cual es 0.

xnor
fuente
3

Python, 50 bytes

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

Construye la fracción continua desde el final de la lista hacia atrás, actualizando repetidamente la fracción n/den el último elemento xcomo n/d -> 1+1/(n/d) == (x*n+d)/n.

xnor
fuente
3

 Lisp común, 54

Un pliegue a la derecha algo detallado:

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

Pruebas

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                
volcado de memoria
fuente
2

Julia (53 bytes)

Esta es la primera vez que uso a Julia, si pasé por alto un iterador podría haber usado para perder algunos bytes más, avíseme. Aquí hay una pista para cualquiera que no sepa qué idioma elegir para este desafío 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;)
  • Invierta la matriz de entrada.
  • Iterar a través de él con división racional.
  • Agregue c al resultado decimal.
Urna de pulpo mágico
fuente
puede guardar dos bytes definiendo un operador (por ejemplo ) en lugar de una función
Tasos Papastylianou
también, cambie el bucle for por un tiempo y x∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
haga
1
25: x->foldr((x,y)->x+1//y,x)(igual que la solución de Haskell). uso:(x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2])
Fengyang Wang
Ooo ... ¿Una función de plegado inverso? ¡Eso es hermoso! Aunque no merezco tomar el crédito por eso jaja.
Urna mágica de pulpo
2

Javascript (ES6), 55 bytes

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

Casos de prueba

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

CJam , 18 16 bytes

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

Intérprete en línea .

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

05AB1E , 19 17 bytes

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

Explicación

Entrada tomada como una 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

Pruébalo en línea!

Emigna
fuente
2

JavaScript (ES6), 44 bytes

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

Javascript (ES6), 50 bytes

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

Es gracias a la respuesta de Arnauld, antes de verlo estaba atascado en 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]

Ejemplo:
Llamada: f([1, 0, 1, 1, 2, 1, 1])
Salida:Array [ 19, 7 ]

Hedi
fuente
1

Perl 6 , 24 bytes

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

Explicación:

  • 1 / * + *es una lambda con dos parámetros ( *) que toma el recíproco del primero y agrega el segundo. (devuelve una rata )

  • R[&(…)]usa eso como si fuera un operador infijo y lo invierte.
    (incluyendo hacerlo correcto asociativo)

  • […](@_) toma eso y lo usa para reducir la entrada.

  • … .nudedevuelve el nu merator y de denominador de la rata .

  • { … }conviértalo en un lambda de bloque desnudo con 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
fuente
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 es el primer lenguaje de programación que he creado. Fue diseñado para ser intuitivo y tener una sintaxis limpia, más bien a expensas de la brevedad. ¿Por qué estoy jugando al golf con eso? Porque, a diferencia de cualquier idioma que he escrito desde entonces, tiene un tipo incorporado Fraction. Incluso puede usar el operador de división /como operador unario para "inverso" (una característica que tomé prestada para Pip).

Ahora, hay limitaciones significativas. El mayor problema para este desafío es que las matrices deben definirse con un tamaño fijo, lo que significa que el programa comienza leyendo el tamaño de la matriz del usuario. (Espero que esto esté bien; la alternativa es codificar el tamaño). También existe el pequeño problema de que la precedencia del operador no existe, lo que significa que las expresiones de múltiples operadores deben tener paréntesis.

Aquí hay un ejemplo de ejecución:

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

Ruby, 34 bytes

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

Esto realiza un plegado a la derecha (invirtiendo y luego plegando a la izquierda), agregando cada elemento a 1 sobre el total acumulado (los elementos a la derecha). Ruby tiene el tipo racional, que es realmente agradable. Y los racionales literales son un número con sufijo r.

IMP1
fuente
1

Stax , 4 bytes

╣╩┼►

Ejecutar y depurarlo

Por pequeño que sea, no está integrado. Sin embargo, los racionales incorporados ayudan bastante. Descomprimido en ASCII, el programa es rksu+.

  1. Invierte la matriz.
  2. Dobla la matriz usando (a, b) => (a + 1/b).
recursivo
fuente
1

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

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

Traducción en Apl (Nars) de la solución Adam J ... la entrada permitida para esa función será toda la lista de números enteros, donde el primer elemento será de tipo racional. Prueba:

  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 

entonces serían 15 caracteres como longitud de función y 1 carácter para "x" para ingresar el tipo de entrada que quiero y salir del tipo que quiero ...

RosLuP
fuente