Los números de Fibonacci son simplemente una suma de los dos números de Fibonacci anteriores dado que fib (0) y fib (1) = 1.
Si me piden que escriba un programa para producir términos de Fibonacci, haría lo siguiente:
fib (n)
si n = 1 o 2
volver 1
más
retorno fib (n-1) + fib (n-2)
- ¿Qué tiene de malo el algoritmo de recomendación de la historia de Quora?
- Dado un componente fuertemente conectado, ¿puede determinar en tiempo lineal si la eliminación de un solo nodo convierte el SCC en un gráfico acíclico dirigido?
- ¿Resolver todos los problemas en Project Euler facilita la resolución de problemas en Topcoder?
- Tengo un muy buen conocimiento de C ¿Debo continuar con estructuras de datos o comenzar con C ++?
- ¿Qué es una cola prioritaria?
Como puede ver, ¡el método “o función” contiene llamadas recursivas a sí mismo! Por lo tanto, se llama un método recursivo !
Para analizar cualquier método recursivo, debemos encontrar su relación de recurrencia y resolverla. Resolver la recurrencia es escribirla en su forma cerrada deshaciéndose de las llamadas recursivas. Recuerde que cualquier relación de recurrencia debe incluir llamadas a sí misma y puede incluir algunas otras operaciones. Sin embargo, nuestra recurrencia en este ejemplo incluye solo llamadas recursivas.
La recurrencia del método sería:
[matemáticas] F_n = 1 [/ matemáticas] si n = 0
[matemáticas] F_n = 1 [/ matemáticas] si n = 1
[matemáticas] F_n = F (n-1) + F (n-2) [/ matemáticas] si n> 1
Afortunadamente, este tipo de recurrencias se llama recurrencia lineal. Una recurrencia lineal La ecuación de grado k u orden k es una ecuación de recurrencia que tiene el formato [matemáticas] x_n = A_1x_ {n − 1} + A_2x_ {n − 2} + A_3x_ {n − 3} +… A_kx_ {n − k} (A_n [/ matemáticas] es una constante y [matemáticas] A_k ≠ 0) . [/ math] Su solución es la solución de su ecuación polinómica. Podemos convertirlo a su ecuación polinómica de la siguiente manera:
- cada [matemática] F (n) [/ matemática] se convierte en [matemática] x ^ k [/ matemática] donde k es (el número de términos -1) en la ecuación.
- [math] F (n-1) [/ math] podría convertirse en [math] x ^ {k-1} [/ math] y así sucesivamente. El último término se eleva a la potencia de 0 “[matemática] k = 0 [/ matemática]”.
- cada constante aparece en la recurrencia también debería aparecer en la ecuación polinómica.
Según las afirmaciones anteriores: la recurrencia de Fibonacci podría convertirse a la siguiente ecuación cuadrática:
[matemáticas] x ^ 2 = x ^ 1 +1 [/ matemáticas].
Resolver la ecuación es un poco fácil. Llegaremos a la misma solución dada por Kevin Latimer que es 1.61803398875.
Por cierto, la solución a esta recurrencia se llama la proporción áurea . Tiene muchas aplicaciones. Será muy útil leer sobre esto en Wikipedia siguiendo este enlace
¡Espero que esto ayude!
