ÉCOLE SUPÉRIEURE DE GESTION ET

D’ADMINISTRATION DES ENTREPRISES

Agrément définitif par Arrêté n°4677/MES/CAB du 05 Juillet 2017
Accréditée par le Conseil Africain et Malgache pour l’Enseignement Supérieur
(CAMES)
BP : 2339 – Brazzaville – CONGO
E-mail : [email protected] Site web : www.esgae.org

Département Licence

Algorithme et structure des données sous

langage C++

Parcours
Licence 1 – Analyse et programmation

Enseignants
Equipe pédagogique
TITRE DE L’UE : ALGORITHME ET STRUCTURE DES DONNÉES

UE1 Elément constitutif (EC) : Algorithme et structure des données sous langage C

Volume horaire présentiel : 60 H

TPE estimé : 90 H

Niveau : LP1-AP Crédits : 6

Semestre 1 Analyse et programmation Coefficient : 4

Cours : TD : TP :

20H 40H

Objectif général :
Cet enseignement vise à mettre à la disposition de l’étudiant les outils d’analyse algorithmique, de structure
des données et de structuration de la programmation en C.

Objectifs spécifiques :
A l’issue de cet enseignement, l’étudiant doit être capable :
• d’analyser un problème donné ;
• de définir l’algorithme traduisant la solution du problème d’une manière rigoureuse ;
• de l’interpréter structurellement ;
• de l’interpréter schématiquement (ordinogramme) ;
• de maîtriser la structure d’un programme en langage C ;
• de traduire un algorithme en langage C.

Prérequis : Connaissances sur les mathématiques et la maîtrise de l’ordinateur

Méthodes pédagogiques : Cours magistral, petite révision en classe, exercices à faire à domicile, exposés à préparer,
recherche documentaire, lecture d’ouvrages et d’articles.

Evaluation :

 Sommative (DST et Examens)

 Formative en TD et du TPE (travail personnel de l’étudiant)

Contenu pédagogique :

Chapitre1 : Introduction à l’algorithmique

Section 1 : Environnement algorithmique
Section 2 : Types de données
 1

Section 3 : Structure conditionnelle

Section 4 : Structure interactive ou boucle ou instruction répétitive ou instruction itérative
Section 5 : Algorithmiques de tri
Section 6 : Algorithmique de recherche (Dichotomie)
Section 7 : Procédures et fonctions
Section 8 : Mode de passage des paramètres
Section 9 : Récursivité
Chapitre 2 : Notion de pointeur
Section 1 : Mémoire et importance dynamique
Section 2 : Listes chainées
Section 3 : Opérations sur les listes chainées
Section 4 : Listes circulaires
Section 5 : Listes bidirectionnelles
Chapitre 3 : Structure d’arbre : arbre binaire de recherche
Section 1 : Opération sur les arbres (Parcours en profondeur)
Section 2 : Piles et files
Section 3 : Recherche
Chapitre 4 : Fichiers
Section 1 : Notion des fichiers
Section 2 : Différents types de fichiers
Section 3 : Organisation et accès aux fichiers
Section 4 : Opérations sur les fichiers
Chapitre 5 : Notion de complexité
Section 1 : Notion de complexité
Section 2 : Calcul de la complexité
Chapitre 6 : Présentation de langage C
Section 1 : Structure d’un langage C
Section 2 : Structure d’un programme C
Section 3 : Types de variables
Section 4 : Déclaration des variables, instruction d’affectation et opérations d’E/S
Chapitre 7 : Instructions de contrôle
Section 1 : Instructions conditionnelles
Section 2 : Instructions de contrôles interactifs
Chapitre 8 : Fonctions et procédure en C
Section 1 : Structure d’une fonction et d’une procédure
Section 2 : Passage des paramètres
Section 3 : Quelques fonctions en C
 2

Chapitre 9 : Structure des données

Section 1 : Tableaux
Section 2 : Fichiers

Bibliographie :

 R. MAHL, 1997, Algorithmique et structures de données, Laboratoire d’Informatique Université ;

 S. BOUTIN, 1994, Algorithmes cours et exercices résolus Edition 1, Bréal ;
 Thomas H. CORMEN, 2010, Cours, exercices et problèmes. Algorithmique. Cours avec 957 exercices et 158
problèmes Edition 3, Dunod.
 3

Sommaire
Chapitre1 : Introduction à l’algorithmique ............................................................................................. 5
Section 1 : Environnement algorithmique .......................................................................................... 5
Section 2 : Types de données ............................................................................................................ 10
Section 3 : Structure conditionnelle.................................................................................................. 12
Section 4 : Structure interactive ou boucle ou instruction répétitive ou instruction itérative......... 17
Section 5 : Algorithmiques de tri....................................................................................................... 22
Section 6 : Algorithmique de recherche (Dichotomie)...................................................................... 22
Section 7 : Procédures et fonctions.................................................................................................. 24
Section 8 : Mode de passage des paramètres................................................................................... 25
Section 9 : Récursivité ....................................................................................................................... 26
Chapitre 2 : Notion de pointeur ............................................................................................................ 30
Section 1 : Mémoire et importance dynamique ............................................................................... 30
Section 2 : Listes chainées ................................................................................................................. 30
Section 3 : Opérations sur les listes chainées................................................................................... 31
Section 4 : Listes circulaires............................................................................................................... 32
Section 5 : Listes bidirectionnelles .................................................................................................... 34
Chapitre 3 : Structure d’arbre : arbre binaire de recherche ................................................................. 36
Section 1 : Opération sur les arbres (Parcours en profondeur) ........................................................ 36
Section 2 : Piles et files ...................................................................................................................... 38
Section 3 : Recherche ........................................................................................................................ 45
Chapitre 4 : Fichiers............................................................................................................................... 47
Section 1 : Notion des fichiers........................................................................................................... 47
Section 2 : Différents types de fichiers............................................................................................. 47
Section 3 : Organisation et accès aux fichiers ................................................................................... 48
Section 4 : Opérations sur les fichiers ............................................................................................... 48
Chapitre 5 : Notion de complexité ........................................................................................................ 50
Section 1 : Notion de complexité ...................................................................................................... 50
Section 2 : Calcul de la complexité ................................................................................................... 51
Chapitre 6 : Présentation de langage C ................................................................................................. 56
Section 1 : Structure d’un langage C ................................................................................................. 56
Section 2 : Structure d’un programme C.......................................................................................... 56
Section 3 : Types de variables ........................................................................................................... 58
Section 4 : Déclaration des variables, instruction d’affectation et opérations d’E/S....................... 59
Chapitre 7 : Instructions de contrôle..................................................................................................... 67
Section 1 : Instructions conditionnelles ............................................................................................ 67
 4

Section 2 : Instructions de contrôles interactifs................................................................................ 68

Chapitre 8 : Fonctions et procédure en C.............................................................................................. 73
Section 1 : Structure d’une fonction et d’une procédure ................................................................. 73
Section 2 : Passage des paramètres .................................................................................................. 74
Section 3 : Quelques fonctions en C................................................................................................. 74
Chapitre 9 : Structure des données....................................................................................................... 75
Section 1 : Tableaux........................................................................................................................... 75
Section 2 : Fichiers................................................................................................................................. 76
Bibliographie.......................................................................................................................................... 85
 5

Chapitre1 : Introduction à l’algorithmique

Section 1 : Environnement algorithmique
1.1 : Qu’est-ce que l’algorithmique ?

Un algorithme est suite finie d’opérations élémentaires constituant un schéma de

calcul ou de résolution d’un problème.

Double problématique de l’algorithmique

1. Trouver une méthode de résolution (exacte ou approchée) du problème.

– Soient trois nombres réels a, b et c, quelles sont les solutions de
l’équation ax2 + bx + c ? (Résultat bien connu.)
– Soient cinq nombres réels a, b, c, d et e, quelles sont les solutions de
l’équation ax5+bx4+cx3+dx2+ex+ f ?
2. Trouver une méthode efficace. Savoir résoudre un problème est une chose,
le résoudre efficacement en est une autre.

Différences entre algorithmes et programmes

Un programme est la réalisation (l’implémentation) d’un algorithme au moyen

d’un langage donné (sur une architecture donnée). Il s’agit de la mise en œuvre
du principe.

Algorigramme: Traduction graphique de l’algorithme. Parfois appelé

Ordinogramme ou Organigramme.

Syntaxe : Règles d’écriture d’un langage donné.

Variable : donnée manipulée par un programme et pouvant être modifiée. Elle

peut être :

- une donnée d’entrée ;

- le résultat final d’un calcul ;

- un résultat intermédiaire de calcul.

 6

Identificateur : nom explicite d’une constante, d’une variable ou d’une fonction.

Exemples : Conversion_BCD, Resultat, Lettre…

Constante : donnée manipulée par un programme et ne pouvant être modifiée.

Exemple : Constante Pi = 3.141559

1.2 : Structure générale d’un algorithme

Schéma général d’un algorithme

Un algorithme comporte généralement deux parties :

‐ Partie déclarative : elle contient l’entête, la déclaration des constantes et celle

des variables.

‐ Partie corps de l’algorithme : elle consiste en une séquence d’actions faisant

appel à des opérations de base de l’ordinateur.

Syntaxe :

Une action peut être :

→ Action d’affectation ou,

 7

→ Action d’entrée- sortie ou,

→ Action de contrôle conditionnelle simple ou à choix multiple ou,

→ Action de répétition.

1.2.1 Déclaration des constantes

Syntaxe : Constante NomConstante : [Type] = Valeur

Exemples : Constante Pi : Reel = 3.141559

Constante NombreLettres : Entier = 10

1.2.2 Déclaration des variables

Syntaxe : Variable NomVariable : [Type]

Exemples : Variable Rayon : Reel

Variable Compteur : Entier

Variable Lettre : Caractere

1.2.3 Définition de la partie principale

La partie principale consiste en une suite d’opérations élémentaires faisant

souvent appel à des fonctions ou procédures.

La partie principale est délimitée par les mots clefs Début et Fin

1.3. AFFECTATION :

Une affectation consiste à attribuer une valeur à une variable.

La syntaxe générale est la suivante : NomVariable Expression « Expression »

peut être :

 une constante. ..............................................................Ex : surface40

 une autre variable. ..............................Ex : DonneeValeurMemorisee
 le résultat d’une fonction. .............................Ex : resultatracine (nombre)
 8

 un calcul portant sur ces différents éléments. Ex :

surface(PI*Carre(Diametre)) / 4

1.4. OPERATEURS

Opérateurs

Les opérateurs permettent d’élaborer une expression en vue d’effectuer un calcul

ou une comparaison. L’usage des parenthèses est vivement conseillé dans le cas
d’expressions complexes.

Il est à noter qu'il n'existe pas de véritable standard sur la forme d'écriture
des opérateurs algorithmiques, mais seulement une tendance très prononce
pour les symboles mentionnés.

Quelques opérateurs peuvent encore s’écrire ainsi :

Les opérateurs de comparaison :

<> : Comparaison d’une différence

>= : Comparaison de plus grand ou égal

<= : Comparaison de plus petit ou égal

Les autres opérateurs:

 9

^ : Exprime la puissance d’un nombre. Exemple : 23=2^3

 : Effectue une affectation à une variable

1.5. Les instructions de lecture (entrée) et d’écriture (sortie)

Pour que l’utilisateur entre la (nouvelle) valeur du rayon, on mettra :

Lire rayon ou Saisir rayon ou Lire(rayon)…

Dès lors, aussitôt que la touche Entrée (Enter) a été frappée, l’exécution reprend.
Dans le sens inverse, pour écrire quelque chose à l’écran, c’est aussi simple que :

Ecrire Toto ou Afficher Toto ou Ecrire (Toto)…

Avant de Lire une variable, il est très fortement conseillé d’écrire des libellés à
l’écran, afin de prévenir l’utilisateur de ce qu’il doit frapper (sinon, le pauvre
utilisateur passe son temps à se demander ce que l’ordinateur attend de lui… et
c’est très désagréable !) :

Ecrire "Entrez votre nom : "

Lire NomFamille

Lecture et Ecriture sont des instructions algorithmiques qui ne présentent pas de

difficultés particulières, une fois qu’on a bien assimilé ce problème du sens du
dialogue (homme → machine, ou machine ← homme).

