Algorithmique

& Structures de données

TRAVAUX DIRIGES/PRATIQUES & EXAMENS
PREPARATOIRE - LICENCE - CYCLE INGENIEUR

Adel DAHMANE
Maître Technologue – ISETSO
[email protected]

Ons BEN ROMDHANE

Maître Technologue – ISETSO
[email protected]

Notions abordées
ELEMENTS DE BASE D'UN ALGORITHME
STRUCTURES DE CONTROLE
Les structures conditionnelles
Les structures itératives (les boucles)
STRUCTURES DE DONNEES COMPOSEES
Les tableaux
Le type Chaîne de caractère
Le type Structure (Enregistrement)
SOUS PROGRAMMES : LES FONCTIONS ET LES PROCEDURES
RECURSIVITE
ALGORITHMES DE RECHERCHE ET DE TRI

2024/2025
 TYPES DE DONNEES
PARTIE
STRUCTURES DE CONTROLE
TABLEAUX & ENREGISTREMENTS
1
Points abordés :
 Les types de données (intégrés, énumérés, tableaux, enregistrements)
 Les structures conditionnelles simples (réduite et complète) : Si..Alors..[Sinon]..FinSi.
 La structure conditionnelle généralisée : Si..Alors..Sinon Si..Alors…FinSi.
 La structure de choix Selon..Faire.
 Les structures itératives à conditions d'arrêts (Répéter et TantQue)
 La structure itérative complète (Pour)

1) SEQUENCE EQUIVALENTE

Soient a, b et c trois variables entières. Proposer une autre séquence équivalente à celle présentée ci-dessous
en utilisant une seule structure conditionnelle.
Si (a > 0)
Alors c  1
SinonSi (b > 0)
Alors c  1
Sinon c  0
FinSi

Soient P et Q deux expressions logiques. Donner une séquence équivalente à celle présentée ci-dessous en
utilisant deux structures de contrôle conditionnelles.

Si (P Et Q)
Alors Traitement1
Sinon Traitement2
FinSi

2) NOMBRE VALIDE

Un nombre n est dit valide partiel s’il est multiple de l’un des chiffres qui le composent.
Exemple : n =52 est divisible par 2 et non divisible par 5.
Ecrire un algorithme qui permet de saisir un entier n, on suppose qu’il est formé de deux chiffres, et indique
s’il est : valide partiel, non valide partiel ou valide total.
NB : Un nombre n est dit valide total s’il est multiple de deux chiffres qui le composent.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

3) NATURE D'UN TRIANGLE

Un point du plan est défini par deux réels (X, Y) représentant ses coordonnées cartésiennes. Soient
trois points A, B et C. On souhaite déterminer la nature du triangle ABC. Un triangle peut être soit :
 Plat : est un triangle ayant les sommets alignés ;
 Isocèle : est un triangle ayant au moins deux côtés de même longueur ;
 Equilatéral : est un triangle dont les trois côtés ont la même longueur ;
 Scalène : est un triangle qui n'est ni isocèle ni plat.

2
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
Travail demandé :
Écrire un algorithme qui permet de :
1. Saisir les coordonnées des trois points A, B et C.
2. Afficher la nature du triangle ABC (plat, équilatéral, isocèle,
scalène). Sachant qu'un triangle équilatéral est aussi isocèle,
alors dans ce cas, l'algorithme affiche seulement la
caractéristique équilatérale.

Exemple - Soient les coordonnées suivantes :

A(xa, ya) = A(1,1) , B(xb, yb) = B(5,1) et C(xc, yc) = C(3,3)

Distances :
AB = √(𝟏 − 𝟓)𝟐 + (𝟏 − 𝟏)𝟐 = 𝟒, AC =√(𝟏 − 𝟑)𝟐 + (𝟏 − 𝟑)𝟐 = √𝟖 et BC = √𝟖

Conclusion :
AC = BC, donc le triangle ABC est isocèle.

NB :
 On rappelle que, la distance AB = √(𝑿𝑨 − 𝑿𝑩)𝟐 + (𝒀𝑨 − 𝒀𝑩)𝟐
 A, B et C sont alignés si et seulement si : (YA - YB)*(XB - XC) = (XA - XB)*(YB – YC)
 La fonction Racine(X) renvoie la racine carrée du nombre X.
 La fonction Carre(X) renvoie le carré du nombre X.

4) QUEL EST LE TARIF DE L'EAU ?

L’eau distribuée aux abonnés est comptabilisée par compteurs et facturée selon un barème de tarifs
progressifs à plusieurs tranches trimestrielles de Consommation d’eau. Le système tarifaire, qui est le même
pour tout le pays, comporte sept tranches de consommation avec un seul tarif par tranche (tarif). Les tarifs
varient de 200 millimes/m3 pour la première tranche sociale (20 m3/trimestre) à 1990 millimes/m3 pour la
tranche de consommation supérieure (> à 150 m3/trimestre).

© 24/25 A. DAHMANE & O. BEN ROMDHANE

Source : https://www.sonede.com.tn/accueil/contenu-principal/tout-savoir-sur-leau/la-facture-deau,
[http://www.sonede.com.tn] consulté en sep. 2023

3
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
TRAVAIL DEMANDE:
Etablir un algorithme qui permet de calculer le tarif de l'eau distribuée ted par la SONEDE à un abonné donné
selon le mode de tarifs binômes présenté ci-dessus.
NB: - la redevance fixe RF est supposée une constante égale à 3800 millimes pour tous les abonnés.
- le volume de consommation vc (en m3) sera saisi au clavier.
- le type de l'usage de l'eau type (domestique, touristique ou fontaine) sera aussi saisi au clavier.
- le taux de TVA applicable est 18% sur le total (redevance fixe RF + partie variable pv=tarif*vc).

5) DEMANDE D'ASSURANCE

L'objectif de cet exercice est d'afficher la réponse à une demande d'assurance vie selon les règles suivantes:

a) Cas 1 : Si le demandeur a moins de 30 ans

✓ S'il est en excellente santé, et n'ayant jamais eu d'accident, il obtient un contrat de type A. La réponse
sera : Contrat de type A
✓ S'il est en mauvaise santé, ou a déjà eu un accident alors une expertise médicale est demandée. Dans
ce cas, la réponse provisoire sera : Expertise Médicale
✓ Si après une expertise médicale, le demandeur est en mauvaise santé, et a déjà eu un accident alors
le contrat est refusé. La réponse sera : Contrat refusé
b) Cas 2 : Un demandeur a plus de 30 ans: On applique les mêmes conditions que dans le Cas1, mais cette
fois le contrat sera de type B. La réponse sera donc: Contrat de type B

TRAVAIL DEMANDE:
1) Compléter la table de vérité suivante pour examiner les différents cas de résultat : refus, expertise ou
contrat :

Refus Expertise Contrat

AGE < 30 V V
Données

SANTE = Vrai F V
ACCIDENT = 0 F F
Contrat de type A       ✓ 
Résultats

Contrat de type B        ✓
Expertise médicale   ✓ ✓ ✓ ✓  
Contrat refusé ✓ ✓      

NB: - SANTE: Vrai pour bonne santé et Faux pour mauvaise santé
© 24/25 A. DAHMANE & O. BEN ROMDHANE

- ACCIDENT : 0 pour aucun accident, 1 pour un seul accident, 2 pour deux accidents, …
- V: Condition vérifiée (Vrai) & F: Condition non vérifiée (Faux)
- ✓: Réponse à la demande (Contrat A, Contrat B, Expertise médicale ou Contrat refusé)

2) Ecrire un algorithme permettant de retourner la réponse adéquate à une demande d'assurance en

fonction de l'âge AGE du demandeur, de son état de santé SANTE (Vrai/Faux) et le nombre d'accidents
ACCIDENT (>=0).

4
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
6) ÉQUATION DU SECOND DEGRÉ

Compléter l'algorithme suivant qui calcul les solutions réelles d’une équation du second degré :
Algorithme Equation_Second_Degre
DefVar
A, B, C, Delta (Réel) //delta représente le discriminant (Delta = B2-4AC)
Début
Ecrire("Calcul des solutions réelles d'une équation du second degré")
Ecrire("de la forme A x^2 + B x + C = 0 ")
Ecrire() //ligne vide
Ecrire("Introduire les valeurs pour A, B, et C :")
Ecrire("A = "), Lire(A)
Ecrire("B = "), Lire(B)
Ecrire("C = "), Lire(C)
//Calcul du discriminant b^2-4ac
//Résolution de l’équation (les différents cas à étudier sont présentés ci-dessous)
Fin

Voici les différents cas à étudier :

a) A=0 et B=0 et C=0 (0x^2 + 0x + 0 = 0)
Tout réel est une solution de cette équation.
b) A=0 et B=0 et C0 (0x^2 + 0x + C = 0)
Cette équation ne possède pas de solutions.
c) A=0 (0x^2 + Bx + c = 0)
La solution de cette équation du premier degré est : x = C/B
d) Delta<0 (B^2-4AC < 0)
Cette équation n'a pas de solutions réelles.
e) Delta=0 (B^2-4AC = 0)
Cette équation a une seule solution réelle : x = -B/2A
f) Delta>0 (B^2-4AC > 0)
Les solutions réelles de cette équation sont :x1 = (-B+ Delta )/2A
x2 = (-B- Delta )/2A

NB :
 Les deux fonctions suivantes sont supposées prédéfinies :
Carre(x)  pow(x, 2) en C
Racine_Carre(x)  sqr(x) en C
© 24/25 A. DAHMANE & O. BEN ROMDHANE

 En langage C, pow et sqr retourne un résultat de type double.

7) L’HEURE SUIVANTE

Écrire un algorithme qui permet de lire une heure sous forme de : heures (hh), minutes (mm) et secondes
(ss), puis de déterminer l'heure à la seconde suivante et de l'afficher.
On suppose que hh, mm et ss sont valides.

5
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
Exemples :
L'heure saisie est : hh = 13, mm = 22, ss = 40
L'heure suivante sera affichée comme suit : 13h:22mn:41s.

L'heure saisie est : hh = 13, mm = 59, ss = 59

L'heure suivante sera affichée comme suit : 14h:0mn:0s.

8) LE LENDEMAIN

Proposer un algorithme qui permet de déterminer la date du lendemain (jj2/mm2/aa2) à partir d’une date
donnée et représentée par 3 entiers (jours jj, mois mm et année aa).

