Nombres de Fibonacci dans la langue C

«Soit N 0. Le numéro Fibonacci pour 0 est:

0

Soit n être 1. Le numéro Fibonacci pour 1 est:

1

Soit n être 2. Le numéro Fibonacci pour 2 est:

1 + 0 = 1

Soit n être 3. Le numéro Fibonacci pour 3 est:

1 + 1 = 2

Soit N 4. Le numéro Fibonacci pour 4 est:

2 + 1 = 3

Soit N 5. Le numéro Fibonacci pour 5 est:

3 + 2 = 5

Soit n 6. Le numéro Fibonacci pour 6 est:

5 + 3 = 8

Soit n être 7. Le numéro Fibonacci pour 7 est:

8 + 5 = 13

Soit n être 8. Le numéro Fibonacci pour 8 est:

13 + 8 = 21

Soit N 9. Le numéro Fibonacci pour 9 est:

21 + 13 = 34

Le tableau suivant montre les douze premiers numéros de Fibonacci:

La première ligne donne les nombres de Fibonacci. La deuxième ligne donne les index basés sur zéro pour le tableau correspondant. Ces index sont les différents n entiers, à partir de zéro. On peut voir dans le tableau que le dixième numéro Fibonacci est de 34 + 21 = 55. De plus, le onzième nombre de Fibonacci est, 55 + 34 = 89 .

Le but de cet article est de produire un numéro de Fibonacci en temps o (n) et en temps constant o (1), en utilisant le langage informatique C.

Les numéros de Fibonacci sont des entiers, à partir de 0."

La formule pour un numéro Fibonacci

Comme le montre le tableau ci-dessus, le numéro de Fibonacci actuel est la somme des deux nombres précédents. Le numéro Fibonacci pour 0 est 0, et le numéro Fibonacci pour 1 est 1. Ces deux premiers chiffres, dans leur ordre, doivent être acceptés comme tels. Développer les nombres de Fibonacci suivants, commencez à partir de là, pour donner 1 + 0 = 1; 1 + 1 = 2; 2 + 1 = 3, etc.

La formule d'un numéro Fibonacci particulier peut être donnée en trois lignes ou une ligne. La formule en trois lignes est donnée comme suit:

Cette formule est la définition d'un numéro Fibonacci.

Produire des nombres de fibonacci en temps o (n)

Plus d'un numéro de Fibonacci peut être produit à partir de zéro pour une valeur donnée de n. Dans ce cas, N est l'index le plus élevé plus 1 pour le tableau - Supposons l'indexation basée sur le zéro. Le numéro Fibonacci pour i = 0 est produit (i.E 0). Le numéro Fibonacci pour i = 1 est alors produit (i.e., 1). Le numéro Fibonacci pour i = 2 est ensuite produit ensuite (i.e., 1 encore). Le numéro Fibonacci pour i = 3 est alors produit (i.e., 2). Le numéro Fibonacci pour i = 4 est alors produit (i.e., 3). Cela se poursuit jusqu'à ce que le numéro Fibonacci pour le nombre donné (indice) de n, disons 12, pour l'indice le plus élevé de 11, soit produit (89).

Un programme C qui prend les entrées du clavier et le publie au terminal (écran) commence par:

#inclure

Avec cette directive de prétraitement, le texte tapé sur le clavier apparaît à l'écran. La sortie du programme apparaîtra également à l'écran. La fonction Fibonacci est:

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

Les deux premières déclarations de la fonction sont considérées comme deux opérations. Le corps de la boucle pour peut être considéré comme une seule opération. Si n est 12, alors le corps de la boucle for-fonction fonctionne 10 fois parce que les premières et deuxième opérations, pour l'index 0 et l'index 1, ont déjà eu lieu. Cela donne une complexité temporelle d'O (12), écrite comme o (n).

Remarque la déclaration:

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

Dans le corps de la boucle pour. Il ajoute les deux nombres Fibonacci précédents pour obtenir le numéro de Fibonacci actuel (NextNO).