1.6. Les commentaires

Les commentaires permettent d’expliquer un pseudo-code pour qu’il devienne

plus compréhensible à l’utilisateur. En algorithme, il existe plusieurs types de
commentaire selon le gré de l’utilisateur par exemple :%...% , --…, /* …*/, //…
 10

Section 2 : Types de données

Un programme peut être amené à manipuler différents types de données :

- booléen : valeur pouvant être soit Vraie, soit Fausse.

- entiers : valeur numériques entières pouvant être signées ou non signées (codées
sur un ou plusieurs octets).

- réels : valeurs numériques codées avec une mantisse et un exposant.

- caractère : octet correspondant à un code ASCII (American Standard Code for

Information Interchange).

- chaîne de caractères : ensemble de caractères.

- tableau de données : ensemble de données de même type (exemple : tableau

d’entiers, tableau de réels).

Exercice 1.1 :

Ecrire un algorithme qui lit le prix HT d’un article, le nombre d’articles et le taux
de TVA, et qui fournit le prix total TTC correspondant. Faire en sorte que des
libellés apparaissent clairement.

Solution 1.1 :

Algorithme Calcul_du_pttc

Variables nb, pht, ttva, pttc : Réels

Début

Ecrire "Entrez le prix hors taxes :"

Lire pht

Ecrire "Entrez le nombre d’articles :"

Lire nb
 11

Ecrire "Entrez le taux de TVA :"

Lire ttva

pttc ← nb * pht * (1 + ttva)

Ecrire "Le prix toutes taxes est : ", pttc

Fin

Exercice 1.2 :

Ecrire un algorithme qui demande un nombre à l’utilisateur, puis qui calcule et

affiche le carré de ce nombre.

Solution 1.2 :

Algorithme Calcul_du_carré

Variable

nb, carr : Entier

Début

Ecrire "Entrez un nombre :"

Lire nb

carr ← nb * nb

Ecrire "Son carré est : ", carr

Fin

Exercice 1.3 :

Ecrire un algorithme utilisant des variables de type chaîne de caractères, et

affichant quatre variantes possibles de la célèbre « belle marquise, vos beaux yeux
me font mourir d’amour ». On ne se soucie pas de la ponctuation, ni des
majuscules.
 12

Solution 1.3 :

Algorithme Affichage_caractères

Variables t1, t2, t3, t4 : Chaîne de caractères

Début

t1 ← "belle Marquise"

t2 ← "vos beaux yeux"

t3 ← "me font mourir"

t4 ← "d’amour"

Ecrire t1 & " " & t2 & " " & t3 & " " & t4

Ecrire t3 & " " & t2 & " " & t4 & " " & t1

Ecrire t2 & " " & t3 & " " & t1 & " " & t4

Ecrire t4 & " " & t1 & " " & t2 & " " & t3

Fin

Section 3 : Structure conditionnelle

3.1.1 Structure SI ... ALORS ...

Une condition est testée pour déterminer si l’action ou le groupe d’actions suivant
doit être exécuté.

Exemple : Calcul d’une racine carrée

Algorithme Racine_carrée
 13

Variables

x: réel ~ opérande ~

r: réel ~ résultat de la racine carrée ~

Début

Afficher (‘’Saisir le nombre x’’)

Saisir (x)

Si x > 0 Alors

r racine (x)

afficher(r)

FinSi

Fin

3.1.2 Structure SI ... ALORS ...SINON ...

Exemple : Calcul d’une racine carrée

Variables

x: réel ~ opérande ~

r: réel ~ résultat de la racine carrée ~

Début

Afficher (‘Saisir le nombre x‘)

 14

Saisir (x)

Si x < 0

Alors

afficher (‘x est négatif’)

Sinon

r racine (x)

afficher(r)

FinSi

Fin

3.1.3 Tests imbriqués

Répétition de plusieurs si est appelée si imbriquée.

Exemple 3.1:

Variable Temp en Entier

Début

Ecrire “Entrez la température de l’eau :”

Lire Temp

Si Temp <= 0

Alors Ecrire “C’est de la glace“

Sinon Si Temp < 100

Alors Ecrire “C’est du liquide”

Sinon Ecrire “C’est de la vapeur”

Finsi
 15

Finsi

Fin

Exemple 3.2:

Variable Temp en Entier

Début Ecrire “Entrez la température de l’eau :”

Lire Temp

Si Temp =< 0 Alors Ecrire “C’est de la glace“

Finsi

Si Temp > 0 Et Temp < 100

Alors Ecrire “C’est du liquide”

Finsi

Si Temp > 100

Alors Ecrire “C’est de la vapeur”

Finsi

Fin

3.2 Structures conditionnelles à choix multiple ou structure sélective selon

Lorsque l’imbrication des alternatives devient importante, l’utilisation de la

structure à choix multiple devient nécessaire.
Selon Sélecteur Faire
Syntaxe :
Valeur 1 : Instruction1
Cas variable Vaut
Valeur 2 : Instruction2
Valeur1 : Instruction1 …:…

Valeur2 : Instruction2 Valeur n : Instruction n

Ou bien Sinon : Autre instruction
FinSelon
 16

…:…

Valeur n : Instruction n

Sinon : Autre instruction

FinCas

Exemple : Ecrire un algorithme, qui permet de lire un produit et d’afficher le prix

de ce produit en kg de FCFA, sinon l’algorithme affiche que ce produit n’existe
pas. On donne :

Boucheries en ligne
Produits Prix par kg (FCFA)
Cuisses 700
Rognons 800
Oignons 500

Solution :

Algorithme Prix_produit

Variable

Produit : Chaine de caractères

Début

Ecrire(‶Veuillez entrer un produit : ″)

 17

Lire(Produit)

Cas Produit vaut

‶Cuisses″ : Ecrire(‶Le prix d’un kg est : 700 FCFA″)

‶Rognons″ : Ecrire(‶Le prix d’un kg est : 800 FCFA″)

‶Oignons″ : Ecrire(‶Le prix d’un kg est : 500 FCFA″)

Sinon : Ecrire(‶Ce produit n’existe pas″)

Fin Cas

Fin

Section 4 : Structure interactive ou boucle ou instruction répétitive ou instruction itérative

4-Définition

Une boucle permet de répéter le même traitement plusieurs fois.

4-1. Boucle TantQue

Organigramme :
Syntaxe :

TantQue <Condition>

<Liste des instructions >

FinTantQue

N.B : Pour exécuter la boucle TantQue, il faut spécifier 3 traitements de base :

 Initialisation du compteur ;
 18

 Spécification de la condition
 Changement de la valeur du compteur

Exemple : Ecrire un algorithme, qui permet de lire le nombre de répétitions que

vous voulez afficher le mot « Bonjour »

Solution :

Algorithme Bonjour

Variables

n,i : Entier

Début

Ecrire(‶Veuillez entrer le nombre de répétitions : ″)

Lire(n)

i0

TantQue i<n

Ecrire(‶Bonjour ″)

ii+1

FinTantQue

Fin

4-2. Boucle Pour

Pour cette boucle, les 3 traitements de base, évoqués précédemment s’exécutent

dans une seule ligne.

Syntaxe :
 19

Pour CompteurValeur_initiale à Valeur_finale Pas ValeurDuPas

<Liste des instructions>

FinPour

Organigramme :

Exemple : Ecrire un algorithme qui demande un nombre de départ, et qui ensuite

