Las fracciones continuas son expresiones que describen fracciones iterativamente. Se pueden representar gráficamente:
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--
code-golf
math
rational-numbers
Aaron
fuente
fuente
2.002
puede expresarse como2002/1000
. Eso es técnicamente una "fracción única", probablemente desee decir, "una fracción única, en su forma más simple".Respuestas:
J,
85 bytesIgual 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 sobrePruébalo en línea!
-3 gracias a millas .
fuente
∘
.Haskell,
373618 bytesEsta función espera el
Ratio
tipo de Haskell como entrada. Ejemplo de uso:Nota: uno explícito
Ratio
en la lista de entrada (4%1
) es suficiente, los sistemas de tipo calculan que los otros también deben serRatio
s.Editar: @Lynn guardó un byte. ¡Gracias!
Editar II: eliminó el
import
(ver esta discusión sobre meta ).fuente
import
. Sin embargo, para llamarlo, tienes que alimentarlo,Ratio
lo que sí necesitaimport
. ¿Debo agregar elimport
al recuento de bytes o no?from fractions import Fraction
para hacer operaciones conFraction
objetos, la declaración de importación también se cuenta.Ratio
que 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í.GolfScript , 13 bytes
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 ...
fuente
Mathematica,
2322 bytesEsencialmente un puerto de mi respuesta GolfScript . Aquí hay algunas alternativas:
Para 24 bytes, podemos escribir una función variable recursiva:
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:
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:
fuente
LabVIEW, 36 bytes equivalentes
Implementación bastante sencilla e ingenua utilizando el algoritmo de OP. ¿Hay una mejor manera de hacer esto?
fuente
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-antepuesto-dividido por el MCD de 1 y+∘÷
más el recíproco de/
reducción sobreTryAPL en línea!
fuente
Python 2, 62 bytes
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/c
yb/d
, la siguiente fracción es(n*b+a)/(n*c+d)
.Por ejemplo, para pi:
Podemos ver que
15*22 + 3 = 333
,15*7 + 1 = 106
,1*333 + 22 = 355
,1*106 + 7 = 113
, etc.fuente
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
fuente
Haskell, 30 bytes
Agrega recursivamente cada capa hacia afuera, actualizando
n/d
ah+(1/(n/d))
, lo que equivale ah+d/n
o(h*n+d)/n
. La fracción se almacena como una tupla de(num,denom)
. La fracción inicial de(1,0)
volteos a la0/1
cual es0
.fuente
Python, 50 bytes
Construye la fracción continua desde el final de la lista hacia atrás, actualizando repetidamente la fracción
n/d
en el último elementox
comon/d -> 1+1/(n/d) == (x*n+d)/n
.fuente
Lisp común, 54
Un pliegue a la derecha algo detallado:
Pruebas
fuente
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
fuente
∘
) en lugar de una funciónx∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
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])
Javascript (ES6), 55 bytes
Casos de prueba
fuente
CJam ,
1816 bytesIntérprete en línea .
fuente
05AB1E ,
1917 bytesExplicación
Entrada tomada como una lista de números
Pruébalo en línea!
fuente
JavaScript (ES6), 44 bytes
fuente
Javascript (ES6), 50 bytes
Es gracias a la respuesta de Arnauld, antes de verlo estaba atascado en 66 bytes:
Ejemplo:
Llamada:
f([1, 0, 1, 1, 2, 1, 1])
Salida:
Array [ 19, 7 ]
fuente
Perl 6 , 24 bytes
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.… .nude
devuelve el nu merator y de denominador de la rata .{ … }
conviértalo en un lambda de bloque desnudo con parámetro implícito@_
.Uso:
fuente
Zephyr , 145 bytes
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:
fuente
Ruby, 34 bytes
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
.fuente
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+
.(a, b) => (a + 1/b)
.fuente
APL (NARS), 15 + 1 caracteres, 30 + 2 bytes
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:
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 ...
fuente