Bases de la programmation (trace de pseudo-code)

÷ est la division ; quand le résultat est affecté à une variable entière (y compris un argument de fonction), la partie fractionnaire est supprimée. Lorsque la fonction pow suivante est appelée sous la forme pow(2, 10), combien de fois pow est-elle appelée, premier appel compris ?

○integer: pow(integer: x, integer: n)
  if (n = 0)
    return 1
  endif
  integer: h ← pow(x, n ÷ 2)
  if (n mod 2 = 0)
    return h × h
  endif
  return h × h × x

Afficher la réponse et l'explication

Réponse : A. 5

pow(x, n) calcule x à la puissance n en élevant au carré le résultat de pow(x, n ÷ 2), où n est divisé par deux (avec une multiplication supplémentaire par x quand n est impair). n prend les valeurs 10, 5, 2, 1 et 0, et la récursion s'arrête à n = 0 : pow est donc appelée 5 fois. La valeur de retour est 2¹⁰ = 1024. Diminuer n de 1 à chaque fois, comme dans x × pow(x, n − 1), donnerait 11 appels, de n = 10 jusqu'à 0. En divisant n par deux, le nombre d'appels croît à peu près proportionnellement à log₂ n.

÷ est la division ; quand le résultat est affecté à une variable entière (y compris un argument de fonction), la partie fractionnaire est supprimée. Lorsque la fonction pow suivante est appelée sous la forme pow(2, 10), combien de fois pow est-elle appelée, premier appel compris ?

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