Chapitre 1 - Introduction aux algorithmes

Chapitre 1 - Introduction aux algorithmes

1. Contexte

Le terme Informatique est un néologisme proposé en 1962 par Philippe Dreyfu 1 s pour

ée comme le support des connaissances

humaines et des communications dans les domaines techniques, économiques et sociaux [3].

2. Notions élémentaires

Informatique
traite de deux
aspects complémentaires :
- les programmes ou logiciels (software) qui décrivent un traitement à réaliser,
- les machines ou le matériel (hardware) qui exécute ce traitement.

Hardware
ments physiques (microprocesseur, mémoire, disques durs, ...)
utilisés pour traiter les informations.

Software

à réaliser par un matériel informatique.

Algorithme
La notion d'algorithme est à la base de toute la programmation informatique [8]. La
n algorithme est une
suite ordonnée instructions qui indique la démarche à suivre pour résoudre un problème
ou effectuer une tâche. Le mot algorithme vient du nom latinisé du mathématicien perse Al-
Khawarizmi, surnommé « le père de l'algèbre » [11].

Informaticien Français
Chapitre 1 - Introduction aux algorithmes

Exemple : Appel téléphonique

a. Ouvrir son téléphone,
b. Chercher/Composer le numéro du destinataire,
c. Appuyer sur le bouton « Appel ».

ouvrir, chercher/composez, appuyer) qui manipulent des données

(t

3. L'algorithmique
3.1. Définition
science des algorithmes.

complexité ou leur efficacité [3].

résoudre à un algorithme qui décrit la démarche de résolution du problème. Par conséquent,
la programmation consiste à traduire un algorithme dans un langage « compréhensible » par
être exécuté automatiquement.

Figure 1. Etapes de développement.

La figure 1 ci-dessus illustre les deux phases nécessaires pour obtenir un code source :
lgorithmique qui implique la recherche un algorithme ;
Phase de programmation qui consiste à t un
un langage de programmation .
Dans la première phase, on doit d
souhaite atteindre, ainsi que prévoir des réponses à tous les cas possibles.
Chapitre 1 - Introduction aux algorithmes

2
Exemple +bx+c =0

1 et x2
0 et b = ,
3.2. Principe général
Le traitement automati consiste à exécuter des instructions (opérations
élémentaires et complexes) sur des donn afin de générer ations
appelées résultats ou données de sortie.

Figure 2. Principe du traitement automatisé.

Exemple :

Donc, on doit :

i. Définir le nombre des matières concernées ainsi que les notes et les coefficients ;
ii. Réaliser les opérations suivantes :
-
- Calculer la somme des résultats des multiplications,
- Diviser la somme obtenue par le total des coefficients,
iii. Afficher le .

Remarque :
L écrit un algorithme, les questions suivantes doivent être considérées :
Quel est le résultat attendu ?
Quelles sont les données nécessaires (informations requises) ?
Comment faire (le traitement à réaliser) ?

4. Caractéristiques des algorithmes

4.1. Structure générale
Un algorithme se compose généralement de deux parties :

Partie déclarative : appelée aussi entête , elle contient généralement les

déclarations (des constantes, des variables, etc.).
Chapitre 1 - Introduction aux algorithmes

: co séquences instructions
faisant appel à des opérations de base à exécuter par

Syntaxe :
Algorithme nom_de_ ;
Partie déclarative (Entête)
< Liste de variables/constantes > ;
Début
< ions > ;
Fin

4.2. Les variables et les constantes

bit. Un bit ne peut avoir que deux

états distincts : 0 ou 1 (vrai ou faux dans la logique). es
données sont manipulées par groupes de 8 bits (octets), ou plus (mots de 16, 32, 64 bits ).
Une case mémoire est donc appelée mot et po une
information et la retrouver dans la mémoire, chaque mot est repéré par une adresse [4].

Dans la programmation, les adresses mémoire sont représentées par des noms. Le
case mais plutôt son nom. Il y a donc deux
façons de voir la mémoire : côté programmeur et côté ordinateur tel
e schéma suivant (figure 3).

Mémoire

Adresses Mots

10000000 6 x

10000001 8 y Variables

10000010 7 moyenne

10000011

Côté ordinateur Côté programmeur

Figure 3. Organisation de la mémoire.

Chapitre 1 - Introduction aux algorithmes

4.2.1. Les variables

Une variable est une case mémoire destiné à contenir des valeurs de type défini au préalable
possède un nom, un type, et un contenu
qui peut être modifié .

Le mot clé est: Var.

4.2.2. Les constantes

sa
valeur reste inchangée tout au long du déroulement (exécution) de .

Le mot clé est: Const.

Les variables et les constantes sont déclarées selon la syntaxe suivante :

Syntaxe :
Var nom_variable : type ;
Const nom_constante = valeur ;

Remarque :

Dans la partie déclarative, les variables et les constantes sont caractérisées essentiellement
par :

Un identificateur : est un nom attribué à la variable ou à la constante, qui peut être

composé de lettres et de chiffres mais sans espaces.
Un type : qui définit la nature et la taille de la variable.
Exemple :
Var x, y : entier;
Const alpha = 0,5 ;
Dans cet exemple, nous avons déclaré :
- Deux variables (x et y) de type entier, ce type est décrit dans la sous-section suivante.
-

4.3. Les types de base

Le type , ainsi que

l el cette variable. Il existe des types
simples prédéfinis tels que : entier, réel, caractère et booléen.
Chapitre 1 - Introduction aux algorithmes

4.3.1. Type entier

type numérique représentant relatifs, tels que: -9, 0, 31,

Les opérations permises sur ce type sont : +, - , *, div (division entière) et mod (modulo ou
reste de la division entière).

Le mot clé est : entier.

Exemple : Var x : entier ;

4.3.2. Type réel

type numérique aussi représent es nombres réels, tels que : 0.25, -

1.33, 2.5 e+10 . Les opérations permises sur ce type sont : +, -, * et /.
Le mot clé est : réel.

Exemple : Var y : réel ;

4.3.3. Type caractère

Ce type représente tous les caractères alphanumériques tels que : a , A , 3 , % ,

Les opérations supportées par ce type sont
Le mot clé est : caractère.

Exemple : Var a : caractère ;

4.3.4. Type booléen

Ce type est utilisé dans la logique pour représenter les deux valeurs : vrai et faux.
Les opérations prises en charge sont : NON, ET, OU.
Le mot clé est : booléen.

Exemple : Var b : booléen ;

4.3.5. Chaîne de caractères

Ce type représente les mots et les phrases tels que "Algorithmique", "Cours", etc. Le mot clé
utilisé est : chaîne

Exemple : Var c : chaîne ;

être représentée comme suit.

Chapitre 1 - Introduction aux algorithmes

Exemple :

Var x, y : entier ;
z, w : réel ;
lettre : caractère ;
nom : chaîne ;
Etat : booléen ;
Const n = 100 ;
arobase = ;
mot = "bonjour" ;

5. Conclusion

te, ainsi que leurs types sont

définis et expliqués à travers des exemples simples. Ceci constitue pour le lecteur un

dans les prochains chapitres.

Chapitre 2 - Les instructions simples

Chapitre 2 - Les instructions simples

1. Introduction

tructions simples notamment : les

riture.

2. L affectation

Cette instruction est élémentaire en algorithmique, elle ssigner une valeur à une
variable selon la syntaxe suivante :

variable expression ;

Une est exécutée comme suit :

- évaluation située à droite , et
- affectation du résultat à la variable située à gauche .

une constante ( c 10 )
une variable ( v x)
une expression arithmétique ( e x+y)
une expression logique ( d a ou b )

Remarque :

Une constante ne figure jamais affectation.

Exemple : Const z = 1 ;
; « Faux »
est substitué (écrasé) par le
nouveau contenu.
Exemple : Var a : entier ;
;
;
Après la deuxième affectation, la valeur de a est devenue 2 (la valeur 1 est écrasée).
Une instruction
Exemple : Var x, y : entier ; z : réel ; a, b : caractère ;
Chapitre 2 - Les instructions simples

Instructions correctes Instructions incorrectes

; ;
x; ;
; ;
; ;
;

termes reliés
par un ou plusieurs opérateurs dont on peut distinguer :

a) Les opérateurs arithmétiques (par ordre de priorité) :