écrit la table de multiplication de ce nombre, présentée comme suit (cas où
l'utilisateur entre le nombre 7) :

Table de 7 :

7x1=7

7 x 2 = 14

7 x 3 = 21

7 x 10 = 70

Solution :
 20

Algorithme Table_Multi

Variables N, i : Entier

Début

Ecrire "Entrez un nombre : "

Lire N

Ecrire "La table de multiplication de ce nombre est : "

Pour i ← 1 à 10 Pas 1

Ecrire N, " x ", i, " = ", n*i

Fin

4-3. Répéter…Jusqu’à

La structure Répéter est une structure itérative, qui permet d’exécuter au moins
une itération avant de vérifier la condition.

Syntaxe :

Répéter

<Liste des instructions>

Jusqu’à <Condition>

Organigramme :
 21

Exemple : Ecrire un algorithme qui permet de calculer la division de c=a/b

lorsque b est différent de 0 en lisant a et b. Si b=0, alors ça reprend la lecture.

Solution :

Algorithme Division

Variables a, b, c : Réel

Début

Ecrire "Entrez le nombre a: "

Lire a

Répéter

Ecrire "Entrez le nombre b: "

Lire b

Jusqu’à b<>0

ca/b

Ecrire(a, " /", b, " = ", c)

Fin
 22

En résumé :

 Structure Pour : quand on connaît d’avance le nombre d’itérations à

exécuter ;
 Structure TantQue : quand on ne connaît pas le nombre d’itérations à
exécuter ;
 Structure Répéter : Quand la condition dépend d’un traitement, qui doit
s’exécuter au moins une fois.

Section 5 : Algorithmiques de tri

 Tris élémentaires
 Tri par insertion
 Tri par sélection
 Tri par permutation
 Tris avancés
 Tri Fusion
 Tri rapide

(Voir TP pour la suite)

Section 6 : Algorithmique de recherche (Dichotomie)

Problème : Déterminer la première position d’une valeur donnée dans un tableau
de N élément

Triés : dans le sens croissant. Résoudre ce problème en utilisant la notion de

procédures/Fonctions.

Principe :

Le principe est de décomposer le tableau T en deux sous tableaux. Trois cas

peuvent se produire :

Si val = T[milieu] alors val est trouvé et la recherche est terminée.

Si val < T[milieu] alors on va chercher val dans la partie gauche du tableau
T.

Si val > T[milieu] alors on va chercher val dans la partie droite du tableau T.
 23

On poursuit la recherche tant que T[milieu] est différent de val est tant que la
dimension de sous tableau reste valide.

Fonction Dichotomique (T : tab ; N, val ) : Entier

VAR

i, pos,mil, inf, sup : entier

DEBUT

pos← -1

inf← 1

sup← N

Tant que ( inf ≤ sup et pos = -1 ) Faire

mil ← (inf + sup)/2

Si (T[mil] = val ) alors

pos = mil

Sinon Si (val<T[mil]) alors

sup ← mil-1

sinon

inf ← mil+1

finsi

Finsi

FinTantque

INDICE←pos

FIN
 24

Section 7 : Procédures et fonctions

Les procédures et fonctions peuvent nécessiter éventuellement un ou plusieurs
paramètres d’entrée ou de sortie.

Un paramètre d’entrée est la référence à une variable manipulée par la procédure

ou la fonction.

Un paramètre de sortie est une valeur renvoyée par une fonction.

Une fonction ou une procédure peut elle-même appeler une ou plusieurs fonctions
et procédures.

Syntaxe de la déclaration d’une procédure :

Procédure NomProcédure (NomEntrée1 : [Type], NomEntrée2 : [Type],…)

Constante ~ déclaration des constantes locales ~

Variable

~ déclaration des variables locales ~

Début

~ description des actions effectuées par la procédure ~

Fin

Syntaxe de l’appel d’une procédure :

NomProcédure (NomEntrée1, NomEntrée2…)

Syntaxe de la déclaration d’une fonction :

Fonction NomFonction (NomEntrée1 : [Type], NomEntrée2 : [Type],…) :

[TypeDuRésultat]

Constante ~ déclaration des constantes locales ~

 25

Variable

~ déclaration des variables locales ~

Début

~ description des actions effectuées par la fonction ~

Fin

Syntaxe de l’appel d’une fonction :

Variable NomFonction (NomEntrée1, NomEntrée2…)

Exemples d’appels de fonctions et procédures :

Procédure sans paramètre : ....................................Ex : Effacer_Ecran

Procédure avec un paramètre d’entrée : .......................................... Ex : Afficher

(‘Bonjour’)

Fonction avec paramètres d’entrée et de sortie : ........ Ex : Resultat Racine (69)

Exemple de déclaration de fonction :

Fonction Moyenne (Note1 : Reel, Note2 : Reel) : Reel

Variable Intermediaire : Reel

Début

Intermediaire Note1 + Note2

Intermediaire Intermediaire / 2

Moyenne  Intermediaire

Fin

Section 8 : Mode de passage des paramètres

L’échange de données entre sous-programmes peut se faire par le partage de
variables globales ou par les variables locales passées comme paramètres.
 26

Il existe plusieurs types de passage de paramètres :

 Par adresse ou par variable

 Par valeur
 Par nom

Section 9 : Récursivité
Une des caractéristiques les plus importantes de programmation est la possibilité
pour une procédure ou une fonction de s’appeler elle-même. On parle de
récursivité. La récursivité est particulièrement utile pour traiter tous les
problèmes formalisables de façon récursive, bien qu’il soit possible de
programmer des solutions n’utilisant pas la récursivité pour ces problèmes.
Syntaxe :

Etude d’un exemple :

On peut définir le factoriel d’un nombre n non négatif de 2 manières.

Définition non récursive :

N ! = N * N-1 * ………. 2 * 1

Définition récursive :

N ! = N * (N – 1) ! et 0 ! = 1

Solution itérative :
 27

Fonction FACT ( n : entier ) : entier

VAR

i, F: entier

DEBUT

Si (n = 0 ) alors

FACT← 1

Sinon F← 1

Pour i de n à 1 (pas = -1 ) faire

F←F * i

Finpour

FACT←F

Finsi

FIN

Solution récursive :

Fonction FACT ( n : entier ) : entier

VAR

F : entier

DEBUT Si (n = 0 ) alors

F←1

Sinon

F←n * FACT (n-1)

Finsi
 28

FACT←F

FIN

/* PROGRAMME PRINCIPAL*/

DEBUT ( P.P )

Répéter

Ecrire ("Donner un entier n : ")

Lire ( n )

Jusqu’à (n ≥ 0 )

Écrire ("La factorielle de ", n , " = " , FACT ( n ))

FIN

Interprétation

Chaque procédure ou fonction récursive doit comporter une condition d’arrêt

(dans notre exemple n=0). Cette condition empêche des appels récursifs sans fin.
Habituellement, la condition d’arrêt se présente sous la forme d’une instruction
si…… alors……sinon qui permet de stopper la récurrence si la condition d’arrêt
est satisfaite. Par contre, tant que la condition d’arrêt n’est pas remplie, la
procédure (ou la fonction) s’appelle au bon endroit.

On remarque que le processus récursif remplace en quelque sorte la boucle. On

remarque aussi qu’on traite le problème à l’envers : on part du nombre, et on
remonte à rebours jusqu’à 1 pour pouvoir calculer la factorielle. Cet effet de
rebours est caractéristique de la programmation récursive.

Pour la solution récursive : La fonction FACT est appelée successivement, une

fois dans le programme principal et (N-1) façon depuis elle-même, de façon
 29

totalement transparente pour l’utilisateur. Le seul résultat visible est la réponse

finale. Lorsque s’exécute un programme récursif, les appels successifs de la
fonction (ou procédure) récursive ne sont pas exécutés immédiatement. Ils sont
de faits placés dans une pile jusqu’à ce que soit atteinte la condition d’arrêt du
processus récursif.

Les appels de fonction sont alors exécutés en ordre inverse, au fur et à mesure
qu’ils sont retirés de la pile.

Une pile est une structure de données de type LIFO (Last In, First Out) ou «
Dernier Entré, Premier Sorti »
 30

Chapitre 2 : Notion de pointeur

Section 1 : Mémoire et importance dynamique
La plupart des langages de programmation offrent la possibilité d'accéder aux
données dans la mémoire de l'ordinateur à l'aide de pointeurs, c.-à-d. à l'aide de
variables auxquelles on peut attribuer les adresses d'autres variables. Un pointeur
possède une technique de programmation très puissante, permettant de définir des
mémoires dynamiques, c'est-à-dire qui évoluent au cours du temps.

Section 2 : Listes chainées

Le principe de base des listes est le type pointeur. Une variable de type pointeur
est une variable dont le contenu est une adresse qui peut indiquer l'emplacement
en mémoire d'une autre variable, créée dynamiquement et ayant un type de base
précis.

Note: Quand une variable pointeur ne pointe sur aucun emplacement, elle doit
contenir la valeur Nil (qui est une adresse négative)

Si une structure contient une donnée avec un pointeur vers un élément de même
composition on parle lors de liste chaînée.

Une liste chaînée est donc une structure de données dans laquelle les éléments
sont rangés linéairement. Chaque élément (dit nœud) est lié à son successeur. Il
est donc impossible d'accéder directement à un élément quelconque de la liste
(sauf le premier auquel on accède via un pointeur –généralement appelé tête de
liste).

Tête est le pointeur avec l’adresse du premier élément alors que chaque nœud est
un enregistrement avec une case (ici Info) pour la valeur à manipuler (12, 25, -4
et 11) et une case (ici Suiv) de type pointeur avec l’adresse où se trouve l’élément
suivant.
 31

Bien évidemment, cette linéarité est purement virtuelle. A la différence du

tableau, les éléments n'ont aucune raison d'être voisins ni ordonnés en mémoire.

Les listes ont l'avantage d'être réellement dynamiques, c'est dire que l'on peut à
loisir les rallonger ou les raccourcir, avec pour seule limite la mémoire disponible.

II- 1- Déclaration d’une liste

Type P = ^Element

Element = Enregistrement

Info : Type-C ;

Suiv : ^Element

Fin ;

Note: Cette déclaration est toujours valable sauf qu’il faut à chaque fois préciser
Type-C selon le type des données manipulées.

Section 3 : Opérations sur les listes chainées

La création d’une liste, le parcours d’une liste ainsi que l’ajout et la suppression
d’un élément sont les principales opérations effectuées sur les listes.

A- Création d’une liste

La création d’une liste revient à des ajouts (insertions) répétitifs de nœuds qui
vont la constituer. L’opération commence cependant à partir d’une liste vide
(il est donc essentiel d’affecter le Nil à la tête avant de commencer). Pour
insérer un nouveau élément il est faut d’abord réserver un espace pour ce
nœud. L’opération est possible via la procédure prédéfinie ALLOUER (p) qui
permet de repérer un espace suffisant pour le nœud (Partie donnée et pointeur
de l’élément qui va suivre). L’espace trouvé, son adresse dans la mémoire est
sauvegardée dans la variable pointeur p.

B- Parcours d’une liste

 32

Les cases d’un tableau sont numérotées successivement. Le parcours dans

un tableau revient alors à initialiser un indice de parcours à 1 (se placer au
niveau de la première case) puis d’incrémenter cet indice à chaque fois pour
passer d’une case à une autre.
Les éléments d’une liste ne sont pas numérotés mais reconnus par leurs
adresses (l’adresse de chaque élément étant sauvegardée dans la tête de la
liste si c’est le premier sinon dans la partie pointeur de l’élément qui le
précède). Le parcours d’une liste revient alors à initialiser un pointeur à la
valeur de la tête de liste puis de lui affecter à chaque déplacement l’adresse
se trouvant dans la partie pointeur de l’enregistrement jusqu’à ne plus avoir
d’élément suivant :
Pt tete ;
Tantque Pt ≠ Nil Faire
Pt Pt^. Suiv
FinTantque ;
Note : La condition d’arrêt change lorsque l’on veut s’arrêter pus tôt que
la fin de liste. Exemple : si l’on veut se placer au niveau du dernier élément
pour réaliser un quelconque traitement sur lui la condition serait alors :
Tantque Pt^.suiv ≠ Nil Faire
C- Ajout d’un élément

On peut ajouter (insérer) un élément en début de liste (il deviendra le nouveau

premier), en fin de liste (il deviendra le dernier) ou encore en milieu de liste
(entre deux éléments)

Section 4 : Listes circulaires

Une liste est dite circulaire si le dernier nœud de cette liste nous remet au premier
nœud de cette liste ; c.-à-d. que la case pointeur du dernier élément ne contient
pas Nil mais l’adresse du premier élément.
 33

L’absence du Nil dans la liste implique des conditions d’arrêt en rapport avec la
tête de liste. Il s’avère alors nécessaire de ne pas traiter tous les "n" éléments de
la liste dans la même boucle mais plutôt de traiter "n-1" éléments ensemble et de
répéter le traitement pour le nœud qui n’a pas été traité.

Note: L’élément à traiter seul peut être le premier de liste (et avoir une boucle de
traitement du 2ème au dernier élément) ou le dernier nœud de la liste (traiter du
1er à l’avant dernier élément dans la boucle puis réécrire le traitement pour le
dernier nœud.)

Exemple : Ecrire une fonction qui calcul le nombre de zéro dans une liste
d’entiers. La liste est supposée déjà lue.

Solution :

Fonction calcul (L : PX) : entier ;

Variable

Pt : PX ;

Co : Entier ;

Debut

Co 0 ;

PtL ;

Tantque Pt^. Suiv ≠ L Faire /* Traitement des N-1 premiers nœuds ensemble*/
Debut

Si Pt^.Info = 0 Alors
 34

CoCo + 1

FinSi ;

PtPt^. Suiv

Fin

FinTantque ;

Si Pt^.Info = 0 Alors /* Traitement du dernier nœud seul*/

CoCo + 1

FinSi ;

Calcul Co ;

Fin ;

Section 5 : Listes bidirectionnelles

Si l'on désire souvent pouvoir atteindre des éléments d'une chaîne qui se trouvent
quelques positions avant un élément donné, on peut alors adjoindre, à chaque
élément, un pointeur supplémentaire vers son prédécesseur. On obtient alors une
chaîne bidirectionnelle :

Manipulations sur les chaînes bidirectionnelles

Insertion en début:

type VersElement = ^Element;

Element = record Info: ...;

Precedent,
 35

Suivant : VersElement;

end; { Element }

procedure Insertion

Debut(var Debut: VersElement;Information: ...);

var Nouveau: VersElement;

begin { InsertionDebut }

new(Nouveau);

with Nouveau^ do begin Info := Information;

Suivant := Debut; Precedent := nil;

end;

{ with }

if Debut <> nil then

Debut

^.Precedent := Nouveau;

Debut := Nouveau; end; { InsertionDebut }

 36

Chapitre 3 : Structure d’arbre : arbre binaire de recherche

Section 1 : Opération sur les arbres (Parcours en profondeur)
Il existe plusieurs opérations possibles sur les arbres :

- Création d’un arbre : définir en arbre vide

- Ajout d’un élément : ajouter un fils au nœud

- Suppression d’un élément : suppression un fils au nœud

- Récupération d’un élément : récupération des informations du nœud - Recherche

d’une information : pour valider son existence dans l’arbre ou non

- Suppression d’un arbre : suppression complète de l’arbre

- Calcul de la hauteur d’un arbre : se base sur la définition récursive un arbre vide
est de hauteur 0 et un arbre non vide a pour hauteur 1 + la hauteur maximale entre
ses fils.

- Calcul du nombre de nœuds : fait selon la règle Si l'arbre est vide : renvoyer 0 ;
Sinon renvoyer 1 plus la somme du nombre de nœuds des sous arbres.

- Calcul du nombre de feuilles : sachant qu’un arbre vide n'a pas de feuille et qu’un
arbre non vide à son nombre de feuille défini de la façon suivante : si le nœud est
une feuille alors on renvoie 1, si c'est un nœud interne alors le nombre de feuille
est la somme du nombre de feuille de chacun de ses fils.

- Calcul du nombre de nœuds internes : selon la règle récursive : un arbre vide n'a
pas de nœud interne ; si le nœud en cours n'a pas de fils alors renvoyer 0 ; si le
nœud a au moins un fils, renvoyer 1 plus la somme des nœuds interne des sous
arbres.

- Parcours d’un arbre : c’est l’opération de visiter tous les nœuds de l'arbre

 En profondeur : permet d'explorer l'arbre en explorant jusqu'au bout une

branche pour passer à la suivante
 37

 En largeur (par niveau) : permet d'explorer l'arbre niveau par niveau.

C'est à dire que l'on va parcourir tous les nœuds du niveau 1 puis ceux du
niveau deux et ainsi de suite jusqu'à l'exploration de tous les nœuds.
 Pour les arbres binaires en particulier, on parle de parcours postfixe,
infixe et préfixe

- Transformation d’un arbre quelconque en arbre binaire

Exemple :

Soit l'arbre suivant :

La taille de cet arbre est de 10

L’arité est de 2 donc c’est un arbre binaire

La hauteur de cet arbre est 3

Le parcours en profondeur donne : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Le parcours en largeur de l'arbre suivant est : 1, 2, 8, 3, 6, 9, 10, 4, 5, 7.

Le parcours postfixe est : 4, 5, 3, 7, 6, 2, 9, 10, 8, 1 (Fils Gauche/ Fils Droit/ Père)

Le parcours en infixe est : 4, 3, 5, 2, 7, 6, 1, 9, 8, 10 (Fils Gauche/ Père / Fils Droit)
et Le parcours en préfixe donne : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (Père /Fils Gauche/
Fils Droit)
 38

Section 2 : Piles et files

Les piles et files ne sont pas de nouveaux types de données mais plutôt une
manière de gérer un ensemble de données. Elles sont très souvent utiles et servent,
entre autres, à mémoriser des évènements en attente de traitement. Il n'y a pas de
structures spécifiques prévues dans les langages de programmation pour les piles
ou files. Il faut donc les créer de toute pièce sachant que la représentation en
mémoire de ces structures de données peut être, selon le besoin, statique
(utilisation des tableaux) ou dynamique (utilisation des listes).

I- Pile

Quand on vous dit pile penser directement à une pile d’assiettes qu’il faut
manipuler avec attention pour éviter les dégâts. Une pile est un ensemble de
valeurs ne permettant des insertions ou des suppressions qu’a une seule
extrémité, appelée sommet de la pile. Empiler un objet sur une pile P consiste
à insérer cet objet au sommet de P (dans la pile d’assiettes une nouvelle assiette
ne peut être ajoutée qu’au-dessus de celle qui se trouve au sommet) ; Dépiler
un objet de P consiste à supprimer de P l'objet placé au sommet (dans la pile
d’assiettes seule peut être retirée celle qui se trouve au sommet). L'objet dépilé
est retourné comme résultat du traitement.

