La computación de los Antepasados de # de Stern-Brocot Árbol

Question

La lectura acerca de la Stern-Brocot árbol, el artículo da este ejemplo:

el uso de 7/5 como un ejemplo, a sus más cercanos más pequeños ancestro es 4/3, por lo que su niño está a la izquierda (4 + 7)/(3 + 5) = 11/8, y a sus más cercanos mayor ancestro es 3/2, por lo que su derecho de hijo (7 + 3)/(5 + 2) = 10/7.

Conseguir la izquierda y a la derecha los niños parece claro para mí:

• a la izquierda - el desarrollo de # (7/5) y más cercana menor antepasado (4/3)
• haga mediant de # (7/5) y más cerca de la más grande antepasado (3/2)

Pero, ¿cómo puedo averiguar la closest smaller and larger ancestors de 7/5?

Answer 1

Esto no es especialmente elegante procedimiento, pero es algorítmica.

Índice de los niveles de Stern-Brocot árbol, de modo que el nivel de $n$ $2^n$ nodos: nivel de $0$ tiene la raíz $\frac11$, nivel de $1$$\frac12$$\frac21$, y así sucesivamente. Deje $T_n$ el conjunto de los números racionales en $[0,1]$ sobre el nivel de $n$ de el árbol y deje $S_n=\bigcup_{k\le n}S_k$; a continuación, $S_n\cup\{0\}$ es la secuencia de Farey de orden $F_{n+2}$ donde $F_k$ $k$- ésimo número de Fibonacci. Esto significa que cada elemento interior de $S_n$ es el desarrollo de sus vecinos inmediatos en $S_n$, por lo que el problema de la búsqueda de 'padres' del Stern-Brocot árbol reduce a la búsqueda de los vecinos del interior de los miembros de una secuencia de Farey.

Supongamos que $\frac{a}b<\frac{c}d$, e $\frac{a}b$ $\frac{c}d$ son adyacentes en algunos secuencia de Farey; es bien sabido que $bc-ad=1$. Por lo tanto, si quiero encontrar a la izquierda de los 'padres' de $\frac{c}d$ en el de Stern-Brocot árbol, tengo que resolver el sistema

$$\begin{align*} &bc-ad=1\tag{1}\\ &0<b<d\\ &0\le a \end{align*}$$

para$a$$b$. Desde $c$ $d$ son relativamente primos, la ecuación de $(1)$ tiene algunos entero solución de $a=a_0,b=b_0$, y la solución general es entonces

$$\begin{align*} a&=a_0+ck\\ b&=b_0+dk\;, \end{align*}$$

donde $k\in\Bbb Z$. Claramente hay un $k\in\Bbb Z$ tal que $0<b_0+dk<d$, y desde $\frac{c}d$ ha dejado de padres, debe haber exactamente una de esas $k$. Por lo tanto, podemos usar el algoritmo de Euclides extendido para calcular $a_0$$b_0$,$b=b_0\bmod d$, y el uso de $(1)$ conseguir $a$. Una vez que tenemos a la izquierda vecino $\frac{a}b$, tenemos el derecho prójimo como a $\frac{c-a}{d-b}$.

Esto se hace cargo de la mitad izquierda de la de Stern-Brocot árbol, que contiene los números positivos racionales que no exceda $1$. La mitad derecha se obtiene a partir de la mitad izquierda por la reflexión en el eje central vertical y, a continuación, tomar el recíproco de cada uno de los racionales, así que para encontrar los 'padres' de un racional mayor que $1$ podemos encontrar los 'padres' de su recíproco y, a continuación, tomar sus recíprocos.

Answer 2

Una conocida propiedad de Stern-Brocot árbol es que existe una correspondencia uno a uno entre las fracciones en el intervalo de $[0,1]$ y las fracciones en el intervalo de $[1,\infty]$. Pero es mucho más simple para inicializar el árbol con el intervalo de $[0,1]$. Haciendo así tenemos el (Pascal) algoritmo de abajo para viajar dos caminos en el Stern-Brocot árbol que nos llevan a la fracción $5/7$ al encerrarla entre un límite inferior $m1/n1$ y un límite superior $m2/n2$ con cada paso. El algoritmo se detiene porque se sabe que cualquier racional número está en el árbol.

programa de Kevin;

procedimiento Stern_Brocot(cajeros,noemer : integer);
{
 Caminar a través de Stern-Brocot árbol
 hasta fracción = cajero/noemer
 (Inglés: numerador/denominador)
}
var
 m1,m2,n1,n2 : integer;
comenzar
{ Inicializar árbol }
 m1 := 0; n1 := 1;
 m2 := 1; n2 := 0;
 mientras que el verdadero ¿
comenzar
 { si cajeros/noemer < (m1+m2)/(n1+n2) entonces }
 si (n1+n2)*cajeros < (m1+m2)*noemer, a continuación,
 { Apretando }
comenzar
 { Límite Superior }
 m2 := m1+m2;
 n2 := n1+n2;
 end else begin
 { Límite Inferior }
 m1 := m1+m2;
 n1 := n1+n2;
end;
 Writeln(m1,'/',n1,' < ',cajeros,'/',noemer,' < ',m2,'/',n2);
 si (cajero/noemer = m1/n1)
 o (cajero/noemer = m2/n2) entonces Break;
end;
end;

comenzar
Stern_Brocot(5,7);
final.

Salida:

0/1 < 5/7 < 1/1
1/2 < 5/7 < 1/1
2/3 < 5/7 < 1/1
2/3 < 5/7 < 3/4
5/7 < 5/7 < 3/4

A partir de este resultado se deriva de la secuencia requerida por la mano (bueno, toda la la cosa podría haber sido hecho por la mano en este caso simple, pero es muy útil tener un un programa de ordenador para, por ejemplo, la aproximación de números irracionales).

1/1 < 7/5 < 1/0
1/1 < 7/5 < 2/1
1/1 < 7/5 < 3/2
4/3 < 7/5 < 3/2
4/3 < 7/5 < 7/5

Tenga en cuenta que el más cercano de pequeños y grandes antepasados están en el árbol justo antes de que el algoritmo se detiene.

EDIT. Mi favorito de referencia es esta:

• Stern-Brocot Árbol

Más impresionantes ejemplos son obtenidos mediante el cálculo de los números irracionales, tales como $1/\sqrt{2}$:

si (n1+n2)(n1+n2) < (m1+m2)(m1+m2)*2 entonces

Dando, por ejemplo, después de 45 iteraciones: $$ \frac{318281039}{225058681} < \sqrt{2} < \frac{768398401}{543339720} $$