Une fonction principale C appropriée pour le programme ci-dessus est:

int main (int argc, char ** argv)

int n = 12;
int arr [12];
Fibonacci (arr, n);
pour (int i = 0; iprintf ("% i",, arr [i]);
printf ("\ n");
retour 0;

Produisant un numéro de fibonacci en temps constant

Ci-dessus, l'indice du numéro Fibonacci, 89, est de 11, et non 12, pour l'indexation zéro. Soit 11 n. Dans ce cas, le numéro de Fibonacci actuel est de 89. Si n est 10, le numéro de Fibonacci actuel serait de 55. Si n est 9, le numéro de Fibonacci actuel serait 34. Cela continue vers le bas jusqu'à ce que n est 0, le numéro de Fibonacci serait 0.

Il existe une formule mathématique pour obtenir le (un) numéro de fibonacci actuel, étant donné l'index (numéro) basé sur zéro, avec le nom de variable n. La formule est:

Notez que sur le côté droit de l'équation, ce n'est pas la racine carrée de 5 qui est élevée au pouvoir n; c'est l'expression entre parenthèses qui est élevée au pouvoir n. Il y a deux telles expressions.

Donc, quand n est 0, fib_n sera 0. Quand n est 1, fib_n sera 1. Quand n est 2, FIB_n sera 1. Quand n est 3, fib_n sera 2 - et ainsi de suite.

Cette fonction mathématique est une opération principale, et elle ne renvoie qu'un seul numéro Fibonacci et non une séquence de nombres correspondant, disons, index 0 à l'index 11. Ceci est un code temporel constant. Il peut toujours être utilisé pour produire une séquence de nombres de Fibonacci en l'appelant simplement encore et encore avec différentes valeurs de n, comme index, dans un programme.

La complexité temporelle de cette fonction mathématique pour produire son numéro de fibonacci est o (1), temps constant.

Maintenant, cette fonction mathématique est codée ci-dessous pour produire 12 nombres de fibonacci. Il utiliserait moins de temps global que l'algorithme précédent.

Le code pour cette fonction mathématique pour produire son numéro de fibonacci est:

#inclure
#inclure
double fibno (int n)
double fibn = (pow ((1 + sqrt (5)) / 2, n) - pow ((1-sqrt (5)) / 2, n)) / sqrt (5);
retour fibn;

Notez que les mathématiques.La bibliothèque H est incluse cette fois, qui apporte les fonctions prédéfinies de puissance (POW) et Square Root (SQRT) au programme. La fonction ne produit qu'un seul numéro Fibonacci et non une séquence d'entre elles. Une fonction principale appropriée pour ce code est:

int main (int argc, char ** argv)

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

Avec un index de 11, la sortie est de 89.000000. Cependant, pour exécuter ce programme avec le compilateur GCC, utilisez une ligne de commande comme:

gcc temp.c -o temp -lm

où «temp.C ”est le code source et« Temp »est le programme compilé. Notez l'utilisation de l'interrupteur, «-lm», où «l» est minuscule L.

Conclusion

Le premier numéro Fibonacci est 0. Le deuxième numéro de Fibonacci est 1. Les autres sont obtenus en ajoutant les deux numéros de Fibonacci précédents. Les chiffres Fibonacci sont des entiers. Pour obtenir la séquence des nombres de Fibonacci à partir de zéro en temps O (n), utilisez une fonction avec une instruction comme:

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

où Nextno est le numéro actuel de l'index I, et «A» est le tableau pour contenir les numéros de séquence Fibonacci. Les deux premiers nombres, 0 et 1, sont produits indépendamment.

Pour obtenir un seul numéro Fibonacci en O (1) Temps, utilisez la formule mathématique:

où n est l'indice basé sur zéro.

Les nombres de Fibonacci peuvent être obtenus à l'aide de matrices mathématiques. Cependant, c'est une discussion pour une autre fois.