Français
Menu

Structures de données et algorithmes

Une fonction f(x, y) est définie par « si y vaut 0, renvoyer x ; sinon, renvoyer f(y, x mod y) ». Quand on appelle f(84, 36), quelle est la valeur renvoyée, et combien de fois f est-elle appelée, premier appel compris ?

  1. ARenvoie 12 ; appelée 3 fois
  2. BRenvoie 12 ; appelée 4 fois
  3. CRenvoie 6 ; appelée 3 fois
Afficher la réponse et l'explication

Réponse : A. Renvoie 12 ; appelée 3 fois

f(84, 36) appelle f(36, 12) car 84 mod 36 = 12 ; celle-ci appelle f(12, 0) car 36 mod 12 = 0 ; et comme y vaut 0, elle renvoie 12. Les appels sont f(84, 36), f(36, 12) et f(12, 0), trois au total : il s'agit de l'algorithme d'Euclide pour le plus grand commun diviseur. Comme la fonction renvoie directement le résultat de son appel récursif (récursion terminale), un compilateur qui effectue l'optimisation des appels terminaux peut la transformer en boucle, si bien qu'elle ne consomme pas de plus en plus d'espace sur la pile, quelle que soit la profondeur de la récursion.

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

Autres questions sur Structures de données et algorithmes

  1. 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 ?
  2. 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 ?
  3. 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 ?
  4. Quelle est une caractéristique de l'algorithme de Boyer-Moore, qui recherche un motif dans une chaîne de caractères ?
  5. 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 ?