^ ou ** : Puissance
* , / , mod : Multiplication, Division et Modulo
+ , - : Addition et Soustraction
b) Les opérateurs logiques ou booléens :
NON : Non logique (négation)
ET : Et logique (conjonction)
OU : Ou logique (disjonction)
NON ET : négation de conjonction
NON OU : négation de disjonction

c) Les opérateurs de comparaison ou relationnels :

> , >= : supérieur et supérieur ou égal
< , <= : inférieur et inférieur ou égal
(ou < >) : égal et différent

Remarque :
Les expressions logiques peuvent être composées des opérateurs logiques et/ou relationnels.
Par exemple, (A<20) ET (B>=10) est Vrai si A est inférieur à 20 et B est égal ou supérieur
à 10, et faux sinon.

3. L de lecture

Cette instruction est très primordiale dans un algorithme. Elle permet de lire des valeurs en
entrée (input) et les affecter aux variables stockées dans la mémoire. Les valeurs affectées
sont souvent des données introduites tel que le clavier.

Syntaxe :
Lire (var1 );
Chapitre 2 - Les instructions simples

Exemple :
Lire(x) : lit et stocke une valeur donnée dans la case mémoire associée à x.
Lire(x, y) : lit et stocke deux valeurs, la première dans x et la deuxième dans y.
Illustration :

Figure 4. Opération de lecture.

4. criture

Cette instruction est au dans les algorithmes. Elle permet

(output)
(valeur, texte, ) en les affichant par exemple sur un périphérique de sortie tel qu écran.

Syntaxe :
Ecrire (var1, var2, expr1, expr2, );

Remarque :

Dans le cas cette expression qui

-même. Par exemple :

Soient deux variables x et y tel que x=5 et y=7, :

Ecrire (x+y) ;
Affiche en sort addition de x et y (soit 12).
Chapitre 2 - Les instructions simples

Illustration :

Figure 5. ture.

E précédentes :

Algorithme Moyenne_deux_réels
Var x, y, z : réel ;
Début
Ecrire ( r la première valeur ) ;
Lire (x) ;
Ecrire ( Donner la deuxième valeur ) ;
Lire (y) ;
(x + y)/2 ;
Ecrire z) ;
// On peut remplacer les deux dernières instructions par une seule :
Ecrire ; // dans ce cas on a pas besoin de z
Fin
our x et 20 pour y
La moyenne est : 15

5. Conclusion

Dans ce chapitre, nous avons présenté les instructions algorithmiques fondamentales à savoir
ables dans
Chapitre 3 - Les instructions conditionnelles (les alternatives)

Chapitre 3 - Les instructions conditionnelles (les

alternatives)

1. Introduction

Les algorithmes comportent généralement :

- Les instructions simples : qui permettent la manipulation des variables telles que

- Les instructions de contrôle : qui précisen

instructions simples. ou
les tests.

2.

Il existe deux formes de test : forme simple (ou réduite) et forme complète.

2.1. Forme simple

Dans cette forme, une action qui correspond à une ou plusieurs instructions, est exécuté si

suit immédiatement le bloc conditionnel.

Syntaxe :

Si (condition) Alors
instruction(s) ; // action
Finsi

Remarque :
« Si » est une variable ou une expression booléenne
qui, à un moment donné, est Vraie ou Fausse. par exemple : x=y ; x <= y ; ...

