La secuencia Stern-Brocot es una secuencia similar a Fibonnaci que se puede construir de la siguiente manera:
- Inicialice la secuencia con
s(1) = s(2) = 1
- Establecer contador
n = 1
- Añadir
s(n) + s(n+1)
a la secuencia - Añadir
s(n+1)
a la secuencia - Incremento
n
, regrese al paso 3
Esto es equivalente a:
Entre otras propiedades, la secuencia Stern-Brocot se puede utilizar para generar todos los números racionales positivos posibles. Cada número racional se generará exactamente una vez, y siempre aparecerá en sus términos más simples; por ejemplo, 1/3
es el cuarto número racional en la secuencia, pero los números equivalentes 2/6
, 3/9
etc., no aparecerán en absoluto.
Podemos definir el enésimo número racional como r(n) = s(n) / s(n+1)
, donde s(n)
está el enésimo número de Stern-Brocot, como se describió anteriormente.
Su desafío es escribir un programa o función que genere el enésimo número racional generado utilizando la secuencia Stern-Brocot.
- Los algoritmos descritos anteriormente están indexados en 1; si su entrada está indexada en 0, indique su respuesta
- Los algoritmos descritos son solo para fines ilustrativos, la salida se puede derivar de la forma que desee (excepto la codificación rígida)
- La entrada puede ser a través de STDIN, parámetros de función o cualquier otro mecanismo de entrada razonable
- Ouptut puede ser STDOUT, consola, valor de retorno de función o cualquier otro flujo de salida razonable
- La salida debe ser como una cadena en el formulario
a/b
, dondea
yb
son las entradas relevantes en la secuencia Stern-Brocot. Evaluar la fracción antes de la salida no está permitido. Por ejemplo, para entrada12
, la salida debe ser2/5
, no0.4
. - Las lagunas estándar no están permitidas
Este es el código de golf , por lo que la respuesta más corta en bytes ganará.
Casos de prueba
Los casos de prueba aquí son 1 indexados.
n r(n)
-- ------
1 1/1
2 1/2
3 2/1
4 1/3
5 3/2
6 2/3
7 3/1
8 1/4
9 4/3
10 3/5
11 5/2
12 2/5
13 5/3
14 3/4
15 4/1
16 1/5
17 5/4
18 4/7
19 7/3
20 3/8
50 7/12
100 7/19
1000 11/39
Entrada de OEIS: A002487
Excelente video de Numberphile que discute la secuencia: fracciones infinitas
True
s en lugar de1
s?True/2
no es una fracción válida (en lo que a mí respecta). Por otro lado,True
no siempre es así1
, algunos lenguajes se utilizan-1
para evitar posibles errores al aplicar operadores bit a bit. [cita requerida]True
es equivalente1
yTrue/2
lo sería1/2
.Respuestas:
Jalea , 14 bytes
Pruébalo en línea!
Ooh, parece que puedo superar la respuesta aceptada por @Dennis, y en el mismo idioma. Esto funciona utilizando una fórmula de OEIS: la cantidad de formas de expresar (el número menos 1) en hiperbinario (es decir, binario con 0, 1, 2 como dígitos). A diferencia de la mayoría de los programas Jelly (que funcionan como un programa completo o una función), este funciona solo como un programa completo (porque envía parte de la salida a stdout y devuelve el resto; cuando se usa como un programa completo, el valor de retorno se envía a stdout implícitamente, por lo que toda la salida está en el mismo lugar, pero esto no funcionaría para el envío de una función).
Esta versión del programa es muy ineficiente. Puede crear un programa mucho más rápido que funcione para todas las entradas de hasta 2ⁿ colocando n justo después de
ẋ
en la primera línea; el programa tiene un rendimiento O ( n × 3ⁿ), por lo que mantener n pequeño es bastante importante aquí. El programa como escrito establece n igual a la entrada, que es claramente lo suficientemente grande, pero también claramente demasiado grande en casi todos los casos (pero bueno, ahorra bytes).Explicación
Como es habitual en mis explicaciones de Jelly, el texto entre llaves (por ejemplo
{the input}
) muestra algo que Jelly completa automáticamente debido a la falta de operandos en el programa original.Función de ayuda (calcula el n º denominador, es decir, el n + numerador 1 Tes):
Los primeros cinco bytes están básicamente generando todos los números hiperbinarios posibles hasta una longitud dada, por ejemplo, con la entrada 3, la salida de
Ḷ
es [[0,1,2], [0,1,2], [0,1,2 ]] entonces el producto cartesiano es [[0,0,0], [0,0,1], [0,0,2], [0,1,0],…, [2,2,1], [2,2,2]].Ḅ
básicamente simplemente multiplica la última entrada por 1, la penúltima entrada por 2, la entrada antepenúltima por 4, etc., y luego agrega; aunque esto normalmente se usa para convertir binario a decimal, puede manejar bien el dígito 2 y, por lo tanto, también funciona para hiperbinario. Luego contamos el número de veces que aparece la entrada en la lista resultante, para obtener una entrada apropiada en la secuencia. (Afortunadamente, el numerador y el denominador siguen la misma secuencia).Programa principal (solicita el numerador y el denominador, y formatea la salida):
De alguna manera sigo escribiendo programas que toman casi tantos bytes para manejar E / S como lo hacen para resolver el problema real ...
fuente
CJam (20 bytes)
Demo en línea . Tenga en cuenta que esto está indexado a 0. Para hacerlo 1 indexado, reemplace la inicial
1_
porT1
.Disección
Esto utiliza la caracterización debido a Moshe Newman que
Si
x = s/t
entonces obtenemosAhora, si asumimos eso
s
yt
somos coprimos, entoncesEntonces
a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))
funciona perfectamente.fuente
Haskell,
78 77 6558 bytesRobar descaradamente el enfoque optimizado nos da:
¡Gracias a @nimi por jugar unos pocos bytes con una función infija!
(Todavía) usa indexación basada en 0.
El viejo enfoque:
Maldita sea el formato de salida ... Y los operadores de indexación. EDITAR: Y precedencia.
Dato curioso: si las listas heterogéneas fueran algo, la última línea podría ser:
fuente
s!!n
debería ser un byte más corto:f n|x<-s!!n=x:x+x+1:f$n+1
s!!n+1
no lo es,(s!!n)+1
peros!!(n+1)
es por eso que no puedo hacer eso: /s!!n
allí!++'/':(show.s$n+1)
enr
guardar un byte.(s#t)0=show...
,(s#t)n=t#(s+t-2*mod s t)$n-1
,r=1#1
. Incluso puede omitirr
, es decir, la última línea es justa1#1
.Jalea , 16 bytes
Pruébalo en línea! o verificar todos los casos de prueba .
Cómo funciona
fuente
05AB1E ,
34332523 bytesExplicación
Pruébalo en línea
Guardado 2 bytes gracias a Adnan.
fuente
XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý
.ý
puede formatear una lista. Agradable.MATL , 20 bytes
Esto utiliza la caracterización en términos de coeficientes binomiales dados en la página OEIS .
El algoritmo funciona en teoría para todos los números, pero en la práctica está limitado por la precisión numérica de MATL, por lo que no funciona para entradas grandes. El resultado es preciso para entradas de hasta
20
al menos hasta.Pruébalo en línea!
Explicación
fuente
Python 2,
8581 bytesEste envío está 1 indexado.
Usando una función recursiva, 85 bytes:
Si un resultado como
True/2
es aceptable, aquí hay uno de 81 bytes:fuente
JavaScript (ES6), 43 bytes
1 indexado; cambie a
n=1
para 0 indexado. La página OEIS vinculada tiene una relación de recurrencia útil para cada término en términos de los dos términos anteriores; Simplemente lo reinterpreté como una recurrencia para cada fracción en términos de la fracción anterior. Lamentablemente, no tenemos TeX en línea, por lo que solo tendrá que pegarlo en otro sitio para descubrir cómo funcionan estos formatos:fuente
Python 2, 66 bytes
Utiliza la fórmula recursiva.
fuente
C (GCC), 79 bytes
Utiliza indexación basada en 0.
Ideona
fuente
x?:y
es una extensión de gcc.En realidad, 18 bytes
Pruébalo en línea!
Esta solución usa la fórmula de Peter y también está indexada en 0. Gracias a Leaky Nun por un byte.
Explicación:
fuente
MATL ,
3230 bytesEsto utiliza un enfoque directo: genera suficientes miembros de la secuencia, selecciona los dos deseados y formatea la salida.
Pruébalo en línea!
fuente
R, 93 bytes
Literalmente la implementación más simple. Trabajando un poco en el golf.
fuente
m4, 131 bytes
Define una macro
r
tal que ser(n)
evalúa de acuerdo con la especificación. Realmente no jugué nada, simplemente codifiqué la fórmula.fuente
Ruby, 49 bytes
Esto está indexado a 0 y utiliza la fórmula de Peter Taylor. Sugerencias de golf bienvenidas.
fuente
> <> , 34 + 2 = 36 bytes
Después de ver la excelente respuesta de Peter Taylor, volví a escribir mi respuesta de prueba (que era una vergonzosa 82 bytes, usando una recursión muy torpe).
Espera que la entrada esté presente en la pila, por lo que +2 bytes para el
-v
indicador. Pruébalo en línea!fuente
Octava, 90 bytes
fuente
C #,
9190 bytesLanza a
Func<int, string>
. Esta es la implementación recursiva.Sin golf:
Editar: -1 byte. Resulta que C # no necesita un espacio entre
return
y$
para las cadenas interpoladas.fuente
Python 2, 59 bytes
Utiliza la fórmula de Peter y tiene un índice 0 similar.
Pruébalo en línea
fuente
J, 29 bytes
Uso
Los valores grandes de n requieren un sufijo
x
que denota el uso de enteros extendidos.fuente
100
cuenta como un "gran valor"?Mathematica,
108106101 bytesfuente
R , 84 bytes
Pruébalo en línea!
La implementación anterior de R no sigue las especificaciones, devuelve un punto flotante en lugar de una cadena, así que aquí hay uno que sí lo hace.
fuente