TD I3

v1.6
avec solution
N. Delestre

Table des matières

1 Affectation et schéma conditionnel 3
1.1 Affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Échanger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Permutation circulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Décomposition d’une somme d’argent . . . . . . . . . . . . . . . . . . . 3
1.1.4 Parité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.5 Date valide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Schéma conditionnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Tri de trois entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Nombre de jours de congés . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Schéma itératif 6
2.1 La multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Calcul de factorielle n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Partie entière inférieure de la racine carrée d’un nombre . . . . . . . . . . . . . . 7
2.4 Multiplication égyptienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.5 Intégration par la méthode des trapèzes . . . . . . . . . . . . . . . . . . . . . . . 8

3 Schéma itératif (suite) 9

3.1 Développement limité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Recherche du zéro d’une fonction par dichotomie . . . . . . . . . . . . . . . . . 10

4 Analyse descendante 11
4.1 Nombre de chiffres pairs dans un nombre . . . . . . . . . . . . . . . . . . . . . 11
4.2 Majuscule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.1 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.2 Conception préliminaire . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2.3 Conception détaillée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

5 TP Pascal : des multiplications 14

5.1 Une première version du programme . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2 Une deuxième version du programme . . . . . . . . . . . . . . . . . . . . . . . 16

1
6 Tableaux 17
6.1 Plus petit élément d’un tableau d’entiers . . . . . . . . . . . . . . . . . . . . . . 17
6.2 Indice du plus petit élément d’un tableau d’entiers . . . . . . . . . . . . . . . . . 18
6.3 Nombre d’occurrences d’un élément . . . . . . . . . . . . . . . . . . . . . . . . 18
6.4 Élément le plus fréquent d’un tableau . . . . . . . . . . . . . . . . . . . . . . . 19
6.5 Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.6 Tris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.6.1 Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.6.2 Tri shaker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

7 TP Pascal : Matrice 22

