Français
Menu

Structures de données et algorithmes

Une fonction fib(n) qui calcule les nombres de Fibonacci est définie par récursion : « si n vaut 1 ou moins, renvoyer n ; sinon, renvoyer fib(n−1) + fib(n−2) ». Quand on appelle fib(5), combien de fois fib est-elle appelée, premier appel compris ?

  1. A6
  2. B9
  3. C15
Afficher la réponse et l'explication

Réponse : C. 15

Soit C(n) le nombre d'appels pour fib(n). On a C(0) = C(1) = 1 et C(n) = 1 + C(n−1) + C(n−2), donc C(2) = 3, C(3) = 5, C(4) = 9 et C(5) = 15. Comme les mêmes valeurs sont recalculées encore et encore, le nombre d'appels croît exponentiellement avec n : fib(30) fait environ 2,69 millions d'appels. Avec la mémoïsation (une forme de programmation dynamique), qui conserve dans une table les valeurs déjà calculées, seules les six valeurs fib(0) à fib(5) sont calculées et le nombre d'appels tombe à 9 (2n − 1). 6 est le nombre d'arguments distincts, et 9 le nombre d'appels avec mémoïsation.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. On paie 8 yens avec des pièces de 1 yen, 4 yens et 6 yens. Quelle affirmation relie correctement le nombre de pièces choisi par un algorithme glouton, qui utilise d'abord autant que possible la plus grosse pièce, et le nombre minimal de pièces ?
  2. On remplit un sac à dos de capacité 8 avec des objets choisis parmi quatre objets de (poids, valeur) (2, 3), (3, 4), (4, 5) et (5, 6). Il n'existe qu'un exemplaire de chaque objet, et les objets ne peuvent pas être fractionnés. Quelle est la valeur totale maximale pour un poids total de 8 ou moins ?
  3. Quelle est une caractéristique de l'algorithme de Boyer-Moore, qui recherche un motif dans une chaîne de caractères ?
  4. Un tableau dynamique, quand on ajoute un élément alors qu'il est plein, alloue une nouvelle zone de capacité double et y copie tous les éléments. Si l'on ajoute un à un 1000 éléments à un tableau vide de capacité 1, combien de copies d'éléments sont effectuées au total ?
  5. Pour une table de hachage contenant de nombreux éléments et maintenue à un facteur de charge d'environ 0,5, quelle est la raison la plus appropriée pour laquelle l'adressage ouvert avec sondage linéaire tend à être plus rapide que le chaînage (relier les éléments par des listes chaînées) ?