Une propriété remarquable des piles est qu'un objet ne peut être dépilé qu'après
avoir dépilé tous les objets qui sont placés "au-dessus" de lui, ce qui fait que
les objets quittent la pile dans l'ordre inverse de leur ordre d'arrivée. Pour cette
 39

raison, une pile est aussi appelée structure LIFO (Last In, First Out) ou (dernier
arrivé, premier sorti) En informatique une pile sert essentiellement à stocker
des données qui ne peuvent pas être traitées immédiatement, car le programme
a une tâche plus urgente ou préalable à accomplir auparavant. En particulier
les appels et retours de fonctions sont gérés grâce à une pile appelée pile
d'exécution.

En termes de programmation, une pile est un enregistrement avec :

- Une structure de données pour enregistrées les valeurs (elle peut être statique
ou dynamique)

- Une variable sommet qui indique le sommet de la pile.

La manipulation d’une pile revient à l’appel de fonctions et procédures dites

de bases définies une seule fois et utilisées autant de fois qu’il est nécessaire.
Ces sous-algorithmes sont :

- Init_Pile : permet d’initialiser une pile à vide lors de sa création ;

- Pile_vide : pour vérifier si une pile est vide ou non et savoir alors s’il reste
des valeurs à traiter ou non ;

- Pile_pleine : pour vérifier s’il est possible de rajouter ou non un nouveau

élément (utilisée dans le seul cas des piles statiques) ;

- Empiler : permet d’ajouter une nouvelle valeur (envoyé en paramètre par

l’appelant) à la pile (au-dessus du sommet et dans le cas d’une pile non pleine)
;

- Depiler : permet de supprimer une valeur (se trouvant au sommet de la pile)

et de la renvoyer en paramètre. Cette opération n’est possible que si la file n’est
pas vide.

I-1- Pile statique

 40

Une pile statique est un enregistrement à 2 cases :

un tableau à hauteur maximale prévisible et un indice entier qui pointe la

dernière valeur ajoutée à la pile (sommet).

I-1-1- Déclaration

Constante

N = …. ; /* taille du tableau*/

Type Tab = Tableau de N Type_C ; /* Type_C est le type des données

enregistrées dans la pile*/

Pile = Enregistrement

T : Tab ;

Sommet : Entier

Fin ;

Note : Les données enregistrées dans la pile peuvent être des entiers, des réels,
des caractères, des chaînes de caractères, des booléens, des tableaux, des
pointeurs de listes ou encore des piles ou files.

I-1-2- Initialisation d’une pile

Procedure Init_Pile (Var P : Pile) ;

Debut

P. Sommet  0
 41

Fin ;

I-1-3- Vérification de pile vide

Fonction Pile_vide (P : Pile) : Booleen ;

Debut

Si P. Sommet = 0 Alors

Pile_videvrai

Sinon

Pile_videfaux

FinSi ;

Fin ;

Une autre façon plus compacte d’écrire cette fonction est la suivante :

Fonction Pile_vide (P : Pile) : Booleen ;

Debut

Pile_videP. Sommet = 0;

Fin ;

Le nom de la fonction recevra le résultat de la comparaison (vrai ou faux) entre

le sommet et le zéro.

II- File

Quand on vous dit file penser directement à une file d’attente où chacun à son
tour qu’il doit respecter.
 42

Une file est un ensemble de valeurs qui a un début (Debut) et une fin (Queue).
Enfiler un objet sur une file F consiste à insérer cet objet à la fin de la file F
(dans la file d’attente un nouvel arrivant se met à la queue c.-à-d., après la
personne arrivée juste avant lui) ;

Défiler un objet de F consiste à supprimer de F l'objet placé en début de file

(dans la file d’attente seule peut être servie la personne qui se trouve en début
de file). L'objet défilé est retourné comme résultat du traitement. En
informatique une file sert essentiellement à stocker des données qui doivent
être traitées selon leur ordre d’arrivée. L’exemple le plus connu est celui de
l’impression de documents reçus par une imprimante qui imprime le premier
document arrivé et termine par le dernier. Ce qui fait que les objets quittent la
pile dans l'ordre de leur ordre d'arrivée. Pour cette raison, une file est aussi
appelée structure FIFO (First In, First Out) ou (premier arrivé, premier sorti)
En termes de programmation, une file est un enregistrement avec :

- Une structure de données pour enregistrées les valeurs (elle peut être statique
ou dynamique)

- Une variable Debut qui indique le premier élément de la file.

- Une variable Queue qui indique le dernier élément de la file. Comme pour
les piles, la manipulation d’une file revient à l’appel de fonctions et procédures
dites de bases définies une seule fois et utilisées autant de fois qu’il est
nécessaire. Ces sous-algorithmes sont :
 43

- Init_File : permet d’initialiser une file à vide lors de sa création ;

- File_vide : pour vérifier si une file est vide ou non et savoir alors s’il reste
des valeurs à traiter ou non ;

- File_pleine : pour vérifier s’il est possible de rajouter ou non un nouveau

élément (utilisée dans le seul cas des files statiques) ;

- Enfiler : permet d’ajouter une nouvelle valeur (envoyé en paramètre par

l’appelant) à la file (après le dernier élément de la file qui se trouve au niveau
de sa queue et dans le cas d’une file non pleine) ;

- Defiler : permet de supprimer une valeur (se trouvant au début de la file) et

de la renvoyer en paramètre. Cette opération n’est possible que si la file n’est
pas vide.

II-1- File statique

Une file statique est un enregistrement à 3 cases : un tableau à hauteur

maximale prévisible, un indice entier qui pointe le premier élément insérer
dans la file (Debut) et un deuxième indice entier qui pointe la dernière valeur
ajoutée (Queue).

Exemples : Sachant que le tableau est indicé de 1 à N et pour une gestion

simpliste des files :

1- Une file à un seul élément Debut = 1 et Queue = 1

2- Une file à 3 éléments Debut = 1 et Queue = 3

3- une file qui vient d’être déclarée (et non encore utilisée)Debut = 1 et
Queue = 0

4- une file complètement vidée → Debut = Queue +1

II-1-1- Déclaration

Constante N = …. ; /* taille du tableau*/

 44

Type

Tab = Tableau de N Type_C ;

/* Type_C est le type des données enregistrées dans la pile*/

File = Enregistrement T : Tab ;

Debut, Queue : Entier

Fin ;

Note : Les données enregistrées dans la pile peuvent être des entiers, des réels,
des caractères, des chaînes de caractères, des booléens, des tableaux, des
pointeurs de listes ou encore des piles ou files.

! Dans certain langages de programmation le nom "File" désigne un type de

données appelé fichier. Dans ce cas ne pas utiliser ce terme comme identifiant
de la file.

II-1-2- Initialisation d’une file

Procedure Init_File (Var F : File) ;

Debut

F. Debut 1 ;

F. Queue0

Fin ;
 45

II-1-3- Vérification de File vide

Fonction File_vide (F : File) : Booleen ;

Debut

Si F. Debut > F. Queue Alors

File_videvrai

Sinon File_videfaux

FinSi ;

Fin ;

Une autre façon plus compacte d’écrire cette fonction est la suivante :

Fonction File_vide (F : File) : Booleen ;

Debut File_vide F. Debut > F. Queue ;

Fin ;

Le nom de la fonction recevra le résultat de la comparaison (vrai ou faux) entre

les indices début et Queue

Section 3 : Recherche
Principe

La recherche d’une valeur dans un ABR consiste, en partant de la racine, à

parcourir une branche en descendant chaque fois sur le fils gauche ou sur le fils
droit selon que la clé portée par le nœud est plus grande ou plus petite que la valeur
cherchée. La recherche s’arrête dès que la valeur est rencontrée ou que l’on a
atteint l’extrémité d’une branche (le fils sur lequel il aurait fallu descendre
n’existe pas).
 46

Algorithme de recherche

Recherche d’une valeur k à partir d’un nœud x d’un ABR :

ABRRecherche(x,k)

Début

Si x = Nil

Alors Retourner Faux

Sinon Si k = cle(x)

Alors Retourner Vrai

Sinon Si k < cle(x)

Alors Retourner ABRRecherche(gauche(x),k)

Sinon Retourner ABRRecherche(droit(x),k)

FinSi

Fin
 47

Chapitre 4 : Fichiers
Section 1 : Notion des fichiers

Section 2 : Différents types de fichiers

Il existe deux types de fichiers :

 Fichiers textes ;
 Fichiers binaires ;
 48

Section 3 : Organisation et accès aux fichiers

Section 4 : Opérations sur les fichiers

Les procédures sur les fichiers

 49

Fonction de test de fin de fichier

 50

Chapitre 5 : Notion de complexité

Section 1 : Notion de complexité
Déterminer la complexité d’un algorithme, c’est évaluer les ressources
nécessaires à son exécution (essentiellement la quantité de mémoire requise) et le
temps de calcul à prévoir. Ces deux notions dépendent de nombreux paramètres
matériels qui sortent du domaine de l’algorithmique : nous ne pouvons attribuer
une valeur absolue ni à la quantité de mémoire requise ni au temps d’exécution
d’un algorithme donné. En revanche, il est souvent possible d’évaluer l’ordre de
grandeur de ces deux quantités de manière à identifier l’algorithme le plus efficace
au sein d’un ensemble d’algorithmes résolvant le même problème. Prenons un
exemple concret : la détermination du nombre de diviseurs d’un entier naturel n.
Une première solution consiste à essayer si chacun des entiers compris entre 1 et
n est un diviseur de n. Ceci conduit à définir la fonction diviseurs1 des images ci-
dessous :

Sur ces images, nous avons deux fonctions calculant le nombre de diviseurs d’un
entier n.

Mais on peut aussi se faire la réflexion suivante : si d ∈ ⟦1, ⟧divise n alors =

aussi ; de plus, d≤ √ ⇐⇒ ≥ √ . Autrement dit, il suffit de rechercher les

diviseurs de n qui sont inférieurs ou égaux à √ n pour en connaitre le nombre total

: c’est le principe utilisé par la fonction diviseurs2 (on notera le traitement
particulier réservé aux carrés parfaits). Comment comparer ces deux versions ? Si
on se focalise sur les deux boucles conditionnelles de ces algorithmes on constate
 51

