Números de fibonacci en lenguaje C

"Sea n 0. El número de fibonacci para 0 es:

0

Sea n 1. El número de fibonacci para 1 es:

1

Sea n 2. El número de fibonacci para 2 es:

1 + 0 = 1

Sea N 3. El número de fibonacci para 3 es:

1 + 1 = 2

Sea n 4. El número de fibonacci para 4 es:

2 + 1 = 3

Sea n 5. El número de fibonacci para 5 es:

3 + 2 = 5

Deje que sea 6. El número de fibonacci para 6 es:

5 + 3 = 8

Sea n 7. El número de fibonacci para 7 es:

8 + 5 = 13

Sea N 8. El número de fibonacci para 8 es:

13 + 8 = 21

Sea N 9. El número de fibonacci para 9 es:

21 + 13 = 34

La siguiente tabla muestra los primeros doce números de Fibonacci:

La primera fila da los números de fibonacci. La segunda fila proporciona los índices basados ​​en cero para la matriz correspondiente. Estos índices son los diferentes n enteros, que comienzan desde cero. Se puede ver desde la tabla que el décimo número de fibonacci es 34 + 21 = 55. Además, el undécimo número de fibonacci es, 55 + 34 = 89 .

El objetivo de este artículo es producir un número de fibonacci en el tiempo O (n) y en el tiempo constante o (1), utilizando el lenguaje de la computadora c.

Los números de Fibonacci son enteros, que comienzan desde 0."

La fórmula para un número de fibonacci

Como se ve en la tabla anterior, el número actual de fibonacci es la suma de los dos números anteriores. El número Fibonacci para 0 es 0, y el número Fibonacci para 1 es 1. Estos dos primeros números, en su orden, deben aceptarse como tales. Desarrollando los siguientes números de Fibonacci, comience desde allí, para dar 1 + 0 = 1; 1 + 1 = 2; 2 + 1 = 3, etc.

La fórmula para un número de fibonacci en particular se puede dar en tres líneas o una línea. La fórmula en tres líneas se da como sigue:

Esta fórmula es la definición de un número de fibonacci.

Producir números de fibonacci en el tiempo o (n)

Se puede producir más de un número de fibonacci a partir de cero para un valor dado de n. En este caso, N es el índice más alto más 1 para la matriz, suponga la indexación basada en cero. Se produce el número de fibonacci para i = 0 (i.E 0). Luego se produce el número de fibonacci para i = 1 (i.mi., 1). El número de fibonacci para i = 2 se produce a continuación (i.mi., 1 otra vez). Luego se produce el número de fibonacci para i = 3 (i.mi., 2). Luego se produce el número de fibonacci para i = 4 (i.mi., 3). Esto continúa hasta que se produce el número Fibonacci para el número dado (índice) de N, digamos 12, para el índice más alto de 11, (89).

Un programa C que toma la entrada del teclado y la lleva al terminal (pantalla) comienza con:

#incluir

Con esta directiva de preprocesamiento, aparecerá texto escrito en el teclado en la pantalla. La salida del programa también aparecerá en la pantalla. La función fibonacci es:

void fibonacci (int a [], int n)
if (n> 0)
A [0] = 0;
if (n> 1)
A [1] = 1;
para (int i = 2; iint nextno = a [i - 1] + a [i - 2];
A [i] = nextno;

Las dos primeras declaraciones en la función se consideran dos operaciones. El cuerpo del for-bucle puede considerarse como una operación. Si n es 12, entonces el cuerpo del bucle for-boil funciona 10 veces porque las operaciones de primera y segunda, para el índice 0 y el índice 1, ya han tenido lugar. Esto da una complejidad de tiempo de O (12), escrita como o (n).

Tenga en cuenta la declaración:

int nextno = a [i - 1] + a [i - 2];

En el cuerpo del bucle. Agrega los dos números de fibonacci anteriores para obtener el número actual de Fibonacci (Nextno).

Una función principal C adecuada para el programa anterior es:

int main (int argc, char ** argv)

int n = 12;
int arr [12];
fibonacci (arr, n);
para (int i = 0; iprintf ("%i", arr [i]);
printf ("\ n");
regresar 0;

Producir un número de fibonacci en tiempo constante

Arriba, el índice para el número Fibonacci, 89, es 11, y no 12, para la indexación basada en cero. Sea 11. En este caso, el número actual de Fibonacci es 89. Si N es 10, el número actual de Fibonacci sería 55. Si N es 9, el número actual de Fibonacci sería 34. Esto continúa hacia abajo hasta que cuando n es 0, el número de fibonacci sería 0.

Hay una fórmula matemática para obtener el número actual (uno) Fibonacci, dado el índice (número) basado en cero, con el nombre de la variable n N. La fórmula es:

Tenga en cuenta que en el lado derecho de la ecuación, no es la raíz cuadrada de 5 la que se eleva al poder n; Es la expresión entre paréntesis la que se eleva al poder n. Hay dos de esas expresiones.

Entonces, cuando n es 0, fib_norte será 0. Cuando n es 1, fib_norte será 1. Cuando n es 2, fib_norte será 1. Cuando n es 3, fib_norte serán 2, y así sucesivamente.

Esta función matemática es una operación principal, y devuelve solo un número de fibonacci y no una secuencia de números correspondientes al índice 0 al índice 11. Este es un código de tiempo constante. Todavía se puede usar para producir una secuencia de números de Fibonacci simplemente llamándolo una y otra vez con diferentes valores de N, como índices, en un programa.

La complejidad del tiempo para esta función matemática para producir su único número de fibonacci es o (1), tiempo constante.

Ahora, esta función matemática se codifica a continuación para producir 12 números de Fibonacci. Usaría menos tiempo general que el algoritmo anterior.

El código para esta función matemática para producir su único número de fibonacci es:

#incluir
#incluir
doble fibno (int n)
doble fibn = (pow ((1+sqrt (5))/2, n) - pow ((1 -sqrt (5))/2, n))/sqrt (5);
return fibn;

Tenga en cuenta que las matemáticas.La biblioteca H se incluye esta vez, que trae funciones predefinidas de Power (POW) y Root Square (SQRT) al programa. La función produce solo un número de fibonacci y no una secuencia de ellos. Una función principal adecuada para este código es:

int main (int argc, char ** argv)

int n = 11;
doble fibn = fibno (n);
printf ("%lf \ n", fibn);
regresar 0;

Con un índice de 11, la salida es 89.000000. Sin embargo, para ejecutar este programa con el compilador GCC, use una línea de comando como:

Temperadora de GCC.C -O temp -lm

Donde "temperatura.C "es el código fuente, y" temp "es el programa compilado. Tenga en cuenta el uso del interruptor, "-lm", donde "l" es en minúscula l.

Conclusión

El primer número de fibonacci es 0. El segundo número de fibonacci es 1. El resto se obtiene agregando los dos números de Fibonacci anteriores. Los números de Fibonacci son enteros. Para obtener la secuencia de números de fibonacci de cero en el tiempo O (n), use una función con una declaración como:

int nextno = a [i - 1] + a [i - 2];

Donde NextNo es el número actual del índice I, y "A" es la matriz para contener los números de secuencia Fibonacci. Los dos primeros números, 0 y 1, se producen de forma independiente.

Para obtener solo un número de fibonacci en el tiempo o (1), use la fórmula matemática:

donde n es el índice basado en cero.

Los números de Fibonacci se pueden obtener utilizando matrices de matemáticas. Sin embargo, esta es una discusión por otro tiempo.