Exemples :
pour jj/mm/aa = 31/12/2017, l’algorithme affiche : Demain = 1/1/2018
pour jj/mm/aa = 5/10/2017, l’algorithme affiche : Demain = 6/10/2017
pour jj/mm/aa = 28/2/2017, l’algorithme affiche : Demain = 1/3/2018
pour jj/mm/aa = 28/2/2016, l’algorithme affiche : Demain = 29/2/2016

NB: une année bissextile est une année qui est divisible par 400 ou bien par 4 mais non par 100.

9) CONDITIONS DE SORTIE D'UNE ITERATION

On considère l’algorithme suivant :

Algorithme Boucle
DefVar
j, r : Entier
ok : Booléen
Début
Ecrire ("Donner un entier ?")
Lire (J)
ok  Faux
Tantque (j  25) Et (Non ok) Faire
Si (j = 25)
Alors ok  Vrai
Sinon j  j + 1
FinSi
FinTantque
r  j
Fin

TRAVAIL DEMANDE :
a) Donner la condition de sortie de l'itération.
b) Donner le tableau de sortie qui permet d'étudier les différents cas de figure possibles à la sortie
de l'itération. Le tableau de sortie se présente ainsi :
© 24/25 A. DAHMANE & O. BEN ROMDHANE

j  25 OK Commentaire
Faux Faux
................................... ... ... .... ..................... ...................................................................

Vrai Faux
..................... ................ ... ........ .....................................................................................

Faux Vrai
............................... ...... ... .................. ...........................................................................

Vrai Vrai
................................. ..... ... ................... .........................................................................

6
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
10) TRACE D'EXÉCUTION

Algorithme Deviner
DefConst
ERR: Réel = 0.00001 //limite de la suite s
DefVar
i: Entier //compteur des itérations
terme: Réel //terme courant de la suite s
s: Réel //suite récurrente
Début
s  1, terme  1, i  0
Tanque (terme ≥ ERR) Faire
i  i + 1
terme  terme / i
s  s + terme
FinTantQue
Fin

Travail demandé :
1) Faire la trace d'exécution des 5 premiers tours da la boucle TantQue de cet algorithme Suite (sans
application numérique).
1er tour 2ème tour 3ème tour 4ème tour 5ème tour
terme = ... ... ... ... ...
A la fin du 5ème tour : S = … + … + … + … + …

2) Déduire la formule générale de cette suite récurrente S.

11) SUITE MATHEMATIQUE

On considère une suite U définie par :

▪ U1 = 1
▪ U2 = 2
▪ Un = Un-1 + (x * Un-2)  n ≥ 3

TRAVAIL DEMANDE :
1) Donner la trace détaillée de calcul du 5ème terme de la suite U pour x = 2.
2) Ecrire un algorithme EstTerme qui permet de vérifier si un entier t donné est un terme de la suite U en
retournant son rang sachant que x est un entier naturel non nul. Cet algorithme retourne -1 si t ne
représente pas un terme de U.
Exemples (pour x = 2) :
▪ t = 1 est un terme de U dont le rang = 1
© 24/25 A. DAHMANE & O. BEN ROMDHANE

▪ t = 4 est un terme de U dont le rang = 3

▪ t = 6 n’est pas un terme de U, dans ce cas le rang = -1

12) LANCEMENT DE DES

Deux joueurs (l’utilisateur et l’ordinateur) "lancent" un dé dont les faces sont numérotées de 1 à 6.
Le joueur qui obtiendra la plus grande valeur aura un point. Le jeu s'arrête quand l'un des joueurs
arrive le premier à un score de 10 points.

7
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
Ecrire un algorithme permettant de simuler ce jeu et afficher le joueur gagnant. On pourra utiliser la
fonction prédéfinie Alea pour le tour de l’ordinateur. Aléa(n) est une fonction prédéfinie qui retourne
un nombre entier aléatoire appartenant à l'intervalle [0, n-1].
Voici une représentation de l'algorithme lorsqu’il sera terminé :
>> Lancement de dés N:1
Joueur 1 : 4
Joueur 2 : 1
Score : Joueur1 (1) & Joueur2 (0)

>> Lancement de dés N:2

Joueur 1 : 5
Joueur 2 : 5
Égalité ! Tirage annulé.
Score : Joueur1 (1) & Joueur2 (0)
...
>> Lancement de dés N:k
Joueur 1 : 6
Joueur 2 : 5
Score : Joueur1 (10) & Joueur2 (7)
>> Joueur gagnant : 1

13) ALGORITHMES RECURRENTS

13.a) Suite de Fibonacci : La suite de Fibonacci est une suite récurrente dont chaque élément obéit à la
relation de récurrence suivante :
U1 = 1 et U2 = 1
Un = Un-1 + Un-2
Cette suite doit son nom à un mathématicien italien du XIIIe siècle connu sous le nom de Leonardo
Fibonacci qui, dans un problème récréatif (amusant) posé dans un de ses ouvrages, le Livre du Calcul,
décrit la croissance d'une population de lapins. Le nième terme correspond au nombre de paires de
lapins au nième mois
Ecrire un algorithme FIBO qui calcul le nième terme de Fibonacci sachant que n >=1.
13.b) Ecrire l'algorithme qui permet de calculer la somme S suivante :
S = 2 + 3/2 – 4/3 - 5/4 + 6/5 + 7/6 – 8/7 - …  n/n-1 avec n2

13.c) Ecrire un algorithme qui permet de calculer et d'afficher les termes de la suite S jusqu'à ce que la
différence entre deux termes consécutifs devienne ≤ epsilon ( 10-4).
𝑺𝟏 = 𝟐 & 𝑺𝒊 = 𝑺𝒊−𝟏 (𝒊 − 𝟏⁄𝒊) (𝒊 + 𝟏⁄𝒊) avec i>1 & i est impair
13.d) Ecrire un algorithme qui permet de calculer la somme suivante :
© 24/25 A. DAHMANE & O. BEN ROMDHANE

𝒏𝒃𝒓

∑(𝑪𝒊 ∗ 𝑵𝒊 )/(𝒊!) =
𝒊=𝟏
(𝐶1 ∗ 𝑁1 )/1 + (𝐶2 ∗ 𝑁2 )/(1 ∗ 2) + (𝐶3 ∗ 𝑁3 )/(1 ∗ 2 ∗ 3) + ⋯ + (𝐶𝑛𝑏𝑟 ∗ 𝑁𝑛𝑏𝑟 )/(1 ∗ 2 ∗ 3 ∗ … ∗ 𝑛𝑏𝑟)

Sachant que :
▪ nbr est une constante = 30
▪ Ci est un coefficient de type entier  {1 ; 2 ; 3}
▪ Ni est un entier strictement positif

8
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
14) ALGORITHMES D'APPROXIMATION

14.a) Ecrire un algorithme Valeur1_Pi permettant de calculer une valeur approchée de 𝝅 en utilisant
la formule suivante (On s’arrête lorsque la marge d’erreur err est < 10-6).

err < 10-6

1 𝟏 1 𝟏 𝟏
𝝅 = 4 ∗ (1 − + − + − … ± )
3 𝟓 7 𝟗 𝒊

14.b) Ecrire un algorithme Valeur2_Pi permettant de calculer une valeur approchée de π en utilisant
la formule suivante (On s’arrête lorsque la marge d’erreur err est < 10-6):

1 𝟏 1 𝟏 1 𝟏 1 𝟏 1 𝟏 err < 10-6

𝝅 = 2 ∗ √3 ∗ (1 − ∗ 𝟏 + ∗ 𝟐 − ∗ 𝟑 + ∗ 𝟒 − … ± ∗ 𝒏 )
3 𝟑 5 𝟑 7 𝟑 9 𝟑 𝑖 𝟑

15) PROPRIETE DE MULTIPLICATION

On remarque que : 12 * 42 = 21 * 24
13 * 62 = 31 * 26
14 * 82 = 41 * 28
…
ab * cd = ba * dc

Il y a des produits vérifiant cette propriété :

(10*a+b) * (10*c+d) = (10*b+a) * (10*d+c)

P1 P2 P3 P4

Où a  b et c  d

Écrire un algorithme permettant de déterminer les couples de nombres entiers vérifiant cette
propriété. Ces nombres sont compris entre 10 et 99 :

 Cas 1 : (ab, cd) et (cd, ab) sont deux couples différents.

 Cas 2 : (ab, cd) et (cd, ab) sont deux couples identiques.

16) CHIFFRE DE CHANCE

Ecrire un algorithme qui saisit un nombre entier nb composé de quatre chiffres puis calcule le chiffre
de chance correspondant à ce nombre de la façon suivante :
▪ Faire la somme de tous les chiffres qui composent le nombre saisi.
▪ Si le nombre calculé est composé de plus d’un chiffre, faire la somme des chiffres qui le composent.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

▪ Répéter ce procédé jusqu’à avoir un nombre composé d’un seul chiffre.

Exemple :
Pour nb = 9569, on aura les sommes suivantes :
9 + 5 + 6 + 9 = 29
2 + 9 = 11
1 + 1 = 2 est le chiffre de chance

9
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
17) MULTIPLICATION RUSSE

La multiplication Russe est une méthode particulière permettant de multiplier deux entiers strictement
positifs, en utilisant seulement la division entière par 2, la multiplication par 2 et l’addition.
Soient a et b deux entiers strictement positifs saisis au clavier. On se propose de multiplier a par b en utilisant
cette méthode.
Le principe consiste à mettre a dans une première colonne et b dans une deuxième puis diviser
successivement a par 2 et multiplier b par 2 jusqu’à atteindre 1 dans la première colonne (celle où on effectue
la division entière). Tous les nombres de la seconde colonne qui sont en face des nombres pairs seront
ignorés. Le résultat de la multiplication de a par b s’obtient alors en additionnant les nombres restants.
Écrire un algorithme qui permet de réaliser cette multiplication.

Exemple 1 :
A B Commentaire
20 5 ignoré car 20 est pair
10 10 ignoré car 10 est pair
5 20 non ignoré car 5 est impair
2 40 ignoré car 2 est pair
1 80 non ignoré car 1 est impair (Fin traitement)

=> Le résultat de 20 * 5 = 20 + 80 = 100

Les nombres 5, 10 et 40 (colonne B) seront ignorés parce qu’ils sont en face de nombres pairs (colonne A)
qui sont respectivement 20, 10 et 2.

Exemple 2 :
A B Commentaire
9 25 non ignoré car 9 est impair
4 50 ignoré car 4 est pair
2 100 ignoré car 2 est pair
1 200 non ignoré car 1 est impair (Fin traitement)

=> Le résultat de 9 * 25 = 25 + 200 = 225

Les nombres 50 et 100 seront ignorés parce qu’ils sont en face de nombres pairs qui sont respectivement 4
et 2.