Exemple :
5; 9;
Si (x = y) Alors Ecrire égale à y ;
Dans cet exemple, le message « x est égale à y » ne sera pas affiché puisque la condition (x
=
Chapitre 3 - Les instructions conditionnelles (les alternatives)

2.2. Forme complète

Cette forme permet de choisir entre deux action une condition est vérifiée ou non.
Syntaxe :
Si (condition) Alors
instruction(s) 1 ; // action1
Sinon instruction(s) 2 ; // action2
Finsi

Remarque :
Certains problèmes exigent parfois de formuler des conditions qui ne peuvent pas être
ex [0, 1[
par la combinaison de deux conditions x >= 0 et x < 1 qui doivent être vérifiées
en même temps.
Pour combiner ces deux conditions, on utilise les opérateurs logiques. Ainsi, la condition x
) ET (x < 1). Cette dernière est appelée une
condition composée ou complexe.

Exemple

;
Si (x = y) Alors Ecrire ;
Sinon Ecrire ;
Avec cette forme, on peut traiter les deux cas possibles. Si la condition (x=y) est vérifiée, le

3. Tests imbriqués

La forme « Si Sinon » permet deux choix correspondants à deux traitements

différents.
alternative insuffisante pour traiter tous les cas possibles (voir exemple ci-dessous).
La forme complète permet de choisir entre plusieurs actions en imbriquant des formes
simples selon la syntaxe ci-dessous.
Syntaxe :
Si (condition1) Alors instruction(s) 1 ;
Sinon Si (condition2) Alors instruction(s) 2 ;
Sinon Si (condition3) Alors instruction(s) 3 ;
Chapitre 3 - Les instructions conditionnelles (les alternatives)

Sinon instruction(s) N ;
FinSi
FinSi
FinSi
Exemple : Etat de [10]
Dans les conditions normales de température et de pression,
la température est inférieure ou égale à 0° C, sous forme de liquide si la température est
comprise entre 0° C et 100° C et sous forme de vapeur au-delà de 100° C. Ecrivons

La solution pourrait être comme suit :

Algorithme Etat_Eau ;
Var t : réel ;
Début
Ecrire ("Donner );
Lire (t) ;
Si (t <= 0) Alors Ecrire ("Etat solide") ;
FinSi
Si (t > 0 ET t < 100) Alors Ecrire ("Etat liquide") ;
Finsi
Si (t >= 100) Alors Ecrire ("Etat gazeux") ;
Finsi
Fin
Cet algorithme est correct mais il évalue les trois conditions qui portent sur la même variable
et qui sont exclusives. En effet, si (t <= 0), alors on ne peut pas avoir (t>= 0 et t < 100) ni (t
> 100) deux dernières conditions si la première est vérifiée,
Pour éviter ce cas de figure, il
sera préférable des tests imbriqués comme suit :

Début
Ecrire ("Donner la :") ;
Lire (t) ;
Si (t <= 0) Alors Ecrire ("Etat solide") ;
Sinon Si (t < 100) Alors Ecrire (" Etat liquide") ;
Sinon Ecrire ("Etat gazeux") ;
Finsi
Finsi
Fin
Chapitre 3 - Les instructions conditionnelles (les alternatives)

6.

Figure 6. Organigramme « ».

Donc, l de tests imbriqués permet de :

Simplifier le (pseudo-) code : é que deux
conditions simples au lieu de trois conditions dont une est composée.
un algorithme (ou programme) plus simple et plus lisible.
Optimiser l : dans le cas où la première condition est vérifiée,
passe directement à la fin, sans tester le reste qui est forcément faux.
un algorithme (ou programme)

Remarque :
Nous avons les équivalences suivantes :
NON (A ET B) NON A OU NON B

NON (A OU B) NON A ET NON B

Chapitre 3 - Les instructions conditionnelles (les alternatives)

Ainsi, toute structure

-versa. Par conséquent, les deux alternatives
suivantes sont équivalentes [7].

Si A ET B Alors Si NON A OU NON B Alors

instruction(s) 1 ; instruction(s) 2 ;
Sinon Sinon
instruction(s) 2 ; instruction(s) 1 ;
Finsi Finsi

4. Les choix multiples

différentes suivant les différentes valeurs que peut avoir une variable. Cette structure est
décrite comme suit :

Syntaxe :

Selon (variable)
valeur1 : instruction(s) 1 ;
valeur2 : instruction(s) 2 ;

valeurN : instruction(s) N ;
défaut : instruction(s) par défaut;
FinSelon ;

Remarque :
Dans la structure de test à choix multiples :
- ;
- La valeur est une constante de même type que la variable ;
- La partie « défaut » est exécutée si aucun des autres cas ;
- -à-
Chapitre 3 - Les instructions conditionnelles (les alternatives)

Exemple :
Dans ce qui suit, le nom du jour de la semaine correspondant est affiché selon la valeur de
la variable « jour ».
;
Selon jour
1 : Ecrire ("Dimanche") ;
2 : Ecrire ("Lundi") ;
3 : Ecrire ("Mardi") ;
4 : Ecrire ("Mercredi") ;
5 : Ecrire ("Jeudi") ;
6 : Ecrire ("Vendredi") ;
7 : Ecrire ("Samedi") ;
Défaut : Ecrire ("Numéro de jour invalide.") ;
FinSelon
Jeudi » est affichée dans ce cas.

5. Conclusion

Dans ce chapitre, nous avons présenté le principe de la condition, suivant lequel un

algorithme peut eff
travers les instructions conditionnelles ou tout simplement les tests avec leurs différentes
formes vues précédemment.
Chapitre 4 - Les instructions itératives (les boucles)

Chapitre 4 - Les instructions itératives (les boucles)

1. Introduction
Considérons le même exemple calcul de la moyenne
se faire, on doit :

Calculer la somme des notes,

Diviser la somme obtenue sur le nombre (ou sur la somme des coefficients).

doivent être répétées.

audra donc instructions.
Cet exemple soulève deux questions importantes :
1- ?
2- Combien de fois doit-on répéter on de
obtenir le résultat attendu ?
Pour répondre à ces questions, de n
des instructions itératives (appelées aussi les boucles ou les itérations).

2. Définition

Une boucle (ou itération) est une instruction de contrôle qui permet de répéter plusieurs fois
un ensemble instructions. Généralement, deux cas sont distingués :
- Le nombre de répétitions est connu.
- Le nombre des répétitions est inconnu ou variable.

3. « Pour »

« Pour »
est privilégiée. Une structure de boucle Pour » une fois que le
nombre de répétitions est atteint. Cette structure possède un indice (compteur) de contrôle
:
- une valeur initiale,
- une valeur finale,
- un pas de variation.
Chapitre 4 - Les instructions itératives (les boucles)

Syntaxe :

Pour indice de début à fin Pas valeur_du_pas

instruction(s) ;
FinPour

Cette structure est dite « croissante » lorsque

valeur finale, le pas de variation est par conséquent positif. Autrement, elle est dite
« décroissante ».

Exemple : un compteur croissant/décroissant

Les deux algorithmes suivants comptent de 1 à N et de N à 1 respectivement.
Algorithme compteur_croissant ; Algorithme compteur_decroissant ;
Var i : entier ; Var i : entier ;
Const N=100 ; Const N=100 ;
Début Début
Pour i de 1 à N /* par défaut le pas = 1 */ Pour i de N à 1 /* par défaut le pas = -1 */
Ecrire (i); Ecrire (i);
FinPour FinPour
Fin Fin

: 1,2, , 99, 100 : 100, 99, 98,

Remarque : Si la valeur du « pas » dans « Pour », elle est

par défaut égale à un (1).
Chapitre 4 - Les instructions itératives (les boucles)

4. « »
Cette instruction permet de tester une condition et répéter le traitement associé tant que cette
condition est vérifiée.

Syntaxe:
Tant que condition faire
instruction(s) ;
FinTq

Exemple : Réécrivons e précédent avec cette instruction.

Var i : entier ;
Début
;
Tant que (i<=100) faire
Ecrire (i) ; ;
FinTq
Fin

6. « »

Dans cette instruction, un traitement est exécuté au moins une fois puis sa répétition se

Syntaxe:
Répéter
instruction(s) ;
(condition) ;

Exemple : :
Var n, p : entier ;
Début
Répéter
Ecrire ("Donner un nombre :") ; Lire (n) ;
p ; Ecrire (p);
(n=0)
Ecrire ( );
Fin
 Chapitre 4 - Les instructions itératives (les boucles)

Les instructions encadrées par les mots répéter et constituent le bloc de la boucle
(n=0) soit vérifiée. Donc le nombre de
répétitio

Question ?
R précédent avec « » puis avec « Pour ».

Remarque :
Dans la boucle « R », la condition -dessus,
constitue une de la boucle ; mais réellement, cela diffère selon le langage
de programmation utilisé. Par exemple, en Pascal, la condition de cette boucle est une
ta
condition de continuation.

7. La notion du compteur

Un compteur est une variable associée à la boucle dont la valeur est incrémentée de un à
chaque itération. Elle sert donc à compter le nombre (répétitions) de la boucle.
La notion du compteur est associée particulièrement aux deux
boucles : « R » et « Tant que ». Par contre, dans la boucle
« Pour », joue le rôle du compteur.
L du compteur dans les deux premières boucles est exprimée ainsi :

; ;
Répéter Tant que (condition) faire
instruction(s) ; instruction(s) ;
Bloc de la boucle
; ;
condition) ; FinTant que ;

Remarque :

Il faut toujours initialiser le compteur avant de commencer le comptage. La variable

« compt » (utilisée ci-dessus comme compteur), a été initialisée à zéro (0) avant le début de
chaque boucle.
« » incrémente la valeur de « compt » de un (1). Elle peut
u bloc de la boucle.
Chapitre 4 - Les instructions itératives (les boucles)

Exemple :
; i ;
Répéter Tant que (i<5) faire
Ecrire (i); Ecrire (i);
; i +1 ;
i=5) ; FinTant que ;

: 0, 1, 2, 3, 4 : 0, 1, 2, 3, 4

8. La n

Cette notion est fondamentale en programmation. Elle est utilisée notamment pour calculer
valeurs. instruction correspondante se présente ainsi :
;
Cette instruction consiste à ajouter une valeur à une variable numérique, puis affecter le
résultat dans la variable elle- e
[4].

Exemple : calcul de la somme de n valeurs données :

Var i, n : entier ; som, val : réel ;

Début
Écrire ("Donner le nombre de valeurs :") ; Lire (n) ;
;
Pour i de 1 à n
Écrire ("Enter une valeur :") ; Lire (val) ;
som ;
Finpour
Écrire ("La somme des valeurs est égale à :", som) ;
Fin
9. Les boucles imbriquées
Les boucles peuvent être imbriquées les unes dans les autres. Deux ou plusieurs boucles
imbriquées peuvent être aussi les mêmes ou différentes.

Exemple :

Pour i de 1 à 2
Écrire ("i = ", i) ;
Pour j de 1 à 3 boucle 1
Écrire ("j = ", j) ; boucle 2
Finpour
Finpour
Dans exemple ci-dessus, chaque itération de la boucle extérieure (boucle 1) exécute la
boucle intérieure (boucle 2 itération suivante, et ainsi de
Chapitre 4 - Les instructions itératives (les boucles)

. Ainsi, l peut être représenté

comme suit :
i=1
j=1
j=2
j=3
i=2
j=1
j=2
j=3
Remarque :

Des boucles peuvent être imbriquées ou successives. Cependant, elles ne peuvent jamais être

croisées :
Var i, j : entier ;
Début
; ;
Répéter
Écrire i ;
Répéter
Écrire j ;
;
i>2
;
j>3
Fin

10. Conclusion

Ce chapitre a été consacré aux structures itératives ou boucles qui permettent de répéter
certains
critères Ainsi, ces instructions

que les tableaux que nous aborderons dans le prochain chapitre.

Chapitre 5 - Les tableaux

Chapitre 5 - Les tableaux

1. Introduction

Supposons que l
par conséquent, déclarer 100 variables
un peu lourd de manipuler
Imaginons maintenant le cas pour une promotion de 1000 étudiants, alors là devient notre
cas un vrai problème.
En algorithmique (et en programmation), on peut regrouper toutes ces variables en une seule
appelle tableau.
Un tableau est un ensemble de variables de même type ayant toutes le même nom.
Suite à cette définition, la question suivante se pose :
- Comment peut-on différencier entre des variables ayant le même nom ?
La réponse est dans la notion du tableau lui-même où chaque élément est repéré par un
indice. Ce dernier est un numéro (généralement un entier) qui permet de différencier chaque
élément du tableau des autres. Ainsi, les éléments du tableau ont tous le même nom, mais
pas le même indice. Pour accéder à un élément d un tableau, on utilise le nom du tableau
crochets [4].
Exemple
Soit le tableau T contenant les valeurs suivantes : 5, 10, 29, 3, 18 et 14 :
organisation du tableau T dans la mémoire peut être représentée comme suit :

indices : i=0 i=1 i=2 i=3 i=4 i=5

T
valeurs : T[0]=5 T[1]=10 T[2]=29 T[3]=3 T[4]=18 T[5]=14

2. Tableaux à une seule dimension

Dans ce type de tableaux, chaque élément est accessible (pour lecture ou modification) par
un seul indice.
2.1. Déclaration

La syntaxe de à une seule dimension est la suivante :

Tableau nom_du_tableau [taille] : type ;

Exemple : Tableau Notes [100] : réel ;

Chapitre 5 - Les tableaux

Remarque :
tableau, peut être exprimé comme un nombre, mais aussi il
peut être exprimé comme une variable ou une expression calculée [10].
La valeur d indice doit être toujours :
Supérieur ou égal à 0
porte (comme en Pascal). Mais
langage C, la numérotation des indices commence à zéro. Par exemple Notes[1] est
le deuxième élément du tableau Notes.
de type entier Notes[ ]n
Inférieur ou égal au nombre des éléments du tableau
à zéro): En langage C, si un tableau T est déclaré comme ayant 10 éléments, la
T[10] déclenchera
automatiquement une erreur.

2.2. Manipulation

Une fois déclaré, un tableau peut être manipulé comme un ensemble de variables simples.
[4].

2.2.1.
affect une valeur v à un élément i T de type numérique, se fait par :

T[i] ;
: T[0] 5 ; affecte la valeur 5 au premier élément du tableau T.

Illustration :
indices : i=0 i=1 i=2 i=3 i=4 i=5
T
valeurs : 5

Supposons affecter la même valeur à tous les éléments du tableau

T, on utilisera pour cela une boucle :

Pour i de 0 à n-1 // n est la taille de T

T[i] 5;
FinPour
Cette boucle permet de parcourir tout le tableau T en affectant à chaque élément la valeur 5.
Illustration :
indices : i=0 i=1 i=2 i=3 i=4 i=5
T
valeurs : 5 5 5 5 5 5
Chapitre 5 - Les tableaux

2.2.2. La lecture

Il est possible aussi

lecture.
Exemple :
Ecrire "Entrer une note :" ;
Lire T[0] ;

Dans cet exemple, la valeur saisie est affectée au premier (1er) élément du tableau T.

Illustration :

indices : i=0 i=1 i=2 i=3 i=4 i=5

T
valeurs : 0

2.2.3.

De même que du :
Ecrire T[i] ;

Remarque :
manipulés de la même façon que les variables simples

des expressions numériques du genre :

Notes [1] + Notes [2]) / 2 ;
Notes [0] Notes [0] + 1 ;

