Si tenemos dos fracciones $a = { a_1 \over a_2} $ y $c = {c_1 \over c_2}$ con $a<c$ ,
cómo encontrar la fracción
$b = { b_1 \over b_2 }$ , $a < b < c$
para el que alguna medida de simplicidad como
$b_1^2+b_2^2$
es mínimo, sin probar todas las fracciones posibles?
Supondré que ambas fracciones son positivas; si sus signos difieren toma $\frac01$ como fracción intermedia y ambas negativas es similar a ambas positivas. La fracción absolutamente más simple en el intervalo $(a,c)$ (en el sentido de que tanto su numerador como su denominador son los más pequeños posibles en el intervalo, por lo que no importa mucho el peso de cada uno de ellos) se encuentra en términos de la posición de $a$ y $b$ en el Árbol de Stern-Brocot . Sea $d$ sea el ancestro común más cercano de $a$ y $c$ (Voy a considerar $0$ para ser la raíz del árbol, por lo que en caso de que $a=0$ se obtiene $d=0$ ). Si $d\notin\{a,c\}$ entonces $d$ es la fracción más simple entre $a$ y $c$ es, de hecho, como todas las fracciones positivas, la fracción más simple en todo el intervalo abierto entre sus "ancestros directos" izquierdo y derecho en el árbol; aquí el padre de una fracción $\alpha$ es un ancestro directo de $\alpha$ y su otro ancestro directo se encuentra subiendo desde el padre hasta el primer ancestro que se encuentra en la dirección opuesta a la del padre $\alpha$ (para los números enteros positivos se considera que el padre derecho es $\infty$ ). Este intervalo contiene tanto $a$ (como descendiente izquierdo de $d$ ) y $c$ (un descendiente derecho de $d$ ).
La situación es algo más complicada si $d\in\{a,c\}$ En otras palabras, si una de las fracciones es un ancestro de la otra (ya que su pregunta prohíbe tomar $b=a$ o $b=c$ ). Establezca $\{d,e\}=\{a,c\}$ Así que $e$ es el de $a,c$ que es desigual a $d$ . Si $d$ no es uno de los dos ancestros directos de $e$ , entonces alguna fracción en el camino de $d$ à $e$ en el árbol se encuentra en el intervalo $(a,c)$ y la primera de estas fracciones da su $b$ . De hecho, se encuentra bajando un escalón desde $d$ en dirección a $e$ , luego cero o más pasos en la dirección opuesta, deteniéndose justo antes del siguiente paso que sería de nuevo en la dirección de $d$ à $e$ .
Por último, queda el caso de que $d$ es uno de los dos ancestros directos de $e$ . Este es el único caso en el que hay que bajar $e$ en el árbol; de hecho, un paso por debajo de $e$ en dirección a $d$ (a la izquierda o a la derecha, pero no hacia arriba, por supuesto) dará la fracción $b$ buscado. De hecho $b=\frac{a_1+c_1}{a_2+c_2}$ en este caso.
Aquí hay ejemplos de los tres casos:
Descender en el árbol de Stern-Brocot es fácil si se conocen los ancestros directos de la fracción actual: añadir al numerador y al denominador por separado el numerador y el denominador del ancestro directo en la dirección a la que se va. Subir es más difícil (ya que no es razonable suponer que se conocen los ancestros directos en este caso), pero realizando el algoritmo euclidiano al par (numerador,denominador) mediante restas, llevando la cuenta del lado desde el que se realiza la resta, se obtendrán las sucesivas direcciones a tomar desde arriba en $\frac11$ abajo para encontrar la fracción dada en el árbol; esto revela todo sus antepasados. Por ejemplo, para $\frac{58}{75}$ los pasos del algoritmo euclidiano $(58,75)$ a la izquierda $(58,17)$ a la derecha $(41,17)$ a la derecha $(24,17)$ a la derecha $(7,17)$ a la izquierda $(7,10)$ a la izquierda $(7,3)$ a la derecha $(4,3)$ a la derecha $(1,3)$ a la izquierda $(2,1)$ a la izquierda $(1,1)$ te diga que puedes encontrar $\frac{58}{75}$ descendiendo en el árbol por $\frac11$ a la izquierda $\frac12$ a la derecha $\frac23$ a la derecha $\frac34$ a la derecha $\frac45$ a la izquierda $\frac79$ a la izquierda $\frac{10}{13}$ a la derecha $\frac{17}{22}$ a la derecha $\frac{24}{31}$ a la izquierda $\frac{41}{53}$ a la izquierda $\frac{58}{75}$ .
Para encontrar el ancestro común más cercano entre dos fracciones, aplique este algoritmo euclidiano en paralelo para las dos, hasta el primer punto en el que las dos requieren operaciones en diferentes direcciones; descendiendo desde $\frac11$ hasta ese punto revela el ancestro común más cercano. Por ejemplo, para el primer ejemplo, las fracciones son $\frac47$ y $\frac34$ , por lo que se realiza en paralelo
El camino común es a la izquierda, a la derecha luego divergen, por lo que se realiza $\frac11$ a la izquierda $\frac12$ a la derecha $\frac23=d$ para encontrar el ancestro común más cercano $d$ .
Un procedimiento bastante sencillo es ampliar ambos $a_1/a_2$ y $b_1/b_2$ comme fracciones continuas y luego tomar la parte de la expansión de la fracción continua que concuerda entre ellas, y poner un denominador final que sea uno más que el El más pequeño de los dos primeros elementos en desacuerdo. (*)
A continuación, convierta la fracción continua resultante de nuevo en una fracción ordinaria. El resultado debería ser (si no recuerdo mal) la fracción en $(\frac{a_1}{a_2},\frac{b_1}{b_2})$ que tiene el menor denominador.
*) con algunos casos especiales si el desacuerdo llega justo al final de una o ambas fracciones continuas.
Sólo nos ceñimos a los enteros positivos y con fracciones en los términos más bajos,
Creo que sólo hay que comprobar cada posible $b_2$ hasta $\max(a_2,c_2)$ si $\lfloor (b_2 a_1+a_2)/a_2 \rfloor \times c_2 \lt b_2 \times c_1$ y si es así $b_1 = \lfloor (b_2 a_1+a_2)/a_2 \rfloor$ .
Si no es así, la teoría en la que se basan los árboles de Stern-Brocot me sugiere que necesitará el mediador con $b_1=a_1+c_1$ y $b_2=a_2+c_2$ .
He aquí un algoritmo sencillo y eficaz, expresado explícitamente en Python. Se parece al algoritmo euclidiano para calcular los máximos comunes divisores, y puede derivarse de las descripciones de otras respuestas en términos de fracciones continuas y/o del árbol de Stern-Brocot, pero también es sencillo dar una prueba de corrección que no utilice esos conceptos directamente. Primero daremos el código y luego haremos un esbozo de la prueba de corrección.
Aquí está el código:
def simplest_in_interval(r, s, u, v):
"""
Find simplest fraction in an open subinterval of the positive reals.
Given nonnegative integers r, s, u and v with r*v < s*u, return a pair
x, y of relatively prime positive integers such that x/y is the
simplest fraction in the open interval (r/s, u/v) (in the case v > 0),
or the simplest fraction in the interval (r/s, ∞) (in the case v = 0).
"""
a, b, c, d = 1, 0, 0, 1
while s <= r or u <= v:
q = r // s
r, u, b, d = r - q * s, u - q * v, b + q * a, d + q * c
q = v // u
s, v, a, c = s - q * r, v - q * u, a + q * b, c + q * d
return a + b, c + dUna nota para los que no hablan Python: el // en Python realiza la división por el suelo; es decir, a // b da el valor de $\lfloor a/b\rfloor$ .
He aquí un ejemplo de la función anterior en acción: encontrar la fracción más simple en el intervalo (314/100, 315/100) . (Tenga en cuenta que no es necesario que las fracciones de entrada se den en términos mínimos).
>>> simplest_in_interval(314, 100, 315, 100)
(22, 7)Escriba $J$ para el intervalo abierto especificado originalmente $(r/s, u/v)$ . A medida que el algoritmo avanza, mantenemos ocho variables de valor entero separadas: $a$ , $b$ , $c$ , $d$ , $r$ , $s$ , $u$ y $v$ . Ahora, en cada etapa del algoritmo, se mantienen las siguientes invariantes del bucle:
Los invariantes anteriores pueden establecerse de la forma habitual, comprobando que son verdaderos justo antes de que el while se entra en el bucle por primera vez (en ese momento $K = J$ y $T$ es el mapa de identidad), y luego comprobando que si son verdaderos al comienzo de cualquier iteración del cuerpo del bucle, entonces también son verdaderos al final del cuerpo del bucle para esa iteración.
Cuando el while sale del bucle, debemos tener $r < s$ y $v < u$ o en otras palabras, $r/s < 1 < u/v$ . Así que en ese momento el intervalo $K$ contiene $1$ . Ahora cada fracción en el intervalo original $J$ tiene la forma $(ap + bq) / (cp + dq)$ para algunos $p/q$ sur $K$ y asumiendo que $p/q$ se escribe en términos mínimos, se deduce del hecho de que $ad-bc = 1$ que $(ap + bq) / (cp + dq)$ también se escribe en términos mínimos. Como $a$ , $b$ , $c$ y $d$ son todas no negativas, la fracción más simple posible surge cuando $p$ y $q$ son mínimos, es decir, cuando $p = q = 1$ y esa fracción más simple es $(a + b) / (c + d)$ .
Hay una última cosa que debemos saber, y es que el while bucle hace salida - es decir, que el while la condición del bucle finalmente se convierte en falsa, y que no entramos simplemente en un bucle infinito. Para ello, basta con observar que en cada iteración del bucle, o bien $r$ o $v$ disminuye, y ninguno aumenta. Dado que ambos $r$ y $v$ permanecen no negativas, no podemos continuar esos decrecimientos indefinidamente, por lo que el bucle debe terminar después de un número finito de iteraciones. Esto completa el esbozo de la prueba.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
