A continuó fracción es una serie de divisiones de este tipo:algoritmo óptimo para calcular el resultado de una fracción continua
depth 1 1+1/s
depth 2 1+1/(1+1/s)
depth 3 1+1/(1+1/(1+1/s))
. . .
. . .
. . .
la profundidad es un número entero, pero s es un número de coma flotante.
¿Cuál sería un algoritmo óptimo (en función del rendimiento) para calcular el resultado de una fracción de este tipo con una gran profundidad?
Pista: desenrollar cada una de estas fórmulas usando álgebra básica. Verás un patrón emergente.
te muestro los primeros pasos por lo que se hace evidente:
f(2,s) = 1+1/s = (s+1)/s
f(3,s) = 1+1/f(2,s) = 1+(s/(s+1)) = (1*(s+1) + s)/(s+1) = (2*s + 1)/(s + 1)
/* You multiply the first "1" by denominator */
f(4,s) = 1+1/f(3,s) = 1+(s+1)/(2s+1) = (1*(2*s+1) + (s+1))/(2*s+1) = (3*s + 2)/(2*s + 1)
f(5,s) = 1+1/f(4,s) = 1+(2s+1)/(3s+2) = (1*(3*s+2) + (2s+1))/(3*s+2) = (5*s + 3)/(3*s + 2)
...
Hint2: si no ve el patrón obvio forma emergente de lo anterior, la más óptima Algoritmo implicaría calcular los números de Fibonacci (por lo que necesitaría buscar el generador de Fibonacci # óptimo).
NOTA: al no tener conocimientos de álgebra básica en inglés, espero no haber mezclado el "denominador" y el "nominador" en el comentario anterior, espero que las fórmulas sean lo suficientemente obvias para ellos, incluso si confundí la terminología. – DVK
No, creo que lo tienes correcto. El Numerador es el número en la "parte superior" de la división, y el denominador está en la "parte inferior". IE, 2/3 -> Numerador = 2; Denominador = 3 – Daenyth
@Daenyth - ¡Thx! – DVK
Huele a recursividad de cola (recursión (recursión (...))).
(En otras palabras - bucle)
Generalmente C no admite recursividad de cola. –
@James Black Pero cualquier algoritmo recursivo se puede desenrollar :-) No cambia la complejidad del tiempo de ejecución. (No estoy argumentando que esta sea una buena respuesta para el algoritmo "óptimo".) –
@James Black: Como @pst menciona, estoy abogando por transformar el problema recursivo de la cola (en el nivel conceptual) en un bucle (en el nivel del código), que probablemente sea un proceso bastante trivial. Ahí es donde entra mi comentario de "bucle", aunque supongo que podría haber sido más claro. –
Me gustaría empezar con el cálculo 1/s, que llamaremos a.
Luego use un bucle for, ya que, si usa recursividad, en C, puede experimentar un desbordamiento de la pila.
Dado que esto es tarea, no daré mucho código, pero, si comienzas con un bucle simple, de 1, entonces sigues aumentando, hasta llegar a 4, entonces puedes ir a n veces.
Dado que siempre va a dividir 1/s y la división es costosa, simplemente hacerlo una vez ayudará con el rendimiento.
Espero que si lo resuelves, puedas encontrar un patrón que te ayude a optimizar aún más.
Puede encontrar un artículo como este: http://www.b-list.org/weblog/2006/nov/05/programming-tips-learn-optimization-strategies/, para ser útil.
Supongo que, por rendimiento, quiere decir que quiere que sea rápido, independientemente de la memoria utilizada, por cierto.
Puede encontrar que si almacena en caché los valores que calculó, en cada paso, puede reutilizarlos, en lugar de volver a hacer un cálculo costoso.
Personalmente, hago 4-5 pasos a mano, escribiendo las ecuaciones y los resultados de cada paso, y veo si surge algún patrón.
Actualización:
GCC ha añadido la recursión de cola, y nunca he dado cuenta de que, desde que trate de limitar en gran medida la recursividad en C, por hábito. Pero esta respuesta tiene una buena explicación rápida de las diferentes optimizaciones que hizo gcc en función del nivel de optimización.
http://answers.yahoo.com/question/index?qid=20100511111152AAVHx6s
sus algoritmos definitivamente NO son los más óptimos, aunque es la implementación más óptima de ese algoritmo en particular. – DVK
@DVK - No estoy tratando de dar el algoritmo más óptimo, ya que fue enumerado como tarea, sino para indicar una forma de quizás encontrar un mejor algoritmo, por lo que sugerí hacer varios pasos a mano para encontrar un patrón , para que se pueda encontrar una solución mejor que la sugerida. –
Me gustaría elaborar un poco en DVK's excellent answer. Me quedaré con su notación f(d,s) para denotar el valor buscado para la profundidad d.
Si calcula el valor f(d,s) para grande d, observará que los valores convergen como d aumenta.
Deje φ = f (∞, s). Es decir, φ es el límite como d se acerca al infinito, y es la fracción continua completamente expandida. Tenga en cuenta que φ contiene una copia de sí mismo, por lo que podemos escribir φ = 1 + 1/φ. Multiplicando ambos lados por φ y reordenando, obtenemos la ecuación cuadrática
φ - φ - 1 = 0
que puede resolverse para obtener
φ = (1 + √ 5)/2.
Este es el famous golden ratio.
Encontrará que f(d,s) está muy cerca de φ como d obtiene grande.
Pero espera. ¡Hay más!
Como señaló DVK, la fórmula para f(d,s) implica términos de la secuencia de Fibonacci. En particular, implica proporciones de términos sucesivos de la secuencia de Fibonacci. Hay una closed form expression for the nth term of the sequence, a saber
(φ n - (1- φ) n)/√ 5.
Desde 1- φ es menor que uno, (1- φ) n se pone pequeño como n se hace grande, por lo que una buena aproximación para el enésimo término de Fibonacci es φ n/√ 5. Y volviendo a la fórmula de DVK, la proporción de términos sucesivos en la secuencia de Fibonacci tenderá a φ n + 1/φ n = φ.
Así que esa es una segunda forma de llegar al hecho de que la fracción continua en esta pregunta se evalúa como φ.
esto no es tarea porque mi escuela está cerrada el pasado julio, ahora estoy sentado en mi casa y solo estoy tratando de resolver algún problema –
Ya que lo más probable es que quiera resolverlo usted mismo, para obtener el mejor efecto de aprendizaje, creo es bueno tratar esta pregunta como si fuera tarea. – Svante