que dans les deux cas on effectue deux additions, une division euclidienne et un
test. Chacune de ces opérations est effectuée n fois dans le premier cas, √ n fois
dans le second. Nous ne connaissons pas le temps τ1 nécessaire à la réalisation de
ces différents calculs, mais on peut légitimement penser que le temps total
d’exécution de diviseurs1 n’est pas éloigné de τ1n + τ2, le temps τ2 étant le temps
requis par les autres opérations. De même, le temps requis par la fonction
diviseurs2 est de l’ordre de τ’1 √ n + τ’2 . Les temps τ2 et τ’2 sont négligeable
pour de grandes valeurs de n ; de plus les valeurs de τ1 et τ’1 importent peu ; elle
dépend de conditions matérielles qui nous échappent. Nous n’allons retenir que le
taux de croissance de chacune de ces deux fonctions : proportionnel à n pour la
première (on dira plus loin qu’il s’agit d’un algorithme de coût linéaire),
proportionnel à √ n pour la seconde. Autrement dit :

– multiplier n par 100 multiplie le temps d’exécution de diviseurs1 par 100 ;

– multiplier n par 100 multiplie le temps d’exécution de diviseurs2 par 10.

Ainsi, connaissant le temps d’exécution pour une valeur donnée de n il est

possible d’évaluer l’ordre de grandeur du temps d’exécution pour de plus grandes
valeurs.

Section 2 : Calcul de la complexité

2.1 Instructions élémentaires

Pour réaliser l’évaluation de la complexité algorithmique, il est nécessaire de

préciser un modèle de la technologie employée ; en ce qui nous concerne, il
s’agira d’une machine à processeur unique pour laquelle les instructions seront
exécutées l’une après l’autre, sans opération simultanées. Il faudra aussi
préciser les instructions élémentaires disponibles ainsi que leurs coûts. Ceci
est particulièrement important lorsqu’on utilise un langage de programmation
tel que Python pour illustrer un cours d’algorithmique car ce langage possède
 52

de nombreuses instructions de haut niveau qu’il serait irréaliste de considérer

comme ayant un coût constant : il existe par exemple une fonction sort qui
permet de trier un tableau en une instruction, mais il serait illusoire de croire
que son temps d’exécution est indépendant de la taille du tableau.

La première étape consiste donc à préciser quelles sont les instructions

élémentaires, c’est-à-dire celle qui seront considérées comme ayant un coût
constant, indépendant de leurs paramètres. Parmi celles-ci figurent en général
:

– les opérations arithmétiques (addition, soustraction, multiplication, division,

modulo, partie entière, . . .)

– la comparaisons de données (relation d’égalité, d’infériorité, . . .)

– le transferts de données (lecture et écriture dans un emplacement mémoire)

– les instructions de contrôle (branchement conditionnel et inconditionnel,
appel à une fonction auxiliaire, . . .)

Attention : il est parfois nécessaire de préciser la portée de certaines de ces

instructions. En arithmétique par exemple, il est impératif que les données
représentant les nombres soient codées sur un nombre fixe de bits. C’est le cas
en général des nombres flottants (le type float) et des entiers relatifs (le type
int) représentés usuellement sur 64 bits, mais dans certains langages existe
aussi un type entier long dans lequel les entiers ne sont pas limités en taille.
C’est le cas en Python, où coexistaient jusqu’à la version 3.0 du langage une
classe int et une classe long. Ces deux classes ont depuis fusionné, le passage
du type int au type long étant désormais transparent pour l’utilisateur.
Cependant, dans un but de simplification nous considérerons désormais toute
opération arithmétique comme étant de coût constant. Dans le cas des nombres
entiers, l’exponentiation peut aussi être source de discussion : s’agit-t’il d’une
opération de coût constant ? En général on répond à cette question par la
 53

négative : le calcul de n k nécessite un nombre d’opérations élémentaires

(essentiellement des multiplications) qui dépend de k. Cependant, certains
processeurs possèdent une instruction permettant de décaler de k bits vers la
gauche la représentation binaire d’un entier, autrement dit de calculer 2k en
coût constant.

Les comparaisons entre nombres (du moment que ceux-ci sont codés sur un
nombre fixe de bits) seront aussi considérées comme des opérations à coût
constant, de même que la comparaison entre deux caractères. En revanche, la
comparaison entre deux chaînes de caractères ne pourra être considérée
comme une opération élémentaire, même s’il est possible de la réaliser en une
seule instruction Python. Il en sera de même des opérations d’affectation : lire
ou modifier le contenu d’un case d’un tableau est une opération élémentaire,
mais ce n’est plus le cas s’il s’agit de recopier tout ou partie d’un tableau dans
un autre, même si la technique du slicing en Python permet de réaliser très
simplement ce type d’opération.

2.2 Notations mathématiques

Une fois précisé la notion d’opération élémentaire, il convient de définir ce

qu’on appelle la taille de l’entrée. Cette notion dépend du problème étudié :
pour de nombreux problèmes, il peut s’agir du nombre d’éléments constituant
les paramètres de l’algorithme (par exemple le nombre d’éléments du tableau
dans le cas d’un algorithme de tri) ; dans le cas d’algorithmes de nature
arithmétique (le calcul de n k par exemple) il peut s’agir d’un entier passé en
paramètre, voire du nombre de bits nécessaire à la représentation de ce dernier.
Enfin, il peut être approprié de décrire la taille de l’entrée à l’aide de deux
entiers (le nombre de sommets et le nombre d’arêtes dans le cas d’un
algorithme portant sur les graphes). Une fois la taille n de l’entrée définie, il
reste à évaluer en fonction de celle-ci le nombre f (n) d’opérations élémentaires
requises par l’algorithme. Mais même s’il est parfois possible d’en déterminer
 54

le nombre exact, on se contentera le plus souvent d’en donner l’ordre de

grandeur à l’aide des notations de Landau.

La notation la plus fréquemment utilisée est le « grand O » :

Cette notation indique que dans le pire des cas, la croissance de f (n) ne
dépassera pas celle de la suite (αn). L’usage de cette notation exprime
l’objectif qu’on se donne le plus souvent : déterminer le temps d’exécution
dans le cas le plus défavorable. On notera qu’un usage abusif est souvent fait
de cette notation, en sous-entendant qu’il existe des configurations de l’entrée
pour lesquelles f (n) est effectivement proportionnel à αn. On dira par exemple
que la complexité de la fonction diviseurs2 est un O(√ n) mais jamais qu’elle
est un O(n), même si mathématiquement cette assertion est vraie puisque f (n)
= O(√ n) =⇒ f (n) = O(n). D’un usage beaucoup moins fréquent, la notation Ω
exprime une minoration du meilleur des cas :

L’expérience montre cependant que pour de nombreux algorithmes le cas «

moyen » est beaucoup plus souvent proche du cas le plus défavorable que du
cas le plus favorable. En outre, on souhaite en général avoir la certitude de voir
s’exécuter un algorithme en un temps raisonnable, ce que ne peut exprimer
cette notation. Enfin, lorsque le pire et le meilleur des cas ont même ordre de
grandeur, on utilise la notation Θ :

Cette notation exprime le fait que quelle que soit le configuration de l’entrée,
le temps d’exécution de l’algorithme sera grosso-modo proportionnel à αn.
Ordre de grandeur et temps d’exécution
 55

Nous l’avons dit, la détermination de la complexité algorithmique ne permet

pas d’en déduire le temps d’exécution mais seulement de comparer entre eux
deux algorithmes résolvant le même problème. Cependant, il importe de
prendre conscience des différences d’échelle considérables qui existent entre
les ordres de grandeurs usuels que l’on rencontre. En s’appuyant sur une base
de 109 opérations par seconde, le tableau suivant est à cet égard significatif. Il
indique en fonction de la taille n de l’entrée (102 , 103 , . . .) et du nombre
d’opérations requis par un algorithme (logn, n, . . . ) le temps d’exécution de
ce dernier.

Tableau – Temps nécessaire à l’exécution d’un algorithme en fonction de sa

complexité.

La lecture de ce tableau est édifiante : on comprend que les algorithmes ayant

une complexité supérieure à une complexité quadratique soient en général
considérées comme inutilisables en pratique (sauf pour de petites voire très
petites valeurs de n).

Tableau – Qualifications usuelles des complexités.

 56

Chapitre 6 : Présentation de langage C

Section 1 : Structure d’un langage C
C/C++ est composé de deux éléments essentiels:
1. Le préprocesseur effectue une mise en forme lexicale, élimination des
espaces, lignes vides et commentaires, inclusions de fichiers externes,
définitions de constantes symboliques et macro-instructions, gestion de code
conditionnel, ...
2. Le compilateur proprement dit traite la sortie du préprocesseur et génère le
fichier objet.
L’utilisation du préprocesseur se fait en incorporant dans le texte source des
directives, qui sont des mots-clés précédés du caractère #, par exemple #include,
#define, #if, etc .

Section 2 : Structure d’un programme C

