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 ?

○integer: c(integer: n, integer: k)
  if (k = 0 or k = n)
    return 1
  endif
  return c(n − 1, k − 1) + c(n − 1, k)

Afficher la réponse et l'explication

Réponse : C. 11

c(n, k) calcule le nombre de façons de choisir k éléments parmi n (le coefficient binomial) à l'aide de la relation du triangle de Pascal. c(4, 2) appelle c(3, 1) et c(3, 2) ; ceux-ci appellent c(2, 0) et c(2, 1), puis c(2, 1) et c(2, 2) ; chacun des deux appels c(2, 1) appelle c(1, 0) et c(1, 1). Il y a 6 appels qui renvoient 1 et 5 appels qui en effectuent deux autres, soit 11 au total. La valeur de retour est 6, égale au nombre d'appels qui renvoient 1.

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

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

⊕ 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 ?
La procédure bubble suivante est un tri à bulles qui trie le tableau d'entiers data par ordre croissant. swap(data, j, k) est une procédure qui échange les valeurs de data[j] et data[k]. Les indices du tableau commencent à 1. Que faut-il écrire à la place de 【a】 dans le programme ?