TD — Séance 5 — Les fonctions et procédures

Appeler, transmettre, empiler, concevoir

TD de la séance 5 d’Algorithmique : découper, nommer, appeler.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Dérouler à la main des appels de fonctions et de procédures, distinguer le passage par valeur du passage en entrée-sortie (E/S), dessiner la pile des appels à un instant donné, repérer les erreurs propres aux sous-programmes, puis écrire et vérifier ses propres fonctions. Une trace se remplit comme dans le CM : une ligne par pas, la ligne exécutée, la pile (les appels en cours au-dessus du programme principal), les variables groupées par cadre d’appel (mettre en gras la valeur qui change ; un paramètre E/S s’écrit \(\rightarrow\)x), le test ou la valeur rendue, et ce qu’écrit Écrire ; un arrêt sur erreur s’écrit « arrêt » avec sa cause.

Exercice 1 : une fonction qui modifie son paramètre

À Ziguinchor, un agent relève les compteurs d’eau ; la fonction suivante compte les chiffres d’un index.

Fonction nbChiffres(n : entier) : entier
  c ← 0
  Répéter
    n ← n div 10
    c ← c + 1
  Jusqu'à n = 0
  Retourner c
FinFonction
Début
  k ← 4072
  d ← nbChiffres(k)
  Écrire k, d
  Écrire nbChiffres(0)
Fin

  1. Pour l’appel de la ligne 11, relever, à chaque tour de Répéter, n après la ligne 4, c après la ligne 5 et le résultat du test de la ligne 6.

    Tour n après la ligne 4 c après la ligne 5 Test de la ligne 6

  2. Qu’écrit la ligne 12 ? Pourquoi k vaut-il encore 4072, alors que n est devenu 0 ?

  3. Qu’écrit la ligne 13 ? Combien de tours fait la boucle pendant cet appel ?

  4. On remplace les lignes 3 à 6 par TantQue \(\texttt{n}>0\) Faire … FinTantQue, avec le même corps. Qu’écrivent les lignes 12 et 13 ? Laquelle des deux versions rend le bon nombre de chiffres de l’index 0 ?

Exercice 2 : des appels dans des expressions

Une boutique de tissus de Saint-Louis accorde 10 % de remise sur un premier article et 20 % sur un second, puis, en période de soldes, 50 % sur le total. Dans la ligne 2, \(\times\) et div ont la même priorité et s’évaluent de gauche à droite : prix \(\times\) taux est calculé avant la division par 100.

Fonction remise(prix : entier, taux : entier) : entier
  Retourner prix - prix × taux div 100
FinFonction
Fonction total(a : entier, b : entier) : entier
  Retourner remise(a, 10) + remise(b, 20)
FinFonction
Début
  t ← total(5000, 2500)
  Écrire t, remise(t, 50)
Fin

  1. Donner la liste des appels, dans l’ordre où ils commencent : la fonction appelée, la ligne de l’appel, les effectifs et la valeur rendue.

    Fonction appelée Ligne de l’appel Effectifs Valeur rendue

  2. Donner la pile des appels, avec les variables de chaque cadre, à chaque exécution de la ligne 2. Quelle est la hauteur maximale de la pile ?

    Ligne 2 cadre 1 (bas) cadre 2 cadre 3 (sommet)

  3. Qu’écrit la ligne 9 ?

  4. La ligne 5 devient Retourner remise(10, a) + remise(20, b). Qu’écrit l’algorithme ? Quelle règle de l’appel cette ligne ne respecte-t-elle pas ?

Exercice 3 : une procédure qui transmet ses paramètres

Au marché de Kaolack, deux sacs d’arachide sont pesés ; la procédure ordonner range les deux poids, le plus léger d’abord.

Procédure echanger(E/S a : entier,
    E/S b : entier)
  t ← a
  a ← b
  b ← t
FinProcédure
Procédure ordonner(E/S x : entier,
    E/S y : entier)
  Si x > y Alors
    echanger(x, y)
  FinSi
FinProcédure
Début
  p ← 8
  q ← 3
  ordonner(p, q)
  Écrire p, q
  ordonner(p, q)
  Écrire p, q
Fin

  1. Tracer l’exécution jusqu’à la fin du premier appel de ordonner (ligne 16). Au moment où la ligne 4 est exécutée, donner chaque cadre de la pile avec ses variables (valeurs ou renvois). Quelle variable la ligne 4 modifie-t-elle effectivement ?

    Cadre Variables (valeur, ou renvoi \(\rightarrow\))
    sommet
    milieu
    bas

  2. Qu’écrivent les lignes 17 et 19 ? Que fait le second appel de ordonner ?

  3. On retire E/S devant x et y (lignes 7 et 8), en gardant celles d’echanger. Qu’écrit l’algorithme ?

  4. On remet les E/S de ordonner, mais on retire celles d’echanger (lignes 1 et 2). Qu’écrit l’algorithme ?

  5. On revient à l’algorithme de départ, mais la ligne 10 devient echanger(p, q). Que se passe-t-il ? Pourquoi ?

Exercice 4 : un tableau par valeur et en entrée-sortie