8 Récursivité 24
8.1 Calcul de C(n,p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.2 Multiplication égyptienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
8.3 Des cercles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
8.3.1 Compréhension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
8.3.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8.4 Recherche d’un élément dans un tableau . . . . . . . . . . . . . . . . . . . . . . 28

9 TP Pascal : Benchmark de tri 29

9.1 Résultats attendus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.1.1 testTri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.1.2 benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.2 Travail à réaliser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10 TP Pascal : Benchmark de tri (suite) 32

10.1 Résultats attendus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
10.1.1 testTri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
10.1.2 benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
10.2 Travail à réaliser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

11 Liste chaı̂née 34

12 TP Pascal : Liste chaı̂née 36

12.1 Résultats attendus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
12.2 Travail à réaliser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

13 TP Pascal : Tableaux dynamiques 38

13.1 Résultats attendus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
13.2 Travail à réaliser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

14 TP Pascal : Fichiers 41
14.1 Résultats attendus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
14.2 Travail à réaliser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2
1 Affectation et schéma conditionnel
1.1 Affectation
1.1.1 Échanger
Ecrire une procédure, échangerDeuxEntiers, qui permet d’échanger les valeurs de deux entiers.

Solution proposée :
procédure échangerDeuxEntiers (E/S a,b : Entier)
Déclaration temp : Entier
debut
temp ← a
a←b
b ← temp
fin

1.1.2 Permutation circulaire

Écrire une procédure qui permet d’affectuer une permutation circulaire des valeurs entières de
trois variables x, y, z (c’est-à-dire la valeur de y dans x, la valeur de z dans y et la valeur de x dans
z.

Solution proposée :
procédure permutationDeTroisEntiers (E/S x,y,z : Entier)
Déclaration temp : Entier
debut
temp ← x
x←y
y←z
z ← temp
fin

1.1.3 Décomposition d’une somme d’argent

Écrire une procédure, decomposerSomme, qui à partir d’une somme ronde d’argent donnée,
donne le nombre minimal de billets de 5 et 10 ¤ et le nombre de pièces de 2 et 1 ¤ qui la compose.

Solution proposée :
procédure decomposerSomme (E somme : Naturel ;S nbBilletDe10, nbBilletDe5, nbPieceDe2,
nbPieceDe1 : Naturel)
Déclaration sommeRestante : Naturel
debut
sommeRestante ← somme
nbBilletDe10 ← sommeRestante div 10
sommeRestante ← sommeRestante mod 10
nbBilletDe5 ← sommeRestante div 5
sommeRestante ← sommeRestante mod 5
nbPieceDe2 ← sommeRestante div 2

3
 nbPieceDe1 ← sommeRestante mod 2
fin
À titre d’exemple de raisonnement à mener pour la validation structurelle de votre algorithme,
voici la démarche à effectuer.
— Cohérence des types : Ici, il n’apparait pas explicitement de contrainte sur le type des pa-
ramètres. Cette contrainte est induite par la sémantique (ce qui est le cas le plus fréquent).
Compte tenu de la sémantique des paramètres, ici le type à utiliser est ”Naturel” et non pas
”Entier”. En effet ”Entier” autoriserait la définition de données négatives (ce qui n’est pas
possible pour une somme d’argent à décomposer).
— Les paramètres de sortie sont tous au moins présents une fois en partie gauche d’une affec-
tation.
— Le paramètre d’entrée n’est jamais présent en partie gauche d’une affectation.
— Le type utilisé pour la variable temporaire est compatible avec le type des paramètres.
Une fois ces contrôles effectués, cela ne signifie pas que votre algorithme est juste mais seule-
ment qu’il a une chance d’être juste car il sera structurellement correct. Son adéquation sémantique
elle ne peut pas être vérifiée formellement à ce stade de vos connaissances.
Il vous appartient maintenant d’appliquer ce raisonnement aux alogrithmes que vous écrivez.

1.1.4 Parité
Écrire une fonction booléenne, estPair, qui à partir d’un nombre entier strictement positif re-
tourne VRAI si ce nombre est pair et FAUX sinon.

Solution proposée :
fonction estPair (a : NaturelNonNul) : Booleen
debut
retourner a mod 2 = 0
fin
Ici, une contrainte apparait sur le paramètre qui doit être un entier strictement positif. Le type
associé est alors NaturelNonNul.

1.1.5 Date valide

Écrire une fonction qui pour un numéro de jour, de mois et d’année donnés, détermine s’il
s’agit ou non d’une date, après JC, valide (d’après le calendrier grégorien).
Rappel 1 :
“Depuis l’instauration du calendrier grégorien, sont bissextiles :
1. les années divisibles par 4 mais non divisibles par 100
2. les années divisibles par 400
Ainsi, l’an 2004 était bissextile suivant la première règle. L’an 1900 n’était pas bissex-
tile, car divisible par 100, ce qui va à l’encontre de la première règle, et non divisible
par 400, ce qui va à l’encontre de la seconde. L’an 2000 était bissextile car divisible
par 400.”

Solution proposée :
Une date j/m/a est valide si et seulement si a > 0 et :
— lorsque m ∈ {1, 3, 5, 7, 8, 10, 12} alors j ∈ [1..31]
1. D’après Wikipedia

4
 — lorsque m ∈ {4, 6, 9, 11} alors j ∈ [1..30]
— lorsque m = 2, alors j ∈ [1..28] pour les année non bissextile et j ∈ [1..29] sinon.
fonction dataValide (j : 1..31, m : 1..12, a : NaturelNonNul) : Booleen
Déclaration validePourMoisEn31Jours, validePourMoisEn30Jours, validePourMoisFevrier :
Booleen
debut
validePourMoisEn31Jours ← (m=1 ou m=3 ou m=5 ou m=7 ou m=8 ou m=10 ou m=12) et
j≤31
validePourMoisEn30Jours ← (m=4 ou m=6 ou m=9 ou m=11) et j≤30
validePourMoisFevrier ← m=2 et ((((a mod 4 = 0 et a mod 100 6= 0) ou (a mod 400 = 0)) et
j≤29) ou j≤28)
retourner a>0 et j>0 (validePourMoisEn31Jours ou validePourMoisEn30Jours ou valide-
PourMoisFevrier)
fin

1.2 Schéma conditionnel

1.2.1 Tri de trois entiers
Écrire une procédure, trierTroisEntiers, qui prend en entrée trois paramètres a, b et c contenant
chacun un entier et qui les retourne triés par ordre croissant : a contient la valeur minimum, et c
contient la valeur maximum.

Solution proposée :
procédure echanger (E/S a,b : Entier)
Déclaration temp : Entier
debut
temp ← a
a←b
b ← temp
fin

procédure trierDeuxEntiers (E/S a,b : Entier)

debut
si a>b alors
echanger(a,b)
finsi
fin

procédure trierTroisEntiers (E/S a,b,c : Entier)

debut
trierDeuxEntiers(a,b)
trierDeuxEntiers(b,c)
trierDeuxEntiers(a,b)
fin

5
1.2.2 Nombre de jours de congés
Dans une entreprise, le calcul des jours de congés payés s’effectue de la manière suivante : si
une personne est entrée dans l’entreprise depuis moins d’un an, elle a droit à deux jours de congés
par mois de présence (au minimum 1 mois), sinon à 28 jours au moins. Si cette personne est un
cadre et si elle est âgée d’au moins 35 ans et si son ancienneté est supérieure à 3 ans, il lui est
accordé 2 jours supplémentaires. Si elle est cadre et si elle est âgée d’au moins 45 ans et si son
ancienneté est supérieure à 5 ans, il lui est accordé 4 jours supplémentaires, en plus des 2 accordés
pour plus de 35 ans.
Écrire une fonction, nbJoursDeConges, qui calcule le nombre de jours de congés à partir de
l’âge exprimé en année, l’ancienneté exprimée en mois et l’appartenance (booléenne) au collège
cadre d’une personne.

Solution proposée :
fonction nbJoursDeConges (age : 16..65 ; anciennete : NaturelNonNul ; cadre : Booleen) : Natu-
rel
Déclaration nbJours : Naturel
debut
si anciennete<12 alors
nbJours ← anciennete*2
sinon
nbJours ← 28
finsi
si cadre alors
si age ≥ 35 et anciennete ≥ 3*12 alors
nbJours ← nbJours + 2
finsi
si age ≥ 45 et anciennete ≥ 5*12 alors
nbJours ← nbJours + 4
finsi
finsi
retourner nbJours
fin

2 Schéma itératif
2.1 La multiplication
Écrire une fonction, multiplication, qui effectue la multiplication de deux entiers positifs (notés
x et y) donnés en utilisant uniquement l’addition entière.

Solution proposée :
fonction multiplication (x,y : Naturel) : Naturel
Déclaration i, produit : Naturel
debut
produit ← 0
pour i ←1 à x faire
produit ← produit + y

6
 finpour
retourner produit
fin

2.2 Calcul de factorielle n

Écrire une fonction, factorielle, qui calcule pour un entier positif donné n la valeur de n !.

Solution proposée :
fonction factorielle (n : Naturel) : Naturel
Déclaration i, valeur : Naturel
debut
valeur ← 1
pour i ←1 à n faire
valeur ← valeur * i
finpour
retourner valeur
fin

2.3 Partie entière inférieure de la racine carrée d’un nombre

Écrire une fonction, racineEntiere, qui retourne la partie entière de la racine carrée d’un entier
positif donné n (sans utiliser racineCarree).

Solution proposée :
fonction racineEntiere (n : Naturel) : Naturel
Déclaration racine : Naturel
debut
racine ← 1
tant que racine * racine ≤ n faire
racine ← racine + 1
fintantque
retourner racine - 1
fin

2.4 Multiplication égyptienne

Les égyptiens de l’antiquité savaient :
— additionner deux entiers strictement positifs,
— soustraire 1 à un entier strictement positif,
— multiplier par 1 et 2 tout entier strictement positif,
— diviser par 2 un entier strictement positif pair.
Voici un exemple qui multiplie 14 par 13 en utilisant uniquement ces opérations :
14 × 13 = 14 + 14 × (13 - 1) = 14 + 14 × 12
= 14 + (14 × 2) × (12 / 2) = 14 + 28 × 6
= 14 + (28 × 2) × (6 / 2) = 14 + 56 × 3
= 14 + 56 + 56 × (3 - 1) = 70 + 56 × 2
= 70 + (56 × 2) × (2 / 2) = 70 + 112 × 1
= 70 + 112 = 182

7
 Donner le corps de la fonction suivante :
fonction multiplicationEgyptienne (a,b : Naturel) : Naturel

Solution proposée :
fonction multiplicationEgyptienne (a,b : Naturel) : Naturel
Déclaration resultat : Naturel
debut
resultat ← 0
tant que b>0 faire
si b mod 2=0 alors
a ← 2*a
b ← b div 2
sinon
resultat ← resultat+a
b ← b-1
finsi
fintantque
retourner a
fin

2.5 Intégration par la méthode des trapèzes

Écrire une fonction, integrale, qui retourne la valeur de l’intégrale d’une fonction f(x) réelle
continue sur l’intervalle réel [a, b]. L’intégration consiste à découper cet intervalle, en n sous-
intervalles de longueur ∆. L’intégrale d’un sous-intervalle [x, x + ∆] est approximée au trapèze
de base ∆ et de côtés f(x) et f(x + ∆). a, b et n vous sont donnés.
Remarque : la communication de f entre l’appelant et la fonction appelée, est réalisée de
manière implicite (opération transparente pour vous). Cette remarque est valide pour tous les
exercices numériques de ce type.

Solution proposée :
fonction integrale (a,b : Reel ; n : NaturelNonNul) : Reel
bprécondition(s) a ≤ b
Déclaration x1, x2, ∆, somme : Reel
debut
somme ← 0
x1 ← a
∆ ← (b - a)/n
pour i ←1 à n faire
x2 ← x1 + ∆
somme ← somme + (f(x1) + f(x2))
x1 ← x2
finpour
somme ← somme * ∆ / 2
retourner somme
fin

8
 Soit vous introduisez une pré-condition sur (a, b) soit vous devez tenir compte dans l’algo-
rithme pour le calcul de ∆ et utiliser valeurAbsolue(b-a).
Version un peu optimisée :
fonction integrale (a,b : Reel ; n : NaturelNonNul) : Reel
bprécondition(s) a ≤ b
Déclaration x1, x2, ∆, somme : Reel
debut
somme ← 0
x←a
∆ ← (b - a)/n
pour i ←2 à n-1 faire
x←x+∆
somme ← somme + f(x)
finpour
somme ← ∆*(somme+((f(a)+f(b)) / 2))
retourner somme
fin

3 Schéma itératif (suite)

3.1 Développement limité
Lorsque x est proche de 0, sinh(x) peut être approximé à l’aide de la formule suivante :

n
X x2i+1
(2i + 1)!
i=0

Écrire la fonction sinh en n’utilisant aucune autre fonction (pas d’analyse descendante) :

fonction sinh (x : Reel, n : Naturel) : Reel

Déclaration i : Naturel
numerateur,denominateur : Reel
resultat : Reel
debut
...
fin

Solution proposée :
fonction sinh (x : Reel, n : Naturel) : Reel
Déclaration i : Naturel
numerateur,denominateur : Reel
resultat : Reel
debut
numerateur ← x
denominateur ← 1

9
 resultat ← resultat+numerateur/denominateur
pour i ←1 à n faire
numerateur ← numerateur*x*x
denominateur ← (2*i+1)*(2*i)*denominateur
resultat ← resultat+numerateur/denominateur
finpour
retourner resultat
fin

3.2 Nombres premiers

Écrire une fonction booléenne, estPremier, qui à partir d’un entier strictement positif donné,
retourne le résultat VRAI ou FAUX selon que le nombre est premier ou non. Pour mémoire, voici
la liste des nombres premiers inférieurs à 100 : 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Solution proposée :
fonction estPremier (n : NaturelNonNul) : Booleen
Déclaration i : NaturelNonNul,
premier : Booleen
debut
premier ← VRAI
i←2
tant que premier et i ≤ racineCarree(n) faire
si n mod i = 0 alors
premier ← FAUX
finsi
i←i+1
fintantque
retourner premier
fin

3.3 Recherche du zéro d’une fonction par dichotomie

Écrire une fonction, zeroFonction, qui calcule le zéro d’une fonction réelle f(x) sur l’intervalle
réel [a, b], avec une précision epsilon. La fonction f ne s’annule qu’une seule et unique fois sur
[a, b]. Pour trouver ce zéro, la recherche procède par dichotomie, c’est-à-dire divise l’intervalle de
recherche par deux à chaque étape. Soit m le milieu de [a, b]. Si f(m) et f(a) sont de même signe,
le zéro recherché est dans l’intervalle [m, b], sinon il est dans l’intervalle [a, m]. a, b et epsilon
vous sont donnés.

Solution proposée :
fonction estMemeSigne (a,b : Reel) : Booleen
debut
retourner a * b ≥ 0
fin

fonction zeroFonction (a,b, epsilon : Reel) : Reel

bprécondition(s) a ≤ b

10
 Déclaration borneMin, milieu, borneMax : Reel
debut
borneMin ← a
borneMax ← b
tant que (borneMax - borneMin) > epsilon faire
milieu ← (borneMin + borneMax) / 2
si estMemeSigne(f(borneMin), f(milieu)) alors
borneMin ← milieu
sinon
borneMax ← milieu
finsi
fintantque
retourner borneMin
fin

4 Analyse descendante
4.1 Nombre de chiffres pairs dans un nombre
On se propose de calculer le nombre de chiffres pairs d’un nombre donné. On suit pour cela
l’analyse descendante présentée par la figure 1, tel que :
nbChiffresPairs résoud le problème demandé. Par exemple pour le nombre 821, on obtient 2.
nbChiffres permet d’obtenir le nombre de chiffres d’un nombre. Par exemple pour le nombre
821, on obtient 3.
iemeChiffre permet d’obtenir le ième chiffre d’un nombre. Par exemple pour 821, le premier
chiffre est 1, le second 2 et le troisième est 8 (on ne traite pas les erreurs).
estPair permet de savoir si un nombre est pair.

nbChiffresPairs

nbChiffres estPair

iemeChiffre

F IGURE 1 – Analyse descendante

1. Reprenez le schéma donné et complétez le (tel que nous l’avons vu en cours).

2. Donnez la signature des fonctions ou procédures des opérations données par l’analyse des-
cendante.
3. Donnez le corps de la fonction ou procédure nbChiffresPairs.

Solution proposée :

11
 Naturel nbChiffresPairs Naturel

Naturel nbChiffres NaturelNonNul Naturel estPair Booléen

Naturel
NaturelNonNul iemeChiffre Naturel
1.
2.
— fonction nbChiffresPairs (nb : Naturel) : Naturel
— fonction nbChiffres (nb : Naturel) : Naturel
— fonction iemeChiffre (nb : Naturel,) : Naturel
— fonction estPair (nb : Naturel,) : Booleen
3.
fonction nbChiffresPairs (nb : Naturel) : Naturel
Déclaration i : Naturel
resultat : Naturel
debut
resultat ← 0
pour i ←1 à nbChiffres(nb) faire
si estPair(iemeChiffre(nb,i)) alors
resultat ← resultat+1
finsi
finpour
retourner resultat
fin

4.2 Majuscule
La fonction majuscule permet de calculer à partir d’une chaı̂ne de caractères ch une chaı̂ne de
caractères ch0 tel que tous les caractères minuscules, et uniquement eux, de ch soient transformés
en majuscule dans ch0 . La signature de cette est fonction est :
— fonction majuscule (uneChaine : Chaine de caracteres) : Chaine de caracteres
Ainsi majuscule(”abc, ?ABC”) donne la valeur ”ABC, ?ABC”.
L’objectif de cet exercice est de donner l’algorithme de cette fonction en considérant que nous
avons les trois fonctions suivantes :
— fonction longueur (uneChaine : Chaine de caracteres) : Naturel
— fonction iemeCaractere (uneChaine : Chaine de caracteres, position : Naturel) : Carac-
tere
— fonction caractereEnChaine (unCaractere : Caractere) : Chaine de caracteres

4.2.1 Analyse
Pour calculer la version majuscule d’une chaı̂ne de caractères ch, on a besoin de savoir calculer
la majuscule d’un caractère c de ch lorsque c représente une lettre minuscule. Nous n’avons aucun
a priori concernant la table de codage de ces caractères, si ce n’est que :
— le caractère ’a’ précède le caractère ’b’, qui précède le caractère ’c’, etc.
— le caractère ’A’ précède le caractère ’B’, qui précède le caractère ’C’, etc.
Proposez une analyse descendante de ce problème à l’aide du formalisme vu en cours.

Solution proposée :

12
 Chaine majuscule Chaine

Caractère estUneLettreMinuscule Booléen

Caractère lettreMajuscule Caractère

4.2.2 Conception préliminaire

Déterminez la signature des fonctions ou procédures correspondant aux opérations de votre
analyse descendante.

Solution proposée :
— fonction majuscule (ch : Chaine de caracteres) : Chaine de caracteres
— fonction estUneLettreMinuscule (c : Caractere) : Booleen
— fonction lettreMajuscule (c : Caractere) : Caractere

4.2.3 Conception détaillée

Donnez le corps de chacune de ces fonctions ou procédures.
Solution proposée :
fonction majuscule (ch : Chaine de caracteres) : Chaine de caracteres
Déclaration i : Naturel
c : Caractere
resultat : Chaine de caracteres
debut
resultat ← ””
pour i ←1 à longueur(ch) faire
c ← iemeCaractere(ch,i)
si estUneLettreMinuscule(c) alors
resultat ← resultat+ caractereEnChaine(lettreMajuscule(c))
sinon
resultat ← resultat+ caractereEnChaine(c)
finsi
finpour
retourner resultat
fin
fonction estUneLettreMinuscule (c : Caractere) : Booleen
debut
retourner c≥’a’ et c≤’z’
fin
fonction lettreMajuscule (c : Caractere) : Caractere
debut
retourner chr(ord(’A’)+ord(c)-ord(’a’))

13
 fin
ou

fonction lettreMajuscule (c : Caractere) : Caractere

Déclaration i : Caractere
resultat : Caractere
debut
resultat ← ’A’
pour i ←’b’ à c faire
resultat ← succ(resultat)
finpour
fin

5 TP Pascal : des multiplications

L’objectif de ce TP est de comparer les algorithmes vus dans les exercices 2.1 et 2.4.

5.1 Une première version du programme

L’objectif de ce premier programme est d’afficher le temps mis pour calculer la multiplication
de deux nombreux positifs saisis par l’utilisateur. Le résultat attendu est du type :

$ ./multiplication
Calcul de a*b :
a = 12
b = 10000000
Multiplication classique, a*b = 120000000 en 28 ms
Multiplication egyptienne, a*b = 120000000 en 0 ms

Afin de tester la multiplication avec des grands nombres, vous utiliserez le type de données
QWord pour un ordinateur 64 bits et LongWord pour un ordinateur 32 bits 2 . De plus, les ordina-
teurs d’aujourd’hui sont si rapides, que vous vous arrangerez pour que les deux algorithmes itèrent
sur le plus grand des deux nombres à multiplier.
Vous pouvez calculer le temps mis pour l’exécution d’une procédure ou d’une fonction en l’en-
cadrant par deux appels à la fonction dateTimeToTimeStamp() avec comme paramètre ef-
fectif l’appel à la fonction time() (disponibles dans l’unité sysutils). La valeur retournée par
dateTimeToTimeStamp est de type TTimeStamp, qui est un enregistrement dont le champ
time possède l’heure correspondante en ms. La soustraction de ces deux valeurs vous permettra
d’avoir une idée quant au temps mis par cette fonction ou procédure.
Vous comparerez le temps mis par ces deux algorithmes en augmentant régulièrement la taille
des nombres saisis (vous pouvez aller jusqu’à des valeurs de plusieurs milliards).

Solution proposée :
1 program multiplication;
2
3 u s e s sysutils;
4
5 type
6 Entier = QWord;

2. L’instruction for ne fonctionne pas avec des entiers sur 64 bits. Il faut dans ce cas utiliser un while

14
 7
8 f u n c t i o n min(a,b : Entier) : Entier;
9 begin
10 i f a<b t h e n
11 min:=a
12 else
13 min:=b
14 end;
15
16 f u n c t i o n max(a,b : Entier) : Entier;
17 begin
18 i f a>b t h e n
19 max:=a
20 else
21 max:=b
22 end;
23
24 f u n c t i o n multiplicationClassique(a,b : Entier) : Entier;
25 var
26 i,a1,b1 : Entier;
27 begin
28 a1:=max(a,b);
29 b1:=min(a,b);
30 multiplicationClassique:=0;
31 w h i l e (i<=a1) do
32 begin
33 multiplicationClassique:=multiplicationClassique+b1;
34 inc(i)
35 end
36 end; { multiplicationClassique }
37
38 f u n c t i o n multiplicationEgyptienne(a,b : Entier) : Entier;
39 var
40 a1,b1 : Entier;
41 begin
42 a1:=min(a,b);
43 b1:=max(a,b);
44 multiplicationEgyptienne:=0;
45 w h i l e (b1>0) do
46 i f (b1 mod 2)=0 t h e n
47 begin
48 a1:=2*a1;
49 b1:=b1 d i v 2;
50 end
51 else
52 begin
53 multiplicationEgyptienne:=multiplicationEgyptienne+a1;
54 b1:=b1-1;
55 end;
56 end; { multiplicationEgyptienne }
57
58 var
59 a,b,res : Entier;
60 t1,t2 : TTimeStamp;
61
62 begin
63 w r i t e l n (’Calcul de a*b :’);
64 w r i t e (’ a = ’); r e a d l n (a);
65 w r i t e (’ b = ’); r e a d l n (b);
66 t1:=DateTimeToTimeStamp(Time());
67 res:=multiplicationClassique(a,b);
68 t2:=DateTimeToTimeStamp(Time());
69 w r i t e l n (’ Multiplication classique, a*b = ’,res,’ en ’, t2.time-t1.time,’ ms’);
70 t1:=DateTimeToTimeStamp(Time());
71 res:=multiplicationEgyptienne(a,b);
72 t2:=DateTimeToTimeStamp(Time());
73 w r i t e l n (’ Multiplication egyptienne, a*b = ’,res,’ en ’, t2.time-t1.time,’ ms’);
74 end.

15
 5.2 Une deuxième version du programme
Nous voulons maintenant pouvoir tracer des courbes montrant la complexité de ces deux algo-
rithmes. Ces graphiques seront tracés grâce au logiciel Libreoffice calc à partir des calculs effectués
par votre programme pascal.
Le programme va multiplier successivement un nombre a de plus en plus grand par un autre
nombre constant (par exemple 1). Au départ a aura pour valeur 1000 et sera après chaque itération
multiplié par 10 jusqu’à être supérieur à un nombre saisi par l’utilisateur. Pour chaque multipli-
cation vous afficherez la valeur de a, le temps pour la multiplication classique et le temps pour la
multiplication égyptienne (valeurs séparées par une virgule).
Voici un exemple d’exécution du programme :

$ ./multiplications
Borne max (>1000 et multiple de 10):10000000000
,Multiplication classique,Multiplication égyptienne
1000,0,0
10000,0,0
100000,0,0
1000000,6,0
10000000,31,0
100000000,199,0
1000000000,1983,0

À l’aide d’un copier/coller vous importerez dans LibreOffice calc ces données afin de créer le
diagramme demandé (diagramme de type dispersion avec ligne et point).

Solution proposée :
1 program multiplication;
2
3 u s e s sysutils;
4
5 type
6 Entier = QWord;
7
8 f u n c t i o n min(a,b : Entier) : Entier;
9 begin
10 i f a<b t h e n
11 min:=a
12 else
13 min:=b
14 end;
15
16 f u n c t i o n max(a,b : Entier) : Entier;
17 begin
18 i f a>b t h e n
19 max:=a
20 else
21 max:=b
22 end;
23
24 f u n c t i o n multiplicationClassique(a,b : Entier) : Entier;
25 var
26 i,a1,b1 : Entier;
27 begin
28 a1:=max(a,b);
29 b1:=min(a,b);
30 multiplicationClassique:=0;
31 i:=1;
32 w h i l e (i<=a1) do
33 begin

16
34 multiplicationClassique:=multiplicationClassique+b1;
35 inc(i)
36 end
37 end; { multiplicationClassique }
38
39 f u n c t i o n multiplicationEgyptienne(a,b : Entier) : Entier;
40 var
41 a1,b1 : Entier;
42 begin
43 a1:=min(a,b);
44 b1:=max(a,b);
45 multiplicationEgyptienne:=0;
46 w h i l e (b1>0) do
47 i f (b1 mod 2)=0 t h e n
48 begin
49 a1:=2*a1;
50 b1:=b1 d i v 2;
51 end
52 else
53 begin
54 multiplicationEgyptienne:=multiplicationEgyptienne+a1;
55 b1:=b1-1;
56 end;
57 end; { multiplicationEgyptienne }
58
59 var
60 i,res,borne : Entier;
61 t1,t2,t3 : TTimeStamp;
62
63 begin
64 w r i t e (’Borne max (>1000 et multiple de 10):’);
65 r e a d l n (borne);
66 w r i t e l n (’,Multiplication classique,Multiplication à c gyptienne’);
67 i:=1000;
68 w h i l e (i<borne) do
69 begin
70 t1:=DateTimeToTimeStamp(Time());
71 res:=multiplicationClassique(i,1);
72 t2:=DateTimeToTimeStamp(Time());
73 res:=multiplicationEgyptienne(i,1);
74 t3:=DateTimeToTimeStamp(Time());
75 w r i t e l n (i,’,’,t2.time-t1.time,’,’,t3.time-t2.time);
76 i:=i*10
77 end;
78 end.

6 Tableaux
Dans tous les exercices qui vont suivre, le tableau d’entiers t est défini comme étant de type
Tableau[1..MAX] d’Entier.

6.1 Plus petit élément d’un tableau d’entiers

Écrire une fonction, minTableau, qui à partir d’un tableau d’entiers t non trié de n éléments
significatifs retourne le plus petit élément du tableau.

Solution proposée :
fonction minTableau (t : Tableau[1..MAX] d’Entier ; n : Naturel) : Entier
bprécondition(s) n ≥ 1 et n≤MAX
Déclaration i : Naturel,
min : Entier

17
debut
min ← t[1]
pour i ←2 à n faire
si t[i]<min alors
min ← t[i]
finsi
finpour
retourner min
fin

6.2 Indice du plus petit élément d’un tableau d’entiers

Écrire une fonction, indiceMin, qui retourne l’indice du plus petit élément d’un tableau d’en-
tiers t non trié de n éléments significatifs.

Solution proposée :
fonction indiceMin (t : Tableau[1..MAX] d’Entier ; n : Naturel) : Naturel
bprécondition(s) n ≥ 1 et n≤MAX
Déclaration i, indiceDuMin : Naturel
debut
indiceDuMin ← 1
pour i ←2 à n faire
si t[i]<t[indiceDuMin] alors
indiceDuMin ← i
finsi
finpour
retourner indiceDuMin
fin

6.3 Nombre d’occurrences d’un élément

Écrire une fonction, nbOccurences, qui indique le nombre de fois où un élément apparaı̂t dans
un tableau d’entiers t non trié de n éléments.

Solution proposée :
fonction nbOccurences (t : Tableau[1..MAX] d’Entier ; n : Naturel ; element : Entier) : Natu-
rel
Déclaration i, nb : Naturel
debut
nb ← 0
pour i ←1 à n faire
si t[i] = element alors
nb ← nb + 1
finsi
finpour
retourner nb
fin

18
Ici, il n’est pas nécessaire d’introduire des préconditions sur la valeur de n. La sémantique de la
fonction s’accorde très bien d’un tableau vide. La boucle sur n ne sera pas effectuée si le tableau
est vide et le retour sera cohérent puisqu’égal à 0.

6.4 Élément le plus fréquent d’un tableau

Soit un tableau d’entiers t non trié de n éléments significatifs. Écrire une procédure, determi-
nerElementPlusFrequent, qui calcule l’élément qui apparaı̂t le plus souvent dans le tableau t, ainsi
que son nombre d’occurrences. Si plusieurs éléments différents répondent au problème, votre al-
gorithme doit en fournir un, quel qu’il soit. Vous ne devez utiliser aucun autre tableau que celui
sur lequel vous travaillez.

Solution proposée :
procédure determinerElementPlusFrequent (E t : Tableau[1..MAX] d’Entier ; n : Naturel ;S ele-
ment : Entier ; nombre : Naturel)
bprécondition(s) n ≥ 1 et n≤MAX
Déclaration i, compteur : Naturel
debut
nombre ← 0
pour i ←1 à n faire
compteur ← nbOccurences(t,n,t[i])
si compteur > nombre alors
nombre ← compteur
element ← t[i]
finsi
finpour
fin
En étudiant cet algorithme, l’initialisation du paramètre de sortie ”element” n’est faite que dans
une alternative. Il faut donc garantir qu’effectivement cette branche de l’alternative sera parcourue
au moins une fois. La précondition (n ≥ 1) garantit que l’itérative sera effectuée au moins une fois.
L’initialisation à 0 de nombre garantit que le test compteur (qui vaut par définition au minimum 1
la première fois) sera forcément supérieur à nombre. La branche ”alors” sera donc parcourue au
moins une fois dans cet algorithme. Le paramètre ”element” sera donc initialisé au moins une fois.
Cet algorithme peut être améliorer en partant de la fin du tableau, en faisant une boucle
indéterministe et en jouant sur le paramètre n de la fonction nbOccurrences.

6.5 Recherche dichotomique

Écrire une fonction, rechercheDichotomique, qui détermine par dichotomie le plus petit indice
d’un élément, (dont on est sûr de l’existence) dans un tableau d’entiers t trié dans l’ordre croissant
de n éléments significatifs. Il peut y avoir des doubles (ou plus) dans le tableau.

Solution proposée :
fonction rechercheDichotomique (t : Tableau[1..MAX] d’Entier ; n : Naturel ; element : Entier)
: Naturel
bprécondition(s) estPresent(t,n,element)
Déclaration g,d,m : Naturel

19
debut
g←1
d←n
tant que g 6= d faire
m ← (g + d) div 2
si t[m] > element alors
d ← m-1
sinon
si t[m] = element alors
d←m
sinon
g←m+1
finsi
finsi
fintantque
retourner g
fin

6.6 Tris
6.6.1 Tri par insertion
Nous avons vu en cours que l’algorithme du tri par insertion est :
procédure triParInsertion (E/S t :Tableau[1..MAX] d’Entier,E nb :Naturel)
Déclaration i,j : Naturel
temp : Entier
debut
pour i ←2 à nb faire
j ← obtenirIndiceDInsertion(t,i,t[i])
temp ← t[i]
decaler(t,j,i)
t[j] ← temp
finpour
fin
Donnez l’algorithme de la fonction obtenirIndiceDInsertion tout d’abord de manière séquentielle,
puis de manière dichotomique. Démontrez que la complexité de ce dernier est-il en O(log2 (n)).

Solution proposée :
— Version séquentielle
fonction obtenirIndiceDInsertion (t : Tableau[1..MAX] d’Entier ; rang : Naturel ; entie-
rAInserer : Entier) : Naturel
bprécondition(s) rang > 1 et rang≤MAX
Déclaration i : Naturel
debut
i←1
tant que t[i]≤entierAInserer et i<rang faire
i ← i+1
fintantque

20
 retourner i
fin
— Version dichotomique
fonction obtenirIndiceDInsertion (t : Tableau[1..MAX] d’Entier ; rang : Naturel ; entie-
rAInserer : Entier) : Naturel
bprécondition(s) rang > 1 et rang≤MAX
Déclaration g, d, m : Naturel
debut
g←1
d ← rang
tant que g 6= d faire
m ← (g+d) div 2
si t[m] > entierAInserer alors
d ← m // l’intervalle g..m contient alors l’indice recherché
sinon
g ← m+1
finsi
fintantque
retourner g
fin

6.6.2 Tri shaker

La tri shaker est une amélioration du tri à bulles où les itérations permettant de savoir si le
tableau et trié (et qui inverse deux éléments successifs t[i] et t[i + 1] lorsque t[i] > t[i + 1]) se font
successivement de gauche à droite puis de droite à gauche.
Donnez l’algorithme du tri shaker.

Solution proposée :
procédure triShaker (E/S t :Tableau[1..MAX] d’Entier,E nb :Naturel)
Déclaration estTrie : Booleen
i,j : Naturel
sens : Entier
debut
sens ← 1
j←1
repeter
estTrie ← VRAI
pour i ←1 à n-1 faire
si t[j]>t[j+1] alors
echanger(t[j],t[j+1])
estTrie ← FAUX
finsi
j ← j+sens
finpour
sens ← -sens
j ← j+sens
jusqu’a ce que estTrie

21
fin

7 TP Pascal : Matrice
Soit l’unité Matrice qui propose un type TMatrice et cinq sous-programmes qui permettent
de manipuler des variables de type TMatrice :
function matriceZero(hauteur,largeur : Integer) : TMatrice permet d’obtenir une matrice com-
posée de 0
function largeur(m : TMatrice) : Integer permet d’obtenir la largeur d’une matrice
function hauteur(m : TMatrice) : Integer permet d’obtenir la hauteur d’une matrice
function obtenir(m : TMatrice ; jHauteur, iLargeur : Integer) : Real ; permet d’obtenir un élément
d’une matrice
procedure fixer(var m : TMatrice ; jHauteur, iLargeur : Integer ; val : Real) ; qui permet de
fixer la valeur d’un des éléments de la matrice
L’objectif de ce TP est développer une unité libMatrice, qui permettra :
— de transformer une matrice en chaı̂ne de caractères (fonction matriceEnChaine) ;
— d’additionner deux matrices (fonction additionnerDeuxMatrices) ;
— de multiplier deux matrices (fonction multiplierDeuxMatrices) ;
— de calculer la transposer d’une matrice (fonction transposer).
Pour les fonctions d’addition et de multiplication, les erreurs sont gérées via une variable
globale erreur de type TErreur. Cette variable possédera la valeur pas d erreur lorsque
tout va bien et la valeur erreur taille lorsque la taille des matrices utilisées pour ces deux
fonctions sont incompatibles. Dans ce dernier ces fonctions retourneront la valeur (0).
Le fichier TP-Matrices-Sources.zip disponible sur moodle, contient :
— l’unité Matrice.pas,
— l’unité libMatrice.pas,
— l’exécutable test.pas.
Complétez l’unité libMatrice.pas et utilisez le programme test.pas pour tester votre
code. Voici un exemple d’exécution du programme test.
$ ./test
m1=
1.00 4.00
2.00 5.00
3.00 6.00

m2=
2.00 5.00
3.00 6.00
4.00 7.00

m3=
3.00 5.00 7.00
4.00 6.00 8.00

m1 + m2 =
3.00 9.00
5.00 11.00
7.00 13.00

m1 * m3 =
19.00 29.00 39.00

22
 26.00 40.00 54.00
33.00 51.00 69.00

transpose de m1 =
1.00 2.00 3.00
4.00 5.00 6.00

Solution proposée :
1 u n i t libMatrice;
2
3 interface
4
5 u s e s Matrice;
6
7 t y p e TErreur = (pas_d_erreur, erreur_taille);
8
9 var erreur : TErreur;
10
11 function matriceEnChaine(m : TMatrice) : String;
12 function additionnerDeuxMatrices(m1,m2 : TMatrice) : TMatrice;
13 function multiplierDeuxMatrices(m1,m2 : TMatrice) : TMatrice;
14 function transposer(m : TMatrice) : TMatrice;
15
16 implementation
17
18 f u n c t i o n plusGdChaine(m : TMatrice) : I n t e g e r ;
19 var
20 i,j : I n t e g e r ;
21 s : String;
22 begin
23 plusGdChaine:=0;
24 f o r j:=1 t o hauteur(m) do
25 begin
26 f o r i:=1 t o largeur(m) do
27 begin
28 str(obtenir(m,j,i):0:2,s);
29 i f length(s)>plusGdChaine t h e n
30 plusGdChaine:=length(s);
31 end;
32 end
33 end; { plusGdChaine }
34
35
36 f u n c t i o n matriceEnChaine(m : TMatrice) : String;
37 var
38 i,j : Integer;
39 s : String;
40 nbChiffres : I n t e g e r ;
41 begin
42 erreur := pas_d_erreur;
43 matriceEnChaine:=’’;
44 nbChiffres:=plusGdChaine(m);
45 f o r j:=1 t o hauteur(m) do
46 begin
47 f o r i:=1 t o largeur(m) do
48 begin
49 str(obtenir(m,j,i):nbChiffres:2,s);
50 matriceEnChaine:=matriceEnChaine+s+’ ’;
51 end;
52 matriceEnChaine:=matriceEnChaine+#10;
53 end
54 end;
55
56 f u n c t i o n additionnerDeuxMatrices(m1,m2 : TMatrice) : TMatrice;
57 var
58 i,j : I n t e g e r ;
59 begin

23
 60 i f (largeur(m1)<>largeur(m2)) or (hauteur(m1)<>hauteur(m2)) t h e n
61 begin
62 erreur := erreur_taille;
63 additionnerDeuxMatrices:=matriceZero(1,1);
64 end
65 else
66 begin
67 erreur := pas_d_erreur;
68 additionnerDeuxMatrices:=matriceZero(largeur(m1),hauteur(m1));
69 f o r i:=1 t o largeur(m1) do
70 f o r j:=1 t o hauteur(m1) do
71 fixer(additionnerDeuxMatrices,j,i,obtenir(m1,j,i)+obtenir(m2,j,i));
72 end
73 end;
74
75 f u n c t i o n multiplierDeuxMatrices(m1,m2 : TMatrice) : TMatrice;
76 var
77 i,j,k : I n t e g e r ;
78 begin
79 i f (largeur(m1)<>hauteur(m2)) or (hauteur(m1)<>largeur(m2)) t h e n
80 begin
81 erreur := erreur_taille;
82 multiplierDeuxMatrices:=matriceZero(1,1);
83 end
84 else
85 begin
86 erreur := pas_d_erreur;
87 multiplierDeuxMatrices:=matriceZero(hauteur(m1),largeur(m2));
88 f o r j:=1 t o hauteur(m1) do
89 f o r i:=1 t o largeur(m2) do
90 f o r k:=1 t o largeur(m1) do
91 fixer(multiplierDeuxMatrices,j,i,obtenir(multiplierDeuxMatrices,j,i)+
92 obtenir(m1,j,k)*obtenir(m2,k,i));
93 end
94 end;
95
96 f u n c t i o n transposer(m : TMatrice) : TMatrice;
97 var i,j : I n t e g e r ;
98 begin
99 transposer := matriceZero(hauteur(m),largeur(m));
100 f o r i:=1 t o largeur(m) do
101 f o r j:=1 t o hauteur(m) do
102 fixer(transposer,i,j,obtenir(m,j,i))
103 end;
104
105 begin
106 erreur := pas_d_erreur;
107 end.

8 Récursivité
8.1 Calcul de C(n,p)
Écrire une fonction cnp, qui en fonction des entiers positifs n et p, retourne le nombre de
combinaisons de p éléments parmi n.

Solution proposée :
Pour rappel : (
1 si p = 0 ou n = p
Cpn = n−1
Cpn−1 + Cp−1
fonction cnp (n,p : naturel) : NaturelNonNul
bprécondition(s) n≥p

24
debut
si p=0 ou n=p alors
retourner 1
sinon
retourner cnp(n-1,p)+cnp(n-1,p-1)
finsi
fin

8.2 Multiplication égyptienne

Soit la multiplication égyptienne définie dans l’exercice 2.4. On se propose cette fois d’écrire
cet algorithme de manière récursive.
1. Déterminer le ou les cas d’arrêt (particuliers). Déterminer le ou les cas généraux.
2. Donner le corps de la fonction suivante en utilisant un algorithme récursif :
fonction multiplicationEgyptienne (a,b : Naturel) : Naturel

Solution proposée :
— Cas particuliers :
— Si b=0 ou a=0 alors a ∗ b = 0
— Si b = 1 alors a ∗ b = a
— Cas général, Si b > 1
— Si b est paire alors a ∗ b = 2a ∗ b/2
— Si b est impaire alors a ∗ b = a + a ∗ (b − 1)
fonction multiplicationEgyptienne (a,b :Naturel) : Naturel
debut
si a=0 ou b=0 alors
retourner 0
sinon
si b=1 alors
retourner a
sinon
si b mod 2=0 alors
retourner multiplicationEgyptienne(2*a,b div 2)
sinon
retourner a+multiplicationEgyptienne(a,b-1)
finsi
finsi
finsi
fin

8.3 Des cercles

Supposons que la procédure suivante permette de dessiner un cercle sur un graphique (variable
de type Graphique) :
— procédure cercle (E/S g : Graphique,E xCentre,yCentre,rayon : Reel)

25
8.3.1 Compréhension
Soit l’algorithme suivant 3 :
procédure cercles (E/S g : Graphique,E x,y,r : Reel, n : Naturel)
Déclaration rTemp : Reel
debut
si n>0 alors
rTemp ← r/(1+racineCarree(2))
cercles(g,x,y+rTemp*racineCarree(2),rTemp,n-1)
cercles(g,x,y-rTemp*racineCarree(2),rTemp,n-1)
cercle(g,x,y,r)
cercles(g,x+rTemp*racineCarree(2),y,rTemp,n-1)
cercles(g,x-rTemp*racineCarree(2),y,rTemp,n-1)
finsi
fin
L’instruction cercles(g,1.0,1.0,1.0,3) permet d’obtenir le graphique de la figure 2.
Numérotez les cercles (numéro à mettre au centre du cercle) suivant leur ordre d’apparition
sur le graphique.

F IGURE 2 – Résultat d’un autre algorithme pour cercles

Solution proposée :
3. Pour comprendre les formules mathématiques de cet algorithme, il faut considérer le carré définit par les 4 centres
des cercles,
√ de rayon r0 , intérieurs au cercle courant,√
de rayon r. Son côté est de 2r0 . Les centres sont donc a une distance
de r 2 du centre du cercle courant et donc r = r 2 + r0
0 0

26
8.3.2 Construction
Proposez un autre algorithme de la procédure cercles qui, pour la même instruction cercles(g,1.0,
1.0,1.0,3), affiche les cercles dans l’ordre proposé par la figure 3.

F IGURE 3 – Résultat d’un autre algorithme pour cercles

Solution proposée :
procédure cercles (E/S g : Graphique,E x,y,r : Reel, n : Naturel)

27
 Déclaration rTemp : Reel
debut
si n>0 alors
rTemp ← r/(1+racineCarree(2))
cercles(g,x+rTemp*racineCarree(2),y,rTemp,n-1)
cercle(g,x,y,r)
cercles(g,x-rTemp*racineCarree(2),y,rTemp,n-1)
cercles(g,x,y-rTemp*racineCarree(2),rTemp,n-1)
cercles(g,x,y+rTemp*racineCarree(2),rTemp,n-1)
finsi
fin

8.4 Recherche d’un élément dans un tableau

Écrire une fonction récursive, estPresent, qui retourne VRAI si un élément donné est un des
éléments d’un tableau d’entiers t et FAUX sinon. Etudier les cas où t n’est pas un tableau trié et
où t est un tableau trié.

Solution proposée :
— Si le tableau n’est pas trié :
fonction estPresent (t : Tableau[1..MAX] d’Entier ; element : Entier ; debut, fin : Natu-
relNonNul) : Booleen
bprécondition(s) debut≤MAX et fin≤MAX
debut
si debut > fin alors
retourner FAUX
sinon
si element = t[fin] alors
retourner VRAI
sinon
retourner estPresent(t, element, debut, fin-1)
finsi
finsi
fin
— Si le tableau est trié :
fonction estPresent (t : Tableau[1..MAX] d’Entier ; element : Entier ; debut,fin : Naturel-
NonNul) : Booleen
bprécondition(s) debut≤MAX et fin≤MAX
Déclaration m : NaturelNonNul
debut
si debut > fin alors
retourner FAUX
sinon
m ← (debut + fin) div 2
si element = t[m] alors
retourner VRAI
sinon
si t[m] > element alors

28
 retourner estPresent(t, element, debut, m - 1)
sinon
retourner estPresent(t, element, m + 1, fin)
finsi
finsi
finsi
fin
Appel initial : estPresent (t, 10, 1, MAX) pour tout le tableau et recherche de l’élément 10.

9 TP Pascal : Benchmark de tri

L’objectif de ce TP est d’implanter et de comparer les performances des tris suivants :
— tri par sélection ;
— tri par insertions avec recherche d’insertion séquentielle ;
— tri par insertions avec recherche d’insertion dichotomique ;

9.1 Résultats attendus

Deux programmes sont utilisés dans ce TP : testTri et benchmark.

9.1.1 testTri
Le programme testTri a pour objectif de vérifier le bon fonctionnement des tris. Voici un
exemple de résultats attendus à son exécution :
Verification des tris :
Nb elements :10
Tableau a trier : 5 5 7 8 6 8 5 8 4 6
Resultat Tri par selection : 4 5 5 5 6 6 7 8 8 8
Resultat Tri par insertion (recherche d’insertion sequentielle) : 4 5 5 5 6 6 7 8 8 8
Resultat Tri par insertion (recherche d’insertion dichotomique) : 4 5 5 5 6 6 7 8 8 8

9.1.2 benchmark
Le programme benchmark a pour objectif de comparer les performances des tris. Voici un
exemple de résultats attendus à son exécution (les XX représentent des temps) :
Nb elements :10000
Tri par selection : XX ms
Tri par insertion (recherche d’insertion sequentielle) : XX ms
Tri par insertion (recherche d’insertion dichotomique) : XX ms

9.2 Travail à réaliser

Comme les tris sont utilisés par deux programmes, nous les avons répartis dans des unités
pascal (une unité par tri).
De même le type TEntiers représentant un tableau d’entiers (avec des sous-programmes
permettant d’en remplir aléatoirement un, d’en afficher un, ou encore de demander à l’utilisateur
combien d’entiers il faut utiliser) est utilisé dans toutes les unités et les deux programmes, il est
donc déclaré dans une unité.
Les programmes donnés compilent et s’exécutent, mais ne donnent pas les bons résultats. Pour
réaliser ce TP, suivez les étapes suivantes :

29
 1. Téléchargez et décompressez l’archive TP-Tris1-Sources.zip disponible sur moo-
dle.
2. Complétez l’unité triselection et compilez les deux programmes.
3. Complétez l’unité triinsertionsequentiel et compilez les deux programmes.
4. Complétez l’unité triinsertiondichotomique et compilez les deux programmes.
Comparez les valeurs obtenues avec 1000, 10000, 20000 et 30000 éléments à trier.

Solution proposée :
1 u n i t triselection;
2
3 interface
4
5 u s e s entiers;
6
7 p r o c e d u r e trier(var t : TEntiers; nbEntiers : I n t e g e r );
8
9 implementation
10
11 u s e s echanger;
12
13 f u n c t i o n indiceDuMinimum(t : TEntiers; debut,fin : I n t e g e r ) : I n t e g e r ;
14 var
15 i : Integer;
16 begin
17 indiceDuMinimum:=debut;
18 f o r i:=debut+1 t o fin do
19 i f t[i]<t[indiceDuMinimum] t h e n
20 indiceDuMinimum:=i
21 end; { indiceDuMinimum }
22
23 p r o c e d u r e trier(var t : TEntiers; nbEntiers : I n t e g e r );
24 var
25 i,j : I n t e g e r ;
26 begin
27 f o r i:=1 t o nbEntiers-1 do
28 begin
29 j:=indiceDuMinimum(t,i,nbEntiers);
30 echangerEntiers(t[i],t[j])
31 end
32 end; { trier }
33
34
35 end.

1 u n i t triinsertionsequentiel;
2
3 interface
4
5 u s e s entiers;
6
7 p r o c e d u r e trier(var t : TEntiers; nb : I n t e g e r );
8
9 implementation
10
11 u s e s echanger;
12
13 f u n c t i o n obtenirIndiceDInsertion(t : TEntiers; borneSup, lEntier : I n t e g e r ) : I n t e g e r ;
14 begin
15 obtenirIndiceDInsertion:=1;
16 w h i l e t[obtenirIndiceDInsertion]<lEntier do
17 obtenirIndiceDInsertion:=obtenirIndiceDInsertion+1
18 end; { obtenirIndiceDInsertion }
19
20 p r o c e d u r e decaler(var t : TEntiers; borneInf,borneSup : I n t e g e r );
21 var i : I n t e g e r ;

30
22 begin
23 f o r i:=borneSup downto borneInf+1 do
24 t[i]:=t[i-1]
25 end; { decaler }
26
27 p r o c e d u r e trier(var t : TEntiers; nb : I n t e g e r );
28 var i,j,temp : I n t e g e r ;
29 begin
30 f o r i:=2 t o nb do
31 begin
32 j:=obtenirIndiceDInsertion(t,i,t[i]);
33 temp:=t[i];
34 decaler(t,j,i);
35 t[j]:=temp
36 end
37 end; { trier }
38
39 end.

1 u n i t triinsertiondichotomique;
2
3 interface
4
5 u s e s entiers;
6
7 p r o c e d u r e trier(var t : TEntiers; nb : I n t e g e r );
8
9 implementation
10
11 u s e s echanger;
12
13 f u n c t i o n obtenirIndiceDInsertion(t : TEntiers; borneSup, lEntier : I n t e g e r ) : I n t e g e r ;
14 var
15 debut,fin,m : I n t e g e r ;
16 begin
17 debut:=1;
18 fin:=borneSup;
19 w h i l e debut<>fin do
20 begin
21 m:=(debut+fin) d i v 2;
22 i f t[m]<=lEntier t h e n
23 debut:=m+1
24 else
25 fin:=m
26 end;
27 obtenirIndiceDInsertion:=debut;
28 end; { obtenirIndiceDInsertion }
29
30 p r o c e d u r e decaler(var t : TEntiers; borneInf,borneSup : I n t e g e r );
31 var i : I n t e g e r ;
32 begin
33 f o r i:=borneSup downto borneInf+1 do
34 t[i]:=t[i-1]
35 end; { decaler }
36
37 p r o c e d u r e trier(var t : TEntiers; nb : I n t e g e r );
38 var i,j,temp : I n t e g e r ;
39 begin
40 f o r i:=2 t o nb do
41 begin
42 j:=obtenirIndiceDInsertion(t,i,t[i]);
43 temp:=t[i];
44 decaler(t,j,i);
45 t[j]:=temp
46 end
47 end; { trier }
48
49 end.

31
10 TP Pascal : Benchmark de tri (suite)
L’objectif de ce TP est de compléter le TP précédent, en implantant et comparant les perfor-
mances des tris suivants :
— tri à bulles
— tri par sélection ;
— tri par insertions avec recherche d’insertion séquentielle ;
— tri par insertions avec recherche d’insertion dichotomique ;
— tri rapide
— tri par fusion

10.1 Résultats attendus

Deux programmes sont utilisés dans ce TP : testTri et benchmark.

10.1.1 testTri
Le programme testTri a pour objectif de vérifier le bon fonctionnement des tris. Voici un
exemple de résultats attendus à son exécution :
Verification des tris :
Nb elements :10
Tableau a trier : 5 5 7 8 6 8 5 8 4 6
Resultat Tri rapide : 4 5 5 5 6 6 7 8 8 8
Resultat Tri par fusion : 4 5 5 5 6 6 7 8 8 8
Resultat Tri par selection : 4 5 5 5 6 6 7 8 8 8
Resultat Tri par insertion (recherche d’insertion sequentielle) : 4 5 5 5 6 6 7 8 8 8
Resultat Tri par insertion (recherche d’insertion dichotomique) : 4 5 5 5 6 6 7 8 8 8
Resultat Tri a bulles : 4 5 5 5 6 6 7 8 8 8

10.1.2 benchmark
Le programme benchmark a pour objectif de comparer les performances des tris. Voici un
exemple de résultats attendus à son exécution (les XX représentent des temps) :
Nb elements :10000
Tri rapide : XX ms
Tri par fusion : XX ms
Tri par selection : XX ms
Tri par insertion (recherche d’insertion sequentielle) : XX ms
Tri par insertion (recherche d’insertion dichotomique) : XX ms
Tri a bulles : XX ms

10.2 Travail à réaliser

Les programmes donnés compilent et s’exécutent, mais ne donnent pas les bons résultats. Pour
réaliser ce TP, suivez les étapes suivantes :
1. Téléchargez et décompressez l’archive TP-Tris2-Sources.zip disponible sur moo-
dle.
2. Remplacez les unités triselection, triinsertionsequentiel et
triinsertiondichotomoqie par celles que vous avez développées au dernier TP.
3. Complétez l’unité trirapide et compilez les deux programmes.
4. Complétez l’unité trifusion et compilez les deux programmes.

32
 Comparez les valeurs obtenues avec 1000, 10000, 20000 et 30000 éléments à trier.

Solution proposée :
1 u n i t trirapide;
2
3 interface
4
5 u s e s entiers;
6
7 p r o c e d u r e trier(var t : TEntiers; nb : I n t e g e r );
8
9 implementation
10
11 u s e s echanger;
12
13 p r o c e d u r e partitionner(var t : TEntiers; d,f : I n t e g e r ; var iP : I n t e g e r );
14 var i,j : I n t e g e r ;
15 begin
16 i:=d+1;
17 j:=f;
18 w h i l e i<=j do
19 i f t[i]<=t[d] t h e n
20 i:=i+1
21 else
22 i f t[j]>t[d] t h e n
23 j:=j-1
24 else
25 echangerEntiers(t[i],t[j]);
26 iP:=j;
27 echangerEntiers(t[d],t[iP])
28 end; { partitionner }
29
30 p r o c e d u r e triRapideRecursif(var t : TEntiers; d,f : I n t e g e r );
31 var iP : I n t e g e r ;
32 begin
33 i f d<f t h e n
34 begin
35 partitionner(t,d,f,iP);
36 triRapideRecursif(t,d,iP-1);
37 triRapideRecursif(t,iP+1,f);
38 end
39 end; { triRapideRecursif }
40
41
42 p r o c e d u r e trier(var t : TEntiers; nb : I n t e g e r );
43 begin
44 triRapideRecursif(t,1,nb)
45 end; { trirapide }
46
47 end.

1 u n i t trifusion;
2
3 interface
4
5 u s e s entiers;
6
7 p r o c e d u r e trier(var t : TEntiers; nb : I n t e g e r );
8
9 implementation
10
11 u s e s echanger;
12
13 p r o c e d u r e fusionner(var t : TEntiers; debut,milieu,fin : I n t e g e r );
14 var
15 i,j,k : I n t e g e r ;
16 temp : TEntiers;
17 begin
18 i:=debut;

33
19 j:=milieu+1;
20 f o r k:=1 t o fin-debut+1 do
21 i f (i<=milieu) and (j<=fin) t h e n
22 begin
23 i f t[i]<=t[j] t h e n
24 begin
25 temp[k]:=t[i];
26 inc(i)
27 end e l s e
28 begin
29 temp[k]:=t[j];
30 inc(j)
31 end
32 end e l s e
33 begin
34 i f i<=milieu t h e n
35 begin
36 temp[k]:=t[i];
37 inc(i)
38 end e l s e
39 begin
40 temp[k]:=t[j];
41 inc(j)
42 end
43 end;
44 f o r k:=1 t o fin-debut+1 do
45 t[debut+k-1]:=temp[k];
46 end; { fusionner }
47
48 p r o c e d u r e trierRecursif(var t : TEntiers; d,f : I n t e g e r );
49 begin
50 i f d<f t h e n
51 begin
52 trierRecursif(t,d,(d+f) d i v 2);
53 trierRecursif(t,((d+f) d i v 2)+1,f);
54 fusionner(t,d,(d+f) d i v 2,f)
55 end
56 end; { triRapideRecursif }
57
58
59 p r o c e d u r e trier(var t : TEntiers; nb : I n t e g e r );
60 begin
61 trierRecursif(t,1,nb)
62 end; { trirapide }
63
64 end.

11 Liste chaı̂née
Pour rappel, le type ListeChaineeDEntiers est défini de la façon suivante :
Type ListeChaineeDEntiers = ˆ NoeudDEntier
Type NoeudDEntier = Structure
entier : Entier
listeSuivante : ListeChaineeDEntiers
finstructure
Et nous l’utilisons à l’aide des fonctions et procédures suivantes :
— fonction listeVide () : ListeChaineeDEntiers
— fonction estVide (uneListe : ListeChaineeDEntiers) : Booleen
— procédure ajouter (E/S uneListe : ListeChaineeDEntiers,E element : Entier)
— fonction obtenirEntier (uneListe : ListeChaineeDEntiers) : Entier
bprécondition(s) non(estVide(uneListe))

34
 — fonction obtenirListeSuivante (uneListe : ListeChaineeDEntiers) : ListeChaineeDEntiers
bprécondition(s) non(estVide(uneListe))
— procédure fixerListeSuivante (E/S uneListe : ListeChaineeDEntiers,E nelleSuite : Liste-
ChaineeDEntiers)
bprécondition(s) non(estVide(uneListe))
— procédure supprimerTete (E/S l :ListeChaineeDEntiers)
bprécondition(s) non estVide(l)
— procédure supprimer (E/S uneListe : ListeChaineeDEntiers)
1. Écrire une procédure itérative, afficher, qui permet d’afficher les éléments d’une liste chaı̂née.
2. Écrire une procédure récursive, afficher, qui permet d’afficher les éléments d’une liste chaı̂née.
3. Écrire une fonction booléenne récursive, estPresent, qui permet de savoir si un entier est
présent dans une liste chaı̂née.
4. Écrire une procédure récursive, concatener, qui concatène deux listes chaı̂nées.
5. Écrire une procédure itérative, inverser, qui permet d’inverser une liste chaı̂née.
6. Écrire une procédure récursive, inverser, qui permet d’inverser une liste chaı̂née.

Solution proposée :
1. Afficher itératif
procédure afficher (E l :ListeChaineeDEntiers)
debut
tant que non est Vide(l) faire
ecrire(obtenirEntier(l))
l ← obtenirListeSuivante(l)
fintantque
fin
2. Afficher récursif
procédure afficher (E l :ListeChaineeDEntiers)
debut
si non est Vide(l) alors
ecrire(obtenirEntier(l))
afficher(obtenirListeSuivante(l))
finsi
fin
3. est présent récursif
fonction estPresent (liste : ListeChaineeDEntiers ; cherche : Entier) : Booleen
debut
si estVide(liste) alors
retourner FAUX
sinon
si obtenirEntier(liste) = cherche alors
retourner VRAI
sinon
retourner estPresent(obtenirListeSuivante(liste),cherche)
finsi

35
 finsi
fin
4. concaténation
procédure concatener (E/S l1 : ListeChaineeDEntiers,E l2 : ListeChaineeDEntiers)
Déclaration temp : ListeChaineeDEntiers
debut
si estVide(l1) alors
l1 ← l2
sinon
si non estVide(l2) alors
temp ← obtenirListeSuivante(l1)
concatener(temp,l2)
fixerListeSuivante(l1, temp)
finsi
finsi
fin
5. inverser (itératif)
procédure inverser (E/S l : ListeChaineeDEntiers)
Déclaration resultat, temp : ListeChaineeDEntiers
debut
resultat ← listeVide
tant que non estVide(l) faire
temp ← obtenirListeSuivante(l)
fixerListeSuivante(l,resultat)
resultat ← l
l ← temp
fintantque
l ← resultat
fin
6. inverser (récursif)
procédure inverser (E/S l : ListeChaineeDEntiers)
Déclaration temp : ListeChaineeDEntiers
debut
si non estVide(l) alors
temp ← obtenirListeSuivante(l)
inverser(temp)
fixerListeSuivante(l,listeChainee())
concatener(temp,l)
finsi
fin

12 TP Pascal : Liste chaı̂née

L’objectif de ce TP est de développer une librairie (unité LibListeChaineeDEntiers)
sur une liste chaı̂née d’entiers (unité ListeChaineeDEntiers). Cette librairie permettra de :
— savoir si deux listes chaı̂nées sont égales ;

36
 — copier une liste chaı̂née d’entiers ;
— savoir si un entier est présent dans une liste chaı̂née d’entiers ;
— savoir les entiers d’une liste sont présents en ordre croissant ;
— concatener deux liste chaı̂nées d’entiers.
Afin de vérifier que la librairie fonctionne, un programme de tests unitaires est proposé (pro-
gramme testLibListeChaineeDEntiers).

12.1 Résultats attendus

L’exécution du programme de tests unitaires devra valider tous les tests :
$ ./testLibListeChaineDEntiers
Tests unitaires de la librairie LibListeChaineeDEntiers
sontEgales(l,l) : OK
sontEgales(l1,l2) (avec l1 et l2 qui possedent les meme elements) : OK
sontEgales(l1,l2) (avec l1 et l2 qui ne possedent pas les meme elements) : OK
copier(l) : OK
estPresent(l,e) (avec e qui est reellement present au debut): OK
estPresent(l,e) (avec e qui est reellement present a la fin): OK
estPresent(l,e) (avec e qui est reellement present, cas general): OK
estPresent(l,e) (avec e qui n’est pas present): OK
estEnOrdreCroissant(l) (avec la liste (1 2 3)): OK
estEnOrdreCroissant(l) (avec la liste (1 2 3 2 1)): OK
concatener(l1,l2) : OK

12.2 Travail à réaliser

1. Téléchargez et décompressez l’archive TP-Liste-Sources.zip disponible sur moo-
dle.
2. Complétez l’unité LibListeChaineeDEntiers. À chaque fois que vous avez codé une
fonction et que la compilation de l’unité réussie, recompilez et lancez le programme de tests
unitaires.

Solution proposée :
1 u n i t LibLIsteChaineeDEntiers;
2
3 interface
4
5 u s e s ListeChaineeDEntiers;
6
7 f u n c t i o n sontEgales(l1,l2 : TListeChaineeDEntiers) : Boolean;
8 f u n c t i o n copier(l : TListeChaineeDEntiers) : TListeChaineeDEntiers;
9 f u n c t i o n estPresent(l : TListeChaineeDEntiers; e : I n t e g e r ) : Boolean;
10 f u n c t i o n estEnOrdreCroissant(l : TListeChaineeDEntiers) : Boolean;
11 p r o c e d u r e concatener(var l1 : TListeChaineeDEntiers; l2 : TListeChaineeDEntiers);
12
13 implementation
14
15 f u n c t i o n sontEgales(l1,l2 : TListeChaineeDEntiers) : Boolean;
16 begin
17 i f estVide(l1) and estVide(l2) t h e n
18 sontEgales:=True
19 else
20 i f obtenirEntier(l1) <> obtenirEntier(l2) t h e n
21 sontEgales := F a l s e
22 else
23 sontEgales := sontEgales(obtenirListeSuivante(l1),obtenirListeSuivante(l2))
24 end;
25
26 f u n c t i o n copier(l : TListeChaineeDEntiers) : TListeChaineeDEntiers;
27 begin
28 i f estVide(l) t h e n

37
29 copier:=listeVide()
30 else
31 begin
32 copier:=copier(obtenirListeSuivante(l));
33 ajouter(copier,obtenirEntier(l))
34 end
35 end;
36
37
38 f u n c t i o n estPresent(l : TListeChaineeDEntiers; e : I n t e g e r ) : Boolean;
39 begin
40 i f estVide(l) t h e n
41 estPresent := F a l s e
42 else
43 i f obtenirEntier(l) = e t h e n
44 estPresent := True
45 else
46 estPresent := estPresent(obtenirListeSuivante(l),e)
47 end;
48
49 f u n c t i o n estEnOrdreCroissant(l : TListeChaineeDEntiers) : Boolean;
50 begin
51 i f estVide(l) t h e n
52 estEnOrdreCroissant := True
53 else
54 i f estVide(obtenirListeSuivante(l)) t h e n
55 estEnOrdreCroissant := True
56 else
57 estEnOrdreCroissant := (obtenirEntier(l) <= obtenirEntier(obtenirListeSuivante(l
))) and estEnOrdreCroissant(obtenirListeSuivante(l))
58 end;
59
60 p r o c e d u r e concatener(var l1 : TListeChaineeDEntiers; l2 : TListeChaineeDEntiers);
61 var
62 temp : TListeChaineeDEntiers;
63 b e g i n
64 i f estVide(l1) t h e n
65 l1:=l2
66 else
67 begin
68 temp:=obtenirListeSuivante(l1);
69 concatener(temp,l2);
70 fixerListeSuivante(l1,temp)
71 end
72 end;
73
74 end.

13 TP Pascal : Tableaux dynamiques

L’objectif de ce TP est de développer une unité pascal qui propose un type TTableauDynamique
DEntiers qui permet d’utiliser une liste chaı̂née d’entiers comme un tableau, à savoir qu’il sera
possible d’accéder aux ième éléments du tableau dynamique. Outre ce type, cette unité proposera
les fonctions et procédures suivantes :
— création (fonction créer) d’un tableau vide (ne contenant aucun entier) ;
— obtention du nombre d’entiers (fonction longueur) ;
— insertion (procédure inserer) d’un entier à une position donnée ;
— ajout (procédure ajouter) d’un entier à la fin du tableau ;
— suppression (procédure supprimer) d’un entier à une position donnée ;
— obtention (fonction iemeEntier) de l’entier à une position donnée ;
— suppression (procédure vider) de tous les éléments du tableau dynamique.

38
 13.1 Résultats attendus
Après vous avoir demandé combien au maximum d’entiers vous vouliez stocker (n), l’exécution
du programme testTableauDynamiqueDEntiers vous affichera un tableau dynamique
suite à :
1. l’ajout de n/2 entiers aléatoires ;
2. l’insertion aléatoire de n/2 entiers aléatoires ;
3. la suppression aléatoire de n/2 entiers ;
4. la suppression de tous les éléments restant.
Voici un exemple d’exécution de ce programme :
$ ./testTableauDynamiqueDEntiers
Combien d’entiers :20
Ajout de 54 : 54
Ajout de 59 : 54 59
Ajout de 71 : 54 59 71
Ajout de 84 : 54 59 71 84
Ajout de 60 : 54 59 71 84 60
Ajout de 85 : 54 59 71 84 60 85
Ajout de 54 : 54 59 71 84 60 85 54
Ajout de 84 : 54 59 71 84 60 85 54 84
Ajout de 42 : 54 59 71 84 60 85 54 84 42
Ajout de 62 : 54 59 71 84 60 85 54 84 42 62
Inserer de 43 a pos=8 : 54 59 71 84 60 85 54 43 84 42 62
Inserer de 5 a pos=8 : 54 59 71 84 60 85 54 5 43 84 42 62
Inserer de 38 a pos=1 : 38 54 59 71 84 60 85 54 5 43 84 42 62
Inserer de 81 a pos=4 : 38 54 59 81 71 84 60 85 54 5 43 84 42 62
Inserer de 56 a pos=6 : 38 54 59 81 71 56 84 60 85 54 5 43 84 42 62
Inserer de 83 a pos=8 : 38 54 59 81 71 56 84 83 60 85 54 5 43 84 42 62
Inserer de 8 a pos=14 : 38 54 59 81 71 56 84 83 60 85 54 5 43 8 84 42 62
Inserer de 36 a pos=9 : 38 54 59 81 71 56 84 83 36 60 85 54 5 43 8 84 42 62
Inserer de 77 a pos=18 : 38 54 59 81 71 56 84 83 36 60 85 54 5 43 8 84 42 77 62
Inserer de 87 a pos=12 : 38 54 59 81 71 56 84 83 36 60 85 87 54 5 43 8 84 42 77 62
Suppression pos=7 : 38 54 59 81 71 56 83 36 60 85 87 54 5 43 8 84 42 77 62
Suppression pos=1 : 54 59 81 71 56 83 36 60 85 87 54 5 43 8 84 42 77 62
Suppression pos=14 : 54 59 81 71 56 83 36 60 85 87 54 5 43 84 42 77 62
Suppression pos=17 : 54 59 81 71 56 83 36 60 85 87 54 5 43 84 42 77
Suppression pos=15 : 54 59 81 71 56 83 36 60 85 87 54 5 43 84 77
Suppression pos=2 : 54 81 71 56 83 36 60 85 87 54 5 43 84 77
Suppression pos=2 : 54 71 56 83 36 60 85 87 54 5 43 84 77
Suppression pos=2 : 54 56 83 36 60 85 87 54 5 43 84 77
Suppression pos=4 : 54 56 83 60 85 87 54 5 43 84 77
Suppression pos=10 : 54 56 83 60 85 87 54 5 43 77
Tableau vide :

13.2 Travail à réaliser

1. Téléchargez et décompressez l’archive TP-TableauDynamique.zip disponible sur
moodle.
2. Complétez le fichier TableauDynamiqueDEntiers.pas.

Solution proposée :
1 u n i t TableauDynamiqueDEntiers;
2
3 interface
4
5 u s e s ListeChaineeDEntiers;
6
7 type
8 TTableauDynamiqueDEntiers = r e c o r d
9 lesEntiers : TListeChaineeDEntiers;

39
10 nbEntiers : Longword;
11 end;
12
13 f u n c t i o n creer() : TTableauDynamiqueDEntiers;
14 f u n c t i o n longueur(t : TTableauDynamiqueDEntiers) : Longword;
15 p r o c e d u r e inserer(var t : TTableauDynamiqueDEntiers; e : I n t e g e r ; pos : Longword);
16 p r o c e d u r e ajouter(var t : TTableauDynamiqueDEntiers; e : I n t e g e r );
17 p r o c e d u r e supprimer(var t : TTableauDynamiqueDEntiers; pos : Longword);
18 f u n c t i o n iemeEntier(t : TTableauDynamiqueDEntiers; pos : Longword) : I n t e g e r ;
19 p r o c e d u r e vider(var t : TTableauDynamiqueDEntiers);
20
21 implementation
22
23 f u n c t i o n creer() : TTableauDynamiqueDEntiers;
24 begin
25 creer.lesEntiers := listeVide();
26 creer.nbEntiers := 0;
27 end;
28
29 f u n c t i o n longueur(t : TTableauDynamiqueDEntiers) : Longword;
30 begin
31 longueur := t.nbEntiers;
32 end;
33
34 p r o c e d u r e inserer(var l : TListeChaineeDEntiers; e : I n t e g e r ; pos : Longword);
35 var
36 temp : TListeChaineeDEntiers;
37 begin
38 i f estVide(l) t h e n
39 ListeChaineeDEntiers.ajouter(l,e)
40 else
41 i f pos <= 0 t h e n
42 ListeChaineeDEntiers.ajouter(l,e)
43 else
44 begin
45 temp := obtenirListeSuivante(l);
46 inserer(temp,e,pos-1);
47 fixerListeSuivante(l,temp)
48 end
49 end;
50
51 p r o c e d u r e inserer(var t : TTableauDynamiqueDEntiers; e : I n t e g e r ; pos : Longword);
52 begin
53 inserer(t.lesEntiers, e, pos-1);
54 t.nbEntiers := t.nbEntiers + 1;
55 end;
56
57 p r o c e d u r e ajouter(var t : TTableauDynamiqueDEntiers; e : I n t e g e r );
58 begin
59 inserer(t,e,t.nbEntiers+1);
60 end;
61
62 p r o c e d u r e supprimer(var l : TListeChaineeDEntiers; pos : Longword);
63 var
64 temp : TListeChaineeDEntiers;
65 begin
66 i f n o t estVide(l) t h e n
67 i f pos=1 t h e n
68 begin
69 temp := l;
70 l := obtenirListeSuivante(l);
71 dispose(temp);
72 end e l s e
73 begin
74 temp := obtenirListeSuivante(l);
75 supprimer(temp,pos-1);
76 fixerListeSuivante(l,temp);
77 end
78 end;
79

40
 80 p r o c e d u r e supprimer(var t : TTableauDynamiqueDEntiers; pos : Longword);
81 begin
82 i f pos <= longueur(t) t h e n
83 begin
84 supprimer(t.lesEntiers,pos);
85 t.nbEntiers := t.nbEntiers-1;
86 end
87 end;
88
89 f u n c t i o n iemeEntier(t : TTableauDynamiqueDEntiers; pos : Longword) : I n t e g e r ;
90 var
91 i : Longword;
92 l : TListeChaineeDEntiers;
93 begin
94 l := t.lesEntiers;
95 i := 1;
96 w h i l e ( n o t estVide(l)) and (pos<>i) do
97 begin
98 l := obtenirListeSuivante(l);
99 inc(i);
100 end;
101 i f n o t estVide(l) t h e n
102 iemeEntier := obtenirEntier(l);
103 end;
104
105 p r o c e d u r e vider(var t : TTableauDynamiqueDEntiers);
106 begin
107 w h i l e t.nbEntiers<>0 do
108 supprimer(t,1);
109 end;
110
111 end.

14 TP Pascal : Fichiers
L’objectif de ce TP est de compléter le mini gestionnaire de contacts vu en cours afin qu’en
plus de l’ajout et de l’affichage d’un contact, le programme puisse :
— supprimer un contact ;
— n’afficher que les contacts correspondant à un nom ;
— que l’affichage des contacts se fasse en ordre croissant sur les noms.
Comme vu en cours, le programme devra séparer l’interface homme machine et la logique
métier. L’interface homme machine sera toujours en mode texte et les actions de l’utilisateur seront
toujours spécifiés dans la ligne de commande. Voici un exemple d’aide qui sera affiché lorsque le
nombre d’arguments ne sera pas valide :
$ ./contactsTxt
contacts nom_fichier : permet d’afficher l’ensemble des contacts
contacts nom_fichier nom : permet d’afficher un contact
contacts nom_fichier nom prenom : permet de supprimer un contact
contacts nom_fichier nom prenom telephone : permet d’ajouter un contact

14.1 Résultats attendus

Voici un exemple d’utilisation du programme une fois qu’il sera terminé :
$ ./contactsTxt insa.fic
$ ./contactsTxt insa.fic "Delestre" "Nicolas" "02 32 95 98 76"
$ ./contactsTxt insa.fic
Nom : Delestre
Prenom : Nicolas
Telephone : 02 32 95 98 76
$ ./contactsTxt insa.fic "Malandain" "Nicolas" "02 32 95 98 83"
$ ./contactsTxt insa.fic
Nom : Delestre

41
 Prenom : Nicolas
Telephone : 02 32 95 98 76
Nom : Malandain
Prenom : Nicolas
Telephone : 02 32 95 98 83
$ ./contactsTxt insa.fic "Delporte" "Julien" ""
$ ./contactsTxt insa.fic
Nom : Delestre
Prenom : Nicolas
Telephone : 02 32 95 98 76
Nom : Delporte
Prenom : Julien
Telephone :
Nom : Malandain
Prenom : Nicolas
Telephone : 02 32 95 98 83
$ ./contactsTxt insa.fic "Malandain"
Nom : Malandain
Prenom : Nicolas
Telephone : 02 32 95 98 83
$ ./contactsTxt insa.fic "Delestre" "Nicolas"
$ ./contactsTxt insa.fic
Nom : Delporte
Prenom : Julien
Telephone :
Nom : Malandain
Prenom : Nicolas
Telephone : 02 32 95 98 83

14.2 Travail à réaliser

1. Téléchargez et décompressez l’archive TP-Contact-Sources.zip disponible sur moo-
dle.
2. Compilez et exécutez le programme de façon à vérifier que l’affichage des contacts et l’ajout
d’un contact fonctionne bien.
3. Complétez la procédure supprimerContact qui permet de supprimer un contact à partir
de son nom et de son prénom. Compilez et testez votre programme pour la suppression d’un
contact.
4. Complétez la procédure parcourirContactsAvecComparaison qui permet de trai-
ter tous les contacts c tels que la fonction comparer retourne 0 si elle est exécutée avec
comme argument ref erence et c. Compilez et testez votre programme pour l’affichage des
contacts d’un certain nom.
5. Modifiez la procédure ajouterContact de façon à ce que l’ajout se fasse dans l’ordre
croissant des noms des contacts. Compilez et testez votre programme avec un nouveau carnet
de contacts.

Solution proposée :
1 u n i t contacts;
2
3 interface
4
5 u s e s sysutils,personne;
6
7 type
8 TTraiterPersonne = p r o c e d u r e (p : TPersonne);
9 TComparerPersonne = f u n c t i o n (p1,p2 : TPersonne) : I n t e g e r ;
10
11 p r o c e d u r e ajouterContact(nomFichier : String; p : TPersonne);
12 p r o c e d u r e parcourirContacts(nomFichier : String; traiter : TTraiterPersonne);
13 p r o c e d u r e parcourirContactsAvecComparaison(nomFichier : String;

42
14 traiter : TTraiterPersonne;
15 comparer : TComparerPersonne;
16 reference : TPersonne);
17 p r o c e d u r e supprimerContact(nomFichier : String; nomPersonne,prenomPersonne : String);
18
19 implementation
20
21 p r o c e d u r e ajouterContact(nomFichier : String; p : TPersonne);
22 var
23 fichier,temp : F i l e o f TPersonne;
24 ficheEcrite : Boolean;
25 pCourant : TPersonne;
26 begin
27 ficheEcrite := F a l s e ;
28 assign(fichier,nomFichier);
29 assign(temp,nomFichier+’.tmp’);
30 i f fileExists(nomFichier) t h e n
31 begin
32 r e s e t (fichier);
33 r e w r i t e (temp);
34 repeat
35 read(fichier,pCourant);
36 i f n o t ficheEcrite and (obtenirNom(pCourant) > obtenirNom(p)) t h e n
37 begin
38 ficheEcrite:=True;
39 w r i t e (temp,p)
40 end;
41 w r i t e (temp,pCourant)
42 u n t i l eof(fichier);
43 i f n o t ficheEcrite t h e n
44 w r i t e (temp,p);
45 close(fichier);
46 close(temp);
47 renameFile(nomFichier,nomFichier+’.bak’);
48 renameFile(nomFichier+’.tmp’,nomFichier);
49 deleteFile(nomFichier+’.bak’)
50 end
51 else
52 begin
53 r e w r i t e (fichier);
54 w r i t e (fichier,p);
55 close(fichier)
56 end
57 end;
58
59 p r o c e d u r e supprimerContact(nomFichier : String; nomPersonne,prenomPersonne : String);
60 var
61 fichier,temp : F i l e o f TPersonne;
62 p : TPersonne;
63 begin
64 assign(fichier,nomFichier);
65 assign(temp,nomFichier+’.tmp’);
66 i f fileExists(nomFichier) t h e n
67 begin
68 r e s e t (fichier);
69 r e w r i t e (temp);
70 w h i l e n o t eof(fichier) do
71 begin
72 read(fichier,p);
73 i f (obtenirNom(p) <> nomPersonne) or (obtenirPrenom(p) <> prenomPersonne) t h e n
74 w r i t e (temp,p)
75 end;
76 close(fichier);
77 close(temp)
78 end;
79 renameFile(nomFichier,nomFichier+’.bak’);
80 renameFile(nomFichier+’.tmp’,nomFichier);
81 deleteFile(nomFichier+’.bak’)
82 end;
83

43
 84 p r o c e d u r e parcourirContacts(nomFichier : String; traiter : TTraiterPersonne);
85 var
86 fichier : F i l e o f TPersonne;
87 p : TPersonne;
88 begin
89 assign(fichier,nomFichier);
90 i f fileExists(nomFichier) t h e n
91 begin
92 r e s e t (fichier);
93 w h i l e n o t eof(fichier) do
94 begin
95 read(fichier,p);
96 traiter(p)
97 end;
98 close(fichier)
99 end
100 end;
101
102 p r o c e d u r e parcourirContactsAvecComparaison(nomFichier : String;
103 traiter : TTraiterPersonne;
104 comparer : TComparerPersonne;
105 reference : TPersonne);
106 var
107 fichier : F i l e o f TPersonne;
108 p : TPersonne;
109 begin
110 assign(fichier,nomFichier);
111 i f fileExists(nomFichier) t h e n
112 begin
113 r e s e t (fichier);
114 w h i l e n o t eof(fichier) do
115 begin
116 read(fichier,p);
117 i f comparer(p,reference)=0 t h e n
118 traiter(p)
119 end;
120 close(fichier)
121 end
122 end;
123
124 end.

44