Exemple :
Soit Notes un tableau de valeurs réelles

Illustration :

indices : i=0 i=1 i=2 i=3 i=4 i=5

Notes
valeurs : 10 15 7 8.25 11.5 16

Est :x= = 11

2.3. Application 1

de taille 20, et les afficher par la suite.

Chapitre 5 - Les tableaux

Algorithme :
Var i : entier ;
Tableau Tab [20] : réel ;
Début
Pour i de 0 à 19
Ecrire ("Donner une valeur :") ;
Lire (Tab[i]) ;
FinPour
Pour i de 0 à 19
Ecrire ("Valeur ", i, "=", Tab[i]) ;
FinPour
Fin

u programme correspondant -dessus,

tableau Tab comme suit :

- Après la fin de la 1ère boucle (boucle de lecture) :

indices : i=0 i=1 i=18 i=19

Tab
valeurs : 5 34 14.5 60

- Après la fin de la 2ème sur écran par exemple,

Valeur 0 = 5
Valeur 1 = 34

Valeur 18 = 14,5
Valeur 19 = 60

Remarque : les valeurs : 5, 34, 14.5 et 60 sont un échantillon de valeurs saisies

pa

3. Tableaux à deux dimensions

Les tableaux à deux dimensions

lignes et de colonnes (Matrice). Par conséquent, chaque élément est repéré par deux indices.
Chapitre 5 - Les tableaux

Exemple : le tableau T ci-dessous possède 3 lignes et 4 colonnes.

j=0 j=1 j=2 j=3

i=0

i=1

i=2 x

Donc, T[2][1] (i=2 et j=1) 3ème ligne et la 2ème colonne (en

commençant de zéro bien sûr).

3.1.

Syntaxe :
Tableau nom_tableau [taille1][taille2] : type ;

Exemple : Tableau Notes [10][20] : réel ;

Le tableau Notes est composé de 10 lignes et 20 colonnes. Ce tableau pourra contenir donc
10*20 soit 200 valeurs réelles.

Remarque :
s réside dans la possibilité de déclarer un seul tableau
au lieu de déclarer plusieurs tableaux identiques. En effet, le tableau
est équivalant à 10 tableaux simples de 2
déclaration :
Tableau Notes [10][20] : réel ;
remplace celle-ci :
Tableau Notes1 [20], Notes2 [20], Notes10 [20] : réel ;

3.2.

Un tableau à deux dimensions est (à une

seule dimension) qu . Ces trois opérations
sont illustrées dans la sous-section suivante.

3.3. Application 2

Reprenons de la sous-section 2.3 mais cette fois-ci pour un tableau de 5 lignes

et 20 colonnes :

Var i, j : Entier ;
Tableau Tab [5][20] : réel ;
Chapitre 5 - Les tableaux

Début
Pour i de 0 à 4
Pour j de 0 à 19
Ecrire ("Donner une valeur :") ; Lire (Tab [i][j]) ;
Finpour
Finpour
Pour i de 0 à 4
Pour j de 0 à 19
Ecrire (Tab [i][j]) ;
Finpour
Finpour
Fin

4. Tableaux à n dimensions
Les tableaux à n dimensions (n>2), peuvent être utilisés pour diverses raisons telles que la
création et le traitement des objets 3D par exemple qui nécessitent des tableaux de 3
dimensions au minimum. La déclaration de ce type de tableaux est comme suit :

Syntaxe :
Tableau nom_tableau tailleN] : type ;

Exemple : Tableau T [10][20][50] : réel ; // un tableau T à 3 dimensions

La suit le même principe que celle des

tableaux à deux dimensions. Ceci tion des boucles imbriquées pour
parcourir le tableau, boucle

5. La recherche dans un tableau

5.1. La notion du drapeau
Le drapeau (ou flag en Anglais) est une variable booléenne initialisée à Faux (drapeau
baissé). Dès qu évènement attendu se produit, la variable change de valeur à Vrai
(drapeau levé). Donc, la valeur finale du drapeau permet de savoir si un évènement a eu lieu
ou pas. : la recherche de
tableau [10].
Exemple :
comportant N valeurs entières. On doit écrire un
algorithme qui lit un nombre donné
Chapitre 5 - Les tableaux

ce nombre dans le tableau. La première étape consiste à écrire les instructions de lecture du
nombre N et de parcours du tableau :
Tableau Tab[N] : Entier ;
Var val, i : Entier ;
Début
Ecrire ("Entrer la valeur à rechercher :") ; Lire (val) ;
Pour i de 0 à N-1

Finpour
Fin

Illustration :
On suppose que N=6 et les valeurs saisies sont celles figurant dans le schéma suivant :
indices : i=0 i=1 i=2 i=3 i=4 i=5
Tab
valeurs : 10 22 31 46 5 7

aintenant, il faut combler les points de la boucle (le bloc qui

devra contenir les instructions de la recherche). Évidemment, il va falloir comparer « val »
à chaque élément du tableau, y a une égalité quelque part, alors « val » fait partie du
tableau. Cela va se traduire, bien entendu, par instruction conditionnelle «
Sinon ».