Le tableau A contient le nombre de sacs de riz restant dans quatre boutiques de Thiès. La procédure placerMin place le plus petit stock en tête, à l’aide d’une fonction posMin.

Fonction posMin(T : tableau[1..n] d'entiers,
    n : entier) : entier
  p ← 1
  Pour i de 2 à n Faire
    Si T[i] < T[p] Alors
      p ← i
    FinSi
  FinPour
  Retourner p
FinFonction
Procédure placerMin(E/S T : tableau[1..n] d'entiers,
    n : entier)
  k ← posMin(T, n)
  tmp ← T[1]
  T[1] ← T[k]
  T[k] ← tmp
FinProcédure
Début
  A : tableau[1..4] d'entiers
  A ← [7, 3, 9, 1]
  placerMin(A, 4)
  Écrire A[1], A[2], A[3], A[4]
Fin

  1. Pour l’appel de posMin, relever à chaque tour \(i\), T[i], T[p] avant le test, le résultat du test de la ligne 5 et p après le tour.

    \(i\) T[i] T[p] avant le test Test de la ligne 5 p après le tour
    2
    3
    4

  2. Au moment où la ligne 9 est exécutée, donner chaque cadre de la pile avec ses variables. Combien de rangées de cases de tableau existent alors ? Lesquelles sont des copies ?

    Cadre Variables (valeur, ou renvoi \(\rightarrow\))
    sommet
    milieu
    bas

  3. Qu’écrit la ligne 22 ?

  4. Qu’écrit l’algorithme si la ligne 11 ne porte pas E/S ?

  5. Qu’écrit l’algorithme si les lignes 14 à 16 sont remplacées par T[1] \(\leftarrow\) T[k] puis T[k] \(\leftarrow\) T[1] ?

Exercice 5 : conception

Partie A. Écrire une fonction puissance(x : entier, k : entier) : entier qui rend \(x^k\) pour \(k\geq0\), à l’aide d’une boucle et de multiplications, puis un programme principal qui écrit puissance(3, 4), puis puissance(5, 0). Numéroter les lignes ; une instruction par ligne.

Algorithme :

  1. Tracer l’algorithme complet (les deux appels). Les colonnes de variables sont à nommer, groupées par cadre d’appel.

    Pas Ligne Pile Test Écrit

  2. Pour l’appel puissance(5, 0) : combien de tours fait la boucle ? Quelle valeur est rendue ? Quelle instruction décide de ce résultat ?

Partie B. Écrire une fonction nbOcc(T, n, x) qui rend le nombre de cases du tableau T (de \(n\) cases) égales à \(x\), puis une fonction majoritaire(T, n, x) : booléen qui appelle nbOcc et rend vrai si \(x\) occupe strictement plus de la moitié des cases. Le programme principal range [2, 7, 2, 2] dans un tableau V et écrit majoritaire(V, 4, 2). Préciser le mode de passage de chaque paramètre.

Algorithme :

  1. Tracer l’algorithme (colonnes groupées par cadre d’appel ; le tableau copié dans majoritaire et nbOcc n’est pas répété). Quelle est la hauteur maximale de la pile, et à quel moment est-elle atteinte ?

    principal majoritaire nbOcc
    Pas Ligne Pile V n x n x c i Test Écrit

  2. Tracer le cas limite d’un tableau d’une case, V \(\leftarrow\) [5], avec \(n=1\) et \(x=5\).

    principal majoritaire nbOcc
    Pas Ligne Pile V n x n x c i Test Écrit

  3. Que rend majoritaire pour [2, 7, 2, 7] et \(x=2\) ? Et si la comparaison de majoritaire est écrite avec \(\geq\) ?

Exercice 6 : nombre d’appels et hauteur de la pile

Fonction divise(d : entier, n : entier) : booléen
  Retourner n mod d = 0
FinFonction
Fonction nbDiv(n : entier) : entier
  c ← 0
  Pour d de 1 à n Faire
    Si divise(d, n) Alors
      c ← c + 1
    FinSi
  FinPour
  Retourner c
FinFonction
Début
  Écrire nbDiv(6), nbDiv(7)
Fin

  1. Pendant l’exécution, combien de fois divise est-elle appelée, et combien de fois nbDiv ? Combien de cadres d’appel sont créés en tout ? Quelle est la hauteur maximale de la pile ?

    n Appels de divise Cadres d’appel créés Valeur rendue par nbDiv
    6
    7

  2. Qu’écrit la ligne 14 ?

  3. Pour \(n\geq2\), un diviseur de \(n\) autre que \(n\) lui-même est au plus \(n\) div 2. Modifier nbDiv pour que la boucle s’arrête à \(n\) div 2, sans changer la valeur rendue. Combien d’appels de divise font alors nbDiv(6) et nbDiv(7) ?

  4. Écrire une fonction estPremier(n) : booléen qui utilise nbDiv (un nombre premier a exactement deux diviseurs). Que rend-elle pour 7, pour 1 et pour 9 ? Quelle est la hauteur maximale de la pile pendant l’appel estPremier(7) ?

Pour cette séance

Le cours

Les slides

Retour au sommet