Université Cadi Ayyad
Faculté des Sciences Semlalia Marrakech
Département d’Informatique
TD3 - Algorithmique II
SMI-S3
Exercice 1
1. Dérouler les sous-algorithmes récursifs suivants pour n = 5 :
Procédure proc1 (n : entier) Procédure proc2 (n : entier)
Début Début
Si (n > 0) alors Si (n > 0) alors
proc1(n - 1); Ecrire(n);
Ecrire(n); proc2(n-1);
FinSi FinSi
FinProcedure FinProcedure
2. Qu’est-ce que vous remarquez ? expliquer ?
3. Dérouler le sous-algorithme suivant pour k=19 et k=13. Dire par la suite ce qu'il fait :
Procédure proc (k : entier)
Début
Si (k > 0) alors
proc (k div 2);
Ecrire (k % 2);
FinSi
FinProcedure
4. Dérouler l’algorithme ci-dessous. Dire par la suite ce qu'il fait :
Fonction fonc(K : Entier, n : Entier) : Entier Algorithme principal;
Début Variable a, b : Entier;
Si (k > 0) alors Début
Ecrire ("Avant appel : ", k, n); aß3;
Retourner fonc(k - 1, n) + n;
bß4;
Ecrire ("Apres appel : " ,k, n);
Ecrire(fonc(a, b));
Sinon
Fin
Retourner 0;
FinSi
Fin
Pr. OUAZZANI TAYBI Ilyass 2023/2024 1/2
Exercice 2 :
1. Ecrire un sous-algorithme itératif qui retourne le quotient de la division entière de
deux entiers en utilisant les soustractions successives.
2. Fournir la version récursive correspondante.
Exercice 3 :
1. Ecrire un sous-algorithme itératif qui permet de calculer la somme des k premiers
carrés. Par exemple, si k est égal à 4, ce sous-algorithme calculera : 12+22+32+42.
2. Ecrire un sous-algorithme récursif qui traite le même problème.
3. Ecrire un algorithme qui utilise ces deux sous-algorithmes.
Exercice 4 :
On considère un jeu à deux joueurs (joueur1 et joueur2). Au début, on dispose de x jetons. A
chaque tour, les joueurs ont droit de prendre soit 1 soit 2 jetons de l'ensemble. Le gagnant
est celui qui prend le ou les derniers jetons. Sachant que chaque joueur a sa propre stratégie
de jeu :
• joueur1 saisit toujours 1 jeton.
• joueur2 saisit 1 jeton si le nombre de jetons est impair, sinon 2 jetons.
1. Ecrire les sous-algorithmes joueur1 et joueur2 qui permettent de représenter la
stratégie de chaque joueur et afficher le nom du vainqueur.
2. Dérouler le jeu quand le joueur1 débute le jeu avec x = 10.
Pr. OUAZZANI TAYBI Ilyass 2023/2024 2/2