Début
Ecrire ("Entrez la valeur à rechercher ") ; Lire (val) ;
Pour i de 0 à N-1
Si (val = Tab[i]) Alors
Ecrire (val, "figure") ;
Sinon ?
Ecrire (val, "ne figure pas") ;
Finsi
Finpour
Fin
Chapitre 5 - Les tableaux

Illustration :
On suppose que la valeur à rechercher (val) est égale à 31 :

O :
- ou bien la valeur « val » figure dans le tableau,
- ou bien elle n'y figure pas.
Mais dans tous les cas, l'algorithme ne doit produire qu'une seule réponse, quel que soit le
nombre d'éléments du tableau. Or, l'algorithme ci-dessus affiche autant de messages qu'il y
a de valeurs dans le tableau. Il y a donc une erreur quelque part.
En fait, on ne peut savoir si la valeur recherchée existe dans le tableau ou non que lorsque le
parcours du tableau est entièrement accompli.
Pour pallier à cette erreur, on doit réécrire algorithme en plaçant le test après la boucle et
en utilisant cette fois-ci une Existe ».
Cette variable doit être gérée comme suit :
- La valeur de départ de « Existe » doit être évidemment Faux (drapeau baissé).
- La valeur de la variable « Existe » doit devenir Vrai (drapeau levé), si un test dans
la boucle est vérifié (lorsque la valeur de « val » est rencontrée dans le tableau). mais

rithme correct devrait être comme suit :

Tableau Tab[N] : entier ;

Var val, i : entier ;
existe : booléen ;
Début
Ecrire ("Entrez la valeur à rechercher ") ;
Lire (val) ;
existe ;
Pour i de 0 à N-1
Si (val = Tab[i]) Alors existe vrai; Finsi
Finpour
Chapitre 5 - Les tableaux

Si (existe) Alors Ecrire (val, "fait partie du tableau") ;

Sinon Ecrire (val, "ne fait pas partie du tableau") ;
Finsi
Fin

Illustration :
En utilisant un drapeau (la variable « Existe ») :

Question ?
Réécrire le même algorithme mais cette fois-ci, la boucle de recherche doit être arrêtée dès
que la valeur du drapeau change.

6.
est-ce qu tri ?

prédéfinie. Le problème du tri est un grand classique en algorithmique. Trier un

tableau numérique Il existe
plusieurs algorithmes de tri, parmi lesquels le tri par sélection, tri par insertion, tri à bulles,
tri par fusion, etc. Nous illustrons dans ce qui suit deux types de tri, à savoir le tri par
sélection et le tri par insertion.

6.1. Tri par sélection

Cette technique est parmi les plus simples, elle consiste à sélectionner, pour une place
donnée, l Par exemple pour trier un tableau en ordre
croissant, on met en première position le plus petit élément du tableau et on passe à la
position suivante pour mettre le plus petit élément parmi les éléments restants et ainsi de
dernier [2].
Chapitre 5 - Les tableaux

Exemple :
Soit à trier, en ordre croissant, le tableau suivant :
25 10 13 31 22 4 2 18

Nous commençons par la recherche de la plus petite valeur et sa position. Une fois identifiée
7ème position), nous ons avec le 1er élément (le
nombre 25). Le tableau devient ainsi :

2 10 13 31 22 4 25 18

Nous recommençons la recherche, mais cette fois, à partir du 2ème élément (puisque le 1er
est à sa position correcte). Le plus petit élément se trouve en 6ème position (le nombre 4).
Nous échangeons donc le 2ème élément avec le 6ème élément :

2 4 13 31 22 10 25 18

Nous recommençons la recherche à partir du 3ème élément (puisque les deux premiers sont
maintenant bien placés), Le plus petit élément se trouve aussi en 6ème position (10), en
3ème, ça donnera:

2 4 10 31 22 13 25 18

Nous recommençons maintenant à partir du 4ème élément et de la même façon nous

procédons :

2 4 10 13 22 31 25 18

2 4 10 13 18 31 25 22

2 4 10 13 18 22 25 31

2 4 10 13 18 22 25 31

Algorithmiquement, nous pouvons décrire ce processus de la manière suivante :

Boucle principale : prenant comme point de départ le premier élément, puis le second,

Boucle secondaire : à partir de ce point de départ mouvant, nous

fin du tableau le plus petit élément. Une fois trouvé, nous ons avec le point de
départ.
Chapitre 5 - Les tableaux

Donc, :

/* boucle principale : le point de départ se décale à chaque tour */

Pour i de 0 à 6
/* on considère provisoirement que T(i) est le plus petit élément */
posmin ; // posmin est la position du minimum initialisée par i
/* on examine tous les éléments suivants */
Pour j de (i + 1) à 7
Si (T(j) < T(posmin)) Alors posmin ; Finsi

Finpour
/* on sait maintenant où est le plus petit élément. Il ne reste plus qu'à effectuer la permutation
*/
T(posmin) ;
T(posmin T(i) ;
T ;
/* On a placé correctement l'élément numéro i, on passe à présent au suivant */

FinPour

6.2. Tri par insertion

Soit à trier un tableau

Le principe de ce type de tri repose à chaque itération sur trois phases [2] :
a) On prend le premier élément dans la partie non encore triée du tableau (la clé).
b) On cherche la place de la clé dans la partie déjà triée du tableau, en commençant par
la droite de cette partie.
c)
tous les éléments de la partie triée dont la valeur est plus grande ou égale à la valeur
de la clé.

tableau, autrement dit, le processus du tri commence à partir du deuxième élément.

Exemple :

Soit à trier, en ordre croissant, le même tableau précédent en appliquant le tri par insertion :

i=1 25 10 13 31 22 4 2 18

Clé Partie non encore triée

Chapitre 5 - Les tableaux

On décale le 1er élément de la partie triée vers la droite puisque sa valeur est supérieure à la
clé. Cette dernière est déplacée à la 1ère position :
i=2 10 25 13 31 22 4 2 18

On recommence le processus avec une nouvelle clé. Le 1er élément à droite de la partie triée
(25) est décalé vers la droite puisque sa valeur est supérieure à la clé. Le 2 ème élément ne sera
Par conséquent, la clé est insérée dans la 2ème
position du tableau :

i=3 10 13 25 31 22 4 2 18

On ne déplace pas cette clé (31) puisque sa valeur est supérieure à celles des éléments qui la
précèdent.

i=4 10 13 25 31 22 4 2 18

On décale les deux premiers éléments (31 et 25) vers la droite et la clé est insérée à la 3 ème
position :

i=5 10 13 22 25 31 4 2 18

On décale tous les éléments de la partie triée vers la droite puisque leurs valeurs sont
supérieures à celle de la clé. Cette dernière est déplacée à la 1 ère position :

i=6 4 10 13 22 25 31 2 18
La même opération est répétée pour cette clé (2) :

i=7 2 4 10 13 22 25 31 18

Les trois éléments (22,25 et 31) sont décalés vers la droite et la clé est déplacée vers la 5ème
position :

2 4 10 13 18 22 25 31

Nous obtenons donc un tableau qui est trié en ordre croissant.

:
Chapitre 5 - Les tableaux

Algorithme Tri_Insertion ;
Var i, j, n, clé : Entier; // n est la taille du tableauT
T: ;
Début
Pour i de 1 à n-1 // on commence par le 2ème élément (début de la partie non triée)
clé T[i] ;
j i - 1 ; // indice du 1er élément à droite de la partie triée
Tant que ((j >= 0) ET (clé < T[j])) Faire
T[j +1] T[j]; // Décalage
j j - 1;
FinTant que
T[j +1] clé; // Insertion de la clé
FinPour
Fin

6.3. Comparaison