18) MATCH DE VOLLEY-BALL

Il s’agit d’écrire un algorithme pour compter le nombre de points marqués tout au long d’un match de Volley-
ball et d’indiquer à la fin l’équipe gagnante (avec affichage du résultat en nombre de sets). Chaque fois que
la balle est en jeu et qu’une faute est commise par une équipe (c’est une donnée à définir aléatoirement en
© 24/25 A. DAHMANE & O. BEN ROMDHANE

utilisant la fonction Alea(n)), l’équipe adverse prendre un point et ainsi de suite jusqu’à la fin du set encours :
 Le match se joue en trois sets gagnants (résultats possibles : 3-0, 3-1 ou 3-2).
 Un set est remporté par l’équipe qui a obtenu un score de 25 points à condition qu’il y ait au moins deux
points d’écart entre les scores des deux équipes. Sinon le set se poursuit jusqu’à ce que cette condition
soit remplie.
 Lorsqu’un set est terminé, les équipes commencent avec zéro point chacune pour le set suivant.
 Une équipe marque un point si l’équipe adverse a commis une erreur.

10
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
19) CHAINE PALINDROME

Ecrire un algorithme qui permet de déterminer si une chaîne de caractères ch, lue au clavier, est palindrome
ou non. Une chaîne de caractères est dite palindrome si elle peut se lire de gauche à droite ou de droite à
gauche.
Exemples :
"elle", "Radar", "sos", "", "Z", "10ABBA01"...

20) SIMULATION DE JEU DE DEVINETTE

Ce jeu se joue à deux. Le premier joueur choisit un mot que le deuxième joueur est chargé de dévoiler en un
nombre fini d'essais. Le jeu se déroule de la façon suivante :
 Le premier joueur masque le mot choisi mot de n lettres par une chaîne S de n tirets.
 Le deuxième joueur propose une lettre. Si celle-ci figure dans le mot mot, elle sera dévoilée dans la chaîne
S à la place de chaque tiret qui lui correspond.
 Chaque proposition d'une lettre compte un essai. Le nombre d’essais maximum est fixé à 2*n.

Ecrire un algorithme "Devinette" simulant ce jeu.

Exemple :
mot  "P O U S S E R"
S  "- - - - - - -"

Essai N° 1 : 'A' S  "-------" nb  0 Nombre de lettres trouvées

Essai N° 2 : 'E' S  "-----E-" nb  1
Essai N° 3 : 'S' S  "---SSE-" nb  3
Essai N° 4 : 'e' S  "---SSE-" nb  3
Essai N° 5 : 'I' S  "---SSE-" nb  3
Essai N° 6 : 'O' S  "-O-SSE-" nb  4
Essai N° 7 : 'p' S  "PO-SSE-" nb  5
Essai N° 8 : 'u' S  "POUSSE-" nb  6
Essai N° 9 : 'R' S  "POUSSER" nb  7 (Stop)

Le mot est dévoilé, c'est le bon résultat. La longueur du mot étant de 7, le nombre d'essais autorisé est de
2*7=14. On a fait seulement 9 essais.

21) NOMBRE DE VOYELLES & LETTRES

Ecrire un algorithme qui permet de compter le nombre de voyelles nv et le nombre de consonnes nc d'une
phrase ph saisie au clavier. Cette phrase peut comporter des lettres, des chiffres, des signes de ponctuations
et des caractères spéciaux.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

Exemple :
Pour ph = "Promotion 2017 ! Génie Informatique"
L'algorithme doit afficher le message suivant :
Le texte contient : 13 voyelles et 13 consonnes (avec redondance)
Ou bien
Le texte contient : 5 voyelles et 8 consonnes (sans redondance)

11
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
22) TROIS TABLEAUX

Algorithme TROIS_TABLEAUX
DefConst
TAILLE = 6
DefVar
i,j : Entier
tinit,trang,tres : Tableau[1..TAILLE] de Entier
Début
//Étape 1 : Remplissage du vecteur Tinit
Pour i de 1 à TAILLE Faire
Ecrire ("Donner l'élément N: ", i)
Lire (Tinit[i])
FinPour

//Étape 2 : Initialisation des éléments du vecteur Trang à 1

Pour i de 1 à TAILLE Faire
Trang[i]  1
FinPour

//Étape 3 : Mise à jour du vecteur Trang à partir de Tinit

Pour i de 1 à TAILLE–1 Faire
Pour j de i+1 à TAILLE Faire
Si (Tinit[i]  Tinit[j])
Alors Trang[i]  Trang[i] + 1
Sinon Trang[j]  Trang[j] + 1
FinSI
FinPour
FinPour

//Étape 4 : Remplissage du vecteur Tres à partir des Trang et Tinit

Pour i de 1 à TAILLE Faire
Tres[Trang[i]]  Tinit[i]
FinPour
Fin

TRAVAIL DEMANDE :
Faire l'exécution de cet algorithme en remplissant les tableaux suivants :
© 24/25 A. DAHMANE & O. BEN ROMDHANE

1 2 3 4 5 6
ÉTAPE 1 : TINIT 10 7 18 5 13 7

1 2 3 4 5 6
ÉTAPE 2 : TRANG

1 2 3 4 5 6
ÉTAPE 3 : TRANG
1 2 3 4 5 6
ÉTAPE 4 : TRES

12
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
23) CONVERSION D'UN ENTIER EN BINAIRE

Écrire un algorithme qui permet de convertir un entier positif (<=65535) en un nombre binaire et de l’afficher
(en base 2 sous forme de suite de 1 et de 0). Le résultat de cette conversion sera mis dans un vecteur ayant
pour dimension n=16 (2 octets) ou bien dans une chaîne de caractères.
Exemples:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
▪ 77 se convertit en "1001101" ou bien 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
▪ 2013 se convertit en "11111011101" 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1

Principe:

Conversion de 77 en base 2 :
Il s'agit de faire une suite de divisions euclidiennes par 2. Le
résultat sera la juxtaposition des restes. Le schéma ci-contre
explique la méthode.
77 s'écrit donc en base 2: 1001101.

24) TRIANGLE DE PASCAL

Le triangle de Pascal est la matrice des coefficients qui sont utilisés pour le développement de certaines
expressions comme (a+b)² ou (a+b)n.

Exemple (pour n = 4) :
0 1 2 3 4
Ligne 0 1 (a+b)0 = 1
Ligne 1 1 1 (a+b)1 = 1*a + 1*b
Ligne 2 1 2 1 (a+b)2 = 1*a2 + 2*a*b + 1*b2
Ligne 3 1 3 3 1 (a+b)3 = 1*a3 + 3*a²*b + 3*a*b² + 1*b3
Ligne 4 1 4 6 4 1 (a+b)4 = 1*a4 + 4*a3*b + 6*a²*b² + 4*a*b3 + 1*b4

En effet, pour une ligne donnée :

 Le premier élément = 1 et le dernier élément = 1.
 Les autres éléments sont déterminés en appliquant la formule récursive suivante :
P[i, j] = P[i-1, j] + P[i-1, j-1] avec i étant le numéro de la ligne et j le numéro de la colonne
Exemple: P[4, 2] = 6 = P[3, 2] + P[3, 1] = 3 + 3

Ecrire un algorithme permettant de remplir et d'afficher une matrice P(n x n) contenant le triangle de Pascal
pour n  10.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

25) RECHERCHE DOUBLE

Ecrire un algorithme qui permet de rechercher deux entiers a et b dans un tableau T de N entiers impairs (N
est supposée une constante = 8). Le résultat de cet algorithme doit être 0, 1 ou 2 :
 0 : si aucune des deux valeurs a et b n'existe dans T,
 1 : si l'une seulement des valeurs a et b existe dans T,
 2 : si les deux valeurs a et b existent dans T.

13
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
26) SOMME DES NOMBRES EXTRAITS DES CHAINES

Soit T un tableau de N chaînes de caractères non vides et dont la taille maximale est 5 caractères. On se
propose d'écrire un algorithme permettant de remplir le tableau T par N chaînes de caractères (2 <=N<=30),
puis de calculer et d'afficher la somme des nombres extraits des chaînes de chaque élément du tableau T.
Le nombre extrait de la chaîne contenue dans la case i du tableau T, est formé par la concaténation de tous
les chiffres de la chaîne parcourue de gauche à droite.
N.B. : si une chaîne ne contient pas des chiffres, elle prend la valeur 0 dans le calcul de la somme finale.

Exemple :
Si N = 9 et que le tableau T contient les éléments suivants :
1 2 3 4 5 6 7 8 9
"3E-
"R4*s2" "12hj5" "5?7e" "Ak!r" "E9Y41" "6754" "G(Y" "U5Kx1"
Z2"

Alors la somme S = 42 + 125 + 57 + 0 + 941 + 6754 + 32 + 0 + 51 = 8002

Le programme affichera la valeur de S.

27) NOMBRES PREMIERS

Écrire un algorithme qui permet de déterminer l’ensemble des nombres premiers compris entre 2 et n (n >
0 saisi au clavier) en utilisant le crible d’Eratosthène.
Cette méthode consiste à laisser le premier entier rencontré puis remplacer tous ses multiples par zéro.
Ensuite continuer de la même manière jusqu’au parcours total du crible.

Exemple (n=18)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
2 est considéré comme nombre premier (c’est le premier entier rencontré), on doit éliminer tous ses
multiples. On aura alors :
2 3 0 5 0 7 0 9 0 11 0 13 0 15 0 17 0
puis on continue le traitement de la même manière. À la fin on affiche les entiers différents de zéro.

28) SENS DU TRI D'UN TABLEAU

Soit un tableau T de 30 nombres réels compris entre 0 et 20. Ecrire un algorithme qui affiche un message
indiquant si :
▪ tous les éléments de T sont égaux.
▪ T est trié dans l’ordre croissant.
▪ T est trié dans l’ordre décroissant.
▪ T n’est pas trié.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

Exemple :
1 2 3 4 27 28 29 30
Si T = 5 7 7 9.5 ... 15 15 17.5 18.5  Tableau trié dans l’ordre croissant

NB : le tableau T doit être parcouru qu’une seule et unique fois.

14
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
29) CALCUL DU TEMPS ECOULE ENTRE DEUX HEURES