Un programme C est composé de :
Directives du préprocesseur : Elles permettent d'effectuer des manipulations
sur le texte du programme source avant la compilation.
Une directive du préprocesseur est une ligne de programme source commençant
par le caractère dièse (#).
Le préprocesseur (/lib/cpp) est appelé automatiquement par la commande
/bin/cc.

Déclarations/définitions :
Déclaration : la déclaration d'un objet C donne simplement ses caractéristiques
au compilateur et ne génère aucun code.
Définition : la définition d'un objet C déclare cet objet et créée effectivement cet
objet.
Fonctions : Ce sont des sous-programmes dont les instructions vont définir un
traitement sur des variables.
Elles peuvent retourner une valeur a la fonction appelante.
Le programme principal est une fonction dont le nom doit impérativement être
main.
Les fonctions ne peuvent pas être imbriquées.
Des commentaires: éliminés par le préprocesseur, ce sont des textes compris
entre /* et */ ou // pour le C++ et certains compilateurs du C. On ne doit pas les
imbriquer et ils peuvent apparaitre en tout point d'un programme (sauf dans une
constante de type chaine de caractères ou caractère).
Pour ignorer une partie de programme il est préférable d'utiliser une directive du
préprocesseur (#if 0 ... #endif).
 57

Exemple :
Créer un programme en C affichant le message suivant : « Bonjour et soyez les
bienvenus en C»
/* **************************
Programme de démonstration
**************************
*/
#include “stdio.h“
#include “stdlib.h“

int main()
{
printf(“Soyez les bienvenus en C++”); /* Affiche un message*/

system(“pause“) ;
return 0 ;

2.1.Mots-cles
Les mots-clés du langage sont strictement réservés et ne peuvent être utilisés
comme identificateurs.
Voici la liste des mots clés en C/C++ :

2.2. Casse caractères

Contrairement à Pascal et Fortran, C/C++ distingue les majuscules et les
minuscules dans les identificateurs et les mots-clés du langage :
 58

float toto, Toto, totO; /* Trois variables distinctes */

Float y; /* Erreur en compilation, Float est inconnu */
Tous les mots-clés du C doivent être saisis en minuscules, les identificateurs
d’un programme sont définis, eux, au gré du programmeur.

2.3 Identicateurs
Les identificateurs, de variables, de fonctions, obéissent à la règle habituelle
"suite de caractères alphanumériques, l’initiale devant être une lettre". Ce sont
des noms qu’on donne selon le gré du programmeur. Le caractère de
soulignement _ est autorisé. L’utilisation d’autres caractères non
alphanumériques est à éviter dans la mesure du possible.
L’utilisation de noms assez longs a l’immense avantage de mieux documenter
un programme :
float constante_de_planck; est probablement plus explicite que :
float h;
NB : il faut éviter d’utiliser le caractère de soulignement _ en début ou fin d’un
identificateur, cette notation est habituellement réservée aux mécanismes
internes des compilateurs.

Section 3 : Types de variables

Voici les types de données ou des variables les plus simples du langage :

À ces types fondamentaux s’ajoutent des types dérivés à l’aide des mots clés «
long » et « short ».
Ces types dérivés se distinguent des types de base par l’étendue des plages de
valeurs qu’ils peuvent stocker. Par exemple, le type long int est plus grand que
 59

le type int. Inversement, le type short int est plus court que le type int. De même,
le type long double est plus grand que le type double.
Il est également possible de n’utiliser que des plages de valeurs positives pour
les types intégraux (sauf pour les booléens). Pour cela, on peut utiliser les mots
clés signed et unsigned. Les types non signés ne peuvent contenir de valeurs
négatives, mais leur valeur maximale est jusqu’à deux fois plus grande que pour
leur homologues signés.
Exemple. Types signés et non signés
unsigned short int
signed short int
unsigned int
signed int
unsigned long int
long unsigned int

Section 4 : Déclaration des variables, instruction d’affectation et opérations d’E/S

4.1. Déclaration des variables
Les variables doivent obligatoirement être déclarées avant d'être utilisées.
La syntaxe générale d'une définition ou déclaration de variable est de la forme :
classe modificateur type identificateur ;
classe : (facultative) elle détermine le mode de stockage, la durée de vie et la
visibilité de la variable.
Elle peut prendre une des valeurs suivantes :
Auto extern register static
modificateur : (facultatif) il peut prendre une des valeurs suivantes :
const volatile
type : c'est un type de base.
Exemple :
int x; /* x est un entier */
float x1, x2; /* x1 et x2 sont des nombres décimaux */
static double delta; /* delta est un double de classe static */
extern unsigned char rep;
4.2. Instruction d’affectation
4.2.1 Instruction d’affectation simple
Les instructions d’affectations simples sont identifiées par le point-virgule. C’est
ce caractère qui marque la fin d’une instruction. Le programme évalue
l’expression délimitée par l’instruction précédente et ce point
 60

virgule. Cette expression peut être vide, le résultat de l’invocation d’une

fonction, ou une combinaison d’expressions plus simples par des opérateurs.
Exemple d’instructions :
; /* Instruction réduite à sa plus simple expression
(ne fait rien) */
printf("Hello World!\n"); /* Instruction appelant une fonction */
i = j + m; /* Instruction évaluant une combinaison d’opérateurs */
Les principales opérations que l’on peut réaliser dans une expression sont les
suivantes :
Tableau : Opérateurs du langage C/C++
 61

Une affectation composée est une opération permettant de réaliser en une seule
étape une opération normale et l’affectation de son résultat dans la variable
servant de premier opérande. Les affectations composées utilisent la syntaxe
suivante :
Variable op_aff valeur
où op_aff est l’un des opérateurs suivants : ’+=’, ’-=’, ’*=’, etc. Cette syntaxe est
strictement équivalente à :
variable = variable op valeur
et permet donc de modifier la valeur de variable en lui appliquant l’opérateur op.
Exemple : Affectation composée
i*=2; /* Multiplie i par 2 : i = i * 2. */
4.2.2 Instruction d’affectation composée
Il est possible de créer des instructions composées, constituées d’instructions plus
simples. Les instructions composées se présentent sous la forme de blocs
d’instructions où les instructions contenues sont encadrées d’accolades ouvrantes
et fermantes (caractères ’{ et ’}’).
Exemple 6. Instruction composée
{
i=1;
j=i+3*g;
}
Note : Un bloc d’instructions est considéré comme une instruction unique. Il est
donc inutile de mettre un point-virgule pour marquer l’instruction, puisque le bloc
lui-même est une instruction.
 62

4.3. Operations d’E/S

Afin de permettre aux programmes d’écrire sur leurs flux d’entrée / sortie
standards, la bibliothèque C/C++ définit plusieurs fonctions extrêmement utiles.
Les deux principales fonctions sont sans doute les fonctions printf et scanf. La
fonction printf (« printformatted » en anglais) permet d’envoyer des données
formatées sur le flux de sortie standard, et scanf (« scan formatted ») permet de
les lire à partir du flux d’entrée standard. Ces fonctions sont déclarées dans le
fichier d’en-tête stdio.h ou stdafx.h.
4.3.1. Opération d’entrée ou lire à partir du clavier scanf
Sa syntaxe générale est : scanf(chaîne de format, &variable [, &variable [...]]);

Chaînes de format Types de variables

%i ou %d int
%f float
%u Unsigned int (Entier non signé)
%lf double
%ld long int
%c char (Symbole ou caractère isolé)
%s string (Chaîne de caractère)

Exemple : scanf(”%i” , &V);/*V est un entier */

2.3.2. Opération de sortie ou d’affichage printf
Sa syntaxe générale est : printf(chaîne de format [, valeur ou variable [, valeur ou
variable [...]]])
Chaînes de format Types de variables
%i ou %d int
%f double
%u unsigned int (Entier non signé)
%c char (Symbole ou caractère isolé)
%s string (Chaîne de caractère)

Symboles Descriptions
\n Saut de ligne
\t Tabulation horizontale
\a Signal-sonnerie

Exemple : printf(“Valeur de la variableV=%i\n” , V); /* Affiche la valeur de V */

 63

N.B : La chaine de format %g vous permet d’afficher une valeur exacte et

%.2f vous permet d’afficher une valeur décimale à 0.01 près.

Exercices et solutions du chapitre 2 sur les variables

I/ Déclarations des variables
1. Déclarer les variables nécessaires au calcul de l’aire du cercle (s= .r2).
Solution:
//Le type double est plus approprié que le type float dans les nombres décimaux.
double s,r ; // , é à 3,14
2. Déclarer des variables nécessaires pour calculer le volume et la surface du
cylindre.
Solution:
double s,r;
double h,v; // , é à 3,14

3. Déclarer les variables nécessaires au calcul du prix d’achat, composé de

plusieurs cahiers, crayons et règle.
Solution:
Pour déclarer les variables dans cet exercice, il faut concevoir une formule pour
calculer le prix d’achat (PA). Voici une formule appropriée :
PA=Quantité_cahier*Prix_unitaire_cahier+
Quantité_crayon*Prix_unitaire_crayon+Quantité_règle*Prix_unitaire_règl
e;
D’où la solution avec le type de variable : int PA, Quantite_cahier,
prix_unitaire_cahier, Quantite_crayon, prix_unitaire_crayon, Quantite_regle,
prix_unitaire_regle ;
II/ Instruction d’affectation
4. Ecrivez une instruction qui affecte la variable x La valeur de -1,5.
Solution: x=-1.5 ;
5. Ecrivez une instruction qui affecte à la variable somme une valeur zéro.
Solution : somme=0 ;
 64

6. Ecrivez une instruction qui augmente à une unité la valeur de la variable n

Solution : n=n+1 ; ou n++
7. Ecrivez une instruction qui réduit la valeur à deux d’une variable compteur.
Solution : compteur=compteur-2 ;
8. Ecrivez sous la forme d’une instruction d’affectation la formule de calcul de la
valeur de la fonction y = -2,7x3 + 0,23x2 -1,4.
Solution : y=-2.7*x*x*x+0.23*x*x-1.4; ou avec #include ‘’math.h’’ :
y=-2.7*pow(x,3)+0.23*pow(x,2)-1.4 ;

9. Ecrivez sous la forme d’une instruction d’affectation la formule de calcul de

l’aire d'un rectangle.
Solution : Aire=longueur*largeur ;
10. Ecrivez sous la forme d’une instruction d’affectation la formule de calcul de
l’aire d'un triangle : s = ½ x a x h, où a - longueur de la base ; h - la hauteur du
triangle.
Solution : s=1/2*a*h;/*Utilisez le type le plus approprié double pour la
déclaration des variables dans un programme complet de calcul scientifique*/
11. Ecrivez sous la forme d'une instruction d’affectation la formule suivante :

− −√ −4
=
2
Solution: x=(-b-sqrt(pow(b,2)-4*a*c))/2*a ;/*Utilisez #include ‘’math.h’’ à
l’entête*/
12. Ecrivez sous la forme d'une instruction d’affectation la formule de calcul de
l’aire d'un cercle s= .r2 .
Solution : s=3.14*r*r;
13. Ecrivez sous la forme d'une instruction d’affectation la formule de calcul de
l’aire d’une surface et d’un volume du cylindre.
 65

Solution :
s=2*pi*r*(h+r); avec pi=3.14 ;
v=pi*r*r*h ;
III/ Operations d’Entrée/Sortie

14. Écrire un programme qui affiche sur l’écran votre prénom(s) et votre nom(s).
15. Ecrire un programme qui affiche sur l’écran ce texte :
Triste temps ! Yeux de charme !
Agréable à moi votre radieuse beauté.
J'aime le dépérissement somptueux de la nature,
en rouge et de la forêt d'or vêtu.
16. Ecrivez une instruction qui affiche sur une seule ligne des valeurs des
variables a, b et c de type entier (int).
Solution : printf(‘’a=%i, b=%i, c=%i‘’,a,b,c);/*%i- la chaine de format des
nombres entiers*/

17. Ecrivez une instruction de sortie des valeurs de variables entières a, b et c.

La valeur de chaque variable doit être affichée sur une ligne distincte.
Solution : printf(‘’a=%i\n‘’,a);/*%i- la chaine de format des nombres entiers*/
printf(‘’b=%i\n‘’,b);
 66

printf(‘’c=%i\n‘’,c);
18. Donnez une instruction qui fournit une entrée avec le clavier des valeurs des
variables radius et hauteur de type float sur la même ligne.
Solution : scanf(‘’%f %f‘’,&radius,&hauteur);/*%f- la chaine de format des
nombres décimaux*/
19. Ecrivez des instructions qui fournissent l’entrée des valeurs des variables
fractionnaires (type float) u et r. Supposé que l’utilisateur après avoir utilisé un
numéro de série de chaque nombre va appuyer sur le bouton du clavier <Entrée>.
Solution: scanf(‘’%f ‘’,&u);/*%f- la chaine de format des nombres décimaux*/
scanf(‘’%f ‘’,&r);
20. Écrire une instruction qui fournit les valeurs d'entrée des variables u et r.
Supposé que l’utilisateur choisira les nombres dans la même rangée. Voir la
solution de l’exo.18
21. Implémenter une application en mode console pour calculer le volume du
cylindre. Cette application doit demander à l’utilisateur de lire au clavier la valeur
du rayon et la valeur de la hauteur.
Voici la liste de quelques fonctions mathématiques à retenir à partir de la
bibliothèque math.h :

Fonctions Descriptions en mathématiques

pow(a,b) ab
sqrt(a+b) √ +
cos(x) cosx
sin(x) sinx
tan(x) tgx
ctan(x) ctgx
abs(x) |x|
 67

Chapitre 7 : Instructions de contrôle

Section 1 : Instructions conditionnelles
1.1 L’instruction conditionnelle if
L’instruction conditionnelle if permet de réaliser un test et d’exécuter une
instruction ou non selon le résultat de ce test.
Où test est une expression dont la valeur est booléenne ou entière. Toute valeur
non nulle est considérée comme vraie. Si le test est vrai, opération est exécuté. Ce
peut être une instruction ou un bloc d’instructions. Une variante permet de
spécifier l’action à exécuter en cas de test faux. Sa syntaxe est la suivante :

if (test) opération1;
else opération2;

Note : Attention ! Les parenthèses autour du test sont nécessaires !

Les opérateurs de comparaison sont les suivants :
Opérateurs de comparaison

Les opérateurs logiques applicables aux expressions booléennes sont les suivants
:
Opérateurs logiques

1.2. Le branchement conditionnel

Dans le cas où plusieurs instructions différentes doivent être exécutées selon la
valeur d’une variable de type intégral, l’écriture de if successifs peut être
 68

relativement lourde. Le C/C++ fournit donc la structure de contrôle switch, qui

permet de réaliser un branchement conditionnel. Sa syntaxe est la suivante :

switch (valeur)
{
case cas1:
[instruction;
[break;]
]
case cas2:
[instruction;
[break;]
]...
case casN:
[instruction;
[break;]
]
[default:
[instruction;
[break;]
]
]
}
valeur est évaluée en premier. Son type doit être un entier. Selon le résultat de
l’évaluation, l’exécution du programme se poursuit au cas de même valeur. Si
aucun des cas ne correspond et si default est présent, l’exécution se poursuit après
default. Si en revanche default n’est pas présent, on sort du switch.
Les instructions qui suivent le case approprié ou default sont exécutées. Puis, les
instructions du cas suivant sont également exécutées (on ne sort donc pas du
switch). Pour forcer la sortie du switch, on doit utiliser le mot clé break.

Exemple : Branchement conditionnel switch

Dans cet exemple, le programmeur veut créer un programme pour trouver le jour
de la semaine selon le numéro du jour qui sera lu au clavier et le jour de la semaine
sera affiché. Si l’utilisateur fait lire au clavier un numéro du jour non valide, alors
ce programme affichera un message d’erreur. (voir TP)

Section 2 : Instructions de contrôles interactifs

2. Les boucles ou instructions itératives ou répétitives
 69

Les boucles sont des instructions de contrôle qui permettent de réaliser une
opération plusieurs fois (répétitions), tant qu’une condition est vérifiée.

2.1. La boucle for

L’instruction de contrôle for est sans doute l’une des boucles les plus importantes.
Elle permet de réaliser toutes sortes de boucles et, en particulier, les boucles
permettant d’itérer sur un ensemble de valeur d’une variable de contrôle. Sa
syntaxe est la suivante :

for (initialisation ; test ; itération) opération;

où initialisation est une instruction évaluée avant le premier parcours de la boucle

du for.
test est une expression dont la valeur déterminera la fin de la boucle. Itération est
une instruction effectuée à la fin de chaque passage dans la boucle, et opération
constitue le traitement de la boucle elle-même. Chacune de ces parties est
facultative.

Exemple : Boucle for

somme = 0;
for (i=0; i<=10; i=i+1) somme = somme + i;

Note : En C++, il est possible que la partie initialisation déclare une variable.
Dans ce cas, la variable déclarée n’est définie qu’à l’intérieur de l’instruction for.
Par exemple:
for (int i=0; i<10; ++i); est strictement équivalent à :

{
int i;
for(i=0; i<10; ++i)
}

2.2. Le while
Le while permet d’exécuter des instructions en boucle tant qu’une condition est
vraie. Sa syntaxe est la suivante :
while(test) opération;

où opération est effectuée tant que test est vérifié. Comme pour if, les parenthèses
autour du test sont nécessaires. L’ordre d’exécution est :
test
si vrai :
opération
retour au test
 70

Exemple : Boucle while

somme = i = 0;
while (somme<1000)
{
somme = somme + 2 * i / (5 + i);
i = i + 1;
}
2.3. Le do
La structure de contrôle do permet, tout comme le while, de réaliser des boucles
en attente d’une condition. Cependant, contrairement à celui-ci, le do effectue le
test sur la condition après l’exécution des instructions. Cela signifie que les
instructions sont toujours exécutées au moins une fois, que le test soit vérifié ou
non. Sa syntaxe est la suivante :
do opération;
while (test);
opération est effectuée jusqu’à ce que test ne soit plus vérifié.
L’ordre d’exécution est :
opération
test
si vrai, retour à opération

Exemple: Boucle do
p = i = 1;
do
{
p = p * i;
i = i + 1;
} while (i != 10);

Exercices du chapitre

A) Instruction if
1. Ecrire un programme en mode console pour calculer le prix d'achat (pantalons
et chaussures avec leurs quantités), en tenant compte des réductions. 10% de
réduction disponible si le montant de l'achat est plus de 9000 FCFA, 15% - si le
montant est plus de 19000 FCFA.

