sucesion fibonacci

En matemática, la sucesión de Fibonacci (a veces mal llamada serie de Fibonacci) es la siguiente sucesión infinita de números naturales:
0, 1, 1, 2, 3, 5, 8, 13, 21

La sucesión inicia con 1 , 1 a partir de ahí cada elemento es la suma de los dos anteriores.
A cada elemento de esta sucesión se le llama número de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemáticas y teoría de juegos. También aparece en configuraciones biológicas, como por ejemplo en las ramas de los árboles, en la disposición de las hojas en el tallo, en la flora de la alcachofa y en el arreglo de un cono.


Antes de que Fibonacci escribiera su trabajo, la sucesión de los números de Fibonacci había sido descubierta por matemáticos indios tales como Pingala (200 a.c.), Gopala (antes de 1135) y Hemachandra (c. 1150), quienes habían investigado los patrones rítmicos que se formaban con sílabas o notas de uno o dos pulsos. El número de tales ritmos (teniendo juntos una cantidad n de pulsos) era fn+1 , que produce explícitamente los números 0, 1, 1, 2, 3, 5, 8, 13, 21, etc.
La sucesión fue descrita por Fibonacci como la solución a un problema de la cría de conejos: "Cierto hombre tenía una pareja de conejos juntos en un lugar cerrado y uno desea saber cuántos son creados a partir de este par en un año cuando es su naturaleza parir otro par en un simple mes, y en el segundo mes los nacidos parir también

Nota: al contar la cantidad de letras distintas en cada mes, se puede saber la cantidad de parejas totales que hay hasta ese mes.
De esta manera Fibonacci presentó la sucesión en su libro Liber Abaci, publicado en 1202. Muchas propiedades de la sucesión de Fibonacci fueron descubiertas por Édouard Lucas, responsable de haberla denominado como se la conoce en la actualidad

También Kepler describió los números de Fibonacci, y el matemático escocés Robert Simson descubrió en 1753 que la relación entre dos números de Fibonacci sucesivos http://upload.wikimedia.org/wikipedia/es/math/b/9/1/b91591398b0bbe2d52bf29c05f0ee57a.png se acerca a la relación áurea fi ( http://upload.wikimedia.org/wikipedia/es/math/3/5/3/3538eb9c84efdcbd130c4c953781cfdb.png ) cuanto más se acerque a infinito; es más: el cociente de dos términos sucesivos de toda sucesión recurrente de orden dos tiende al mismo límite. Esta serie ha tenido popularidad en el siglo XX especialmente en el ámbito musical, en el que compositores con tanto renombre como Béla Bartók, Olivier Messiaen y Delia Derbyshire la han utilizado para la creación de acordes y de nuevas estructuras de frases
musicales

1.-Recursividad:

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * ..., incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.

El siguiente párrafo muestra una función, expresada con palabras, que calcula un factorial.

"Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato."

Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.

La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.

Claramente, esta técnica puede constituir un modo de meterse en problemas. Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito".

Para entender mejor lo que en realidad es el concepto de recursión veamos un poco lo referente a la secuencia de Fibonacci.

Principalmente habría que aclarar que es un ejemplo menos familiar que el del factorial, que consiste en la secuencia de enteros.

0,1,1,2,3,5,8,13,21,34,...,

Cada elemento en esta secuencia es la suma de los precedentes (por ejemplo 0 + 1 = 0, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, ...) sean fib(0) = 0, fib (1) = 1 y así sucesivamente, entonces puede definirse la secuencia de Fibonacci mediante la definición recursiva (define un objeto en términos de un caso mas simple de si mismo):

fib (n) = n if n = = 0 or n = = 1

fib (n) = fib (n - 2) + fib (n - 1) if n >= 2

Por ejemplo, para calcular fib (6), puede aplicarse la definición de manera recursiva para obtener:

Fib (6) = fib (4) + fib (5) = fib (2) + fib (3) + fib (5) = fib (0) + fib (1) + fib (3) + fib (5) = 0 + 1 fib (3) + fib (5)

+ fib (1) + fib (2) + fib(5) =
+ 1 + fib(0) + fib (1) + fib (5) =
+ 0 + 1 + fib(5) = 3 + fib (3) + fib (4) =
3 + 1 + fib (0) + fib (1) + fib (4) =

+ fib (1) + fib (2) + fib (4) =
+ 0 + 1 + fib (2) + fib (3) = 5 + fib (0) + fib (1) + fib (3) =
+ 0 + 1 + fib (1) + fib (2) = 6 + 1 + fib (0) + fib (1) =
+ 0 + 1 = 8
Obsérvese que la definición recursiva de los números de Fibonacci difiere de las definiciones recursivas de la función factorial y de la multiplicación . La definición recursiva de fib se refiere dos veces a sí misma . Por ejemplo, fib (6) = fib (4) + fib (5), de tal manera que al calcular fib (6), fib tiene que aplicarse de manera recursiva dos veces. Sin embargo calcular fib (5) también implica calcular fib (4), así que al aplicar la definición hay mucha redundancia de cálculo. En ejemplo anterior, fib(3) se calcula tres veces por separado. Sería mucho mas eficiente "recordar" el valor de fib(3) la primera vez que se calcula y volver a usarlo cada vez que se necesite. Es mucho mas eficiente un método iterativo como el que sigue parar calcular fib (n).

If (n < = 1)

return (n);

lofib = 0 ;

hifib = 1 ;

for (i = 2; i < = n; i ++)

{

x = lofib ;

lofib = hifib ;

hifib = x + lofib ;

} /* fin del for*/

return (hifib) ;

Compárese el numero de adiciones (sin incluir los incrementos de la variable índice, i) que se ejecutan para calcular fib (6) mediante este algoritmo al usar la definición recursiva. En el caso de la función factorial, tienen que ejecutarse el mismo numero de multiplicaciones para calcular n! Mediante ambos métodos: recursivo e iterativo. Lo mismo ocurre con el numero de sumas en los dos métodos al calcular la multiplicación. Sin embargo, en el caso de los números de Fibonacci, el método recursivo es mucho mas costoso que el iterativo.


podria seguir, pero seguro que nadie paso del tercer renglon, y si lo hicieron, no creo que nadie entienda ni j, pero si llegaron hasta aca, se merecen lo que sigue......................




o si prefieren algo mas util.......................