El árbol Stern-Brocot es un árbol binario de fracciones donde cada fracción se adquiere al sumar los numeradores y denominadores de las dos fracciones vecinas en los niveles anteriores.
Se genera comenzando con 0/1
y 1/0
como "fracciones de punto final", y a partir de ahí, iterando colocando una fracción entre cada par de fracciones consecutivas al sumar los numeradores y denominadores de esas fracciones, de la siguiente manera:
0. 0/1 1/0
1. 0/1 1/1 1/0
2. 0/1 1/2 1/1 2/1 1/0
3. 0/1 1/3 1/2 2/3 1/1 3/2 2/1 3/1 1/0
4. 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0
En cada iteración del árbol Stern-Brocot (la n
iteración th), hay 2^n + 1
elementos en la secuencia, a los que podemos atribuir una fracción de 0/2^n
a 2^n/2^n
. Cada nueva iteración simplemente inserta una fracción "a mitad de camino" entre cada par de fracciones consecutivas.
Esto hace que el árbol Stern-Brocot sea un mapeo uno a uno entre los números racionales positivos y las fracciones binarias entre 0 y 1, lo que también sirve como prueba de que los dos conjuntos tienen la misma cardinalidad.
Su tarea es escribir un programa o función que, dado el numerador y el denominador de un número racional positivo en términos más bajos, determine la fracción binaria que corresponde a la posición de esa fracción en el árbol Stern-Brocot.
A continuación se proporcionan ejemplos de entradas y salidas:
2/3 -> 3/8 (4th number in iteration 3)
4/7 -> 9/32 (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2 (middle number in the first iteration)
Entradas que no necesita admitir, pero se incluyen como referencia:
0/1 -> 0/1 (0/1 is considered the left number)
1/0 -> 1/1 (1/0 is considered the rightmost number)
El programa más corto en cualquier idioma para lograr este objetivo gana.
1/1 => 1
,1/2 => 2
,2/1 => 3
,1/3 => 4
, etc.). Si el número así generado para un nodo esn
, entonces2^lg n
(registro binario) es el bit más alto establecidon
, y la fracción binaria deseada es(2*(n - 2^lg n) + 1) / 2^(lg n + 1)
. (Cualquier persona que intente una solución de ensamblador en un conjunto de instrucciones con un bit de conjunto más alto probablemente quiera usar este enfoque).Respuestas:
GolfScript (
49 4846 caracteres)o
Ambas son funciones que toman el numerador y el denominador en la pila y dejan el numerador y el denominador en la pila. Demo en línea .
La idea central se expresa en pseudocódigo en la sección 4.5 de Matemáticas concretas (p122 en mi edición):
Si la cadena de Ls y Rs se interpreta como un valor binario con L = 0 y R = 1, entonces dos veces ese valor más uno es el numerador, y el denominador es un poco más largo.
Como punto de interés para Golfscripters, esta es una de esas raras ocasiones en las que he encontrado que el despliegue es útil. (Ok, solo lo uso como contador de bucles, pero eso es mejor que nada).
fuente
Mathematica,
130 114111 caracteresEjemplo:
fuente
Rubí,
132125Rubied & golfed la solución de referencia de @JoeZ.
Ejemplos de uso:
fuente
Ruby (69 caracteres)CoffeeScript (59 caracteres)Esta es una función que toma el numerador y el denominador como argumentos y devuelve una matriz que contiene el numerador y el denominador después de la biyección.
Demostración en línea
Utiliza el mismo enfoque que mi solución GolfScript anterior, pero es mucho más legible porque puedo usar 4 variables sin tener que preocuparme por el encajonamiento y el desempaquetado en una matriz. Elegí CoffeeScript porque no tiene prefijos variables con
$
(20 caracteres guardados, por ejemplo, PHP), tiene una sintaxis de definición de función corta que permite valores de parámetros predeterminados (por lo que no es necesario ajustarf(a,b,x,y)
una funcióng(a,b) = f(a,b,0,1)
) y me permite usar booleanos como enteros en expresiones con valores útiles. Para aquellos que no lo saben, CoffeeScript no tiene el operador ternario estándar de estilo C (C?P:Q
), pero puedo sustituirloC&&P||Q
aquí porqueP
nunca será falso.Una alternativa posiblemente más elegante, pero posiblemente menos corta, es reemplazar la resta repetida con división y módulo:
(65 caracteres; demostración en línea ). Escribirlo de esta manera expone la relación con el algoritmo de Euclides.
fuente
a<b
que le ahorra un carácter. La inclinaciónc
da otros dos. También puede considerar la sintaxisf=->a,b,x=0,y=1{...}
para una definición aún más corta.c=a<b ?
con un espacio extra despuésb
. De lo contrario, el signo de interrogación se trata como parte deb
.Python - 531
Una solución no protegida en Python, que sirve como solución de referencia de último lugar:
Simplemente realiza una búsqueda binaria entre fracciones, aprovechando el hecho de que el mediador de cualquiera de las dos fracciones siempre estará entre los valores de esas dos fracciones.
fuente
GolfScript, 54 caracteres
La entrada debe darse en STDIN en la forma especificada en la tarea. Puede probar el código en línea .
fuente
Mathematica 138
No es tan simple como el procedimiento de alephalpha, pero fue lo mejor que he podido producir hasta ahora.
Pruebas
fuente
JavaScript 186
podría ser menos, pero me gusta el golf legible
fuente
Haskell , 125 bytes
Pruébalo en línea!
Entrada y salida en forma de un par
(n,d)
.Breve explicacion:
n
construye la siguiente fila de la anterior mirando cada par de fracciones e insertando la nueva entre la primera y la recursión (que colocará la segunda fracción allí). El caso base es muy simple ya que es básicamente la función de identidad. Lat
función itera esa función indefinidamente en función del estado inicial con solo las dos fracciones de límite.t
luego indexa cada fila (i
) y cada elemento en la fila (j
) y busca la primera fracción que coincide con lo que estamos buscando. Cuando lo encuentra, rindej
como numerador y2^i
como denominador.fuente