Dans l tri par sélection, nous avons dans tous les cas, la boucle interne est
exécuté pour i=1, 2, 3 -1) par conséquent, nous avons (n-1) + (n-2) + (n-
+ 1 étant n (n-1) / 2 exécutions. Par exemple, pour un tableau de 100 éléments, la boucle est
exécutée 4950 fois dans tous les cas.
par insertion, nous avons dans le pire des cas un tableau trié à
), et la boucle interne est exécuté (n-1) + (n-2) +
(n- , étant n (n-1) / 2 exécutions au maximum. Au meilleur des cas, le tableau
est trié en ordre voulu (croissant dans ce cas) et ra jamais. En
moyenne, n (n-1) / 4. Par exemple, pour un tableau de 100
éléments, la boucle est exécutée 4950 fois au maximum et 2475 en moyenne.

7. Conclusion

Dans ce chapitre, nous avons vu comment mémoriser et manipuler un ensemble de valeurs

représentées par le même nom et identifiées par des numéros à travers la notion du tableau.

donné. Le p
suite à travers deux algorithmes parmi les plus simples, à savoir le tri par sélection et le tri
par insertion. Une comparaison entre les deux algorithmes a été donnée à la fin de ce
chapitre.
Chapitre 6 - Les enregistrements (structures)

Chapitre 6 - Les enregistrements (structures)

1. Introduction

Nous avons vu dans le chapitre précédent, que les tableaux nous permettent de stocker
plusieurs éléments de même type, tel que stocker les notes des étudiants dans un tableau de

autre structure qui permet de stocker des données de différents types. Donc, une nouvelle
structure appelée enregistrement est plus adaptée dans ce cas.

2. Définition
Un enregistrement (ou structure) permet de regrouper un ensemble de données de différents
types sous le même nom (un seul objet). léments appelés
champs. Ces derniers sont des données élémentaires ou composées qui peuvent être de types
différents.

3. Déclaration et manipulation
La syntaxe de est la suivante :
Structure nom_structure
champ1 : type1 ;
champ2 : type2 ;
...
champN : typeN ;
FinStructure ;

Tel que « nom_structure

champ2, champN » sont les variables membres de la structure déclarée.
Exemple :
Structure Etudiant
num : entier ;
nom : chaîne ;
moyenne : réel;
FinStructure ;
Par la suite, des variables de type Etudiant peuvent être déclarées comme suit :
Var x,y : Structure Etudiant ; /* Deux variables structures x et y de type Etudiant */
Chapitre 6 - Les enregistrements (structures)

champ (membre à une

information contenue dans un champ se fait en précisant le nom de la variable structure
suivie du champ concerné. Les deux séparés par un point.
Exemple :
[Link] 123 ; // affecte le nombre 123 au champ num
Lire ([Link]) ; // lire le champ nom
[Link] 13.5 ; // affecte le nombre 13.5 au champ moyenne

4. Tableau de structures
Il est possible de déclarer un tableau dont les éléments sont des structures avec la syntaxe
suivante :
Tableau nom_tableau [taille] : Structure nom_structure ;

Exemple : Tableau T[10] : Structure Etudiant ;

Donc, T est un tableau de 10 éléments de type structure (« Etudiant » dans ce cas).

i d un tableau de structure se fait comme suit :

nom_tableau [i].champ

Par exemple, les instructions :

T[0].nom "Mohamed" ;
T[0].num 1 ; et
T[0].moyenne ;
affectent respectivement la valeur entière « 1 », la chaîne de caractères « Mohamed » et la
valeur réelle « 12.5 » aux champs « num », « nom » et « moyenne » du 1er élément du
tableau T.
Illustration :

indices : i=0 i=1 i=9

T num : 1 num : num :
Eléments : nom : Mohamed nom : nom :
moyenne : 12.5 moyenne : moyenne :

De même, les instructions :

Ecrire (T[0].num) ;
Ecrire (T[0].nom) ;
Ecrire (T[0]. moyenne) ;
Affichent les contenues des trois champs du 1er élément du tableau T.
Chapitre 6 - Les enregistrements (structures)

5.
Une structure peut figurer parmi les champs d'une autre structure. Dans ce cas, elle doit être
déclarée avant la structure qui la contient [6].

Exemple :
Structure Date
jour, mois, annee : entier ;
Finstructure ;
Structure Compte
Ncpt: entier;
nom: chaine ;
DtOuverture : Date ;
Finstructure ;
Où « DtOuverture » est une variable structure de type « Date », champ de la structure «
Compte ». Donc, la structure « Date » est déclarée obligatoirement avant la structure «
Compte ».
Lorsqu'un champ d'une structure est lui-même une structure, ccès à ce champ se fait
comme suit :
variable_structure.variable_sous_structure.champ

Par exemple : [Link] ; affecte la valeur 2019 au champ année de

DtOuverture » qui est lui- ». Tel
que « c » est une variable de type « Compte ».

Dans le cas d'un tableau, l'accès se fait comme suit :

nom_tableau[indice].variable_sous_structure.champ

Par exemple : T[i].[Link] ;

Où T[i] fait référence au ième élément du tableau T de type « Compte ».

6. Conclusion

Nous avons vu dans le cinquième chapitre que les tableaux sont très pratiques, cependant ils
ne permettent pas de répondre à tous les besoins de stockage tels que le regroupement de
plusieurs données de types différents en un seul objet. A cet effet, la notion de structure (ou
abordée dans le présent chapitre permet de pallier ce problème en créant
un nouveau type permettant le stockage des données de types différents ou non. Un
enregistrement qui est composé de plusieurs champs où chaque champ correspond à une
donnée, constitue la brique de base pour les structures de données telles que les listes, les
piles et les files qui ne font pas l objet d étude dans ce polycopié.
Chapitre 7 - Les fonctions et les procédures

Chapitre 7 - Les fonctions et les procédures

1. Introduction

La fiabilité, la lisibilité et la réutilisabilité des programmes, utilisation des

sous-programmes. Ces derniers permettent :

- La réduction de la taille des programmes : il est possible de déterminer les blocs

analogues, les substituer par un sous-
déterminés au niveau du programme principal.
- ganisation du code : le problème initial peut être découpé en sous-problèmes
(modules) où chacun sera résolu par un sous-programme [1].

Exemple : Codage en base b [3]

Un entier positif en base b est représenté par une suite de chiffres (c n c . . . c1c0)b où les ci
sont des chiffres de la base b (0 ci < b).

cnbn + cn-1bn-1 1b
1
+ c0b0 =

On suppose que le nombre x est représenté par un tableau de chiffres (code) en base b ; par
exemple si b = 2 et code = [1,0,1], alors en base 10 le nombre entier x correspondant vaudra
1×22 + 0×21 + 1×20 = 4+0+1 = 5 qui permet de calculer
x en base 10 est le suivant :

;
Pour i de 0 à L-1 // L est la longueur du code
+ code[i]*b^(L-1-i);

23)5
et (123)8, on devra donc recopier deux -dessus.

; ;
2,3] ; c 2,3] ;
; ;
Pour i de 0 à L-1 Pour i de 0 à L-1
+ code[i]*b^(l-1-i); + code[i]*b^(l-1-i);
Chapitre 7 - Les fonctions et les procédures

Dans la pratique, souhaitable deux fois le même programme,

plus, si celui-ci nécessite de très nombreuses lignes de code source. Pour améliorer la
la solution est d er le code à répéter au -
programme.

2. La notion de sous-programme

Un sous-programme est une portion de code analogue à un programme, destiné à réaliser

. Il est identifié par un nom unique et
qui peut être exécuté plusieurs fois par des appels. Un appel est une
ramme ou sous-programme appelé le (sous-)
programme appelant.
Pour résumer, un sous-programme est utilisé pour deux raisons essentielles :
- : on écrit un sous-programme pour cette

le même code à plusieurs endroits dans le même programme.

- Pour -problèmes : on divise le
problème en sous-problèmes pour mieux le contrôler (diviser pour régner).

Il existe deux types de sous-programmes : les fonctions et les procédures. Cependant, avant
de détailler ces deux concepts, il sera utile de définir quelques notions utiles.

2.1.

Dans cette sous-section, nous illustrons une notion appelée . L'idée

principale est qu'il est possible d'avoir deux variables différentes avec le même nom toutefois
qu'elles ont des portées différentes. Le cas le plus connus que l'on peut citer, est qu'une
variable définie au niveau du programme principal (celui qui résout le problème initial) est
appelée variable globale et sa portée est totale, par conséquent, tout sous-programme du
programme principal peut utiliser cette variable. Alors qu'une variable définie au sein d'un
sous-programme est appelée variable locale dont la portée est limitée au sous-programme
dans lequel elle est déclarée [7].

