Bases de la programmation (trace de pseudo-code)

Quelle est la valeur de retour de la fonction fib suivante appelée sous la forme fib(10) ?

○integer: fib(integer: n)
  integer: a ← 0, b ← 1, t
  for (i from 1 to n step 1)
    t ← a + b
    a ← b
    b ← t
  endfor
  return a

Afficher la réponse et l'explication

Réponse : B. 55

Chaque passage fait avancer (a, b) d'une paire de nombres de Fibonacci voisins : (0, 1) → (1, 1) → (1, 2) → (2, 3) → (3, 5) → (5, 8) → (8, 13) → (13, 21) → (21, 34) → (34, 55) → (55, 89). Après 10 passages, la fonction renvoie a = 55. Après le i-ème passage, a est le i-ème nombre de Fibonacci. Une implémentation naïve par récursion calcule plusieurs fois les mêmes valeurs, alors que celle-ci n'a besoin que de n passages.

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

Autres questions sur Bases de la programmation (trace de pseudo-code)

Lorsque la fonction c suivante est appelée sous la forme c(4, 2), combien de fois c est-elle appelée, premier appel compris ?
⊕ désigne le OU exclusif bit à bit. Quelles sont les valeurs de x et y après l'exécution du programme suivant ?
x et y sont des entiers non signés sur 8 bits. << et >> sont des décalages logiques : les bits libérés sont remplis par 0, et les bits qui sortent des 8 bits sont perdus. ∨ désigne le OU bit à bit. Quelle est la valeur de y après l'exécution du programme suivant ?
∧ désigne le ET bit à bit. Quelle est la valeur de c après l'exécution du programme suivant ?
x et y sont des entiers non signés sur 8 bits. << et >> sont des décalages logiques : les bits libérés sont remplis par 0, et les bits qui sortent des 8 bits sont perdus. ∨ désigne le OU bit à bit. Avec x = 75, quelle est la valeur de y après l'affectation suivante ?