Écrire un algorithme qui permet de calculer le temps écoulé diff (en minutes) entre deux temps tm1 et tm2
(en heures et minutes) saisis au clavier. On convertit chaque temps en une valeur entière correspondant au
nombre de minutes écoulées depuis minuit. L'algorithme doit effectuer les opérations suivantes :
a) Saisie de deux structures temps tm1 et tm2,
Structure Temps
Hh: Entier //heures  [0, 23]
mm: Entier //minutes  [0, 59]
FinStructure
b) Conversion de deux temps tm1 et tm2 en minutes (tmm1 et tmm2),
c) Calcul de la différence entre tmm1 et tmm2 en tenant compte du cas particulier de temps qui se situent
de part et d’autre de minuit.
 Cas 1 : Si tm1 = 15:45 et tm2 = 17:30 Alors temps écoulé : diff = 105 minutes
 Cas 2 : Si tm1 = 23:30 et tm2 = 00:45 Alors temps écoulé : diff = 75 minutes
d) Affichage du résultat : Nombre de minutes écoulées entre ces deux temps = diff

30) ALBUM DE CHANSONS

Soit la partie déclarative suivante :

DEFCONST
MAXCHAN = 15
MAXALBUM = 2000
DEFTYPE
Structure Chanson
titrec : Chaîne[30]
duree : Entier
type : Chaîne[15] //type de musique: Oriental, Folklorique, Classique, …
Fin Structure
Structure Album
titrea : Chaîne[30] //Titre d’un album
annee : Entier //Année de sortie d’un album
nbChan : Entier //Nombre de chansons d’un album (<=MAXCHAN)
chansons : Tableau [1..MAXCHAN] de Chanson
Fin Structure
Studio = Tableau [1..MAXALBUM] de Album

TRAVAIL DEMANDE :
Écrire un ensemble d'actions qui permet d’afficher tous les titres de chansons folkloriques enregistrés dans
le studio s durant l’année a. Le résultat doit comporter aussi le titre de l’album de chaque chanson, sachant
que le nombre d’albums enregistrés dans s est égal à nbr (les variables s et a sont supposées définies).

31) PROJETS REALISES

© 24/25 A. DAHMANE & O. BEN ROMDHANE

L’objectif de cet exercice est de proposer une structure de données adéquate pour représenter les projets
réalisés dans les différents départements d'une société.
 La société est découpée en 5 départements. Chaque département est caractérisé par son nom et son chef
et il est responsable d'un certain nombre de projets (100 au maximum). Il est à noter que le nombre de
projets réellement réalisé doit être également mémorisé.
 Un projet est caractérisé par une désignation, une date de début, une date de fin et il est réalisé par trois
personnes (la 1ère personne représente le chef du projet)

15
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
 Chaque personne est identifiée par son numéro de CIN et décrit par un nom, une adresse et un numéro
de téléphone. Le nombre d'heures passé par une personne sur chaque projet doit être mémorisé.

a) Proposer une structure de données « Société » pour représenter ces cinq départements.
b) Ecrire un bloc d’instructions (Boucle Pour) pour déterminer le nombre d’heures total « NBHT » passé par
les chefs des projets sur tous les projets réalisés par le premier département de la société S.

32) ATHLETES

On se propose d'effectuer le suivi des athlètes participant à des compétitions sportives ainsi que le calcul
des points qu'ils ont gagnés au cours d'une année. Les structures de données proposées pour la
représentation de l'ensemble des athlètes et ses compétitions sont illustrées par les 3 tableaux suivants :

1- Liste_Categories
1 … MAXCATEG = 10
+ Code catégorie (codcateg)
+ Nom de catégorie (nomcateg)

2- Liste_Competitions
1 … MAXCOMP = 30
+ Code compétition (codcomp)
+ Désignation de compétition (nomcomp)
+ Catégorie de compétition (categ)
Représente l'indice d'une catégorie dans le tableau Liste_Categories

3- Liste_Athletes
1 … MAXA=100
+ Numéro de licence d'un athlète (licence)
+ Nom et prénom d'un athlète (noma)
+ Pays d'un athlète (pays)
+ Nombre de compétitions auxquelles un athlète a participé (Nbc)
+ Compétitions (comp) :
1 … MAXC = 5
+ Indice de compétition (numc)
Représente l'indice d'une compétition dans le tableau Liste_Competitions
+ Nombre de points gagnés (score).

Travail demandé :
Soient les variables suivantes :
▪ LA : représente une liste d'athlètes qui est supposée remplie avec des données valides et cohérentes.
▪ NA : représente le nombre réel d'athlètes (1≤ NA ≤ MAXA).
▪ LCom : représente la liste des toutes les compétitions.
▪ LCat : représente la liste des toutes les catégories.
▪ Cat : représente le code d'une catégorie de compétitions.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

1) Afficher les nombres des points gagnés par chaque athlète tunisien dans
chacune des compétitions auxquelles il a participé. Seules les
compétitions de catégorie Cat seront affichées.
Voici un
2) Dire comment faire, au niveau des structures de données, pour
Exemple
supprimer une compétition donnée sans perdre l'historique des athlètes d'affichage
(Attention à la redondance de données !).

16
Algorithmique et Structures de données I
TD Partie 1 : Types de données, Structures de contrôle, Tableaux, Chaînes de caractères & Enregistrements
 LES SOUS-PROGRAMMES PARTIE
LA RECURSIVITE
LES ALGORITHMES DE RECHERCHE
LES ALGORITHMES DE TRI
2
Points abordés :
 Les structures de contrôle & les structures de données simples et composées
 Les sous-programmes (procédures, fonctions, paramètres, passage par valeur/par référence, variable globale/locale… )
 L'approche récursive
 Les méthodes de recherche séquentielle et dichotomique
 Les méthodes de tri : Tri par sélection, Tri à bulles, Tri par insertion, Tri fusion, …

1) TRACE D’EXECUTION : BLA-BLA !

Algorithme BlaBla
DefVar
essai, precedent : entier
ok : booléen
Début
precedent  9
Répéter
Ecrire("Principal : une donnée SVP : ")
Lire(essai)
ok  faux
Deviner(essai, precedent, ok)
Ecrire("Principal : ", essai, precedent)
//Ne pas chercher à comprendre le rôle de cet algorithme !!!
Jusqu'à ok
Fin

Procédure Deviner(val1: entier, VAR val2: entier, VAR rep: booléen)

Début
Ecrire("Début deviner : ", val1, val2)
Si (val2 Mod 2 = 0)
Alors val2  val2 / 2
Sinon val2  val2 + (val2 + 1) / 2
FinSi
rep  val1 = val2
© 24/25 A. DAHMANE & O. BEN ROMDHANE

val1  0
Ecrire("Fin deviner : ", val1, val2)
Fin

Travail demandé :
a) Quels sont les affichages de l'algorithme BlaBla lorsque les données saisies sont 11, 11, 11, 11, ... ?
b) Quelles sont les instructions inutiles qui peuvent être supprimées sans que le fonctionnement général de
l'algorithme ne soit modifié ?

17
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
2) TRACE D’EXECUTION : DECRYPTAGE

Le programme présenté ci-dessous permet de décrypter un message en anglais. Vous êtes appelés à faire la
trace d’exécution de ce programme pour décrypter le message stocké dans le tableau T.
Voici le contenu initial du tableau T (taille = 5)
"HXG\U'" "\rx" "lezi" "7" "swv"
0 1 2 3 4

DefType
Tab = Tableau[1..5] de Chaîne
DefVar
T: Tab = {"HXG\U'", "\rx", "lezi", "7", "swv"}
Procédure Decrypter(T: Tab, taille: Entier)
DefVar
i: Entier
Début
Pour i de 1 A taille Faire
T[i]  Decrypter_UnMot(T[i])
FinPour
Fin

Fonction Decrypter_UnMot(mot: Chaîne): Chaîne

DefVar
i(Entier)
motDec (Chaîne)
code, i (Entier) Exemple: mot="HXG\U'"
Début LONG(mot)=6
motDec  "" mot[1]="H", mot[2]="X"
Pour i de 1 A Long(mot) Faire
Code  Asc(mot[i]) - Long(mot)
motDec  Concat(motDec, Chr(Code))
FinPour
Decrypter_UnMot  motDec
Fin

Quel sera le contenu du T après l’exécution de la procédure Decrypter

? ? ? ? ?
0 1 2 3 4

Voici un extrait de la table ASCII standard

033 ! 047 / 061 = 075 K 089 Y 103 g 117 u
034 " 048 0 062 > 076 L 090 Z 104 h 118 v
035 # 049 1 063 ? 077 M 091 [ 105 i 119 w
036 $ 050 2 064 @ 078 N 092 \ 106 j 120 x
037 % 051 3 065 A 079 O 093 ] 107 k 121 y
038 & 052 4 066 B 080 P 094 ^ 108 l 122 z
© 24/25 A. DAHMANE & O. BEN ROMDHANE

039 ' 053 5 067 C 081 Q 095 _ 109 m 123 {

