Encuentra la posición de una fracción en el árbol Stern-Brocot

11

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/1y 1/0como "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 niteración th), hay 2^n + 1elementos en la secuencia, a los que podemos atribuir una fracción de 0/2^na 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.

Joe Z.
fuente
¿Hay algún requisito de entrada / salida? Por ejemplo, ¿es suficiente una función como en su solución de referencia, o necesita ser un programa independiente? ¿Importa el formato de salida de fracción?
Darren Stone
Una función es suficiente. Lo aclararé en la descripción del problema.
Joe Z.
Es un poco tarde para mí pensarlo; Probablemente intentaré aclararlo mañana.
Joe Z.
2
Ok, creo que la biyección que tienes en mente es asignar a cada profundidad en el árbol un denominador constante 2 ^ (profundidad + 1) y numeradores 1, 3, 5, 7, ... desde la izquierda.
Peter Taylor
1
Una forma alternativa de construir que es primer número de los nodos del árbol en orden de partida primero en amplitud en 1 (es decir 1/1 => 1, 1/2 => 2, 2/1 => 3, 1/3 => 4, etc.). Si el número así generado para un nodo es n, entonces 2^lg n(registro binario) es el bit más alto establecido n, 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).
Peter Taylor

Respuestas:

1

GolfScript ( 49 48 46 caracteres)

{0\@{}{@2*2$2$>!+@@{{\}3$)*}:j~1$-j}/\)\,?}:f;

o

{0:x;\{}{.2$<!2x*+:x){\}*1$-{\}x)*}/x@)@,?}:g;

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

while m != n do
    if m < n then (output(L); n := n - m)
             else (output(R); m := m - 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).

Peter Taylor
fuente
1

Mathematica, 130 114 111 caracteres

f=#~g~0&;0~g~q_=q;p_~g~q_:=g[#,(Sign[p-#]+q)/2]&@FromContinuedFraction[ContinuedFraction@p/.{x___,n_}:>{x,n-1}]

Ejemplo:

f[2/3]

3/8

f[4/7]

9/32

f[1]

1/2

alephalpha
fuente
1

Rubí, 132 125

Rubied & golfed la solución de referencia de @JoeZ.

def t(n,d)u=k=0;v,j,f,g,b=[1,]*5;c=2
while(z=(f*d).<=>(g*n))!=0;z>0?(j,k=f,g):(u,v=f,g);b=b*2-z;f,g=u+j,v+k;c*=2;end
[b,c]end

Ejemplos de uso:

>> t(2,3)
=> [3, 8]
>> t(4,7)
=> [9, 32]
>> t(1,1)
=> [1, 2]
Piedra de Darren
fuente
1

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.

g=(a,b,x=0,y=1)->c=a>=b;a&&g(a-b*c,b-a*!c,2*x+c,2*y)||[x,y]

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 ajustar f(a,b,x,y)una función g(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 sustituirlo C&&P||Qaquí porque Pnunca será falso.

Una alternativa posiblemente más elegante, pero posiblemente menos corta, es reemplazar la resta repetida con división y módulo:

f=(a,b,x=0,y=1,p=0)->a&&f(b%a,a,(x+p<<b/a)-p,y<<b/a,1-p)||[x+p,y]

(65 caracteres; demostración en línea ). Escribirlo de esta manera expone la relación con el algoritmo de Euclides.

Peter Taylor
fuente
No necesita los paréntesis, lo a<bque le ahorra un carácter. La inclinación cda otros dos. También puede considerar la sintaxis f=->a,b,x=0,y=1{...}para una definición aún más corta.
Howard
@Howard, no sé qué versión de Ruby estás usando, pero en IDEOne obtengo un error de sintaxis si intento eliminar esos paréntesis o usar esa sintaxis de función.
Peter Taylor
Prueba c=a<b ?con un espacio extra después b. De lo contrario, el signo de interrogación se trata como parte de b.
Howard
0

Python - 531

Una solución no protegida en Python, que sirve como solución de referencia de último lugar:

def sbtree(n, d): 
    ufrac = [0, 1]
    lfrac = [1, 0]
    frac = [1, 1]
    bfrac = [1, 2]
    while(frac[0] * d != frac[1] * n): 
        if(frac[0] * d > frac[1] * n): 
            # push it towards lfrac
            lfrac[0] = frac[0]
            lfrac[1] = frac[1]
            bfrac[0] = bfrac[0] * 2 - 1 
        elif(frac[0] * d < frac[1] * n): 
            # push it towards ufrac
            ufrac[0] = frac[0]
            ufrac[1] = frac[1]
            bfrac[0] = bfrac[0] * 2 + 1 
        frac[0] = ufrac[0] + lfrac[0]
        frac[1] = ufrac[1] + lfrac[1]
        bfrac[1] *= 2
    return bfrac

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.

Joe Z.
fuente
0

GolfScript, 54 caracteres

'/'/n*~][2,.-1%]{[{.~3$~@+@@+[\]\}*].2$?0<}do.@?'/'@,(

La entrada debe darse en STDIN en la forma especificada en la tarea. Puede probar el código en línea .

> 4/7
9/32

> 9/7
35/64

> 5/1
31/32
Howard
fuente
0

Mathematica 138

No es tan simple como el procedimiento de alephalpha, pero fue lo mejor que he podido producir hasta ahora.

q_~r~k_:=Nest[#+Sign@k/(2Denominator@# )&,q,Abs@k]  
g@d_:=
Module[{l=ContinuedFraction@d,p=-1},
l[[-1]]-=1;
(p=-p;# p)&/@l]
h[q_]:=Fold[r,1/2,g@q]

Pruebas

h[2/3]
h[4/7]
h[1]

3/8
9/32
1/2

DavidC
fuente
0

JavaScript 186

f=(p1,q1,p2,q2)=>{if(p1*q2+1==p2*q1){return{p:p1+p2,q:q1+q2}}let p,q,pl=0,ql=1,ph=1,qh=0;for(;;){p=pl+ph;q=ql+qh;if(p*q1<=q*p1){pl=p;ql=q}else if(p2*q<=q2*p){ph=p;qh=q}else return{p,q}}}

podría ser menos, pero me gusta el golf legible

caub
fuente
0

Haskell , 125 bytes

n((a,b):(c,d):r)=(a,b):(a+c,b+d):n((c,d):r)
n a=a
z=zip[0..]
t x=[(j,2^i)|(i,r)<-z$iterate n[(0,1),(1,0)],(j,y)<-z r,x==y]!!0

Pruébalo en línea!

Entrada y salida en forma de un par (n,d).

Breve explicacion:

nconstruye 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. La tfunción itera esa función indefinidamente en función del estado inicial con solo las dos fracciones de límite. tluego 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, rinde jcomo numerador y 2^icomo denominador.

usuario1472751
fuente