2. Ecrire un programme en mode graphique, permettant de résoudre une équation

du second degré.
 71

B) Boucle for
3. Écrire un programme qui affiche une table des carrés des dix premiers nombres
entiers positifs. Le programme doit travailler de la manière suivante :

4. Calculer la somme des n premiers termes de la « série harmonique », c’est-à-

dire la somme :
1 + 1/2 + 1/3 + 1/4 + ..... + 1/n
La valeur de n sera lue en donnée.
5. Ecrire un programme qui consiste à afficher un triangle isocèle formé d'étoiles
de N lignes (N est fourni au clavier) :

C) do... while
 72

6. Ecrire un programme qui calcule la somme et la moyenne arithmétique des

suites d'entiers positifs en faisant entrer ces suites à partir du clavier. Vous devez
faire entrer les nombres après la flèche.

D) while
7. Ecrire un programme qui affiche sur l’écran un tableau des valeurs de fonction
y = 2x2 -5x-8 de l’intervalle -4 à 4. Incrément à 0,5 argument.
 73

Chapitre 8 : Fonctions et procédure en C

Section 1 : Structure d’une fonction et d’une procédure
1.1 : Structure d’une fonction

La structure des fonctions se fait comme suit :

type identificateur (paramètres)//paramètres sont composés des types et des
arguments
{
... /* Instructions de la fonction. */
}
type est le type de la valeur renvoyée, identificateur est le nom de la fonction, et
paramètres
est une liste de paramètres. Les règles de nommage des identificateurs de
fonctions sont les mêmes
que pour les identificateurs de variables.
La syntaxe de la liste de paramètres est la suivante :
type variable [= valeur] [, type variable [= valeur] [...]]
où type est le type du paramètre variable qui le suit et valeur sa valeur par défaut.
La valeur par
défaut d’un paramètre est la valeur que ce paramètre prend si aucune valeur ne lui
est attribuée lors
de l’appel de la fonction.
Note : L’initialisation des paramètres de fonctions n’est possible qu’en C++, le C
n’accepte pas
cette syntaxe.
La valeur de la fonction à renvoyer est spécifiée en utilisant le mot clé return, dont
la syntaxe est :
return valeur;

1.2 : Structure d’une procédure

La structure d’une procédure se fait comme suit :

type identificateur ()//peut ou ne pas avoir des arguments
{
... /* Instructions de la procédure. */
return 0;

} Procédure
Fonction n’attendant pas de paramètres et ne renvoyant pas de valeur.
return 0; //Cette ligne est facultative.
 74

Section 2 : Passage des paramètres

Quand on invoque une fonction, on doit généralement lui passer des valeurs. Il y
a deux points de vue pour le passage des données à la fonction, celui de la fonction
appelante et celui de la fonction appelée.
-Du côté appelant, les valeurs passées sont appelées paramètres réels ou
paramètres effectifs ou arguments.
Par exemple, dans l'appel suivant, deux arguments, une variable (s1) et une
constante chaine de caractères, sont passés : strcpy( s1 , "Le langage C++");
-Du côté appelé, les variables spécifiées sont appelées paramètres formels ou
paramètres.
-Lors de l'appel de la fonction, la liste des paramètres réels est mise en
correspondance avec la liste des paramètres formels.
-Le mode de transmission entre ces deux contextes est effectué par valeur : la
fonction travaille donc sur une copie des paramètres réels.

Section 3 : Quelques fonctions en C

Le langage C a plusieurs fonctions. Voici quelques fonctions :
 Fonctions d’Entrée/Sortie (printf, scanf, fprintf, fscanf, putchar ,puts…) ;
 Fonctions standard (strcpy,strlen,toupper,tolower…) ;
 Fonctions mathématiques (exp(x),sqrt(x),abs(),pow(x) ...) ;
 75

Chapitre 9 : Structure des données

Section 1 : Tableaux
9.1 Définition
Un tableau est un ensemble d’éléments consécutifs. Celui-ci peut être constitué
de plusieurs lignes et colonnes. Nous n’utiliserons dans un premier temps que les
tableaux à une seule ligne.

Exemple de tableau de caractères :

Les cases d’un tableau sont numérotées à partir de 0.

9.2 Déclaration
Un tableau se déclare de la manière suivante :
<type><nom du tableau> [<taille du tableau>];
Exemple :

Un tableau de plusieurs dimensions se déclare de la façon suivante :

<type><nom du tableau> [<taille 1ère dimension 1>][<taille 2nde
dimension>][<taille 3-eme dimension>][<taille n dimension>];
Exemple :

9.3 Utilisation
On accède à un tableau en l’appelant par son nom et son numéro de case.
Exemple :
 76

Exercice 1 :
Ecrire un programme, qui saisit à l’aide du clavier un tableau de 1-ère dimension
de 5 éléments. Apres cela, le programme doit afficher le nombre des éléments
non-nuls.
Saisissez le tableau des nombres entiers
Apres chaque saisie des nombres, appuyer sur Entrée

Section 2 : Fichiers
2-1 - La notion de flux

Les entrées/sorties (E/S) ne font pas partie du langage C car ces opérations sont
dépendantes du système. Néanmoins puisqu'il s'agit de tâches habituelles, sa
bibliothèque standard est fournie avec des fonctions permettant de réaliser ces
opérations de manière portable. Ces fonctions sont principalement déclarées dans
le fichier stdio.h. Les entrées/sorties en langage C se font par l'intermédiaire
d'entités logiques, appelés flux, qui représentent des objets externes au
programme, appelés fichiers. En langage C, un fichier n'est donc pas
nécessairement un fichier sur disque (ou périphérique de stockage pour être plus
précis). Un fichier désigne en fait aussi bien un fichier sur disque (évidemment)
qu'un périphérique physique ou un tube par exemple. Selon la manière dont on
veut réaliser les opérations d'E/S sur le fichier, qui se font à travers un flux, on
distingue deux grandes catégories de flux à savoir les flux de texte et les flux
binaires. Les flux de texte sont parfaits pour manipuler des données présentées
sous forme de texte. Un flux de texte est organisé en lignes. En langage C, une
ligne est une suite de caractères terminée par le caractère de fin de ligne (inclus) :
'\n'. Malheureusement, ce n'est pas forcément le cas pour le système sous-jacent.
Sous Windows par exemple, la marque de fin de ligne est par défaut la
combinaison de deux caractères : CR (Carriage Return) et LF (Line Feed) soit '\r'
 77

et '\n' (notez bien que c'est CR/LF c'est-à-dire CR suivi de LF pas LF suivi de CR).
Sous UNIX, c'est tout simplement '\n'. On se demande alors comment on va
pouvoir lire ou écrire dans un fichier, à travers un flux de texte, de manière
portable. Et bien c'est beaucoup plus simple que ce à quoi vous-vous attendiez :
lorsqu'on effectue une opération d'entrée/sortie sur un flux de texte, les données
seront lues/écrites de façon à ce qu'elles correspondent à la manière dont elles
doivent être représentées et non caractère pour caractère. C'est-à-dire par exemple
que, dans une implémentation où la fin de ligne est provoquée par la combinaison
des caractères CR et LF, l'écriture de '\n' sur un flux de texte va provoquer
l'écriture effective des caractères '\r' et '\n' dans le fichier associé. Sur un flux
binaire les données sont lues ou écrites dans le fichier caractère pour caractère.

2-2 - Les fichiers sur disque

La communication avec une ressource externe (un modem, une imprimante, une
console, un périphérique de stockage, etc.) nécessite un protocole de
communication (qui peut être texte ou binaire, simple ou complexe, ...) spécifique
de cette ressource et qui n'a donc rien à voir le langage C. La norme définit tout
simplement les fonctions permettant d'effectuer les entrées/sorties vers un fichier
sans pour autant définir la notion de matériel ou même de fichier sur disque afin
de garantir la portabilité du langage (ou plus précisément de la bibliothèque).
Cependant, afin de nous fixer les idées, nous n'hésiterons pas à faire appel à ces
notions dans les explications. Les fichiers sur disque servent à stocker des
informations. On peut « naviguer » à l'intérieur d'un tel fichier à l'aide de fonctions
de positionnement (que nous verrons un peu plus loin). A chaque instant, un «
pointeur » indique la position courante dans le fichier. Ce pointeur se déplace, à
quelques exceptions près, après chaque opération de lecture, d'écriture ou appel
d'une fonction de positionnement par exemple. Bien entendu, cette notion de
position n'est pas une spécificité exclusive des fichiers sur disque. D'autres types
de fichiers peuvent très bien avoir une structure similaire.
 78

2-3 - Les messages d'erreur

En langage C, il est coutume de retourner un entier même quand une fonction