040 ( 054 6 068 D 082 R 096 ` 110 n 124 |
041 ) 055 7 069 E 083 S 097 a 111 o 125 }
042 * 056 8 070 F 084 T 098 b 112 p 126 ~
043 + 057 9 071 G 085 U 099 c 113 q
044 , 058 : 072 H 086 V 100 d 114 r
045 - 059 ; 073 I 087 W 101 e 115 s
046 . 060 < 074 J 088 X 102 f 116 t

Exemples:
ASC("7")=55, ASC("'")=39, ASC("\")=92 CHR(55)="7", CHR(39)="'", CHR(92)="\"

18
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
3) TRACE D’EXECUTION : FREQUENCE

Le programme présenté ci-dessous est composé de deux fonctions : Devinette & Fonc et une procédure Proc :

Fonction Devinette (t: Tab, taille: Entier): Entier

DefVar
i, f, fmax, vmax (Entier), existe (Booléen)
Début
fmax  0
Pour i de 1 à taille Faire
existe  Fonc(t, i)
Si (existe) Alors
Proc(t, taille, i, f)
Si (f > fmax) Alors
fmax  f
vmax  t[i]
FinSi
FinSi
FinPour
Retourner (vmax)
Fin
Fonction Fonc (t: Tab, pos : Entier) : Booléen
DefVar
i (Entier), ok (Booléen)
Début
ok  Faux, i  1
TantQue (i < pos ET ok = Faux) Faire
Si (t[i] = t[pos])
Alors ok  Vrai
Sinon i  i + 1
FinSi
FinTantQue
Retourner (ok)
Fin

Procédure Proc (t: Tab, taille: Entier, pos: Entier, VAR k: Entier)
DefVar
i (Entier)
Début
k  0, i  pos
Répéter
Si (t[pos] = t[i]) Alors
k  k + 1
FinSi
i  i + 1
Jusqu’à (i > taille)
Fin

a) Remplir le tableau d’exécution suivant de la fonction Devinette pour :

© 24/25 A. DAHMANE & O. BEN ROMDHANE

1 2 3 4 5 6 7 8 9 10 MAX
t= 3 2 8 6 8 8 2 2 3 2 … & taille = 10

i Avant Pour 1 2 3 4 5 6 7 8 9 10
existe 
f 
fmax 0
vmax 

b) Dire que fait ce programme ?

19
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
4) DATE VALIDE

Soit la structure date suivante :

Date = Structure
jj: Entier //jour: 1..31
mm: Entier //mois: 1..12
aa: Entier //annee: 1..9999
FinStructure

Exemples de dates :
 28/11/2006  C’est une date valide
 29/02/2016  C’est une date valide (car 2016 est bissextile)
 31/6/2017  C’est une date invalide (car le mois 6 [juin] a seulement 30 jours)
 20/13/2017  C’est une date invalide (car le mois 13 n’existe pas)

Indications :
 La plage autorisée pour le champ année aa est [1..9999].
 Si l’année aa est bissextile alors le mois de février a 29 jours ; sinon, 28 jours.
 Une année bissextile est une année qui est divisible par 400 ou bien par 4 et non par 100.

TRAVAIL DEMANDE :
On souhaite écrire un algorithme modulaire permettant de saisir une date valide. Pour ce faire, développer
les modules suivants :
a) Fonction Bissextile (aa: Entier): Booléen
// retourne Vrai si aa est une année bissextile, sinon Faux
b) Fonction isDate (d: Date): Booléen
// retourne Vrai si l’expression d représente une date valide, sinon Faux
c) Algorithme Principal
// Il permet de saisir une date valide en utilisant les deux modules Bissextile et isDate
// Cet algorithme doit afficher les messages suivants :
▪ Donner une date (jj/mm/aaaa) : message de saisie d'une date au format français jj/mm/aaaa
▪ Date invalide ! Réessayer... (taper f/F pour annuler) : Si la date saisie est invalide
▪ OK ! Date Valide : Si la date saisie est valide
▪ Opération Annulée ! : Si l'opération a été annulée

5) NOMBRES ROMAINS
© 24/25 A. DAHMANE & O. BEN ROMDHANE

La notation des nombres romains est basée sur l'utilisation des lettres M, D, C L, X, V et I. On se propose
d'écrire un programme qui, à partir d'une chaîne de caractères formée uniquement de chiffres romains,
donne son équivalent décimal selon le principe suivant :
 L'équivalent décimal de chaque chiffre romain est : M=1000, D=500, C=100, L=50, X=10, V=5 et I=1.
 L'équivalent décimal de la chaîne de chiffres romains est obtenu en additionnant les équivalents décimaux
de ses chiffres. Le parcours de la chaîne se fait de gauche à droite et dans le cas où un chiffre est inférieur
à son successeur, il sera précédé du signe moins (-).

20
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
Exemples :
CDXL = -100 + 500 -10 + 50 = 440
CXVI = 100 + 10 + 5 +1 = 116
CXIV = 100 + 10 – 1 + 5 = 114
MMCIX = 1000 + 1000 + 100 -1 +10 = 2109

Travail demandé :
Ecrire un algorithme modulaire qui permet de saisir une chaîne formée uniquement par des chiffres romains,
de calculer et d'afficher son équivalent décimal.

6) CARACTERES CONTIGUS

Ecrire un algorithme modulaire permettant de chercher dans un tableau TM de N chaînes de caractères, la

première chaîne comportant deux caractères identiques contigus (qui se suivent). Cet algorithme doit faire
appel à deux fonctions :
a) une fonction nommée Contigus qui détermine si une chaîne passée en paramètre comporte au moins
deux caractères identiques contigus.
Exemples
▪ Contigus ("Foot") retourne vrai
▪ Contigus ("chance") retourne faux
▪ Contigus ("prograMmation") retourne vrai // on ne tient pas compte de la casse
▪ Contigus ("ABC##") retourne vrai
▪ Contigus ("Réel") retourne faux // e et é sont 2 caractères différents
b) Une deuxième fonction nommée Rechercher_Mot qui retourne la position de la 1ère chaîne désirée, si elle
existe ; sinon -1.

7) SUPPRIMER LES DOUBLONS

Le tableur Microsoft Excel offre une fonctionnalité nommée "Supprimer les doublons" permettant de
supprimer les lignes en double dans une feuille de données. La figure présentée ci-dessous montre un
exemple d'un tableau Excel L1 qui regroupe 10 candidats (matricule, nom et bac) contenant des lignes
redondantes.
Figure : Exemple d'un tableau Excel (L1 et L2)

© 24/25 A. DAHMANE & O. BEN ROMDHANE

21
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
1) Définir les structures de données nécessaires pour la représentation d'une liste de candidats.
2) Ecrire une procédure, nommée Supprimer_Doublons (…), qui prend en entrée une liste de candidats L1
et retourne une deuxième liste L2 dans laquelle chaque candidat n'apparaît qu'une seule fois. L'ordre des
candidats doit être conservé. Cette procédure doit déterminer aussi le nombre de valeurs en double
trouvées.
NB: Pour simplifier le traitement, penser à développer une fonction de recherche nommée Existe(…) et
l'appeler dans la procédure Supprimer_Doublons.

8) CONCOURS SUR DOSSIER

Soit Grade, un tableau contenant les matricules et les scores de N employés qui ont participé à un concours
sur dossier pour le passage à un grade. On se propose d'écrire un algorithme modulaire qui affiche le résultat
de ce concours, sachant que 25% des participants seront déclarés admis pour ce grade par ordre de mérite
(du plus grand au plus petit score).

Remarques :
 Les matricules sont des chaînes de caractères formées de 8 chiffres.
 Les scores des employés sont des entiers compris entre 20 et 120.
 Si le calcul de 25% des participants ne donne pas un entier, on utilisera l'arrondi du nombre trouvé.

Exemple :
Pour N = 7 et le tableau Grade suivant :
1 2 3 4 5 6 7
Matricule 63078256 45789623 45786237 45231216 45781269 23564789 01245786
Score 38 31 45 56 28 60 21

Le programme affiche :
Liste des admis : 23564789 45231216

Travail demandé :
Ecrire un algorithme modulaire qui permet de saisir le nombre des employés N (avec 5  N  100), puis de
remplir le tableau Grade et d'afficher les résultats de passage de grade comme expliqué ci-dessus.

9) FILE D'ATTENTE

Une file est un type particulier de tableau, où les éléments sont insérés en queue (en arrière) et supprimés
en tête. Le nom vient des files d’attente à un guichet, où le premier arrivé est le premier servi, ce que justifie
le terme anglo-saxon de « FIFO » (First In First Out). Elles sont d’un usage très répandu dans la
© 24/25 A. DAHMANE & O. BEN ROMDHANE

programmation système. Les trois modules suivants sont supposés définis sur les files :

a) Fonction Vide (F : File) : Booléen

// retourne vrai si la file F est vide, faux sinon

b) Procédure Enfiler (VAR F : File, E : TypeElement)

// On suppose que la taille maximale de la file n’est jamais atteinte
// La file finale F' ayant tous les éléments de la file initiale F et en queue un élément contenant E
// Si F contient (a1, a2, … an), elle devient F’ (a1, a2, … an, E)

22
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
c) Procédure Défiler (VAR F : File, VAR E : TypeElement)
// On suppose que F n’est pas vide
// La file finale F' ayant tous les éléments de la file initiale F sans le premier
// Si F contient (a1, a2, … an), elle devient F’ (a2, … an) et E = a1

La figure présentée ci-après décrit l'organisation de passage des processus dans le CPU (Central Processing
Unit) de l'ordinateur pour exécution.

Passage des processus dans le CPU

 A chaque processus est alloué un temps d'exécution maximal t dans le CPU.

 Un Processus est décrit par un enregistrement contenant le Descripteur de processus et sa Duree
d'exécution nécessaire (en nombre de secondes).
 L'ensemble des processus est initialement rangé dans la file F1.
 Un processus est défilé de la File F1 et testé.
▪ Si sa Duree est supérieure à t il sera exécuté pendant un temps t dans le CPU, sa Duree sera donc
diminuée de t et il sera ensuite enfilé dans F2.
▪ Sinon il sera exécuté et disparaîtra.
 Lorsque la file F1 devient vide, on défile les processus de F2 de la même manière, si leurs durées
sont supérieures à t ils seront diminués de t enfilés dans F3.
 Lorsque la file F2 devient vide, on défile les processus de F3 un à un et ceux dont la Duree dépasse
t, seront diminués de t puis enfilés dans F3.
 Ce traitement continue jusqu'à obtenir F3 vide.

Voici les déclarations nécessaires pour représenter les files de processus :

© 24/25 A. DAHMANE & O. BEN ROMDHANE

Structure Processus
descripteur : Chaîne
duree : Entier
FinStructure
Structure File
taille : 0..1000
File_Process : Tableau [1..1000] de Processus
FinStructure
// le champ taille représente le nombre de processus présents dans la file d’attente

23
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
Travail demandé :

1) Écrire la procédure TraiterFile qui permet de défiler tous les processus de la file F et d’enfiler dans FF
ceux qui ont une durée d’exécution supérieure à t.
Procédure TraiterFile (VAR F : File, t : Entier, VAR FF : File)
// Après l'exécution de TraiterFile :
// F devient une file vide
// et FF comporte tous les processus défilés de F et dont la durée a été diminuée de t

2) Écrire une procédure MultiLevel permettant de régler le passage des processus dans le CPU en faisant
appel à la procédure TraiterFile (les trois files doivent être traitées).

Procédure MultiLevel (VAR F : File, t : Entier)

// On suppose que F est une file non vide.
// Après l'exécution de MultiLevel, F devient une file vide.

3) Développer les deux procédures Enfiler et Défiler

10) DEGRES DE TEMPERATURES

On relève dans certains jours de l’année les degrés de températures. Une observation sera un tableau de
trois valeurs {jour, moi, degré}. Par exemple, une température 24°C enregistrée le 22 Avril correspond au
tableau {22, 4, 24}. Le but de l’exercice est de manipuler une liste de telles observations qui est un tableau
de tableaux et pour simplifier on supposera que toutes les observations sont enregistrées pendant les années
non bissextiles (le nombre de jours du mois de février d’une année non bissextile est égal à 28).

Soient les déclarations suivantes :

DefConst
MAX = 365 //nombre de jours d’une année non bissextile
DefType
Jours_Mois = Tableau [1..12] de Entier
Observation = Tableau [1..3] de Entier //{jour, moi, degré}
Liste_Observations = Tableau [1..MAX] de Observation
DefVar
JM (Jours_Mois) // JM = {31Janvier, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31Décembre}
OBS(Observation)
LO (Liste_Observations)
© 24/25 A. DAHMANE & O. BEN ROMDHANE

Coups de pouces :
LO[1] : représente l’observation du premier jour de l’année.
LO[1][2] : représente le mois de l’observation du premier jour de l’année.
LO[1][3] : représente le degré de température enregistrée le premier jour de l’année.
OBS  LO[1] : permet d’affecter l’observation du premier jour de l’année dans OBS

24
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
Voici un exemple du tableau LO :

1 2 … 31 32 … 112 … MAX
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
1 1 12 2 1 12 … 31 1 9 1 2 10 … 22 4 24 …
jour mois degré

Observation N° 1 (LO[1]) enregistrée Observation N° 112 enregistrée le 22 avril (Température : 24°)

le 1er janvier (Température 12°) LO[112][1] = 22 | LO[112][2] = 4 | LO[112][3] = 24

TRAVAIL DEMANDE :
Le tableau JM = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} contenant les nombres de jours des mois d’une
année non bissextile est supposé déjà défini. Donc, Il sera passé comme paramètre en cas de besoin.

1) Ecrire la fonction Valide qui retourne vrai si à une observation obs donnée correspond un mois et un

jour corrects, et retourne faux sinon.

Exemples : - L’observation {22, 4, 24} est valide.
- L’observation {35, 15, 17} n’est pas valide (15  [1..12] et 35  [1..31]).
2) Ecrire la fonction Numero_Jour qui permet de retourner le numéro du jour dans l’année d’une

observation obs donnée et supposée valide.

Exemple : L’observation {22, 3, 20} enregistrée le 22 mars correspond au 81ème jour de l’année
(81 = 31Janvier + 28Février + 22Mars).
3) Ecrire une fonction Chercher_Observation qui retourne Vrai si l’observation obs existe dans une liste

d’observations LO donnée de taille nb, et retourne Faux sinon.

4) Ecrire la procédure Ajouter_Observation qui ajoute, à la fin d’une liste d’observations LO donnée de

taille nb, une observation obs donnée, si celle-ci est valide et non déjà enregistrée.

5) Ecrire la procédure Trier_Observation qui ordonne une liste LO de nb observations par ordre

chronologique croissant des observations.

Voici un exemple d’une liste triée LO de taille nb = 112 :
{{1, 1, 12}, {2, 1, 12}, …, {31, 1, 9}, {1, 2, 10}, …, {14, 2, 12}, …, {20, 4, 22}, {21, 4, 24}, {22, 4, 24}, …}
NB : - Dans cet exemple, 22 avril est la date de la dernière observation enregistrée dans LO.
- La taille nb = 112 = 31(janvier) + 28(février) + 31(mars) + 22(avril)
© 24/25 A. DAHMANE & O. BEN ROMDHANE

11) COURSE DE SKI

On souhaite gérer la saisie et l’affichage des résultats d’une course de ski. Pour cela, on dispose, avant la
course, d’un tableau contenant le nom et la nationalité de chacun des concurrents inscrits. Les dossards sont
attribués aux concurrents dans l’ordre où ils figurent dans ce tableau. Le numéro de dossard d’un concurrent
sera donc égal à son indice dans le tableau.
Au moment da la course, les concurrents prennent le départ les uns après les autres, à une minute
d’intervalle, dans un ordre qui n’est pas nécessairement celui des dossards.

25
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
A l’arrivée de chaque concurrent, on saisit directement son numéro de dossard et son temps (en minutes,
secondes et centièmes). On veut obtenir alors l’affichage du classement provisoire de la course : dans l’ordre
croissant des temps de parcours, on affichera le rang, le nom et le temps, de chaque concurrent déjà classé.
Ce classement s’allongera au fur et à mesure du déroulement de la course.

Exemple :
Soit le tableau de 5 skieurs suivant :
1 2 3 4 5
Bouteflika Adli Marzouki Erdogan MohamedVI
Algérie Egypte Tunisie Turquie Maroc

Premier résultat saisi : 4 2 15 75 Premier affichage : 1 Erdogan 2:15:75

Deuxième résultat saisi : 2 2 55 25 Deuxième affichage : 1 Erdogan 2:15:75

2 Adli 2:55:25

Troisième résultat saisi : 3 2 15 90 Troisième affichage : 1 Erdogan 2:15:75

2 Marzouki 2:15:90
3 Adli 2:55:25

et ainsi de suite jusqu’à la fin de la course. On aura ainsi le classement final.

On utilisera les déclarations de types suivants :

Structure Temps
min : 0..59
sec : 0..59
cent : 0..99
Fin Structure
Structure Skieur Structure Classement
nom : Chaîne[20] nom : Chaîne[20]
pays : Chaîne[20] tps : Temps
Fin Structure Fin Structure

TabSkieur = Tableau [1..maxSkieur] de Skieur -- maxSkieur: nombre total de skieurs

TabClass = Tableau [1..maxSkieur] de Classement

On suppose que la variable globale nb donne le nombre courant de skieurs.

1) Ecrire la fonction suivante, qui permet la comparaison de deux temps t1 et t2 :

Fonction CompTemps (t1, t2 : Temps) : Booléen
-- Postcond : résultat = t1 est inférieur ou égal à t2

2) Ecrire la fonction suivante, qui permet de trouver la position du temps t parmi les temps déjà
© 24/25 A. DAHMANE & O. BEN ROMDHANE

enregistrés dans TC[1..nb] :

Fonction PosTemps (TC : TabClass, t : Temps) : Entier
-- Précond : nb > 0, TC[1..nb] trié
-- Postcond : résultat = p, p  [1..nb+1], TC[1..p-1].tps  t  TC[p..nb].tps

3) Ecrire la procédure suivante, qui permet d'insérer le nom correspondant au skieur s et le temps
donné t, à la place donnée p, dans le vecteur trié TC[1..nb]. Le nom sera extrait du vecteur
TS[1..maxSkieur] :

26
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
 Procédure InsPlace (s : Entier, p : Entier, t : Temps, TS : TabSkieur, VAR TC : TabClass)
-- Précond : TC[1..nb] trié
-- Postcond : le skieur s et son temps t ont été insérés dans TC[1..nb]

4) Ecrire la procédure suivante, qui permet l'insertion dans TC du nom correspondant au skieur s et
du temps donné t, de telle sorte que TC reste trié.
Procédure Insérer (à compléter…)
-- Précond : TC[1..nb] trié
-- Postcond : TC[1..nb] trié, le skieur s et son temps t ont été insérés dans TC[1..nb]

5) Ecrire la procédure suivante, qui permet l'affichage du classement des nb premiers concurrents :
Procédure Afficher (à compléter…)
-- Précond : nb > 0, TC[1..nb] trié
-- Postcond : TC[1..nb] a été affiché

6) Ecrire la procédure suivante, qui permet la saisie du numéro de dossard doss et du temps t :
Procédure Saisie (à compléter)
-- Postcond : saisie de doss et t (avec doss  [0..maxSkieur])

7) Ecrire l'algorithme principal qui permet d'enchaîner les opérations de saisie et d'affichage des
classements, puis délivre le classement final et le nombre total de concurrents dans TC[1..nb]. on
supposera que la fin de la saisie est indiquée par un numéro de dossard nul.

© 24/25 A. DAHMANE & O. BEN ROMDHANE

27
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
 © 24/25 A. DAHMANE & O. BEN ROMDHANE

28
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
 LES ALGORITHMES RECURSIFS Partie 2

Points abordés :
 Les structures de données simples et composées & Les structures de contrôle
 Les sous-programmes (procédures, fonctions, paramètres, passage par valeur/par référence, variable globale/locale…)
 L'approche récursive

12) TRACE D'EXECUTION

Fonction Deviner (a : Entier, n : Entier) : Entier
DefVar
b(Entier)
Début
Si (n = 1) Alors
Deviner  a
Fin Si
b  Deviner(a, n Div 2)
Si (n Mod 2 =0) Alors
Deviner  b + b
Sinon
Deviner  b + b + a
FinSi
Fin

TRAVAIL DEMANDE :
1) Exécuter la fonction Deviner pour les 4 cas suivants :
Deviner(3,3), Deviner(4,11), Deviner(10,19062012) et Deviner(2,-5)

2) Si on changeait la structure conditionnelle

Si (n = 1) Alors Deviner  a FinSI
par
Si (n = 0) Alors Deviner  0 FinSI
Dites quel serait l’effet sur les valeurs suivantes :
a) k1, k2, k3 et k4.
b) La valeur de Deviner (a, n) lorsque n<0.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

13) INVERSION D’UN TABLEAU

Développer un algorithme récursif et/ou un programme C (main+fonction récursive) qui permet d’inverser
un tableau t de n entiers.

14) PALINDROME

Développer un algorithme récursif et/ou un programme C (main+fonction récursive) qui permet de vérifier
si une chaîne de caractères est palindrome ou pas (une chaîne palindrome est une chaîne qu’on peut lire
dans les deux sens).

29
Algorithmique et Structures de données I
TD N°7: La récursivité
15) OCCURRENCES D’UN ELEMENT DANS UN TABLEAU

Développer un algorithme récursif et/ou un programme C (main+fonction récursive) qui permet de

déterminer le nombre d’occurrences d’un nombre entré au clavier elem dans un tableau t de n réels.

16) TRIANGLE DE PASCAL

Le triangle de Pascal est la matrice des coefficients qui sont utilisés pour le développement de certaines
expressions comme (a+b)² ou (a+b)n. Proposer une solution récursive pour le remplissage de ce triangle.
Exemple (pour n = 4) :
0 1 2 3 4
Ligne 0 1 (a+b)0 = 1
Ligne 1 1 1 (a+b)1 = 1*a + 1*b
Ligne 2 1 2 1 (a+b)2 = 1*a2 + 2*a*b + 1*b2
Ligne 3 1 3 3 1 (a+b)3 = 1*a3 + 3*a²*b + 3*a*b² + 1*b3
Ligne 4 1 4 6 4 1 (a+b)4 = 1*a4 + 4*a3*b + 6*a²*b² + 4*a*b3 + 1*b4

En effet, pour une ligne donnée :

 Le premier et le dernier éléments sont égaux à 1.
 Les autres éléments sont déterminés en appliquant la formule récursive suivante :
P[i, j] = P[i-1, j] + P[i-1, j-1] avec i étant le numéro de la ligne et j le numéro de la colonne
Exemple : P[4, 2] = 6 = P[3, 2] + P[3, 1] = 3 + 3

17) TRACE D'EXECUTION : SAC A DOS

On donne la fonction récursive suivante :

Fonction SacADos (Masse: Entier, E: Entier): Booléen
Début
Si (Masse = 0)
Alors SacADos  Vrai //return 1 (en C)
Sinon Si (Masse < 0) Ou (E > n)
Alors SacADos  Faux //return 0 (en C)
Sinon Si SacADos(Masse – Poids[E], E + 1)
Alors Ecrire(Poids[E])
SacADos  Vrai //return 1 (en C)
Sinon SacADos  SacADos(Masse, E + 1)
//return SacADos(Masse, E + 1) (en C)
Fin Si
Fin Si
Fin Si
Fin
© 24/25 A. DAHMANE & O. BEN ROMDHANE

 Le tableau d’entiers Poids et l’entier n sont supposées deux variables globales.

 La variable Poids est définie par: Poids (Tableau [1..n] de Entier)

Travail demandé :
Faire la trace d’exécution de cette fonction SacADos sachant que :
1 2 3 4
Masse = 10, E = 1, n = 4, Poids = 5 3 4 2

30
Algorithmique et Structures de données I
TD N°7: La récursivité
 LES ALGORITHMES Partie

DE RECHERCHE ET DE TRI 2

Points abordés :
 Les structures de données simples et composées, les structures de contrôle, les sous-programmes et la récursivité
 Les méthodes de recherche séquentielle et dichotomique
 Les méthodes de tri : Tri par sélection, Tri à bulles, Tri par insertion, Tri fusion

1) RECHERCHE DICHOTOMIQUE

Sur un vecteur délimité par les indices 1 (BInf) et N (BSup), ordonné de manière croissante, le principe de
recherche dichotomique est le suivant :

Raisonnement itératif
 On rechercher l'élément situé à l'indice Pivot du vecteur (c-à-d le milieu du vecteur).
 On effectue une comparaison entre l'élément recherché et l'élément Pivot :
1. Elément à chercher = Elément Pivot : arrêt du traitement.
2. Elément à chercher  Elément Pivot : l'élément à chercher est obligatoirement (s'il existe) dans la partie
gauche du vecteur. On rapplique le même principe en modifiant la borne supérieure de recherche dans
le vecteur (BSup = Indice Pivot – 1).
3. Elément à chercher  Elément Pivot : l'élément à chercher est obligatoirement (s'il existe) dans la partie
droite du vecteur. On rapplique le même principe en modifiant la borne inférieure de recherche dans
le vecteur (BInf = Indice Pivot + 1).

Raisonnement récursif
 Paramétrage du problème : ...
 Recherche d'une valeur d'arrêt : le processus d'appel récursif s'arrête dans les 2 cas suivants :
▪ Lorsqu'on trouve l'élément recherché,
▪ Ou lorsque la borne inférieure dépasse la borne supérieure (Elément non trouvé).
 Décomposition du cas général : au moment du premier appel la borne inférieure vaut 1 et la borne
supérieure vaut N. Au deuxième appel, le champ de la recherche est diminué en positionnant l'élément à
chercher dans la partie adéquate (gauche ou droite).
© 24/25 A. DAHMANE & O. BEN ROMDHANE

Travail demandé :

1) Ecrire une fonction itérative, nommée Dicho1(...) permettant d'effectuer une recherche dichotomique

d'un élément réel elem dans un tableau T de N nombres réels triés dans l’ordre croissant. Le résultat de
la recherche est de type Booléen (Vrai si elem existe dans T, Faux sinon).
2) Ecrire une fonction récursive nommée Dicho2(...).

3) Développer un algorithme principal qui permet d'appliquer cette méthode de recherche dichotomique.

31
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
2) TRI COMPTAGE

Soit la procédure Tri_Comptage suivante :

Procédure TRI_COMPTAGE (tinit : TAB, VAR tres : TAB, N : Entier)

//tinit et tres sont deux tableaux d'entiers de taille N.
DefVar
i,j : Entier
trang : TAB //TAB est un type Tableau d'une seule dimension
Début
//Étape 1 : Initialisation des éléments du vecteur Trang à 1
Pour i de 1 à N Faire
Trang[i]  1
FinPour

//Étape 2 : Mise à jour du vecteur Trang à partir de Tinit

Pour i de 1 à N–1 Faire
Pour j de i+1 à N Faire
Si (Tinit[i]  Tinit[j])
Alors Trang[i]  Trang[i] + 1
Sinon Trang[j]  Trang[j] + 1
FinSI
FinPour
FinPour

//Étape 3 : Remplissage du vecteur Tres à partir des Trang et Tinit

Pour i de 1 à N Faire
Tres[Trang[i]]  Tinit[i]
FinPour
Fin

TRAVAIL DEMANDE :

Faire l'exécution de cette procédure en remplissant les tableaux suivants :

1 2 3 4 5 N= 6
TINIT 10 9 18 5 13 9
© 24/25 A. DAHMANE & O. BEN ROMDHANE

1 2 3 4 5 6
ÉTAPE 1 : TRANG 1 1 1 1 1 1

1 2 3 4 5 6
ÉTAPE 2 : TRANG

1 2 3 4 5 6
ÉTAPE 3 : TRES

32
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
3) TRI PAR SELECTION

Le principe du tri par sélection consiste à sélectionner l'élément dont la valeur est la plus basse (le minimum),
puis échanger la valeur de cet élément avec le premier élément du tableau. Le traitement se poursuit en
cherchant le minimum parmi ceux qui restent : c'est à dire à partir du deuxième élément du tableau puis
faire l'échange avec le deuxième élément jusqu'à atteindre T[n-1] et T[n]. La figure suivante présente un
exemple d'utilisation de cette méthode de tri par sélection.

Exemple d'utilisation de la méthode de tri par sélection

TRAVAIL DEMANDE :
© 24/25 A. DAHMANE & O. BEN ROMDHANE

1) Ecrire une procédure modulaire TRI_SELECTION (...) permettant de trier un tableau T de N entiers dans

l'ordre croissant en utilisant la méthode de tri par sélection.

2) Donner une trace d'exécution de cet algorithme en utilisant le tableau T suivant :

1 2 3 4 5 6
T 9 14 2 9 5 12

33
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
4) TRI A BULLES

L’idée de cet algorithme de tri est de faire descendre les éléments les plus petits, tandis que les
éléments les plus grands remontent. Chaque passe consiste en un parcours séquentiel. Durant ce
parcours, on permute les éléments consécutifs non ordonnés. Le vecteur est trié si lors d’une passe
on n’effectue aucune permutation.

Exemple d'utilisation de la méthode de tri à bulles

© 24/25 A. DAHMANE & O. BEN ROMDHANE

TRAVAIL DEMANDE :
Ecrire une procédure TRI_BULLES (...) permettant de trier un tableau T de N entiers dans l'ordre croissant en
utilisant la méthode de tri à bulles.

34
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
5) TRI PAR INSERTION

Procédure TRI_INSERTION (VAR T: TAB, N: Entier)

Le principe du tri par insertion consiste à placer l'élément T[i] du tableau (2  i  n) à la bonne place, c'est à
dire l'insérer parmi les éléments déjà ordonnés du sous-vecteur T[1..i-1]. Chaque insertion se fait par
comparaisons et décalages successifs et a pour conséquence d'agrandir le sous-vecteur ordonné d'un
élément.

Exemple d'utilisation de la méthode de tri par insertion

© 24/25 A. DAHMANE & O. BEN ROMDHANE

TRAVAIL DEMANDE :
Ecrire une procédure TRI_INSERTION (...) permettant de trier un tableau T de N entiers dans l'ordre croissant
en utilisant la méthode de tri à par insertion.

35
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
6) FUSION DE DEUX TABLEAUX TRIES

Soit un tableau t contenant une suite d’éléments triés entre les indices g et m inclus, puis une 2ème suite
d’éléments triés entre les indices m+1 et d inclus. On se propose d’écrire une procédure Fusion permettant
de fusionner ces deux suites d’éléments pour obtenir une suite triée entre les indices g et d inclus.

Coup de pouce : Vous pouvez commencer par recopier les deux suites t[g..m] et t[m+1..d] dans deux tableaux t1 et
t2, puis vous traitez le problème de la fusion (voir Figure ci-dessous). Il serait également possible de faire la fusion
“sur place” sans tableaux intermédiaires. La fusion consiste donc en des comparaisons successives. Des 2 sous-
séquences à fusionner, un seul élément peut-être origine de la nouvelle séquence. La détermination de cet élément
s'effectue suivant l'ordre du tri à adopter.

Voici l’entête de la procédure Fusion :

Procédure Fusion (VAR t: TAB, g: Entier, m: Entier, d: Entier)
avec g <= m, m <= d et d <= MAX

Le type TAB est défini comme suit :

TAB = Tableau [1..MAX] de Entier //MAX est une constante

Exemple de fonctionnement de la procédure Fusion

© 24/25 A. DAHMANE & O. BEN ROMDHANE

36
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
7) TRI PAR FUSION

Le principe de cet algorithme consiste à fusionner

deux sous-séquences triées en une séquence triée.
Il exploite directement le principe du "divide-and-
conquer" qui repose, grosso-modo, en la division
d'un problème en ses sous problèmes et en des
recombinaisons bien choisies des sous-solutions
optimales. Le principe de cet algorithme tend à
adopter une formulation récursive :
▪ On découpe les données à trier en deux parties
plus ou moins égales
▪ On trie les 2 sous-parties ainsi déterminées
▪ On fusionne les deux sous-parties pour retrouver
les données de départ

Donc chaque instance de la récursivité va faire

appel à nouveau au programme, mais avec une
séquence de taille inférieure à trier.
La terminaison de la récursivité est garantie, car les découpages seront tels qu'on aboutira à des
sous-parties d'un seul élément; le tri devient alors trivial. Une fois les éléments triés
indépendamment les uns des autres, on va fusionner (merge) les sous-séquences ensemble jusqu'à
obtenir la séquence de départ, triée (voir Fusion de deux tableaux triés).
La figure présentée ci-dessus montre une illustration des étapes de l'algorithme avec des données
réelles.

TRAVAIL DEMANDE :

a) Ecrire une procédure récursive TRI_FUSION (...) permettant de trier un tableau T de N entiers
dans l'ordre croissant selon la méthode de tri à par fusion en faisant appel à la procédure
précédente FUSION.
Procédure TRI_FUSION (VAR t : TAB, ...)

b) Faites la trace d’exécution de cette procédure TRI_FUSION avec le tableau réel suivant :
© 24/25 A. DAHMANE & O. BEN ROMDHANE

1 2 3 4 5 6 7 8
t 7 3 2 9 8 4 3 0

37
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
 © 24/25 A. DAHMANE & O. BEN ROMDHANE

38
Algorithmique et Structures de données I
TD Partie 2 : Sous-programmes, Récursivité, Algorithmes de recherche et de tri
 ALGORITHMES AVANCES
TD 9
& ANCIENS EXAMENS
Points abordés :
 Les structures de données, les structures de contrôle, les sous-programmes
 La récursivité
 Les algorithmes de recherche et de tri

1) DEMINEUR

Le démineur est un jeu de réflexion dont le but est de localiser des x mines
cachées dans une grille de taille n x m, qui peut avoir trois dimensions
différentes en fonction du niveau de difficulté, avec pour seule indication le
nombre de mines dans les cases adjacentes :
Niveau de difficulté :
-1- Débutant : Grille 9x9 et 10 Mines
-2- Intermédiaire : Grille 16x16 et 40 Mines
-3- Avancé : Grille 16x30 et 99 Mines

La grille Démineur est définie comme suit :

Démineur 9x9
DefConst (10 Mines)
LIN (Entier) = 15 'représente le nombre maximum de lignes (16)
COL (Entier) = 29 'représente le nombre maximum de colonnes (30)
DefType
Demineur = Tableau [0..LIN, 0..COL] de Entier //La mine (*) sera représentée en mémoire par le chiffre (-1)

Travail demandé – Développer les actions suivantes :

1) Procédure PlacerMines (…)
Cette procédure fait le placement aléatoire des mines en fonction du niveau de difficulté en utilisant la fonction
prédéfinie RAND(x) qui retourne un nombre entier dans l'intervalle [0 ; x-1].

2) Fonction CalculerChiffre (…)

Cette fonction permet de calculer le nombre de mines se trouvant dans le voisinage direct d'une case vide (ne
contenant pas une mine) passée en paramètre.

3) Procédure PlacerChiffres (…)

Cette procédure termine le remplissage complet d'une grille Démineur. Elle fait le calcul des nombres des différentes
cases du démineur.

Voici un exemple d'une grille démineur (9x9) complète après le placement des mines (*) et des chiffres
© 24/25 A. DAHMANE & O. BEN ROMDHANE

Au voisinage
direct de la case
[1,6], il y a 2 mines

39
Algorithmique et Structures de données I
TD N°9 : Algorithmes avancés & Sujets d’examens
4) Calcul du nombre de mines de chaque case : Après le placement des mines, l'algorithme parcourt
la grille en entier, case par case. Pour chacune d'entre elles, il compte le nombre de mines dans
le voisinage direct, et lui assigne ce nombre. Cette méthode est la plus évidente à comprendre
et à mettre en place, mais ce n'est pas la plus optimisée. Vous êtes appelés à proposer une
deuxième méthode plus performante ?

2) SUDOKU
Jeu de chiffres d'origine japonaise consistant à compléter une grille, subdivisée en 9 zones de 9 cases, avec des chiffres de 1 à 9.
Sur chaque ligne, il doit y avoir tous les chiffres de 1 à 9.
Sur chaque colonne, il doit y avoir tous les chiffres de 1 à 9.
Dans chaque bloc de 3x3 cases, il doit y avoir tous les chiffres de 1 à 9

Soit une matrice carrée S définie comme suit :

DefConst
MAX = 9
DefType
Sudoku = Tableau [1..MAX, 1..MAX] de Entier
TabChiffres = Tableau[1..MAX] de Entier
DefVar
S: Sudoku

Travail demandé - Développer les actions suivantes :

1) Procédure RemplirSudoku (VAR s : Sudoku, n : Entier)

Cette procédure permet de remplir la grille Sudoku s de taille (n x n) avec des entiers aléatoires compris
entre 1 et 9 en utilisant la fonction prédéfinie RAND(x).

2) Procédure Vidage (VAR S: Sudoku, Niv: Entier)

S est supposée remplie totalement et correctement avec des chiffres de 1 à 9. Cette procédure permet
de cacher d’une façon aléatoire un nombre (nb) de cases en fonction du niveau (niv) de difficulté du jeu
passé en paramètre. La figure ci-dessus montre un exemple d’une grille Sudoku avant et après vidage :
▪ Niveau 1 (Débutant) : nb = 27 cases vides
▪ Niveau 2 (Normal) : nb = 36 cases vides
▪ Niveau 3 (Expert) : nb = 45 cases vides

NB: Le choix des cases à vider doit se faire d'une façon aléatoire en utilisant la fonction prédéfinie RAND(x)
qui retourne un nombre entier dans l'intervalle fermé [0 ; x-1]. Le vidage consiste simplement à mettre
un zéro dans les différentes cases à vider.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

40
Algorithmique et Structures de données I
TD N°9 : Algorithmes avancés & Sujets d’examens
3) Procédure ChiffresPossibles(s:Sudoku, l:Entier, c:Entier,
ldeb: Entier, cdeb: Entier,
VAR tc: TabChiffres)
Elle permet de déterminer, dans le tableau tc (supposé initialisé à zéro), tous les chiffres possibles
pouvant être placés dans la case référencée par la ligne l et la colonne c de la grille s. ldeb et cdeb
représentent respectivement la ligne et la colonne de début du bloc encours. Voir exemple ci-
dessous :

4) Fonction VerifierLigne(s:Sudoku, l:Entier, elem:Entier) : Booléen

Elle renvoie Vrai si le chiffre elem se trouve déjà dans la ligne l de la grille s. Sinon, Faux. Cette
fonction permet de garantir l’unicité des chiffres dans chaque ligne d’une grille Sudoku.

a) Développer la fonction VerfierLigne(...)

b) Le bloc d’instructions présenté ci-dessous
permet de remplir une grille Sudoku S avec
des chiffres de 1 à 9 sans aucun contrôle.
Dire comment utiliser la fonction
VerifierLigne pour avoir, sur chaque ligne de
la grille S, tous les chiffres de 1 à 9.
© 24/25 A. DAHMANE & O. BEN ROMDHANE

NB : On s’intéresse seulement à la vérification au

niveau des lignes.

Pour i de 1 à MAX Faire

Voici un exemple d'une
Pour j de 1 à MAX Faire ligne Sudoku avec des
S[i,j]  RAND(9) + 1 chiffres distincts
FinPour
FinPour

41
Algorithmique et Structures de données I
TD N°9 : Algorithmes avancés & Sujets d’examens
5) Procédure AfficherSudoku (s : Sudoku, n : Entier)
Cette procédure permet d’afficher toute la grille S (n x n) de la façon suivante :

6) Procédure Sudoku (VAR s : Sudoku, ...)

Cette procédure permet de remplir la grille Sudoku s en fonction du niveau de difficulté (avec
respect des toutes les contraintes du jeu).

3) PROBLEME DES 8 DAMES

Le but du problème des huit dames est de placer huit dames d'un jeu
d'échecs sur un échiquier de 8 × 8 cases sans que les dames ne
puissent se menacer mutuellement, conformément aux règles du jeu
d'échecs (la couleur des pièces étant ignorée). Par conséquent, deux
dames ne devraient jamais partager la même rangée, colonne, ou
diagonale. Le plus souvent, il est employé comme exemple d'un
problème qui peut être résolu avec un algorithme récursif, en
© 24/25 A. DAHMANE & O. BEN ROMDHANE

exprimant qu'une solution du problème des n dames peut être

obtenue, par récurrence, à partir d'une solution quelconque du
problème des (n-1) dames par l'adjonction d'une dame. La récurrence
commence avec la solution du problème de 0-dame qui repose sur un échiquier vide (92 solutions distinctes).

42
Algorithmique et Structures de données I
TD N°9 : Algorithmes avancés & Sujets d’examens
4) TOURS DE HANOI

Implémenter en langage C le jeu des tours de Hanoï en utilisant une démarche récursive.
 Paramétrage du problème :
▪ n : nombre de disques
▪ A, B, C : les trois tours (départ, intermédiaire et arrivée)
 Recherche de la valeur d’arrêt : Si (n = 1) Alors « Déplacer un disque de A vers C »
 Décomposition du cas général : Résoudre le problème pour n disques ne présente pas de difficulté si on
sait le résoudre pour (n-1) disques ; en effet, transporter les n disques de la tour A à la tour C, c’est :
▪ Transporter les (n-1) premiers disques de A vers B (C tour intermédiaire), puis
▪ Déplacer le disque restant de A vers C, et enfin
▪ Transporter les (n-1) disques de B vers C (A tour intermédiaire).

void hanoi (int n, char t1, char t2, char t3);

//ou bien void hanoi (int n, int t1, int t2, int t3);

int main ()
{ int n;
char t1='A', t2='B', t3='C'; //ou bien int t1=1, t2=2, t3=3;
printf("Donner le nombre des disques : "); scanf("%d", &n);
hanoi(n, t1, t2, t3);
system("pause");
}

Voici un exemple de trois disques de tours de Hanoi

Voici un exemple d'exécution de la procédure Hanoi pour 3 disques

© 24/25 A. DAHMANE & O. BEN ROMDHANE

43
Algorithmique et Structures de données I
TD N°9 : Algorithmes avancés & Sujets d’examens
5) CRYPTAGE/DECRYPTAGE

On se propose de développer un programme (C, VB, Pascal ou autres) qui permet de crypter et décrypter un
texte. Un texte est constitué de plusieurs blocs de caractères (lettre, chiffre [0..9], symbole [#, &, *, @, ~,
%, …] ou signe de ponctuation [?, !, :, …]). Les différents blocs peuvent être éventuellement séparés par un
ou plusieurs espaces (bloc d’espaces).
➢ Le cryptage traite chaque bloc de caractères séparément selon son longueur et laisse invariant les blocs
d’espaces: on ajoute à chaque code "Unicode" d’un caractère le nombre de caractères du bloc qui le
contient.
➢ Le décryptage traite aussi chaque bloc de caractères (crypté) séparément selon son longueur et laisse
invariant les blocs d’espaces: on diminue de chaque code "Unicode" d’un caractère le nombre de
caractères du bloc qui le contient.

Voici un exemple d’exécution du programme lorsqu’il sera terminé :

"Petità petit,l’oiseaufaitsonnid!"
Espace

"vkzoz2"
Unicode("p") + long("petit,")
donne le nouveau caractère "v"
© 24/25 A. DAHMANE & O. BEN ROMDHANE

44
Algorithmique et Structures de données I
TD N°9 : Algorithmes avancés & Sujets d’examens