Remarque :
Si d'une variable locale est identique à une variable globale,
cette dernière est localement masquée. Autrement dit, la variable globale devient
inaccessible dans le sous-programme contenant la variable locale de même nom.
Chapitre 7 - Les fonctions et les procédures

Exemple :
le sous-programme suivant :
Algorithme Secondaire ;
Var x : entier ; // variable locale
Début
x 3;
Ecrire (x, y) ;
Fin
Supposons maintenant que nous appelons ce sous-programme « Secondaire » depuis une
autre partie du programme « Principal » qui utilise également deux variables globales :
Algorithme Principal ;
Var x, y : entier ; // variables globales
Début
x ;y ;
; // Appel au sous-programme Secondaire
Ecrire (x, y) ;
Fin
e comme suit :

Programme Espace mémoire

-Principal
Début
5,8

Fin

-Secondaire
Début 3,8

Fin

Dans cet exemple, la variable « x », ayant la valeur 5 dans le programme principal, est une
variable globale. Une autre variable qui porte le même nom « x » est utilisée au niveau du
programme secondaire ayant comme valeur 3. Cet variable locale a masqué la variable
globale « x » au niveau du programme secondaire x » au
niveau de ce sous-programme correspond à la valeur 3. Par contre, la variable globale y est
quant à elle accessible, ce qui justi age de la valeur 8 au niveau du sous-
programme.
Chapitre 7 - Les fonctions et les procédures

2.2. Les paramètres

Les paramètres d'un sous-programme sont un ensemble de variables locales (paramètres

formels) associées à un ensemble de variables ou constantes du (sous-) programme appelant
(paramètres effectifs).

Remarque :

- Un paramètre est une variable locale, donc il admet un type.

- L un sous-programme possédant un ou plusieurs paramètres, implique une
association entre ces paramètres et les paramètres effectifs du programme (ou sous-
programme) appelant, respectivement de même type.

Par exemple, si le sous-programme Racine permet de calculer la racine carrée d'un réel :
- Ce sous-programme admet un seul paramètre de type réel positif.
- Le programme appelant Racine doit fournir le réel positif dont il veut calculer la
racine carrée, cela peut être une variable (Racine (y)) ou une constante (Racine (9)).

2.3. Le passage de paramètres

L'association entre les paramètres effectifs et les paramètres formels est appelé passage de
paramètres. Il existe deux types de passage de paramètres :
- Le passage par valeur.
- Le passage par référence (ou adresse).
Dans le premier type, la valeur du paramètre effectif est affectée (copiée) au paramètre
formel correspondant. Sachant que les paramètres formels ne sont que des variables locales
de la fonction. Ce type de passage sera illustré dans la section qui suit.

formel correspondant. Ceci rend possible au sous- directement à

pointeurs [5] [9].

Remarque :

Une illustration du passage de paramètre par valeur e ection

4. Le passage de paramètre par adresse sera illustré dans le chapitre suivant.

3. Les fonctions

Une fonction est un sous-programme qui admet un nom, un type et des paramètres. Une
fonction admet un type et retourne toujours un résultat.
Chapitre 7 - Les fonctions et les procédures

3.1. Dé

On définit une fonction comme suit :

Fonction nom_fonction (paramètres : types) : type de la valeur retournée
Var : types; // variables_locales
Début
instructions de la fonction ;
Retourner (résultat) ; // (au moins une fois)
Fin
Où :

Le type de la valeur retournée est le type de la fonction.

La valeur de retour (ou le résultat) est spécifiée par l'instruction Retourner.

3.2.

On fait appel à une fonction comme suit :

var nom_fonction (paramètres) ;
Où l

Remarque :
jours présentes même
lorsqu'il n'y a pas de paramètres.
Exemple 1 :
Soit algorithme A fonction :

Algorithme A ;
Var a, b : entier ;
Fonction Abs (n : entier) : entier /* Définition de la fonction */
Var valabs : entier
Début
Si (n >= 0) alors valabs ;
Sinon valabs -n ;
FinSi
Retourner valabs ;
Fin
Début /* Algorithme principal */
Ecrire (" Donner une valeur ") ;
Lire (a) ;
Abs(a) ;
Ecrire (b) ;
Fin
Chapitre 7 - Les fonctions et les procédures

Abs(), il y a une association entre le paramètre effectif a

et le paramètre formel n a est copiée dans n.
passage de paramètre par valeur.

4. Les procédures
Une procédure est un sous-programme qui admet également un nom et des paramètres mais
ne retournant aucun résultat.

4.1. Définition
On définit une procédure comme suit :
Procédure nom_procédure (paramètres : types)
Var
Début
instructions de la procédure ;
Fin
4.2. ne procédure
appel une procédure se fait comme suit :
nom_procédure (paramètres) ;

Exemple 2 :
mais cette fois-ci en utilisant une
procédure :
Algorithme B ;
Var a : entier ;
Procédure Abs (n : entier) /* Définition de la procédure */
Début
Si (n >= 0) alors
Ecrire n ;
Sinon
Ecrire -n ;
FinSi
Fin

Début /* Algorithme principal */

Ecrire (" Donner une valeur ") ;
Lire (a) ;
Abs(a) ;
Fin
Chapitre 7 - Les fonctions et les procédures

Exemple 3 :
Soit un algorithme utilisant une procédure comme suit :
Algorithme C ;
Var x : entier ;
Procédure Modif (x : entier)
Début
x x + 1 ; /* le x local est modifié, pas le x du programme principal */
Fin

Début /* Algorithme principal */

x ;
Ecrire ("Valeur de x :", x) ;
Modif (x) ;
Ecrire :", x) ;
Fin

Programme Espace mémoire

Algorithme C x 1
Début
:1
x ;
;
Valeur de x après :1
Modif (x) ;
Ecr ;
Fin

Procédure Modif()
x 12
Début
x ;
Fin

Lorsqu on passe un paramètre à une fonction (ou à une procédure), cette dernière ne peut
pas modifier la variable. La variable est automatiquement recopiée et la fonction travaille
sur une copie de la variable. La modification de la copie n entraîne pas une modification de
la variable originale. C est ce qu on appelle le passage de paramètre par valeur [3].
Chapitre 7 - Les fonctions et les procédures

5. Fonctions et procédures récursives

-même directement ou indirectement.

5.1. Exemple illustratif

mbre N non négatif de deux manières :

Définition non récursive : N ! = N * N-

Définition récursive : N ! = N * (N 1) ! et 0 ! = 1

Par conséquent, deux solutions sont possibles pour le calcul de la factorielle.

a) Solution itérative :

Fonction FACT ( n : entier ) : entier

Var i, F: entier ;
Début
Si (n = 0) alors F 1;
Sinon
F 1;
Pour i de 2 à n
F F * i;
Finpour
Retourner F;
Finsi
Fin

b) Solution récursive :

Fonction FACT ( n : entier ) : entier

Début
Si (n=0) alors Retourner 1 ;
Sinon Retourner n * fact (n-1) ; // Appel récursif de la fonction FACT
Finsi
Fin

5.2. Interprétation

-dessus). Cette condition empêche des appels récursifs sans arrêt.

Généralement, la condition e instruction «
Chapitre 7 - Les fonctions et les procédures

inon » qui permet de stopper Dans

le cas contraire, la fonction ou la procédure continue à exécuter les appels récursifs.
onverger toujours vers la condition
Un processus récursif remplace en quelque sorte une boucle, ainsi tout processus
récursif peut être également formulé .

5.3. Mécanisme de fonctionnement

e, le calcul de la factorielle de 4 en appliquant la fonction
récursive FACT(). Pour calculer FACT(4), il faut calculer FACT(3). Pour calculer FACT(3),
il faut calculer FACT(2). Pour calculer FACT(2), il faut calculer FACT(1). Pour calculer
FACT(1), il faut connaître FACT(0), ce dernier vaut 1. Ensuite, on revient à rebours pour
terminer le calcul pour 1, 2, 3 puis 4.
Il y a paramètre n et que de niveaux de
récursivité. A chaque niveau, un nouvel environnement, comprenant les paramètres et les
variables locales de la fonction, est créé. Cette gestion des variables est invisible à
récursivité
[5]. Une illustration de ce mécanisme est donnée dans la figure 6.