n'est censée retourner aucune valeur. Cela permet au programme de contrôler les
erreurs et même d'en connaître la cause. Certaines fonctions comme malloc par
exemple retournent cependant une adresse, NULL en cas d'erreur. Pour fournir
d'amples informations quant à la cause de l'erreur, ces fonctions placent alors une
valeur dans une variable globale appelée errno (en fait la norme n'impose pas
qu'errno doit être forcément une variable globale !), cette valeur bien entendu est
à priori dépendante de l'implémentation. Ces valeurs doivent être déclarées dans
le fichier errno.h. Par exemple, une implémentation peut définir un numéro
d'erreur ENOMEM qui sera placée dans errno lorsqu'un appel à malloc a échoué
car le système manque de mémoire.

La fonction strerror, déclarée dans string.h, permet de récupérer une chaîne à

priori définie par l'implémentation décrivant l'erreur correspondant au numéro
d'erreur passé en argument. La fonction perror, déclarée dans stdio.h, quant à elle
utilise cette chaîne, plus une chaîne fournie en argument, pour afficher la
description d'une erreur. Le texte sera affiché sur l'erreur standard (stderr). Pour
résumer :

perror(msg);

est équivalent à : fprintf(stderr, "%s: %s\n", msg, strerror(errno));

Si nous n'avons pas parlé de ces fonctions auparavant, c'est parce que nous n'en
avions pas vraiment jusqu'ici besoin. A partir de maintenant, elles vont être très
utiles car les fonctions d'entrées/sorties sont sujettes à de très nombreuses sortes
d'erreurs : fichier non trouvé, espace sur disque insuffisant, on n'a pas les
permissions nécessaires pour lire ou écrire dans le fichier, ...

2--4 - Ouverture d'un fichier

 79

Toute opération d'E/S dans un fichier commence par l'ouverture du fichier.

Lorsqu'un fichier est ouvert, un flux lui est associé. Ce flux est représenté par un
pointeur vers un objet de type FILE. Pendant l'ouverture d'un fichier, on doit
spécifier comment en désire l'ouvrir : en lecture (c'est-à-dire qu'on va lire dans le
fichier), en écriture (pour écrire), ou en lecture et écriture.

La fonction fopen : FILE * fopen(const char * filename, const char * mode);

permet d'ouvrir un fichier dont le nom est spécifié par l'argument filename selon
le mode, spécifié par l'argument mode, dans lequel on souhaite ouvrir le fichier.
Elle retourne l'adresse d'un objet de type FILE qui représente le fichier à l'intérieur
du programme. En cas d'erreur, NULL est retourné et une valeur indiquant la
cause de l'erreur est placée dans errno. En pratique, dans le cas d'un fichier sur
disque, l'argument nom peut être aussi bien un chemin complet qu'un chemin
relatif. Notez bien que les notions de chemin, répertoire (qui inclut également les
notions de répertoire courant, parent, etc.), ... sont dépendantes du système, elles
ne font pas partie du langage C. La plupart du temps, le répertoire courant est par
défaut celui dans lequel se trouve le programme mais, si le système le permet, il
est possible de spécifier un répertoire différent. Fondamentalement, les valeurs
suivantes peuvent être utilisées dans l'argument mode :

• "r" : ouvrir le fichier en lecture. Le fichier spécifié doit déjà exister.

• "w" : ouvrir le fichier en écriture. S'il n'existe pas, il sera créé. S'il existe déjà,
son ancien contenu sera effacé.

• "a" : ouvrir le fichier en mode ajout, qui est un mode dans lequel toutes les
opérations d'écriture dans le fichier se feront à la fin du fichier. S'il n'existe pas, il
sera créé.

Quel que soit le cas, le fichier sera associé à un flux de texte. Pour spécifier qu'on
veut ouvrir le fichier en tant que fichier binaire, il suffit d'ajouter le suffixe 'b'
(c'est-à-dire "rb", "wb" ou "ab"). Sauf dans le cas du mode "ab" et dérivés, dans
 80

lequel le pointeur pourrait, selon l'implémentation, être positionné à la fin du

fichier, il sera positionné au début du fichier. On peut également ajouter un '+'
dans l'argument mode. Par exemple : "r+", "r+b" ou encore "rb+" mais "r+b" et
"rb +", c'est évidemment la même chose. La présence du '+' aura pour effet de
permettre d'effectuer aussi bien des opérations de lecture que d'écriture sur le
fichier. On dit alors que le fichier est ouvert en mode mise à jour. Il y a cependant
une remarque très importante concernant les fichiers ouverts en mode mise à jour
:

• avant d'effectuer une opération de lecture juste après une opération d'écriture, il
faut tout d'abord appeler fflush ou une fonction de positionnement

• avant d'effectuer une opération d'écriture juste après une opération de lecture, il
faut d'abord appeler une fonction de positionnement, à moins d'avoir atteint la fin
du fichier

• dans de nombreuses implémentations, tout fichier ouvert en mode mise à jour

est supposé être un fichier binaire qu'on ait mis oui ou non la lettre 'b'.
Personnellement, je recommande donc de n'utiliser le mode mise à jour qu'avec
les fichiers binaires.

Lorsqu'on n'en a plus besoin, il faut ensuite fermer le fichier :

int fclose(FILE * f);

Le programme suivant crée un fichier, hello.txt, pour y écrire ensuite une et une
seule ligne : Hello, world.

#include <stdio.h>

int main() {

FILE * f;

f = fopen("hello.txt", "w");
 81

if (f != NULL) {

fprintf(f, "Hello, world\n");

fclose(f); }

else perror("hello.txt");

return 0;

En supposant que pour le système la fin de ligne est représentée par la

combinaison des caractères CR et LF, ce programme est aussi équivalent au
suivant :

#include <stdio.h>

int main() {

FILE * f;

f = fopen("hello.txt", "wb");

if (f != NULL) {

fprintf(f, "Hello, world\r\n");

fclose(f);

else

perror("hello.txt");

return 0;

}
 82

Exemple : copier un fichier Il y a plusieurs moyens de réaliser la copie d'un

fichier, le plus simple est peut-être de copier la source vers la destination octet par
octet. Voici un programme qui réalise une telle copie :

#include <stdio.h>

#include <string.h>

char * saisir_chaine(char * lpBuffer, int buf_size);

int main()

{ char src[FILENAME_MAX];

/* FILENAME_MAX est defini dans stdio.h */

FILE * fsrc;

printf("Ce programme permet de copier un fichier.\n");

printf("source : ");

saisir_chaine(src, sizeof(src));

fsrc = fopen(src, "rb");

if (fsrc == NULL)

perror(src);

else { char dest[FILENAME_MAX];

FILE * fdest; printf("dest : ");

saisir_chaine(dest, sizeof(dest));

if (strcmp(src, dest) == 0)

printf("La source ne peut pas etre en meme temps la destination.\n");

else { fdest = fopen(dest, "wb");

 83

if (fdest == NULL)

perror(dest);

else { int c;

while ((c = getc(fsrc)) != EOF)

putc(c, fdest); fclose(fdest);

printf("Copie terminee.\n"); } }

fclose(fsrc); }

printf("Merci d'avoir utilise ce programme. A bientot !\n");

return 0;

char * saisir_chaine(char * lpBuffer, int buf_size)

{ char * ret = fgets(lpBuffer, buf_size, stdin);

if (ret != NULL) { char * p = strchr(lpBuffer, '\n');

if (p != NULL) *p = '\0';

else { int c; do c = getchar();

while (c != EOF && c != '\n'); } }

return ret;

3-Les erreurs d'E/S

Une erreur d'E/S est erreur qui peut se produire lors d'une tentative d'opération
d'E/S, par exemple : fin de fichier atteinte, tentative d'écriture dans un fichier
 84

ouvert uniquement en lecture, tentative de lecture dans un fichier ouvert

uniquement en lecture, etc

La fonction feof :

int feof(FILE * f);

peut être appelé à n'importe quel moment pour connaître si l'on a atteint la fin du
fichier. Je rappelle qu'un programme (du moins d'après les fonctions du C) ne peut
affirmer que la fin d'un fichier a été atteinte qu'après avoir tenté de lire dans le
fichier alors qu'on se trouve déjà à la fin c'est-à-dire derrière le dernier octet, pas
juste après avoir lu le dernier octet, donc faites gaffe. Evidemment, une telle
fonction ne sera utilisée que sur un fichier ouvert en lecture. Elle retourne VRAI
si la fin de fichier a été atteinte et FAUX dans le cas contraire. Cette information
est en fait maintenue par un indicateur de fin de fichier qui indique à tout moment
si on a oui ou non déjà atteint la fin du fichier. Après un appel fructueux à une
fonction de positionnement, l'indicateur de fin de fichier est remis à zéro. La
fonction ferror :

int ferror(FILE * f);

permet de connaître si une erreur différente de "fin de fichier atteinte" s'est

produite lors de la dernière opération d'E/ S sur f. Cette information est maintenue
en permanence par un indicateur d'erreur. Bien qu'une lecture à la fin d'un fichier
soit également une erreur, elle n'est pas considérée par la fonction ferror car les
indicateurs d'erreur et de fin de fichier sont des données bien distinctes. Attention,
une fois qu'une erreur s'est produite, l'indicateur d'erreur ne sera remis à zéro
qu'après un appel à clearerr.

void clearerr(FILE * f);

Cette fonction remet à zéro l'indicateur d'erreur du fichier f.

 85

Bibliographie

 R. MAHL, Algorithmique et structures de données, Laboratoire

d’Informatique Université 1977 ;
 S. BOUTIN, Algorithmes cours et exercices résolus Edition 1, Bréal
1994 ;
 Thomas H. CORMEN, Cours, exercices et problèmes. Algorithmique.
Cours avec 957 exercices et 158 problèmes Edition 3, Dunod 2010.
 86

Table des matières

Chapitre1 : Introduction à l’algorithmique ............................................................................................. 5
Section 1 : Environnement algorithmique .......................................................................................... 5
Les opérateurs de comparaison : ................................................................................................. 8
<> : Comparaison d’une différence................................................................................................. 8
>= : Comparaison de plus grand ou égal......................................................................................... 8
<= : Comparaison de plus petit ou égal........................................................................................... 8
Les autres opérateurs:................................................................................................................... 8
^ : Exprime la puissance d’un nombre. Exemple : 23=2^3 ............................................................. 9
 : Effectue une affectation à une variable ................................................................................... 9
Section 2 : Types de données ............................................................................................................ 10
Section 3 : Structure conditionnelle.................................................................................................. 12
Section 4 : Structure interactive ou boucle ou instruction répétitive ou instruction itérative......... 17
Section 5 : Algorithmiques de tri....................................................................................................... 22
Section 6 : Algorithmique de recherche (Dichotomie)...................................................................... 22
Section 7 : Procédures et fonctions.................................................................................................. 24
Section 8 : Mode de passage des paramètres................................................................................... 25
Section 9 : Récursivité ....................................................................................................................... 26
Chapitre 2 : Notion de pointeur ............................................................................................................ 30
Section 1 : Mémoire et importance dynamique ............................................................................... 30
Section 2 : Listes chainées ................................................................................................................. 30
Section 3 : Opérations sur les listes chainées................................................................................... 31
Section 4 : Listes circulaires............................................................................................................... 32
Section 5 : Listes bidirectionnelles .................................................................................................... 34
Chapitre 3 : Structure d’arbre : arbre binaire de recherche ................................................................. 36
Section 1 : Opération sur les arbres (Parcours en profondeur) ........................................................ 36
Section 2 : Piles et files ...................................................................................................................... 38
Section 3 : Recherche ........................................................................................................................ 45
Chapitre 4 : Fichiers............................................................................................................................... 47
Section 1 : Notion des fichiers........................................................................................................... 47
Section 2 : Différents types de fichiers............................................................................................. 47
Section 3 : Organisation et accès aux fichiers ................................................................................... 48
Section 4 : Opérations sur les fichiers ............................................................................................... 48
Chapitre 5 : Notion de complexité ........................................................................................................ 50
Section 1 : Notion de complexité ...................................................................................................... 50
Section 2 : Calcul de la complexité ................................................................................................... 51
 87

Chapitre 6 : Présentation de langage C ................................................................................................. 56

Section 1 : Structure d’un langage C ................................................................................................. 56
Section 2 : Structure d’un programme C.......................................................................................... 56
Section 3 : Types de variables ........................................................................................................... 58
Section 4 : Déclaration des variables, instruction d’affectation et opérations d’E/S....................... 59
Chapitre 7 : Instructions de contrôle..................................................................................................... 67
Section 1 : Instructions conditionnelles ............................................................................................ 67
Section 2 : Instructions de contrôles interactifs................................................................................ 68
Chapitre 8 : Fonctions et procédure en C.............................................................................................. 73
Section 1 : Structure d’une fonction et d’une procédure ................................................................. 73
Section 2 : Passage des paramètres .................................................................................................. 74
Section 3 : Quelques fonctions en C................................................................................................. 74
Chapitre 9 : Structure des données....................................................................................................... 75
Section 1 : Tableaux........................................................................................................................... 75
Section 2 : Fichiers................................................................................................................................. 76
Bibliographie.......................................................................................................................................... 85