FACT(4) = 24

6. Conclusion

Figure 7. Calcul de la factorielle par récursivité.

Chapitre 7 - Les fonctions et les procédures

6. Conclusion

La notion du sous-programme est très importante en programmation. Elle résulte de la

décomposition du programme initial en de plus petites unités ou parties réutilisables qui sont
ensuite appelées le moment opportun par le programme principal. Un sous-programme évite
la répétition inutile de code et permet de clarifier le programme. En algorithmique, un sous-
programme correspond à une fonction ou à une procédure dont la description et le
mécanisme de fonctionnement sont présentés plus haut dans ce chapitre. Aussi, une initiation
à la notion de récursivité, une des outils puissants de la programmation, a été donnée à la fin
de ce chapitre.
Chapitre 8 - Les pointeurs

Chapitre 8 - Les pointeurs

1. Introduction

une variable est déclarée et ce, quel que soit le langage de programmation, le
compilateur réserve, à une adresse donnée en mémoire,
cette variable. Donc, toute variable possède :

- Un identificateur (nom),
- Une valeur (donnée),
- Une adresse en mémoire.

exemple 2 octets pour un entier, 4 ou 8 octets pour un réel, plus encore pour une chaîne).

Exemple :

Var n : entier ; //
; // affectation de la valeur 5 à n

dans la mémoire.

Figure 8. Représentation d une variable en mémoire [10].

On peut donc accéder à une variable de deux façons :
par son identificateur,
par l'adresse mémoire à partir de laquelle elle est stockée (pointeur).
Chapitre 8 - Les pointeurs

2. Notion de pointeur
2.1. Définition
Un pointeur est une variable qui contient l adresse d une autre variable.
Le pointeur pointe sur une autre va
étant dite variable pointée. Si on obtient une adresse
qui est celle de la variable pointée, tandis que si le contenu de la variable pointée,
on obtient la valeur associée à cette dernière.
Un pointeur est une variable. De ce fait, elle doit être déclarée, dispose elle-même de sa
propre adresse en mémoire,
adresse, donc en principe
variable de type
réel devrait donc être déclaré avec un type réel [10].

Figure 9. Le pointeur et la variable pointée en mémoire [10].

Dans ce qui suit, nous décrivons comment déclarer et manipuler un pointeur avec quelques

2.2. Opérations sur les pointeurs

2.2.1. Déclaration
En algorithmique, un pointeur est déclaré comme suit :
nom_pointeur : pointeur sur type ; ou
nom_pointeur : *type ; //
Dans ce qui suit, nous utilisons la deuxième syntaxe qui est plus proche du langage C.
Chapitre 8 - Les pointeurs

Par exemple :
p : *entier ; // p est un pointeur vers un ent

2.2.2. Initialisation

aucune variable constante

symbolique NIL. Un pointeur non initialisé pointe n importe quoi dans la mémoire.
Par exemple :
p : *entier ;
p ; // p est un pointeur qui ne pointe rien

2.2.3. Accès aux données

eux opérateurs suivants :

* : opérateur unaire qui permet de déréférencer un pointeur (accéder directement à la
valeur de pointé).
& : opérateur une variable.
Il convient de noter que ces opérateurs sont les mêmes utilisés en langage C,
opérateurs peuvent être rencontrés par le lecteur tels que ^ et @
Exemple :
Algorithme Exemple_pointeur ;
Var x : entier ;
p1, p2 : *entier ;

Début
x ;
p1 ; // p1
p2 ; // p2 ne contient aucune adresse
Ecrire ("Le contenu de la variable pointé par p1 est :", *p1) ;
*p1 ; // modification de x à travers p1
Ecrire ("x=", x, "*p1=", *p1) ;
p2 ; // aff
Ecrire ("Le contenu de la variable pointé par p2 est :", *p2) ;
Fin
:
Le contenu de la variable pointé par p1 est : 3
x=5 , *p1=5
Le contenu de la variable pointé par p2 est : 5
Chapitre 8 - Les pointeurs

Remarque :

Avant toute utilisation, un pointeur doit être initialisé :

par la valeur générique NIL, par exemple ;

par l'affectation de l'adresse d'une autre variable, par exemple ;
par allocation dynamique d'un nouvel espace-mémoire.

3. Allocation dynamique

existe déjà par affectation. Il est aussi possible de réserver un emplacement mémoire pour
une donnée pointée directement. Dans ce cas, on peut créer un pointeur sur un entier par
exemple, et réserver un espace mémoire (qui contiendra cet entier) sur lequel la variable

On peut employer la syntaxe suivante :

pointeur nouveau type ;
Le type doit bien entendu être celui de la valeur qui sera contenue à
alloué. Après cette
exemple) il reçoit la valeur NIL.
Exemple :
D algorithme qui suit, un pointeur « p » sur un entier est déclaré. Pour placer une valeur
entière dans la zone
Puis on y place un entier.
Algorithme allouer ;
Var p : *entier
Début
;
;
Ecrire ("Le contenu de p est :", *p) ;
Fin
Quand une zone mémoire est allouée dynamiquement, elle reste occupée tout le temps de

du programme. Il est aussi facile de libérer un espace alloué de la mémoire dès que le ou les
pointeurs ne sont plus utiles. Pour ceci on applique la syntaxe suivante :
Libérer pointeur ;
Chapitre 8 - Les pointeurs

Exemple :
p » sur un entier est déclaré. Pour placer une valeur

et on y place un entier.
Algorithme libérer ;
Var p : *entier
Début
;
;
Ecrire ("Le contenu de p est :", *p) ;
Libérer p ;
NIL ; // réinitialiser p
Fin
Quand on libère un pointeur, on libère la zone mémoire sur laquelle il pointait, cette zone
redevient disponible pour toute autre utilisation. Après chaque libération, il est préférable de
utiliser.

faut faire attention au fait que ce pointeur pointe sur une zone éventuellement réaffectée à
autre chose. Y accéder risque de fournir une valeur arbitrai
des problèmes, voire des plantages [10].

4. Application des pointeurs

Les applications des pointeurs sont nombreuses, exemple en langage C :

- Une fonction ne peut
en

-
de faire des calculs
de suite.
-
complexes telles que listes chainées, les arbres, etc.
- ossible aussi
pointeurs où un sous-
Chapitre 8 - Les pointeurs

Exemple :
Nous reprenons dans ce qui suit le même exemple vu dans le chapitre précédent concernant
le passage de paramètres en utilisant le deuxième mode : passage par adresse.
Algorithme D ;
Var x : entier ;
Procédure Modif (px : *entier) // Procédure utilisant un pointeur comme paramètre local
Début
*px *px + 1 ; // le contenu pointé par px est modifié
Fin

Début /* Algorithme principal */

x ;
Ecrire :", x) ;
Modif (&x) ;
Ecrire :", x) ;
Fin

D peut être illustrée comme suit :

Programme Espace mémoire

Algorithme D
Début x 12
x ; :1
;
Modif (&x) ; :2
;
Fin

Procédure Modif()
Début px (&x)
*px *px + 1 ;
Fin

Lorsqu on passe l adresse d une variable à une fonction (ou à une procédure), cette dernière
peut modifier directement cette variable à travers le pointeur contenant son adresse. Donc
l accès au contenu pointé (*px) est équivalent à l accès à la variable (x) dans ce cas. La
modification se fait directement sur la variable originale. C est le passage de paramètre par
adresse.
Chapitre 8 - Les pointeurs

5. Conclusion

Dans ce dernier chapitre de la partie « cours », nous avons présenté la notion des pointeurs
avec des exemples sur leur utilisation. Le lecteur est initié aussi au mécanisme de gestion

chapitre, un survol sur les principales applications des pointeurs notamment en langage C a
été présenté dans lequel le mode de passage de paramètres par adresse a été pris comme