SUPPORT DE COURS

Année académique / Semestre 2024-2025/ SEMESTRE 1

Intitulé du cours Algorithmique de base

Classe / Niveau GL/ Niveau 1

Enseignant M. NDJE MAN Dieudonné François
Coordonnées Tél : 654080512
Email : [email protected]
Volume Horaire global 45 h CM : 20 h TD : 10 h TP : 15 h
TABLE DES MATIERES
CHAPITRE 1 INTRODUCTION A L’ALGORITHMIQUE .................................................. 1
1.1 CONCEPTS ET PRINCIPES FONDAMENTAUX DE L’ALGORITHMIQUE
1
1.1.1 ALGORITHMIQUE ................................................................................................... 1
1.1.2 ALGORITHME ........................................................................................................... 2
1.1.3 PSEUDOCODE .......................................................................................................... 2
1.1.4 TRACE D’EXECUTION D’UN ALGORITHME ............................................... 4
1.1.5 PROGRAMME ............................................................................................................ 4
1.2 DEMARCHE ALGORITHMIQUE ET RESOLUTION DE PROBLEMES....... 6
1.2.1 ELABORATION D’UN ALGORITHME : SPECIFICATION ET TESTS 6
1.3 INSTRUCTIONS DE BASE ........................................................................................ 11
1.4 STRUCTURE DE BASE D’UN ALGORITHME ................................................... 12
1.4.1 L'EN-TETE ................................................................................................................ 12
1.4.2 LA PARTIE DECLARATIVE ............................................................................... 13
1.4.3 LE CORPS DE L'ALGORITHME....................................................................... 13
1.5 EXERCICES DE FIN DE CHAPITRE ...................................................................... 14
1.5.1 EXERCICE 1 : DEFINITIONS DES CONCEPTS ....................................... 14
1.5.2 EXERCICE 2 : QUESTIONS DE COURS...................................................... 14
1.5.3 EXERCICE 3 : ECRITURE D’UN ORGANIGRAMME .............................. 14
CHAPITRE 2 : TYPE DE DONNEES ET VARIABLES ...................................................... 1
2.1 TYPE DE DONNEES EN ALGORITHMIQUE ........................................................ 1
2.1.1 TYPE DE DONNEES SIMPLE ............................................................................. 1
2.2 DECLARATION ET MANIPULATION DES VARIABLES ................................. 3
2.2.1 VARIABLES ET CONSTANTES : CONCEPTS CLES DES
ALGORITHMES ........................................................................................................................ 3
CHAPITRE 3 : STRUCTURES DE CONTRÔLES ................................................................ 6
3.1 INTRODUCTION .............................................................................................................. 6
3.1.1 EXPRESSION CONDITIONNELLE ................................................................... 7
3.2 STRUCTURES CONDITIONNELLES....................................................................... 7
3.3 STRUCTURES ITERATIVES .................................................................................... 13
 3.3.1 PRINCIPE DE L'ITERATION ............................................................................. 13
3.4 EXERCICES DE FIN DE CHAPITRE ...................................................................... 23
CHAPITRE 4 : STRUCTURES DE DONNEES ................................................................... 25
4.1 LES TABLEAUX ............................................................................................................. 25
4.1.1 DEFINITION ............................................................................................................. 25
4.1.2 DIMENSION D'UN TABLEAU ........................................................................... 25
4.2 LES ENREGISTREMENTS ......................................................................................... 31
4.2.1 DEFINITION ET DECLARATION DES ENREGISTREMENTS ............ 32
4.1 LES CHAINES DE CARACTERES .......................................................................... 37
4.1.1 DECLARATION ET INITIALISATION D’UNE CHAINE.......................... 37
4.1.2 OPERATIONS DE BASE SUR LES CHAINES DE CARACTERES..... 38
4.1.3 MANIPULATION DES SOUS-CHAINES ....................................................... 39
4.1.4 COMPARAISON DE CHAINES ......................................................................... 39
4.1.5 RECHERCHE DE SOUS-CHAINES ................................................................. 39
4.1.6 RECHERCHE OPTIMISEE (KNUTH-MORRIS-PRATT, BOYER-
MOORE) ..................................................................................................................................... 40
4.2 EXERCICES SUR LES CHAINES DE CARACTERE ........................................ 40
CHAPITRE 5 : LES SOUS ALGORITHMES : FONCTIONS ET PROCEDURES... 42
5.1 GENERALITES ............................................................................................................... 42
5.2 DEFINITION ..................................................................................................................... 42
5.2.1 SOUS-PROGRAMMES ......................................................................................... 42
5.2.2 DECLARATION DES SOUS-PROGRAMMES.............................................. 43
5.2.3 VARIABLES LOCALES ET VARIABLES GLOBALES ............................ 52
5.2.4 PASSAGE DE PARAMETRES : PAR VALEUR ET PAR REFERENCE
56
5.2.5 LA RECURSIVITE.................................................................................................. 61
5.2.6 DIFFERENCE ENTRE ITERATION ET RECURSIVITE .......................... 63
5.3 EXERCICES DE FIN CHAPITRE ............................................................................. 70
CHAPITRE 6 : ALGORITHMIQUE AVANCEE ................................................................... 72
6.1 ALGORITHMES DE TRI .............................................................................................. 72
6.1.1 INTRODUCTION .................................................................................................... 72
6.1.2 DEFINITION DU TRI ............................................................................................ 72
• La complexité d'un algorithme de tri par insertion ................................................. 82
 • Complexité générale ........................................................................................................ 83
Code en C pour le tri à bulles ........................................................................................................ 85
• Complexité ......................................................................................................................... 86
6.2 ALGORITHMES DE RECHERCHE .......................................................................... 87
6.2.1 INTRODUCTION .................................................................................................... 87
6.2.2 ALGORITHMES DE RECHERCHE CLASSIQUES .................................... 87
6.3 EXERCICES DE FIN CHAPITRE ............................................................................. 96
6.3.1 EXERCICES SUR LES TRIS ............................................................................. 96
6.3.2 EXERCICES SUR LES ALGORITHMES DE RECHERCHE ................... 96
CHAPITRE 7 : APPLICATIONS PRATIQUES .................................................................... 98
7.1 IMPLEMENTATION D’ALGORITHME EN LANGAGE DE
PROGRMAMTION C ................................................................................................................. 98
7.1.1 ÉTAPES POUR DEVELOPPER UN PROGRAMME .................................. 98
7.1.2 DIFFERENTS TYPES DE LANGAGES .......................................................... 98
7.1.3 PARTICULARITES DU LANGAGE C ............................................................. 99
7.1.4 QUELQUES INCONVENIENTS........................................................................ 99
7.2 TRADUIRE UN ALGORITHME EN LANGAGE C .............................................. 99
7.3 ENTREES-SORTIES EN LANGAGE C : COMPRENDRE, SIMPLIFIER ET
APPLIQUER ............................................................................................................................... 100
7.3.1 CORRESPONDANCE ALGORITHME - C ................................................... 100
7.3.2 COMPRENDRE LES FORMATS ..................................................................... 100
7.3.3 PRECISIONS SUR L'INSTRUCTION PRINTF EN LANGAGE C ...... 103
7.3.4 CAPTURE DES SORTIES DU PROGRAMME DANS UN FICHIER . 104
7.3.5 CONSEILS .............................................................................................................. 104
7.3.1 STRUCTURE D’UN PROGRAMME ............................................................... 105
7.3.2 TYPES DE DONNEES ET LEURS ÉQUIVALENTS................................ 105
7.3.3 OPERATIONS ........................................................................................................ 105
7.3.4 ENTREES ET SORTIES .................................................................................... 105
7.3.5 CONDITIONNELLES .......................................................................................... 106
7.3.6 BOUCLES ................................................................................................................ 108
7.3.7 TABLEAUX ............................................................................................................. 109
7.3.8 FONCTIONS........................................................................................................... 109
7.4 EXERCICE DE FIN DE CHAPITRE ....................................................................... 109
CHAPITRE 1 INTRODUCTION A L’ALGORITHMIQUE
L’algorithmique est une compétence essentielle en génie logiciel, car elle permet de résoudre
des problèmes de manière structurée et efficace. Ce cours d’introduction vise à familiariser les
apprenants avec les bases de la conception d’algorithmes, en leur apprenant à transformer
des idées en solutions claires et optimisées, prêtes à être traduites en code. Historiquement,
Ada Lovelace1, souvent considérée comme la première programmeuse de l'histoire, a joué un
rôle pionnier lors de son travail sur la machine analytique de Charles Babbage, un ancêtre de
l’ordinateur moderne. Dans ses notes, elle a décrit le premier programme destiné à être
exécuté par une machine, établissant ainsi les fondements de la programmation. Ce cours
s’inscrit dans cette lignée, en enseignant comment concevoir des algorithmes efficaces, tout
comme Ada Lovelace l’a fait à ses débuts, pour rendre les programmes plus rapides et
économes en ressources.

1.1 CONCEPTS ET PRINCIPES FONDAMENTAUX DE

L’ALGORITHMIQUE

1.1.1 ALGORITHMIQUE
L’algorithmique est l'étude des algorithmes en les analysant afin d'en mesurer l'efficacité et la
fiabilité.

L'algorithmique est essentielle dans tous les domaines où l'on cherche à résoudre des
problèmes de manière efficace, que ce soit en informatique, mathématiques, sciences,
ingénierie ou gestion. C'est le cœur même de l'informatique, car un informaticien sans
connaissances en algorithmique serait limité dans sa capacité à concevoir des solutions
optimales. Ce domaine est d'une grande richesse : certains problèmes admettent plusieurs
solutions efficaces avec des approches variées, tandis que d'autres, comme les problèmes
NP-complets2, semblent n'avoir que des solutions inefficaces. De plus, certains problèmes,
comme les valeurs numériques exactes ou les problèmes indécidables, ne peuvent pas être
résolus avec certitude par un algorithme.

1
Ada Lovelace était une mathématicienne britannique du 19e siècle, considérée comme la première
programmeuse de l'histoire pour son travail sur la machine analytique. Charles Babbage, ingénieur et
mathématicien, est l'inventeur de cette machine, souvent vue comme le premier concept d'ordinateur
mécanique.
2 Les problèmes NP-complets sont des problèmes très complexes dont on peut vérifier rapidement
une solution, mais pour lesquels trouver cette solution peut prendre un temps énorme. Un exemple est
le problème du voyageur de commerce, où il est facile de vérifier un chemin, mais très difficile de trouver
le meilleur.

1
Étudier l'algorithmique permet de mieux comprendre comment un ordinateur fonctionne et de
répondre à des questions essentielles comme : un algorithme se termine-t-il toujours ? Le
résultat obtenu est-il correct ? Combien de temps prendra son exécution ? L'ordinateur a-t-il
assez de mémoire pour le faire tourner efficacement ? Et peut-on rendre le programme plus
rapide ou moins gourmand en ressources ? L'algorithmique nous aide à prouver qu'un
algorithme est correct, à comparer différentes solutions pour un même problème, et à explorer
des exemples concrets de modélisation et de résolution de problèmes.

1.1.2 ALGORITHME
Un algorithme est une suite finie d'instructions claires et précises permettant de résoudre un
problème en un nombre limité d'étapes. Il est structuré en trois parties :
▪ L’entrée des données
▪ Le traitement des données
▪ La sortie des données
Les algorithmes sont indépendants des langages de programmation et suivent des principes
universels. Historiquement, le mot "algorithme" vient du mathématicien Al-Khwarizmi, bien que
des algorithmes comme celui d'Euclide existaient déjà il y a des milliers d'années. En pratique,
les algorithmes sont souvent rédigés en pseudo-code, ce qui permet de se concentrer sur la
logique du problème sans se soucier des détails techniques d'un langage spécifique.
L'importance de l'algorithmique en informatique réside dans le fait que les ordinateurs, ne
pouvant prendre d'initiatives, exécutent strictement les algorithmes fournis. Un programme
informatique est donc fondamentalement un algorithme.
Dans le cas particulier de l'informatique, une étape supplémentaire vient se glisser entre la
conception de l'algorithme et sa réalisation à travers un processus : l'algorithme doit être rendu
compréhensible par la machine que nous allons utiliser pour résoudre effectivement le
problème. Le résultat de la traduction de l'algorithme dans un langage connu de la machine
est appelé un programme.

1.1.3 PSEUDOCODE
Le pseudo-code est un langage simplifié, proche du langage humain, utilisé pour décrire les
étapes d'un algorithme sans se soucier des règles spécifiques d'un langage de
programmation. Il existe plusieurs façons de créer un algorithme : avec du pseudo-code, en
dessinant un algorigramme (un diagramme représentant l'algorithme visuellement), ou en
écrivant directement le code dans un langage compréhensible par l’homme. Le pseudo-code
et l'algorigramme3 sont souvent privilégiés car ils sont universels, lisibles et compréhensibles,

3 Un algorigramme est une représentation graphique d'un algorithme, utilisant des symboles pour
illustrer le flux des étapes de traitement et les décisions logiques.

2
 même par des non-experts, contrairement aux langages de programmation qui utilisent des
symboles complexes.

Exemple : Écrivez un algorithme qui permet de résoudre une équation du premier degré de la
forme a * x + b = 0, où a et b sont des nombres réels donnés.
L'algorithme doit commencer par demander à l'utilisateur de saisir les valeurs de a et b.
Ensuite, il vérifie si a est différent de zéro.
Si c'est le cas, il calcule et affiche la solution x = -b / a. Dans le cas où a est égal à zéro,
l'algorithme doit indiquer s'il y a une solution unique, une infinité de solutions, ou aucune
solution selon la valeur de b.

Solution par utilisation de pseudocode et d’algorigramme.

Pseudocode Algorigramme ou Organigramme

Algorithme RésolutionÉquation
Début
// Étape 1 : Entrer les valeurs a et b
Lire a // Coefficient de l'équation
Lire b // Terme constant

// Étape 2 : Vérifier si a est différent

de 0
Si a <> 0 Alors
// Calculer la solution unique
x <- -b / a
Ecrire "La solution est : ", x
Sinon
// Étape 3 : Vérifier si b est
différent de 0
Si b <> 0 Alors
Ecrire "Il n'y a pas de
solution"
Sinon
Ecrire "x peut être n'importe
quel nombre"
FinSi
FinSi
Fin

L'organigramme
Un organigramme est une représentation visuelle du déroulement d'un problème, en utilisant
des symboles graphiques standardisés pour montrer l'ordre des actions à effectuer. Il permet
de visualiser clairement chaque étape d'un processus. Quatre symboles principaux sont
utilisés pour construire un organigramme :

3
 AVANTAGES DU PSEUDO-CODE PAR RAPPORT A L'ALGORIGRAMME
Le pseudo-code est souvent préféré à l'algorigramme pour plusieurs raisons. D'abord, il reste
clair et lisible même lorsque l'algorithme devient long ou complexe. Il est également mieux
adapté pour représenter des informations textuelles, comme des messages à afficher à
l'écran. De plus, la traduction en langage de programmation est plus fluide, car la structure du
pseudo-code est proche de celle des langages informatiques. Enfin, il convient
particulièrement bien à la conception de programmes purement informatiques, destinés aux
ordinateurs, applications mobiles ou web.

1.1.4 TRACE D’EXECUTION D’UN ALGORITHME

La trace d'exécution d'un algorithme est une méthode qui permet de suivre et d'analyser le
déroulement des opérations effectuées par celui-ci sur des données spécifiques. Elle offre un
aperçu précieux sur la manière dont les valeurs sont manipulées à chaque étape, facilitant
ainsi la compréhension du fonctionnement de l'algorithme et la détection d'éventuelles erreurs.

La trace se décompose en plusieurs étapes : initialisation des variables, évaluation des

conditions, mise à jour des valeurs et retour final. Par exemple, pour une fonction médiane (a,
b, c), on suit l'appel de la fonction avec des valeurs spécifiques et l'évaluation des conditions.
C’est donc un outil essentiel qui aide les informaticiens à comprendre le comportement des
algorithmes, à garantir leur fiabilité et à optimiser leurs performances.

1.1.5 PROGRAMME
Un programme est une réalisation concrète d'un algorithme, écrit dans un langage de
programmation compréhensible par un ordinateur. Il permet de transformer les idées
abstraites d'un algorithme en un ensemble d'instructions exécutables.

4
Une fois l'algorithme écrit et validé, il faut donc, dans un second temps :
▪ Le traduire dans un langage informatique (C++, Python, Javascript, etc.) ;
▪ Éventuellement, l’adapter aux composants matériels du système numérique.
On obtient alors un programme informatique qui implémente l’algorithme.

Un programme se compose généralement de trois étapes fondamentales :

▪ L’entrée des données : C'est la phase où les informations nécessaires à la résolution
du problème sont fournies. Ces données peuvent provenir de l'utilisateur, de
fichiers, ou d'autres sources.

▪ Le traitement des données : Il s'agit du cœur du programme. Ici, les données

d'entrée sont manipulées selon les règles définies dans l'algorithme. C'est cette
étape qui résout effectivement le problème posé.

▪ La sortie des données : Après le traitement, les résultats sont affichés ou stockés,
afin que l'utilisateur puisse en prendre connaissance ou les utiliser à d'autres fins.

Un algorithme est abstrait et indépendant du langage de programmation, tandis qu'un

programme est lié à un langage spécifique. Cela permet à un même algorithme de fonctionner
sur différents appareils, même si le langage utilisé change. Le programme traduit l'algorithme
pour que l'ordinateur puisse l'exécuter, tout en gérant la mémoire, les erreurs et les
performances. En informatique, la qualité du programme est cruciale pour automatiser les
tâches et contrôler des systèmes efficacement, qu'ils soient simples ou complexes.
Tableau différenciant l'algorithmique, l'algorithme et le programme :

5
 1.2 DEMARCHE ALGORITHMIQUE ET RESOLUTION DE
PROBLEMES

1.2.1 ELABORATION D’UN ALGORITHME : SPECIFICATION

ET TESTS
1.2.1.1 SPECIFICATION
Avant de commencer à écrire un algorithme, il est essentiel de bien définir ce que l'on cherche
à accomplir et à partir de quelles données. Cela revient à formuler une spécification du
problème. Pour cela, voici les étapes à suivre :
▪ Nom explicite de l'algorithme : Choisir un nom qui reflète
clairement l'objectif de l'algorithme. Ex : Calculatrice, Addition, etc.
▪ Conditions d'utilisation (ou préconditions) : Décrire les données
d'entrée, comme leur nature et leurs contraintes. Par exemple, une
précondition peut être : "l'entrée doit être un entier supérieur à 0".
▪ Résultat attendu (ou postcondition) : Décrire les données qui
seront renvoyées à la fin de l'exécution de l'algorithme et expliquer
ce qu'elles représentent.
DEFINITIONS IMPORTANTES
❖ Précondition
Une précondition est une condition qui doit être vérifiée avant le début d’un calcul ou l’appel
d’une fonction. Cela permet de garantir que l'algorithme pourra s'exécuter correctement. Par
exemple, avant d'effectuer une division, il faut vérifier que le dénominateur n'est pas égal à
zéro, sinon le calcul échouerait.
❖ Postcondition
Une postcondition est une condition qui doit être vérifiée à la fin de l'exécution d’un calcul ou
d’une fonction. Si cette condition est remplie, cela indique que le calcul s'est déroulé
correctement. À l'inverse, si la postcondition n'est pas respectée, cela révèle une erreur,
souvent due à un problème de programmation. Par exemple, à la fin d'une fonction qui retourne
la valeur absolue d'un nombre, il faut s'assurer que le résultat est bien supérieur ou égal à
zéro.
Bien définir les préconditions et postconditions est crucial pour garantir la fiabilité d’un
algorithme. Cela permet d’éviter les erreurs en s’assurant que les entrées sont valides et que
le résultat produit est correct.

Remarque 1.1 : Un programmeur qui prend le temps de bien documenter ses fonctions
effectue, en réalité, l’étape de spécification. Cette démarche permet de clarifier le
fonctionnement du programme avant même de l’écrire.

6
Exemple pratique : Calculer la somme des n premiers entiers
Problème : Nous voulons calculer la somme des n premiers entiers, où n est un entier donné.
Spécification de l'algorithme :
▪ Nom de l’algorithme : Somme des premiers entiers.
▪ Données d’entrée : Un entier strictement positif, noté n, qui représente la limite
supérieure de la somme (c’est la précondition, car n doit être strictement positif pour
que l’algorithme fonctionne correctement).
▪ Données de sortie : Un entier S, qui contiendra la somme des entiers allant de 1 à n
(c’est la postcondition, car elle indique le résultat attendu après l'exécution de
l'algorithme).
L’algorithme suivant correspond à cette spécification :
fonction somme_premiers_entiers(n)
S ← 0
k ← 1
tant que k ≤ n faire
S ← S + k
k ← k + 1
fin tant que
renvoyer S
fin fonction

Méthodologie générale pour écrire un algorithme

1. Identification des données d’entrée
La première étape consiste à déterminer quelles sont les données nécessaires à la résolution
du problème. Ces données peuvent prendre différentes formes :

▪ Numériques (par exemple des entiers ou des réels),

▪ Textuelles (comme des chaînes de caractères),
▪ Logiques (valeurs booléennes : vrai ou faux),
▪ Ou encore graphiques (positions, images, etc.).

Dans cette étape, on récupère les données via diverses méthodes, comme une saisie par
l’utilisateur, un clic de souris, ou la lecture d’un fichier. Il est crucial de définir ici des
préconditions, c’est-à-dire les conditions que doivent respecter ces données pour que
l’algorithme fonctionne correctement.

2. Définition de la sortie
Ensuite, il faut décider sous quelle forme le résultat de l’algorithme sera présenté. Ce résultat
peut être affiché à l’écran, stocké dans des variables pour un usage ultérieur, ou encore écrit
dans un fichier. Il s’agit ici des postconditions, qui décrivent le format et la nature du résultat.
7
 3. Traitement des données
L’étape la plus importante consiste à écrire précisément la séquence d'instructions permettant
de transformer les données d’entrée en données de sortie. Ces instructions se répartissent en
trois types :
▪ Affectations : Transfert ou manipulation des données (par exemple, lire une
donnée, la stocker dans une variable ou la copier).
▪ Instructions arithmétiques : Effectuer des opérations mathématiques comme
l'addition, la soustraction, la multiplication, la division, ou l'utilisation
d’opérateurs comme le modulo et la partie entière.
▪ Instructions de contrôle : Gérer la logique du programme à travers des
structures alternatives (par exemple, si... alors... sinon) ou répétitives (comme
les boucles tant que ou pour), ainsi que les appels à des fonctions externes.

Pour bien écrire un algorithme, il est essentiel de suivre une méthodologie claire. Cela inclut
la définition des données d’entrée et de sortie, la spécification des conditions (préconditions
et postconditions) et l'écriture détaillée du traitement des données. En suivant ces étapes, on
peut garantir un algorithme précis et fiable, minimisant ainsi les erreurs et assurant un bon
fonctionnement.

Exercice d’application 1 : Samuel Eto’o veut avoir une solution pour calculer sa moyenne en
Sport, en tenant compte de trois notes qui ont des coefficients différents. La première note
(Note de Vitesse) qui a un coefficient de 1, la deuxième note (Note de Précision) un coefficient
de 2, et la troisième note (Note d'Endurance) un coefficient de 0,5. Pour résoudre ce problème,
il faut d'abord écrire une spécification qui décrit clairement le calcul : on multiplie chaque note
par son coefficient respectif, on additionne les résultats obtenus, puis on divise cette somme
par le total des coefficients (c'est-à-dire 3,5). Ensuite, on peut écrire un algorithme simple qui
suit ces étapes pour calculer et afficher la moyenne pondérée de Samuel Eto’o.

Notez-bien : La moyenne pondérée est un moyen de calculer une moyenne en tenant compte
de l'importance de chaque note, appelée coefficient. On multiplie chaque note par son
coefficient, on additionne les résultats, puis on divise par le total des coefficients.

Résolution de l’exercice :
Pour résoudre cet exercice, il faut suivre les étapes décrites pour calculer la moyenne
pondérée d’Eto’o:
1. Spécification du calcul :
- Première note (N1) : coefficient 1
- Deuxième note (N2) : coefficient 2
- Troisième note (N3) : coefficient 0,5

8
 - Total des coefficients : 1 + 2 + 0,5 = 3,5
- Formule de la moyenne pondérée : Moyenne = [(N1 * 1) + (N2 * 2) + (N3 * 0,5)] / 3,5
2. Exemple avec des valeurs concrètes :
- Supposons que les notes soient N1 = 12, N2 = 15, et N3 = 10.
- Calcul :
- 12 * 1 = 12
- 15 * 2 = 30
- 10 * 0,5 = 5
- Somme des résultats : 12 + 30 + 5 = 47
- Moyenne pondérée : 47 / 3,5 ≈ 13,43
3. Algorithme (en pseudo-code) :
Algorithme CalculMoyenneSport
Variables N1, N2, N3 : réel
Variable S : réel
Variable Moyenne : réel
Début
// Étape 1 : Entrer les notes
Écrire "Entrez la note de Vitesse :"
Lire N1 // Note de Vitesse
Écrire "Entrez la note de Précision :"
Lire N2 // Note de Précision
Écrire "Entrez la note d'Endurance :"
Lire N3 // Note d'Endurance
// Étape 2 : Calculer la somme pondérée
S <- (N1 * 1) + (N2 * 2) + (N3 * 0,5)
// Étape 3 : Calculer la moyenne pondérée
Moyenne <- S / 3,5
// Étape 4 : Afficher la moyenne
Écrire "La moyenne pondérée est : ", Moyenne
Fin
Si on applique ce calcul avec les notes données dans l'exemple, la moyenne pondérée de
Charles serait environ 13,43.

1.2.1.2 TESTS
Même en ayant correctement défini la fonction, des erreurs peuvent encore survenir lors de
l'écriture de l'algorithme. Pour détecter ces éventuelles erreurs, il est important de tester
l'algorithme sur des cas concrets afin de vérifier qu'il produit bien le résultat attendu. Si ce n'est

9
pas le cas, il faudra alors passer à l'étape de débogage, où l'on tentera de corriger les erreurs
identifiées dans l'algorithme.

Exemple 1.1 : Prenons la fonction somme_premiers_entiers(n) qui calcule la somme des

premiers entiers de 1 à n. Pour vérifier son bon fonctionnement, il est essentiel de la tester
avec des valeurs spécifiques afin de s'assurer qu'elle renvoie bien les résultats attendus.
Exemple de tests :

Les tests permettent de s'assurer que l'algorithme fonctionne correctement sur des données
précises. Pour une programmation efficace, il est essentiel de concevoir des séries de tests
qui vérifient que l'algorithme donne les résultats attendus dans des cas spécifiques bien
choisis. Bien que l'on ne puisse pas couvrir toutes les erreurs possibles avec un seul ensemble
de tests, il est conseillé de respecter certaines règles pour en maximiser l'efficacité, telles que
:
▪ Si la spécification de l'algorithme mentionne plusieurs cas possibles, il est
important de les tester tout.
▪ Si l'algorithme doit renvoyer une valeur booléenne, il faut s'assurer que les tests
permettent d'obtenir à la fois un résultat vrai et faux.
▪ Si l'algorithme travaille sur un tableau (ou une liste), il est crucial d'effectuer un test
avec un tableau vide.
▪ Si l'algorithme traite des nombres, il convient de tester des valeurs positives,
négatives et zéro, ou d'autres valeurs spécifiques comme les limites de l'intervalle
défini par la spécification.

Exercice d’application 2 : Le pseudocode suivant compare les trois valeurs données (a, b,
et c) pour renvoyer celle qui est située au milieu, c'est-à-dire la médiane.
fonction médiane(a, b, c)
si (a ≤ b et b ≤ c) ou (c ≤ b et b ≤ a) alors
renvoyer b
sinon si (b ≤ a et a ≤ c) ou (c ≤ a et a ≤ b) alors

10
 renvoyer a
sinon
renvoyer c
fin si
fin fonction
Proposez un test pour la fonction médiane avec les valeurs suivantes : a = 7, b = 3, c = 5

1.3 INSTRUCTIONS DE BASE

1.3.1.1 L’AFFECTATION
L'instruction d'affectation permet d’attribuer une valeur à une variable. Cette valeur peut être
un nombre ou le résultat d'une opération arithmétique ou logique. Il est essentiel que la variable
et la valeur attribuée soient du même type pour garantir la cohérence des données. C'est un
moyen de stocker des données que l'on peut utiliser et modifier dans un programme. En
général, cette instruction est représentée par une flèche (←).
Syntaxe :
<identificateur> ← <expression> ou encore nom_variable ← valeur
Exemple :
x ← 5 // Cela signifie que la variable x reçoit la valeur 5.

1.3.1.2 LES ENTREES / SORTIES

Les instructions d’entrée/sortie permettent de lire des données (entrée) ou d'afficher des
résultats (sortie). Ce sont des actions qui expriment la communication entre l'algorithme et
l’utilisateur.
▪ Entrée : Utilisée pour obtenir des informations de l'utilisateur. Elle ordonne à
l'ordinateur de de lire ou prendre une donnée (valeur), que l'utilisateur va entrer au
clavier et qu'elle va mettre dans sa mémoire. C'est donc une instruction qui permet de
stocker les valeurs, tapées au clavier, dans les cases mémoires correspondants aux
variables. Après le mot Écrire, on indique ce qui sera transmis. Cela peut être la valeur
d'une variable, une chaine ou un mélange des deux.
Exemple :
o Lire(n) /Saisir(n) // Lit un nombre entier n entrée par l’utilisateur

▪ Sortie : Utilisée pour afficher des informations à l'utilisateur. Elle ordonne à la machine
d'écrire ou d'afficher à l'écran le contenu d'une variable ou d'un message. La valeur de
cette information est affectée à une variable, dont le nom suit le mot-clé Lire.
Exemple :
o Ecrire/Afficher ("Le résultat est :", x) // Affiche "Le résultat est :" suivi de la valeur
de x

11
 1.3.1.3 LES INSTRUCTIONS DEBUT ET FIN
Ces instructions délimitent un algorithme ou une procédure, marquant son commencement et
sa conclusion.
a. Début de l'algorithme
L'instruction de début marque le commencement de l'algorithme.
Syntaxe :
début.
b. Fin de l'algorithme
L'instruction de fin indique que l'algorithme est terminé.
Syntaxe :
fin.

Ces instructions de base sont cruciales en algorithmique. Elles permettent de structurer les
algorithmes, et en les combinant, on peut concevoir des solutions efficaces pour une large
gamme de problèmes.

1.4 STRUCTURE DE BASE D’UN ALGORITHME

La structure d'un algorithme suit généralement un schéma similaire, bien que des variations
puissent apparaître selon le langage de programmation utilisé ou le contexte d'application.
Un algorithme est une méthode pour résoudre un problème en le décomposant en étapes
simples et claires, à suivre dans un ordre précis. Il se présente toujours sous une forme bien
définie, avec trois parties principales : l’entête, la partie déclarative et le corps de l’algorithme.

1.4.1 L'EN-TETE
Cette partie commence par le mot-clé "Algorithme", suivi d'un nom qui décrit le problème à
résoudre. Par exemple, "Algorithme Somme" pour un algorithme qui calcule une somme.

12
 1.4.2 LA PARTIE DECLARATIVE
Ici, on énumère toutes les variables nécessaires à l'algorithme. Cela inclut les variables
d'entrée (données à traiter), les variables de sortie (résultats), et les variables intermédiaires.
On commence cette section par le mot-clé "Var".
Exemple :
Var x, y : entier (pour des nombres entiers)
c : caractère (pour une variable de type caractère).

1.4.3 LE CORPS DE L'ALGORITHME

Cette section contient les instructions à exécuter pour résoudre le problème. Elle commence
par le mot "Début" et se termine par "Fin". Entre ces deux mots, se trouvent toutes les étapes
que la machine doit suivre pour arriver au résultat final.
Avec ces trois parties, un algorithme devient une solution claire et ordonnée à un problème
donné.
▪ Début de l'algorithme : Indique le point de départ de l'algorithme.
▪ Instructions et séquences d'opérations : C'est la partie centrale où l'on décrit, étape par
étape, la manière de résoudre le problème. Cela inclut des calculs, des opérations, des
prises de décision (instructions conditionnelles), ainsi que des boucles (instructions
itératives) pour répéter certaines actions.
▪ Sortie des résultats : Après l'exécution complète des étapes, les résultats de
l'algorithme sont produits ou affichés. Cela peut consister en l'affichage de valeurs
calculées, la création de rapports, ou d'autres types de sortie.
▪ Fin de l'algorithme : Marque la conclusion de l'algorithme.
Arrivé au terme de ce chapitre, nous dirons que, ce chapitre a posé les bases de
l'algorithmique, une discipline fondamentale en informatique. Nous avons exploré les concepts
essentiels, allant de la définition des algorithmes jusqu'à la manière dont ils sont traduits en
programmes exécutables par des machines. L'algorithmique permet de concevoir des
solutions structurées et efficaces pour résoudre divers problèmes, tout en garantissant la
bonne utilisation des ressources informatiques. L'apprentissage de ces bases est
indispensable pour tout futur programmeur ou ingénieur en informatique, car les algorithmes
sont à la fois le moteur et l'âme des programmes que nous utilisons chaque jour.

Maîtriser l'algorithmique permet non seulement de mieux comprendre comment les

ordinateurs fonctionnent, mais aussi de créer des programmes plus rapides, fiables et
économes en ressources. Grâce à une approche méthodique, comme celle employée par Ada
Lovelace dans ses premières expérimentations, vous serez en mesure de transformer des
idées en solutions pratiques.

13
1.5 EXERCICES DE FIN DE CHAPITRE

1.5.1 EXERCICE 1 : DEFINITIONS DES CONCEPTS

Instructions : Pour chaque concept ci-dessous, donnez une définition claire et concise.

Algorithmique, Algorithme, Pseudocode, Organigramme, Trace d’exécution

1.5.2 EXERCICE 2 : QUESTIONS DE COURS

Instructions : Répondez aux questions ci-dessous en vous basant sur vos connaissances du
chapitre 1.

1. Pourquoi l'algorithmique est-elle essentielle en informatique et en génie logiciel ?

2. Quelle est la différence entre un algorithme et un programme ?
3. En quoi le pseudocode est-il avantageux par rapport à un algorithme directement écrit
en langage de programmation ?
4. Comment tester et valider un algorithme une fois celui-ci écrit ?
5. Quels sont les éléments à prendre en compte lors de l'élaboration d'un algorithme pour
garantir qu'il est efficace et correct ?

1.5.3 EXERCICE 3 : ECRITURE D’UN ORGANIGRAMME

Soit un rectangle ABCD écrire sous forme d’algorigramme un algorithme qui permet de
calculer ma surface et le périmètre de ce rectangle.

14
CHAPITRE 2 : TYPE DE DONNEES ET VARIABLES
Maintenant qu’on a compris les bases de l’algorithmique, il est temps d'aborder un aspect
fondamental de tout programme : les types de données et les variables. Ces concepts sont
essentiels pour la manipulation des informations dans un algorithme. Un type de donnée
détermine la nature des informations qu’une variable peut stocker, tandis que les variables
servent de conteneurs pour ces informations. Dans le prochain chapitre, nous explorerons les
différents types de données, comment les utiliser, et leur rôle crucial dans la construction
d’algorithmes efficaces.

2.1 TYPE DE DONNEES EN ALGORITHMIQUE

Le type de données en algorithmique définit la nature des valeurs que cet objet peut contenir.
Il existe deux grandes catégories de types : les types simples et les types structurés.
▪ Types simples : Un objet de type simple contient une seule valeur. Par exemple, on
peut avoir des variables de type numérique (comme un nombre entier ou un nombre
décimal) ou des variables de type caractère (comme une lettre ou un symbole).

▪ Types structurés : En revanche, un objet structuré peut contenir plusieurs valeurs,

regroupées en une seule entité. Par exemple, un tableau peut contenir plusieurs
éléments sous un même nom.
2.1.1 TYPE DE DONNEES SIMPLE
Les types simples en programmation représentent les éléments de base avec lesquels nous
travaillons. Ils se divisent principalement en trois catégories : les types numériques, le type
logique (booléen) et le type caractère. Chaque catégorie possède ses propres caractéristiques
et opérations associées.

2.1.1.1 TYPES NUMERIQUES

Les types numériques sont utilisés pour représenter des valeurs numériques. Ils se divisent
en deux sous-catégories principales :
ENTIERS
- Description : Les entiers sont des nombres qui n'ont pas de partie décimale. Ils peuvent être
positifs, négatifs ou nuls.
- Exemples : -2, 0, 5, 42.
- Utilisation : Ils sont souvent utilisés pour compter des objets, indexer des tableaux ou
réaliser des opérations de base où les décimales ne sont pas nécessaires.
REELS
- Description : Les réels sont des nombres qui incluent des parties décimales, permettant une
représentation plus précise.

1
 - Exemples : 3.14, -0.5, 2.71828.
- Utilisation : Ils sont utilisés dans les calculs nécessitant une précision, comme en sciences,
en ingénierie et dans les applications financières.

2.1.1.2 OPERATIONS SUR LES TYPES NUMERIQUES

Les opérations sur les types numériques incluent les opérations arithmétiques et de
comparaison. Elles constituent les bases des calculs numériques et des prises de décision
logiques dans la programmation et les mathématiques. On peut citer :
OPERATIONS ARITHMETIQUES
+ : Addition — Combine deux nombres pour donner leur somme.
- : Soustraction — Calcule la différence entre deux nombres.
* : Multiplication — Produit de deux nombres.
\: Division — Division d'un nombre par un autre.
OPERATIONS DE COMPARAISON
< : Inférieur — Vérifie si un nombre est inférieur à un autre.
> : Supérieur — Vérifie si un nombre est supérieur à un autre.
= : Égal — Vérifie si deux nombres sont égaux.
<> : Différent — Vérifie si deux nombres ne sont pas égaux.
≤ : Inférieur ou égal — Vérifie si un nombre est inférieur ou égal à un autre.
≥ : Supérieur ou égal — Vérifie si un nombre est supérieur ou égal à un autre.

2.1.1.3 TYPE LOGIQUE (BOOLEEN)

Le type booléen est un type de données fondamental qui ne peut prendre que deux valeurs
possibles :
VRAI : Indique une condition ou une assertion correcte.
FAUX : Indique une condition ou une assertion incorrecte.

2.1.1.4 OPERATIONS SUR LES TYPES BOOLEENS

ET (AND)
Description : Renvoie VRAI uniquement si les deux conditions sont vraies.
Exemple : A ET B est VRAI si A est VRAI et B est VRAI.
OU (OR)
Description : Renvoie VRAI si au moins une des conditions est vraie.
Exemple : A OU B est VRAI si A est VRAI, B est VRAI, ou les deux.
NON (NOT)
Description : Inverse la valeur booléenne. Si la valeur est VRAI, elle devient FAUX, et vice
versa.
Exemple : NON A est VRAI si A est FAUX.

2
 2.1.1.5 TYPE CARACTERE
Le type caractère représente des lettres, des chiffres ou des symboles, permettant de stocker
des données textuelles.
Description : Chaque caractère est souvent stocké sous forme d'un code (comme ASCII ou
Unicode) qui le représente numériquement.
Exemples : 'A', '1', '?', '$'.
Utilisation : Utilisé pour créer des chaînes de texte, des messages et pour représenter des
données alphanumériques.

2.1.1.6 OPERATIONS SUR LES TYPES CARACTERES

Comparaison
Les caractères peuvent être comparés entre eux à l'aide d'opérations comme >, <, et =.
Exemple : 'A' < 'B' renvoie VRAI, car 'A' est avant 'B' dans l'ordre alphabétique.

2.2 DECLARATION ET MANIPULATION DES VARIABLES

2.2.1 VARIABLES ET CONSTANTES : CONCEPTS CLES DES

ALGORITHMES

En écriture d’algorithmes, les variables et les constantes sont deux types fondamentaux
d'éléments utilisés pour stocker des données en mémoire. Ils permettent de gérer et de
manipuler l'information au cours de l'exécution d'un programme, mais ils diffèrent dans la
manière dont ils fonctionnent.

2.2.1.1 VARIABLES
Une variable est une zone de la mémoire d'un ordinateur destinée à stocker une valeur qui
peut être modifiée durant l'exécution d'un algorithme ou d’un programme. Chaque variable a
trois caractéristiques essentielles :
▪ Nom : c'est un identifiant attribué à la variable, utilisé pour la référencer.
▪ Type : il détermine la nature des données que la variable peut stocker (exemple
: entier, réel, caractère, etc.).
▪ Valeur : c'est le contenu de la variable, qui peut changer à tout moment pendant
l'exécution du programme.
Exemple de déclaration :
▪ Variables x, y : entier // x et y sont des variables de type entier.
▪ Variables z, w : réel // z et w sont des variables de type réel.
▪ Variable lettre : caractère // lettre est une variable de type caractère.
▪ Variable nom : chaîne // nom est une variable de type chaîne de caractères.
▪ Variables Etat : booléen // Etat est une variable de type booléen (vrai ou faux).

3
L'algorithme ci-dessous déclare des variables de types différents, leur affecte des valeurs, puis
affiche ces valeurs.
Algorithme DeclarationVariables
// Déclaration des variables
Variables x, y : entier
Variables z, w : réel
Variable lettre : caractère
Variable nom : chaîne
Variable Etat : booléen
Début
// Étape 1 : Affecter des valeurs aux variables
x <- 10 // Affectation de la valeur 10 à x
y <- 25 // Affectation de la valeur 25 à y
z <- 12.5 // Affectation de la valeur 12.5 à z
w <- 8.75 // Affectation de la valeur 8.75 à w
lettre <- 'A' // Affectation de la valeur 'A' à lettre
nom <- "Martin" // Affectation de la chaîne "Martin" à nom
Etat <- vrai // Affectation de la valeur vrai à Etat
// Étape 2 : Afficher les valeurs des variables
Écrire "Valeur de x : ", x
Écrire "Valeur de y : ", y
Écrire "Valeur de z : ", z
Écrire "Valeur de w : ", w
Écrire "Valeur de lettre : ", lettre
Écrire "Valeur de nom : ", nom
Écrire "Valeur de Etat : ", Etat
Fin

2.2.1.2 CONSTANTES
Une constante est similaire à une variable, à la différence près que sa valeur ne peut jamais
changer pendant l'exécution du programme. Elle reste fixe tout au long du processus.
Exemple de déclaration :
Const
n = 100; // n est une constante entière de valeur 100.
arobase = '@'; // arobase est une constante de type caractère.
mot = "bonjour"; // mot est une constante chaîne de caractères avec la valeur "bonjour".

L'algorithme ci-dessous déclare des constantes de types différents, leur affecte des valeurs,
puis affiche ces valeurs.

4
Algorithme DeclarationConstantes
Constantes n : entier = 100
Constante arobase : caractère = '@'
Constante mot : chaîne = "bonjour"
Début
// Étape 1 : Afficher la valeur des constantes
Écrire "La valeur de n est : ", n
Écrire "La valeur de arobase est : ", arobase
Écrire "La valeur de mot est : ", mot
Fin
Remarque : Dans la partie déclarative d'un programme, les variables et les constantes sont
définies par :
▪ Un identifiant : c'est le nom que vous choisissez pour la variable ou la constante.
▪ Un type : il spécifie la nature des données (entier, réel, chaîne de caractères, etc.).

En Résumé
▪ Les variables : Ce sont des espaces mémoire dont la valeur peut changer au cours de
l’exécution d’un algorithme ou d’un programme.
▪ Les constantes : Ce sont des espaces mémoire dont la valeur reste fixe pendant tout
l’exécution de l’algorithme ou du programme.

Avec ces concepts, un programmeur peut organiser et manipuler les informations efficacement
tout en différenciant ce qui est modifiable (variables) et ce qui ne l'est pas (constantes).

En conclusion, ce chapitre a introduit les concepts clés des types de données et des
variables, éléments fondamentaux pour toute construction algorithmique. Comprendre
les différents types de données — des types simples comme les entiers, réels,
booléens et caractères, aux types structurés comme les tableaux — est essentiel pour
manipuler efficacement les informations. De même, la distinction entre variables, dont
les valeurs peuvent changer, et constantes, dont les valeurs sont fixes, permet une
gestion optimisée des données tout au long d’un programme. Ce cadre de base
constitue le socle de la programmation, sur lequel reposent les algorithmes et les
applications plus complexes à venir.

5
CHAPITRE 3 : STRUCTURES DE CONTRÔLES

3.1 INTRODUCTION
En programmation procédurale, comme en algorithmique, l'ordre des instructions est
essentiel. Chaque étape doit suivre un chemin précis : le processeur exécute les
instructions les unes après les autres, dans l'ordre où elles apparaissent dans le
programme. C'est ce qu'on appelle l'exécution séquentielle.

L’exécution séquentielle d’un algorithme consiste donc en l’exécution des instructions les unes
après les autres, dans l'ordre où elles sont écrites. Chaque étape doit être suivie strictement
selon la séquence définie.

Exemple : Algorithme à exécution séquentielle qui échange les valeurs de deux entiers.
Algorithme Échange
Variables : X, Y, Z (entiers)
Début
Écrire "Donnez la valeur de X :"
Lire X
Écrire "Donnez la valeur de Y :"
Lire Y
Z ← X // Stocker la valeur de X dans Z
X ← Y // Remplacer X par Y
Y ← Z // Remplacer Y par l'ancienne valeur de X (contenue dans Z)
Écrire "La nouvelle valeur de X est :", X
Écrire "La nouvelle valeur de Y est :", Y
Fin
Dans cet algorithme, chaque instruction est exécutée dans l'ordre où elle apparaît, de haut en
bas. Cependant, l'exécution séquentielle d'un algorithme, où chaque instruction est exécutée
strictement dans l'ordre, est simple mais limitée. Elle ne permet pas de prendre des décisions
en fonction des données ou des conditions particulières, ni de répéter des actions de manière
efficace. Dans certains cas, il est nécessaire de modifier cet ordre d'exécution. Cela peut être
pour éviter que toutes les instructions soient exécutées ou pour répéter certaines d'entre elles.
C'est ici qu'interviennent les structures de contrôle.

Une structure de contrôle est un mécanisme permettant de modifier l'ordre d'exécution des
instructions dans un programme et se divise en deux grandes catégories :
▪ Les structures conditionnelles : elles permettent d'exécuter certaines
instructions uniquement si une condition est remplie. Exemple classique : "Si
l'utilisateur a plus de 18 ans, alors il peut accéder au contenu."

6
 ▪ Les boucles (ou structures répétitives) : elles permettent de répéter une série
d'instructions un certain nombre de fois, tant qu'une condition est vérifiée. Exemple
: "Répéter l'action jusqu'à ce que l'utilisateur entre la bonne réponse."

Ces structures permettent à l'algorithme de s'adapter à différents scénarios, de traiter des

ensembles de données plus complexes, et d'éviter des opérations inutiles, rendant ainsi
l'algorithme plus flexible et performant.

3.1.1 EXPRESSION CONDITIONNELLE

Une expression conditionnelle (ou expression logique) est une expression dont la valeur est
soit VRAIE, soit FAUSSE. Parmi les types d'expressions conditionnelles, on trouve les
comparaisons simples, qui comparent deux valeurs du même type, comme `(a < 0)` ou `(op =
"s")`. Les symboles de comparaison incluent `<`, `>`, `=`, `≤`, `≥`, et `≠`. Pour les caractères,
l'ordre est déterminé par l'ASCII, où "a" est inférieur à "b" et "s" est supérieur à "m". Une
condition simple peut être complexe, comme la comparaison `(a + b - 3) * c ≤ (5 * y - 2) / 3`.
Par exemple, pour afficher la valeur absolue de la différence entre deux entiers ( x ) et ( y ),
on affichera ( x - y ) si ( x ) est supérieur à ( y ), sinon ( y - x ).

3.2 STRUCTURES CONDITIONNELLES

Les structures conditionnelles permettent à un programme de réaliser différentes actions en
fonction d’une condition donnée. Une condition (aussi appelée expression logique) est une
affirmation qui peut être soit vraie, soit fausse. Si la condition est vraie, le programme exécute
une action précise; si elle est fausse, il effectue une action différente avant de continuer son
déroulement.

3.2.1.1 TYPES DE STRUCTURES CONDITIONNELLES

Il existe principalement deux types de structures conditionnelles :
▪ Structure alternative (Si… Alors… Sinon) : permet de choisir entre deux actions en
fonction d’une condition.
▪ Structure conditionnelle simple ou sélective (Si… Alors) : permet d’exécuter une action
uniquement si la condition est vraie.
UTILISATION DANS LES ALGORITHMES
Dans un algorithme, on est souvent amené à choisir entre plusieurs actions en fonction de la
valeur de certaines données. La structure alternative permet de gérer ces choix.

3.2.1.1.1 STRUCTURE SÉLECTIVE OU SIMPLE

La structure sélective permet d'exécuter certaines instructions seulement si une condition est
remplie (vraie). Cela permet d’adapter le comportement du programme selon la situation.

Structure sélective simple (un seul choix)

7
Ici, une action est réalisée uniquement si une condition est vraie. Si la condition est fausse,
aucune action n’est effectuée.

Syntaxe générale :
Si <condition> Alors
<instructions>
Fin si

Exemple : Un algorithme qui détermine le maximum entre deux nombres.

Algorithme Maximum
Variables : A, B, Max (réels)
Début
Écrire "Entrez les valeurs de A et B :"
Lire A, B
Max ← A
Si Max < B Alors
Max ← B
Fin si
Écrire "Le maximum est :", Max
Fin
Note : Les instructions placées entre Si et FinSi sont indentées (décalées vers la droite) d'un
cran. Cela permet de distinguer visuellement ces instructions des autres lignes de l'algorithme.

3.2.1.1.2 STRUCTURE SÉLECTIVE AVEC ALTERNATIVE (DEUX

CHOIX)

Avec cette structure, une action est réalisée si la condition est vraie, et une autre action est
exécutée si la condition est fausse.
Syntaxe générale :
Si <condition> Alors
<instructions si vrai>
Sinon
<instructions si faux>
Fin si
Exemple : Un algorithme qui informe si un nombre est positif ou négatif.
Algorithme NatureNombre
Variable : n (entier)
Début
Écrire "Entrez un nombre :"
Lire n

8
 Si n > 0 Alors
Écrire "Ce nombre est positif"
Sinon
Écrire "Ce nombre est négatif"
Fin si
Fin
Exemple simple de structure alternative : Supposons que nous devons créer un programme
qui indique si une variable, nommée "n", est positive ou négative. Pour cela, on utilise une
structure conditionnelle alternative.
Ecrire "Entrez un nombre"
Lire n
Si n > 0 Alors
Afficher "valeur positive"
Sinon
Afficher "valeur négative ou nulle"
Finsi

Dans cet exemple : Si la condition n > 0 est vraie, le programme affiche "valeur positive".
Si la condition est fausse, il affiche "valeur négative ou nulle".

3.2.1.1.3 STRUCTURE ALTERNATIVE IMBRIQUÉE

Parfois, il est nécessaire de vérifier plusieurs conditions les unes après les autres. Cela conduit
à imbriquer des structures conditionnelles.
Syntaxe générale :
Si <condition1> Alors
<instructions si vrai>
Sinon
Si <condition2> Alors
<instructions si condition2 vraie>
Sinon
<instructions si condition2 fausse>
Fin si
Fin si
Exemple : Un algorithme qui détermine si un nombre est positif, nul ou négatif.
Algorithme NatureNombre
Variable : n (entier)
Début
Écrire "Entrez un nombre :"
Lire n
Si n > 0 Alors

9
 Écrire "Ce nombre est positif"
Sinon
Si n = 0 Alors
Écrire "Ce nombre est nul"
Sinon
Écrire "Ce nombre est négatif"
Fin si
Fin si
Fin

3.2.1.1.4 STRUCTURE A CHOIX MULTIPLE : SELON CAS

La structure "Selon Cas" (ou "Switch Case" dans certains langages) permet de simplifier la
gestion de multiples alternatives dans un programme. Contrairement aux instructions "Si-
Sinon" imbriquées, elle offre une meilleure lisibilité et un code plus propre. Plutôt que d'évaluer
une série de conditions, "Selon Cas" identifie directement la valeur à comparer et exécute le
bloc de code correspondant. C'est particulièrement utile lorsque plusieurs valeurs doivent être
testées, car cela évite de complexifier le programme avec des imbrications difficiles à suivre.
Cette structure est pratique pour traiter plusieurs alternatives sans avoir à enchaîner des
conditions multiples.

L'instruction "Si-Sinon" est adaptée pour choisir entre deux actions. Cependant, lorsqu'il y a
plusieurs options, l'imbrication de conditions peut rendre le code moins lisible. "Selon" offre
une solution plus élégante en testant directement la valeur d'une variable ou d'une expression
(comme un entier ou un caractère). Chaque valeur correspond à un bloc d'instructions
spécifique, et un bloc par défaut peut être ajouté pour gérer les cas où aucune valeur ne
correspond. Cela simplifie grandement la gestion des multiples cas dans un programme.

Syntaxe générale :
selon expression faire
cas val_1 : bloc d'instructions 1
cas val_2 : bloc d'instructions 2
...
cas val_n : bloc d'instructions n
sinon
autre bloc d'instructions
FinSelon

10
Les mots-clés selon, faire, case (ou cas), sinon et FinSelon sont réservés dans de nombreux
langages d'algorithme. En C, on utilise les termes switch, case et default pour un
fonctionnement similaire.

Exemple de conversion d'un nombre en lettres :

Cet algorithme demande un nombre entier inférieur à 10, puis affiche ce nombre en lettres en
anglais.

algorithme conversion
var nb : entier
début
écrire("Entrez un nombre")
lire(nb)
selon nb faire
cas 0 : écrire("zero")
cas 1 : écrire("one")
cas 2 : écrire("two")
cas 3 : écrire("three")
cas 4 : écrire("four")
cas 5 : écrire("five")
cas 6 : écrire("six")
cas 7 : écrire("seven")
cas 8 : écrire("eight")
cas 9 : écrire("nine")
sinon
écrire("Nombre non traité")
FinSelon
Fin
Exemple Afficher Résultat :
Le pseudocode ci-dessous, demande à l'utilisateur d'entrer une moyenne et utilise une
structure "selon" pour évaluer cette valeur. En fonction de la moyenne saisie, il affiche
différents messages : si la moyenne est inférieure à 10, il indique "Non admis"; pour une
moyenne entre 10 et 12, il affiche "Admis passable"; entre 12 et 14, il écrit "Admis avec la
mention assez bien"; entre 14 et 16, il mentionne "Admis avec la mention Bien"; et pour une
moyenne de 16 ou plus, il conclut avec "Admis avec la mention Très bien". Cette logique
permet de classifier les résultats académiques de manière claire et structurée.

11
ALGORITHME Résultats
VAR moyenne : réel
DEBUT
Ecrire("Entrez la moyenne :")
Lire(moyenne)

selon moyenne faire

cas 0 à 9:
Ecrire("Non admis")
cas 10 à 11:
Ecrire("Admis passable")
cas 12 à 13:
Ecrire("Admis avec la mention assez bien")
cas 14 à 15:
Ecrire("Admis avec la mention Bien")
sinon
Ecrire("Admis avec la mention Très bien")
FinSelon
FIN
L'instruction selon est utilisée ici avec des conditions pour chaque CAS, qui comparent
directement la variable moyenne à différentes plages de valeurs.
L'instruction selon rend le programme plus lisible et plus structuré que les si imbriqués, surtout
lorsque vous traitez plusieurs cas avec la même variable ou expression.
Détails de l'exécution
▪ Si la moyenne est inférieure à 10, l'étudiant est considéré comme Non admis.
▪ Si la moyenne est comprise entre 10 et 12 (10 inclus, 12 exclus), l'étudiant est
Admis passable.
▪ Si la moyenne est comprise entre 12 et 14 (12 inclus, 14 exclus), l'étudiant reçoit
la mention Assez bien.
▪ Si la moyenne est comprise entre 14 et 16 (14 inclus, 16 exclus), l'étudiant reçoit
la mention Bien.
▪ Si la moyenne est supérieure ou égale à 16, l'étudiant obtient la mention Très bien.

La structure Selon Cas permet de simplifier le code lorsqu'il s'agit de gérer plusieurs cas
distincts, en évitant les longues séquences de conditions imbriquées. C’est une alternative
élégante aux Si-Sinon et rend le programme plus clair et facile à maintenir.
De manière générale, les structures séquentielles permettent l'exécution d'instructions dans
un ordre strict, tandis que les structures sélectives permettent de prendre des décisions et de

12
choisir différentes actions selon les conditions. La structure à choix multiple simplifie la gestion
de nombreux cas sans complexifier le code.

3.3 STRUCTURES ITERATIVES

3.3.1 PRINCIPE DE L'ITERATION

Lorsque l'on répète plusieurs fois les mêmes actions, on parle d'itération. Une structure
d'itération est une structure, dans le code, qui permet de rejouer les mêmes actions, avec
d'éventuelles petites différences. Par exemple appliquer une même séquence d'actions à une
variable différente à chaque itération. Il existe plusieurs types de structures itératives, mais
elles sont généralement communes entre les différents langages.

3.3.1.1 DEFINITION
Une itération représente l'exécution d'un bloc d'instructions. Un ensemble d'itérations
représente donc l'exécution multiple d'un même bloc d'instructions : on dit qu'on itère sur un
bloc d'instructions.

3.3.1.2 STRUCTURE ITERATIVE

Les structures itératives fournissent un moyen d'effectuer des boucles sur des instructions :
la boucle permet d'exécuter des itérations.
a. CONDITION DE SORTIE
Une boucle s'exécute un certain nombre de fois avant de s'interrompre et que la suite du
programme poursuive son exécution. Si une boucle ne s’interrompt jamais, c'est une boucle
infinie : le programme reste bloqué car la boucle se répète indéfiniment. Les structures
itératives nécessitent donc une condition de sortie, c'est-à-dire une condition qui interrompt les
itérations dès qu'elle est remplie.
b. COMPTEUR
Un compteur est souvent utilisé à l'intérieur d'une boucle : une variable entière, généralement
initialisée à 0, est incrémentée à chaque nouvelle itération. Le compteur permet ainsi de
compter simplement le nombre d'itérations déjà effectuées. La valeur du compteur est très
souvent utilisée dans la condition de sortie, pour interrompre la boucle après un certain nombre
d'itérations.
À retenir : Les structures itératives permettent de répéter plusieurs fois une même suite
d'instructions grâce à une boucle.
Il existe trois principaux types de structures itératives :
▪ La structure Tant que…Faire : elle permet d'effectuer une instruction tant qu'une
condition est satisfaite.
▪ La structure Pour : elle permet de répéter une instruction un certain nombre de fois.

13
 ▪ La structure Répéter…Jusqu'à : comme son nom l'indique, elle permet de répéter
une instruction jusqu'à ce qu'une condition soit satisfaite.

Toutes les situations ne se prêtent pas à une boucle avec un compteur à incrémenter. Prenons
un exemple simple : un programme qui demande à l’utilisateur d’entrer son âge. Si l’âge saisi
n’est pas valide, le programme redemande de le renseigner. Ici, le programme doit répéter
l’action un nombre de fois inconnu à l’avance, jusqu’à ce que l’utilisateur saisisse une valeur
valide. La condition de la boucle sera de vérifier la validité de l’âge entré, par exemple en
testant s'il s'agit bien d'un nombre.

3.3.1.3 BOUCLE TANT QUE…FAIRE

La boucle Tant que…Faire permet de répéter une instruction tant qu’une condition donnée est
vraie et que le nombre d’itérations n’est pas connu d’avance. Si dès le début, la condition n’est
pas satisfaite, l'instruction n'est pas exécutée. En cela, elle présente une similitude avec les
structures conditionnelles : lorsque la condition n’est pas remplie, le traitement est ignoré.
Cette boucle est fondamentale. Avec elle, il est possible de réaliser toutes les autres boucles,
tandis que l'inverse n'est pas évident.
o Syntaxe
Tant que <condition> Faire
<instruction> // action ou bloc d'actions
FinTantQue

Exemple d'algorithme : Calcul du cube d'un nombre

Prenons l'exemple d’un programme qui calcule le cube d’un nombre donné par l’utilisateur. Le
programme se répète tant que l’utilisateur n'entre pas 0. Si l’utilisateur saisit 0, la boucle se
termine.

Le déroulement souhaité serait le suivant :

1. L’utilisateur saisit un nombre.
2. Le programme vérifie si ce nombre est différent de 0.
3. Si le nombre est 0, le programme s’arrête.
4. Si le nombre est différent de 0, le programme calcule et affiche le cube de ce nombre,
puis redemande un nouveau nombre.
Ainsi, le programme répète les dernières instructions (vérification de la condition, affichage du
cube, nouvelle saisie) dans une boucle.
Exemple de programme :
Variable x : Entier
Début

14
 Ecrire "Ce programme calcule le cube des nombres que vous entrez.
Pour arrêter, tapez 0."
Ecrire "Entrez un nombre"
Lire x
Tant que x <> 0 Faire
Ecrire "Le cube de", x, "est", x * x * x
Ecrire "Entrez un autre nombre ou 0 pour arrêter"
Lire x
FinTantQue
Ecrire "Fin du programme"
Fin
o Fonctionnement
Le programme commence par demander à l’utilisateur d’entrer un nombre. Si l’utilisateur entre
0, la condition n’est pas satisfaite et le programme se termine immédiatement. Si un autre
nombre est entré, le programme calcule son cube, l’affiche, puis redemande un nouveau
nombre. Cette boucle continue jusqu’à ce que l’utilisateur entre 0, qui sert de "valeur drapeau",
indiquant la fin du programme.
o Trace d’exécution
La trace du programme avec les entrées est donnée dans le tableau ci-dessous :

La trace en elle-même :

15
Cette trace permet de vérifier que le programme fonctionne correctement avec différentes
valeurs.

3.3.1.4 LA BOUCLE POUR

La boucle Pour permet de répéter une instruction un nombre de fois déterminé à l'avance.
Syntaxe générale :
Pour <compteur> de <valeur initiale> à <valeur finale> [pas de
<incrément>] Faire
<traitement>
FinPour

Cette structure est particulièrement utile lorsque le nombre de répétitions est connu. Elle
fonctionne de manière similaire à la boucle Tant que, mais permet de simplifier l'écriture
dans les cas où l'on sait à l'avance combien de fois l'action doit être répétée.
▪ La variable compteur est généralement un entier. Elle est initialisée à une valeur de
départ et augmente à chaque itération par un incrément (qui, par défaut, est de 1).
▪ Lorsque la variable compteur atteint la valeur finale, le traitement s'exécute une
dernière fois avant que le programme ne sorte de la boucle.
Exemple de syntaxe simple :
Pour x de 1 à 20 Faire
<traitement>
FinPour

Dans cet exemple, l’instruction à l'intérieur de la boucle sera exécutée 20 fois. Cela peut être
réalisé aussi avec une boucle Tant que, mais celle-ci nécessiterait d’initialiser le compteur
manuellement et de l'incrémenter à chaque tour, ce qui est plus verbeux.

Exemple avec boucle Tant que :

16
x = 1
Tant que x <= 20 Faire
<traitement>
x = x + 1
FinTantQue

Comme on peut le constater, la boucle Pour est une simplification qui permet d’éviter
l'incrémentation manuelle, tout en assurant un comportement identique.
Application pratique : Table de multiplication
Prenons l’exemple d’un programme qui affiche la table de multiplication de 7. La variable a va
varier de 1 à 10 et servir à la fois de compteur et de multiplicateur. À chaque itération, a est
multipliée par 7, et le résultat est affiché.
Programme "multiplication7" :
Variable a : Entier
Début
Pour a de 1 à 10 Faire
Afficher a, " * 7 = ", a * 7
FinPour
Fin

Fonctionnement :
1. La variable a commence à 1.
2. À chaque itération, a est multipliée par 7, et le résultat est affiché.
3. a est incrémentée automatiquement de 1 à chaque tour de boucle.
4. Lorsque a atteint 10, le programme sort de la boucle et se termine.
Comparaison avec la boucle Tant que
Avec une boucle Tant que, le même programme nécessiterait d’écrire l’incrémentation
explicitement :
a = 1
Tant que a <= 10 Faire
Afficher a, " * 7 = ", a * 7
a = a + 1
FinTantQue

Dans ce cas, il faut penser à incrémenter la variable a manuellement, tandis qu’avec la boucle
Pour, cette opération est effectuée automatiquement. La boucle Pour est donc une version
plus concise et plus lisible pour les situations où le nombre de répétitions est connu à l'avance.
La démarche itérative

17
L’itération consiste à répéter un processus, où la valeur d’une variable dépend de sa valeur
au tour précédent. Elle est fréquemment utilisée en programmation pour résoudre divers
problèmes algorithmiques. La clé de cette approche réside dans l'utilisation d'une variable qui
se trouve à la fois à gauche et à droite d’une affectation. Pour comprendre cette démarche,
nous étudierons des problèmes algorithmiques simples.

3.3.1.5 LA BOUCLE RÉPÉTER

La boucle RÉPÉTER est utilisée lorsqu'on ne connaît pas le nombre exact d'itérations à
l'avance. Elle permet de répéter un ensemble d'instructions tant qu'une condition n'est pas
satisfaite. Contrairement à d'autres boucles, elle garantit que le bloc d'instructions à l'intérieur
de la boucle sera exécuté au moins une fois.
Fonctionnement
▪ Traitement : Les instructions à exécuter.
▪ Condition d'arrêt : La boucle continue jusqu'à ce que cette condition retourne `Vrai`.
Syntaxe
RÉPÉTER
<Traitement>
JUSQU’À <Condition_arret>

Remarques :
▪ La condition d'arrêt est une expression logique.
▪ Une action dans le bloc de traitement doit modifier la condition pour permettre à la
boucle de s'arrêter.
▪ Le traitement de la boucle est toujours exécuté au moins une fois, même si la condition
est déjà vraie lors de la première exécution.

Exemple 1 : Demander si l'utilisateur veut un examen facile

Cet algorithme demande à l'utilisateur s'il veut un examen facile. La réponse est validée jusqu'à
ce que l'utilisateur entre 'O' ou 'N'.
ALGORITHME Examen_facile
VAR rep: caractère
DEBUT
RÉPÉTER
Ecrire(“Voulez-vous un examen facile? (O/N) ")
Lire(rep)
JUSQU’À (Majus(rep) = ‘O’) OU (Majus(rep) = ‘N’)
Si (Majus(rep) = ‘O’) ALORS
Ecrire(“Vous voulez un examen facile”)
SINON

18
 Ecrire(“Vous voulez un examen difficile”)
FINSI
FIN
Exemple 2 : Demander un nombre supérieur à 10
Cet algorithme demande à l'utilisateur d'entrer un nombre supérieur à 10. Tant que le nombre
saisi est inférieur ou égal à 10, l'utilisateur est invité à entrer un nouveau nombre.
ALGORITHME Application
VAR
n: entier
DEBUT
RÉPÉTER
Ecrire(“Saisir un nombre plus grand que 10: ")
Lire(n)
JUSQU’À (n > 10)
Ecrire("Vous avez saisi le nombre: " , n)
FIN
Relation entre les boucles RÉPÉTER et TANT QUE
Les boucles TANT QUE et RÉPÉTER peuvent parfois être interchangeables, mais ce n’est
pas toujours possible. Une boucle RÉPÉTER effectue le traitement au moins une fois avant
d’évaluer la condition, tandis qu'une boucle TANT QUE peut ne jamais entrer dans le
traitement si la condition est déjà fausse.
Exemple : Calcul de la somme de nombres saisis
L'algorithme ci-dessous calcule la somme de plusieurs nombres saisis par l'utilisateur. La
saisie s'arrête lorsque l'utilisateur entre `-1`.
Algorithme utilisant une boucle RÉPÉTER :
ALGORITHME Somme
CONST STOP = -1
VAR valeur, total: réel
DEBUT
total ← 0
RÉPÉTER
Ecrire("Donnez une valeur")
Lire(valeur)
total ← total + valeur
JUSQU’À (valeur = STOP)
Ecrire("La somme est : ", total)
FIN

19
Remarque : Dans cet exemple, une boucle TANT QUE pourrait être plus appropriée, car il faut
une condition de départ pour entrer dans la boucle.
Erreurs courantes
Il est important que la condition d'arrêt d'une boucle **TANT QUE** ou **RÉPÉTER** soit
modifiée par une action dans le corps de la boucle, sinon la boucle peut devenir infinie. Voici
un exemple d'erreur courante :
DEBUT
val1 ← 2
val2 ← 3
TANT QUE (val1 < 100) FAIRE
val2 ← val2 * val1
FINTANTQUE
FIN
Dans cet exemple, la condition `val1 < 100` n’est jamais modifiée, donc la boucle ne s’arrête
jamais.
La boucle RÉPÉTER est idéale lorsque vous avez besoin d'exécuter un bloc d'instructions au
moins une fois avant d'évaluer une condition. Cependant, il est essentiel de s'assurer que la
condition d'arrêt sera modifiée à l'intérieur de la boucle pour éviter des boucles infinies.

3.3.1.5.1 COMPTER ET ACCUMULER

a. Comptage systématique dans une boucle Tant que

Lorsque vous voulez compter le nombre de tours d’une boucle Tant que, il suffit d’utiliser une
variable comme compteur. Cette variable est initialisée à 0 avant l'entrée dans la boucle, et
elle est incrémentée à chaque tour à l’intérieur de la boucle.
Exemple : Programme de calcul du cube
Variable x : Entier
compteur : Entier
Début
// Initialisation
compteur = 0
Tant que x <> 0 Faire
Afficher "Le cube de ", x, " est ", x*x*x
compteur = compteur + 1
Afficher "Entrez un nombre ou 0 pour arrêter"
Saisir x
FinTantQue
Afficher "Vous avez calculé ", compteur, " cubes"
Fin

20
Dans cet exemple, le compteur est incrémenté à chaque itération pour compter le nombre de
cubes calculés.
b. Comptage sélectif
Pour ne compter que les cubes négatifs, l'incrémentation du compteur se fait uniquement
lorsqu'une condition est vérifiée, ici lorsque x est inférieur à 0.
Exemple : Comptage des cubes négatifs
Variable x : Entier
compteur : Entier
Début
compteur = 0
Tant que x <> 0 Faire
Afficher "Le cube de ", x, " est ", x*x*x
Si x < 0 Alors
compteur = compteur + 1
FinSi
Afficher "Entrez un nombre ou 0 pour arrêter"
Saisir x
FinTantQue
Afficher "Vous avez obtenu ", compteur, " cubes négatifs"
Fin
c. Comptage multiple
Dans certains cas, vous devrez compter plusieurs éléments simultanément. Par exemple,
vous pouvez vouloir compter à la fois les cubes négatifs et les cubes pairs.
Exemple : Comptage des cubes négatifs et pairs
Var
x : Entier
cptneg : Entier // compteur des cubes négatifs
cptpair : Entier // compteur des cubes pairs
Début
cptneg = 0
cptpair = 0
Tant que x <> 0 Faire
Afficher "Le cube de ", x, " est ", x*x*x
Si x < 0 Alors
cptneg = cptneg + 1
FinSi
Si (x*x*x) mod 2 = 0 Alors

21
 cptpair = cptpair + 1
FinSi
Afficher "Entrez un nombre ou 0 pour arrêter"
Saisir x
FinTantQue
Afficher "Vous avez obtenu ", cptneg, " cubes négatifs et ",
cptpair, " cubes pairs"
Fin
d. Calculer le résultat de x^n avec une itération
Dans certains langages de programmation, l’opérateur exposant n’existe pas. Pour calculer
x^n, vous pouvez utiliser une boucle Pour afin de répéter n fois la multiplication de x.
Exemple : Programme de calcul de l'exposant
Variable x, n, res : Entier
Début
Afficher "Veuillez entrer un nombre puis son exposant"
Saisir x, n
res = 1 // Initialisation du résultat
Pour i de 1 à n Faire
res = res * x // Itération
FinPour
Afficher x, " puissance ", n, " vaut ", res
Fin
Dans cet algorithme, la variable res accumule le résultat intermédiaire à chaque tour de
boucle, et sa valeur finale est obtenue à la sortie de la boucle.

e. Trouver le minimum d’une suite de nombres

Pour trouver le plus petit nombre dans une liste de 100 nombres, il suffit d’utiliser une seule
variable pour stocker le minimum. À chaque tour de boucle, un nouveau nombre est comparé
avec le minimum actuel. Si le nouveau nombre est plus petit, il devient le nouveau minimum.

Exemple : Programme de recherche du minimum

Variable nb, min : Réel
Début
Afficher "Entrez un nombre"
Saisir nb
min = nb // Le premier nombre saisi est le minimum initial
Pour i de 2 à 100 Faire
Afficher "Entrez un autre nombre"

22
 Saisir nb
Si nb < min Alors
min = nb // Mise à jour du minimum
FinSi
FinPour
Afficher "Le minimum des nombres saisis est ", min
Fin

f. La démarche itérative : cas général

Une itération consiste à passer d’un état initial à un état final en répétant une série d’actions,
chaque étape modifiant l'état des variables impliquées. Pour découvrir l’itération adaptée à un
problème, il faut suivre ces étapes :

1. Identifier un état intermédiaire.

2. Trouver les instructions permettant de passer d’un état intermédiaire à un autre.
3. Déterminer les conditions d’arrêt, c’est-à-dire quand l'état final est atteint.
4. Initialiser les variables de départ pour commencer correctement.

La boucle permet ainsi de progresser vers l'état final de manière ordonnée et contrôlée.

3.4 EXERCICES DE FIN DE CHAPITRE

STRUCTURES CONDITIONNELLES

Exercice 1 :
Ecrire un algorithme d’une action qui échange deux variables A et B

Exercice 2 :
Ecrire une action qui fournit les félicitations ou l’ajournement d’un élève suivant sa
note en utilisant Si-alors-sinon.

Exercice 3 :
Ecrire un programme qui donne la valeur absolue de 2 réels
Exercice 4 :
Ecrire un algorithme permettant de résoudre une équation du premier degré

Exercice 5 :
Ecrire un algorithme permettant de résoudre une équation du second degré en
utilisant des si alors..

Exercice 6 :
Ecrire le même algorithme avec des selon-cas

23
 STRUCTURES ITERATIVES
Exercice 16
Écrire un algorithme permettant de calculer la somme S=1+2+3+...+ N, où N saisi par
l’utilisateur. Utilisant la boucle Tant Que
Écrire un programme qui lit et affiche 10 entiers dans un tableau en utilisant la boucle Tant
Que.
Exercice 17
Écrire un programme qui permet d’afficher le message "bonjour" 10 fois. Utilisant la boucle
Pour.
Exercice 18
Écrire un algorithme qui permet d'afficher "Bienvenue en GL1" 10 fois. Utilisant la boucle
Répéter Jusqu’à.
Exercice 19
Écrire un algorithme qui affiche la table de multiplication de 8. Utilisant la boucle Répéter
Jusqu’à.
Exercice 20
Écrire un algorithme qui permet de calculer la somme d’entiers impaires de 1 jusqu'à un
entier N saisi par l'utilisateur en utilisant la boucle Pour. Exemple N=8 Somme = 1
+3+5+7= 16
Exercice 21
Écrire un algorithme qui permet de calculer la somme d’entiers impaires de 1 jusqu'à un
entier N saisi par l'utilisateur en utilisant la boucle Tant Que cette fois ci.

24
CHAPITRE 4 : STRUCTURES DE DONNEES

4.1 LES TABLEAUX

Les tableaux sont des structures de données permettant le stockage d’un grand nombre
d’éléments individuels. Nous pouvons les parcourir séquentiellement pour y rechercher des
informations, les trier si nécessaire et ensuite exploiter le fait qu’ils soient triés pour optimiser
nos recherches.

4.1.1 DEFINITION
Un tableau est une structure de données qui permet de stocker un ensemble d'éléments du
même type (entiers, chaînes de caractères, etc.) sous une seule variable. Chaque élément est
accessible via un indice, c'est-à-dire un numéro représentant sa position dans le tableau.

Un tableau est représenté en mémoire sous la forme de cellules contiguës. Il n’est pas possible
de créer une case ou d’en supprimer une. On dit qu’ils sont statiques. En raison de ces
limitations, tous les langages de programmation ne permettent pas d’utiliser des variables pour
concevoir des tableaux.

4.1.2 DIMENSION D'UN TABLEAU

Un tableau peut être unidimensionnel ou multidimensionnel. Un tableau unidimensionnel est
une liste d'éléments qui se compose d'une seule ligne d'éléments ou d'une seule colonne
d'éléments. Un tableau bidimensionnel est un tableau d'éléments composé de lignes et de
colonnes. La manière de référencer un élément dans un tableau unidimensionnel est
Tableau(i), où i est l'indice de l'élément. La manière de référencer un élément dans un tableau
bidimensionnel est Tableau(i, j), où (i, j) est l'indice de l'élément. Habituellement, il suffit
d'utiliser des tableaux unidimensionnels et bidimensionnels, nous n'avons besoin d'utiliser des
tableaux de dimensions supérieures que si nous devons traiter des problèmes plus complexes.
La figure ci-dessous illustre un exemple de tableau à une et à deux dimensions.

Représentation graphique tableau à une et à deux dimensions

▪ Pour un tableau à une dimension : on travaille généralement avec une seule
dimension (soit une seule ligne ou une seule colonne).

25
 ▪ Pour un tableau à deux dimensions : on travaille avec deux dimensions (lignes et
colonnes), donc on peut accéder aux éléments en utilisant des coordonnées de ligne
et de colonne.

4.1.2.1 TABLEAUX À UNE DIMENSION OU VECTEURS

Un tableau à une dimension, souvent appelé simplement un "vecteur", est une structure de
données en programmation qui stocke une collection ordonnée d'éléments du même type. Le
type du tableau est imposé à tous ses éléments (un tableau Integer ne pourra stocker que des
entiers).

Représentation graphique tableau à une dimension

Il est important de savoir que l'indice commence toujours à 0. Cela signifie que le premier
élément du tableau se trouve à l'indice 0, le deuxième à l'indice 1, et ainsi de suite.
Prenons un exemple avec un tableau d'entiers t contenant 6 éléments :
Indices 0 1 2 3 4 5
Valeurs 42 -9 21 0 999 21

Dans cet exemple :

Pour accéder à la valeur 0 (située à l'indice 3), on utilise la notation t[3].
Deux cases d'un tableau peuvent avoir la même valeur. Ici, les indices 2 et 5 contiennent tous
deux la valeur 21.

4.1.2.1.1 DECLARATION ET UTILISATION D'UN TABLEAU 1D

En algorithmique, un tableau est généralement déclaré avec une taille fixe, et ses
éléments peuvent être de différents types. La notation dépend du langage de
programmation. Pour créer un tableau à une dimension de taille fixe, il faut définir sa
taille au moment de sa création comme l’indique le pseudo-code ci-dessous :

DÉBUT
CONSTANTE N ← 6 // Définition de la taille du tableau
TABLEAU t: N ENTIER // Déclaration d'un tableau d'entiers de taille N
t[0] ← 42 // Remplissage du tableau avec des valeurs
t[1] ← -9
t[2] ← 21
t[3] ← 0
t[4] ← 999
t[5] ← 21
FIN

26
Dans l’exemple ci-dessus, nous avons défini un tableau t de taille 6 et nous avons
assigné des valeurs aux différentes cases, de l'indice 0 à 5.
4.1.2.1.2 PARCOURIR LES ELEMENTS D’UN TABLEAU AVEC

UNE BOUCLE

Les boucles sont un concept fondamental en algorithmique. Elles permettent d'itérer

ou de parcourir les éléments d'une structure de données, comme un tableau, afin
d'effectuer des opérations répétées. Dans ce contexte, une boucle peut être utilisée
pour accéder à chaque élément d'un tableau et, par exemple, afficher les valeurs, les
modifier, ou effectuer des calculs.
Le parcours d’un tableau consiste à utiliser une boucle qui itère sur chaque position
du tableau, de l’indice 0 jusqu’à l’indice du dernier élément, en utilisant l'indice pour
accéder aux éléments.
Exemple1 en pseudocode : Le pseudocode ci-dessous initialise un tableau de 6 entiers
avec des valeurs spécifiques (42, -9, 21, 0, 999, 21), puis utilise une boucle pour
parcourir chaque élément du tableau. À chaque itération, il affiche l'indice de l'élément
et sa valeur correspondante, du premier élément (indice 0) jusqu'au dernier (indice 5).
DÉBUT
CONSTANTE N ← 6 // Taille du tableau
TABLEAU t: N ENTIER // Déclaration du tableau de N
entiers
// Initialisation du tableau avec des valeurs
t[0] ← 42
t[1] ← -9
t[2] ← 21
t[3] ← 0
t[4] ← 999
t[5] ← 21
// Boucle pour parcourir le tableau et afficher les valeurs
POUR i ← 0 JUSQU'À N - 1 FAIRE
AFFICHER "t[", i, "] = ", t[i] // Affiche l'indice et la valeur
correspondante
FIN POUR
FIN

Exemple2 : l’algorithme ci-dessous demande à l'utilisateur de saisir 10 nombres entiers qu'il

stocke dans un tableau `tab` à une dimension. Ensuite, il parcourt ce tableau pour compter
combien de ces nombres sont pairs et combien sont impairs. Il initialise deux compteurs,
`Nb_pair` pour les nombres pairs et `Nb_impair` pour les nombres impairs. Pour chaque
nombre saisi, l'algorithme vérifie s'il est pair (en utilisant l'opération modulo) et incrémente le
compteur correspondant. À la fin, il affiche le nombre de nombres pairs et impairs.

27
Algorithme : Nombre pairs
Variables i,tab[10],Nb_pair, Nb_impair :entiers
Debut
Nb_pair ← 0 ; Nb_impair ← 0
pour i de 1 à 10 faire
Ecrire("donner un entier:")
Lire(tab[i])
FinPour
pour i de 1 à 10 faire (
Si( tab[i] mod 2 ← 0 ) alors
Nb_pair ← Nb_pair + 1
else Nb_impair ← Nb_impair + 1
FinSi
FinPour
Ecrire("Nombre de paires:",Nb_pair)
Ecrire("Nombre d'impaires:",Nb_impair)
Fin

4.1.2.2 TABLEAUX À DEUX DIMENSIONS OU MATRICES

Un tableau à 2 dimensions est une structure de données tabulaire composée de colonnes et
de lignes (similaire à une feuille de calcul d'un tableur ou une table de base de données).
L'accès à une cellule (représentation de l'intersection d'une ligne et d'une colonne) s'effectue
à partir de deux indices, l’un représentant l'accès ligne et l'autre représentant l'accès colonne.
La vocation d'un tableau à 2 dimensions est de représenter le lien dynamique entre deux types
d'information statique : par exemple, les notes obtenues par une classe d'élèves aux devoirs
d'une matière ; une note est bien l’intersection logique entre l'indice d'un élève et l'indice d'un
devoir.

Réprésentation graphique tableau à deux dimensions

Il est parfois utile de stocker un tableau à deux dimensions, que l'on compare à la notion
courante de tableau avec des lignes et des colonnes. Pour accéder à un élément d'un tel

28
 tableau, il faut maintenant utiliser deux indices : le premier représentant la ligne et le second
la colonne. Par exemple, un tableau t de taille 5x3 (5 lignes et 3 colonnes) peut être représenté
graphiquement comme suit :
Index ligne Index Colonne 0 Index Colonne 1 Index Colonne 2 tableau
Ligne 0 0 0 0 tableau(0, 0), tableau(0, 1), tableau(0, 2)
Ligne 1 0 0 0 tableau(1, 0), tableau(1, 1), tableau(1, 2)
Ligne 2 0 0 0 tableau(2, 0), tableau(2, 1), tableau(2, 2)
Ligne 3 0 0 0 tableau(3, 0), tableau(3, 1), tableau(3, 2)
Ligne 4 0 0 0 tableau(4, 0), tableau(4, 1), tableau(4, 2)

NB : Pour accéder à un élément, on utilise la notation t[ligne, colonne]. Par exemple, t[2,1] fait référence à l'élément situé sur la
ligne 2 et la colonne 1.

4.1.2.2.1 CRÉATION ET INITIALISATION DE TABLEAUX 2D

Comme pour les tableaux 1D, les boucles sont essentielles pour parcourir un tableau 2D. Dans
ce cas, deux boucles imbriquées sont utilisées : une pour parcourir les lignes et une autre pour
parcourir les colonnes de chaque ligne.

Exemple 1 en pseudocode :
Le pseudocode ci-dessous initialise un tableau 2D de 3x3 avec des valeurs spécifiques, puis
utilise deux boucles imbriquées pour parcourir et afficher chaque élément.
DÉBUT
CONSTANTE L ← 3 // Nombre de lignes
CONSTANTE C ← 3 // Nombre de colonnes
TABLEAU t: L x C ENTIER // Déclaration d'un tableau 2D de
taille 3x3
// Initialisation du tableau avec des valeurs
t[0, 0] ← 1
t[0, 1] ← 2
t[0, 2] ← 3
t[1, 0] ← 4
t[1, 1] ← 5
t[1, 2] ← 6
t[2, 0] ← 7
t[2, 1] ← 8
t[2, 2] ← 9
// Parcourir le tableau et afficher chaque élément
POUR i ← 0 JUSQU'À L - 1 FAIRE
POUR j ← 0 JUSQU'À C - 1 FAIRE
AFFICHER "t[", i, ",", j, "] = ", t[i, j] // Affiche l'indice
et la valeur correspondante
FIN POUR
FIN POUR
FIN

Dans cet exemple, nous initialisons un tableau 2D de 3 lignes et 3 colonnes, puis nous utilisons
deux boucles pour parcourir chaque élément. La première boucle parcourt les lignes, et la
seconde boucle imbriquée parcourt les colonnes.

29
Exemple 2 : Compter les pairs et impairs dans un tableau 2D
L’algorithme suivant demande à l'utilisateur de remplir un tableau 2D de 3x3 avec des entiers.
Il compte ensuite combien de ces nombres sont pairs et combien sont impairs en vérifiant
chaque élément avec une condition modulo. Pour parcourir tous les éléments, on doit itérer
sur les indices des lignes et des colonnes, qui sont compris entre 0 et 2.
Algorithme : Nombres pairs et impairs
Variables : i, j, t[3,3], Nb_pair, Nb_impair : entiers
Début
Nb_pair ← 0 ; Nb_impair ← 0
// Saisie des valeurs pour remplir le tableau
POUR i ← 0 JUSQU'À 2 FAIRE
POUR j ← 0 JUSQU'À 2 FAIRE
Écrire("Donner un entier pour la position [", i, ",", j, "] :")
Lire(t[i, j])
FIN POUR
FIN POUR

// Parcourir le tableau et compter les pairs et impairs

POUR i ← 0 JUSQU'À 2 FAIRE
POUR j ← 0 JUSQU'À 2 FAIRE
SI t[i, j] MOD 2 = 0 ALORS
Nb_pair ← Nb_pair + 1
SINON
Nb_impair ← Nb_impair + 1
FIN SI
FIN POUR
FIN POUR

Écrire("Nombre de pairs : ", Nb_pair)

Écrire("Nombre d'impairs : ", Nb_impair)
Fin

Les tableaux constituent des structures de données fondamentales et efficaces pour le

stockage et la manipulation d'ensembles d'éléments de même type. Qu'ils soient
unidimensionnels ou multidimensionnels, ils permettent de gérer de grandes quantités
d'informations de manière ordonnée, facilitant ainsi la recherche, le tri, et le traitement de ces
données. Leur utilisation est particulièrement utile dans des algorithmes nécessitant des
opérations répétitives grâce à des boucles. Toutefois, en raison de leur caractère statique, la
taille d'un tableau doit être définie à l'avance, ce qui constitue une contrainte à prendre en
compte lors de leur mise en œuvre.

4.1.2.3 EXERCICES SUR LES TABLEAUX

Exercice 1
Écrire un algorithme permettant de saisir 10 entiers et de les stocker dans un tableau nommé
Tableau, puis les afficher.
Exercice 2

30
Écrire un algorithme permettant de saisir 10 notes d'étudiants dans un vecteur et qui affiche la
moyenne de ces notes.
Exercice 3
Rédigez un algorithme qui permet de saisir au clavier les notes de `n` étudiants et de les
stocker dans un vecteur. L'algorithme devra ensuite calculer et afficher la somme, le produit,
ainsi que la moyenne de ces notes.
Exercice 3 bis
Reprendre l'exercice 3 pour une matrice.
Exercice 4
Écrire un algorithme permettant de saisir n entiers au clavier dans un vecteur et qui affiche le
maximum de ces entiers.
Exercice 5
Écrire un algorithme permettant de remplir un tableau de 10 entiers saisis par l'utilisateur.
Ensuite, l'algorithme doit demander à l'utilisateur de saisir un nombre N, et afficher le nombre
de fois où ce nombre apparaît dans le tableau.
Exercice 6
Ecrire un programme qui permet de tester l'égalité entre deux vecteurs d'entiers (tailles 10).
Le programme affiche VRAI si les composants des deux tableaux sont correspondent position
par position, sinon il affiche FAUX.
Exercice 7
Écrire un algorithme qui compte le nombre d'éléments en double (deux éléments ou plus)
dans un vecteur de n entiers saisie par l'utilisateur.

4.2 LES ENREGISTREMENTS

Lorsqu'on souhaite gérer des données liées entre elles mais de types différents, comme les
noms, prénoms et notes d’élèves, l’utilisation de tableaux séparés peut rapidement devenir
source d'erreurs, surtout lors d’opérations telles que le tri. Une alternative plus sûre et efficace
est l'utilisation des structures ou enregistrements. Contrairement aux tableaux, qui ne peuvent
stocker que des données du même type, les enregistrements permettent de regrouper
plusieurs types de données au sein d’une seule entité sous un même nom. Par exemple, dans
le cas d'un élève, on peut créer une structure qui contient son nom (chaîne de caractères),
son prénom (chaîne de caractères), et sa note (nombre). Chaque donnée est alors appelée
un **champ**, et ces champs sont identifiés par des noms au lieu d’indices numériques comme
dans les tableaux. Ainsi, les enregistrements facilitent la manipulation de données
hétérogènes, en simplifiant les opérations et réduisant les risques d’erreurs, tout en offrant une
organisation plus claire et logique.

31
 4.2.1 DEFINITION ET DECLARATION DES ENREGISTREMENTS

4.2.1.1 DEFINITION
Un enregistrement, également appelé article ou record en anglais, est une structure de
données définie par l'utilisateur, composée d'un nombre fixe de champs qui peuvent être de
types différents. Chaque champ de l'enregistrement fonctionne comme une variable
individuelle, avec des types variés. Par exemple, un enregistrement pour représenter une date
pourrait contenir trois champs : jour, mois, et année.

4.2.1.2 DECLARATION
La déclaration des enregistrements se fait dans une section spécifique des algorithmes
appelée Type, qui précède la section des variables. Contrairement aux tableaux, il n’existe
pas de type structure par défaut ; l’utilisateur doit d'abord créer un nouveau type basé sur une
structure, puis déclarer des variables de ce type. La syntaxe pour créer un type basé sur une
structure ressemble à celle d'une déclaration de variables, mais avec des champs pouvant
être de types simples ou complexes (comme des tableaux ou d'autres structures).
Syntaxe :
Type <id_Enreg> = Enregistrement
<id_ch1> : <type1>
<id_ch1> : <type2>
...
<id_chN> : <typeN>
Fin_ <id_Enreg>

Où <id_ch1>, <id_ch2>, …, <id_chN> sont les identificateurs des champs et <type1>,

<type2>, …, <typeN> leurs types respectifs.
Pour l'exemple du Produit précédent, la déclaration de l'enregistrement sera comme suit :
Type
Produit = Enregistrement
Reference : Chaîne [5]
Designation : Chaîne[25]
Quantite : Entier
Prix_U : Réel
Fin_Produit

Exemple 2 : construire un enregistrement Date basé sur une structure. Cette structure a aussi
trois attributs : jour, mois et annee.

32
Type
Date = Enregistrement
jour : Entier // Le jour du mois (1-31)
mois : Entier // Le mois de l'année (1-12)
annee : Entier // L'année (par exemple, 2024)
Fin_Date

4.2.1.3 ACCES AUX CHAMPS D’UNE STRUCTURE

Alors que les éléments d'un tableau sont accessibles via leur indice, les champs d'un
enregistrement sont accessibles par leur nom, grâce à l'opérateur '.' (point). Chaque champ
d’une structure peut être manipulé comme n’importe quelle variable du type correspondant.
Pour accéder à un champ spécifique d'un enregistrement, on utilise le nom de la variable
correspondant à l'enregistrement (identificateur), suivi d'un point, puis du nom du champ
auquel on souhaite accéder.
La syntaxe est la suivante : <Nom_Variable_Enregistrement>.<Nom_Champ>
Par exemple, pour accéder au champ Quantite de la variable prod dans l'exemple précédent,
on écrirait : prod.Quantite.

Prenons l’exemple d’une structure Etudiant, qui regroupe trois champs : nom (chaîne de
caractères), prenom (chaîne de caractères), et note (nombre réel). Une fois cette structure
déclarée, il est possible de créer des variables comme Etud1 ou Etud2, qui appartiennent au
type Etudiant. L'accès à un champ spécifique d'un enregistrement se fait à l'aide de l’opérateur
« . », par exemple, Etud1.nom. Cette flexibilité permet de manipuler efficacement des données
complexes et hétérogènes, tout en simplifiant leur gestion et organisation.

Le pseudocode ci-dessous définit une structure appelée `Etudiant`, composée de trois champs
: `nom`, `prenom`, et `note`, qui sont respectivement une chaîne de caractères (de longueur
maximale de 50) pour le nom et le prénom, et un réel pour la note. Ensuite, deux variables,
`Etud1` et `Etud2`, de type `Etudiant`, sont déclarées. Les données de ces deux étudiants sont
initialisées. Le pseudocode affiche ensuite les informations des deux étudiants en utilisant
l'opérateur `.` pour accéder à chaque champ de la structure. Cela permet de manipuler
efficacement des données structurées et hétérogènes.
Algorithme : Enregistreur d’etudiants
Type
Etudiant = Enregistrement
nom : Chaîne[50]
prenom : Chaîne[50]
note : Réel
Fin_Etudiant

33
Variables :
Etud1, Etud2 : Etudiant // Déclaration de deux variables de type
Etudiant

Début
// Initialisation de l'étudiant 1
Etud1.nom <- "Eto’o Fils"
Etud1.prenom <- "Samuel"
Etud1.note <- 19.5

// Initialisation de l'étudiant 2
Etud2.nom <- "Bona"
Etud2.prenom <- "Richard"
Etud2.note <- 17.0

// Affichage des informations de l'étudiant 1

Ecrire("Nom : ", Etud1.nom)
Ecrire("Prénom : ", Etud1.prenom)
Ecrire("Note : ", Etud1.note)

// Affichage des informations de l'étudiant 2

Ecrire("Nom : ", Etud2.nom)
Ecrire("Prénom : ", Etud2.prenom)
Ecrire("Note : ", Etud2.note)
Fin

AFFECTATION ET ENREGISTREMENTS
L’affectation de valeurs aux différents champs d’une variable de type enregistrement suit la
syntaxe suivante : Nom_variable ← valeur
prod.Quantite ← 50

Note : Il est possible d’affecter une variable de type enregistrement à une autre variable de
même structure. Dans ce cas, tous les champs seront copiés.
LECTURE
Cette opération permet de remplir les champs d’un enregistrement avec les valeurs saisies
par l’utilisateur via le clavier. La syntaxe est : Lire(Nom_variable.champ)
Exemple : Lire(prod.Designation)
ECRITURE
Cette opération sert à afficher le contenu des champs d’un enregistrement à l’écran. La
syntaxe est : ecrire(Nom_variable.champ)
Exemple : ecrire(prod.Prix_U)

34
Remarques :
1. La seule opération possible sur des enregistrements de même type est l’affectation.
2. Il n’est pas possible de lire ou d’écrire globalement un enregistrement. Chaque champ
doit être traité individuellement.
3. Un type structuré (enregistrement) peut être utilisé comme type pour les champs d’un
autre enregistrement. Exemple : pour accéder à l'année de naissance d'une personne,
il est nécessaire d’utiliser deux fois l’opérateur '.' (point).

4.2.1.4 TABLEAU D’ENREGISTREMENTS

Il est courant de vouloir manipuler plusieurs enregistrements simultanément, plutôt qu’un seul.
Par exemple, si l’on souhaite gérer un groupe de personnes, il serait inefficace de créer autant
de variables du type personne qu’il y a d'individus. La solution consiste à créer un tableau
d’enregistrements, où chaque élément du tableau est un enregistrement contenant plusieurs
champs de données.
CONCEPT D’UN TABLEAU D’ENREGISTREMENTS
▪ Un tableau d’enregistrements permet de stocker un ensemble d’enregistrements du
même type dans une structure ordonnée.
▪ Chaque élément du tableau est un enregistrement complet, et on peut accéder aux
champs de chaque enregistrement à l’aide de son indice dans le tableau.
Exemple en algorithmique :
Imaginons une classe de 30 étudiants. Nous allons déclarer un tableau d’étudiants et écrire
un algorithme pour remplir la fiche de chacun.
Type
Etudiant = enregistrement
nom: chaine[25]
prenom: chaine[35]
age: entier
moyenne: réel
Fin_enregistrement

Variables
Classe: tableau [1..30] de Etudiant

Algorithme fiche_etudiants
Constante M = 30
Variables
Classe [M] : Etudiant
i, n : entier
Début
Ecrire ("Entrez le nombre d’étudiants dans la classe :")
Lire (n)
Pour i ← 0 à n-1 faire
Ecrire ("Entrez le nom de l’étudiant ", i+1, " :")
Lire (Classe[i].nom)
Ecrire ("Entrez le prénom de l’étudiant ", i+1, " :")

35
 Lire (Classe[i].prenom)
Ecrire ("Entrez l’âge de l’étudiant ", i+1, " :")
Lire (Classe[i].age)
Ecrire ("Entrez la moyenne de l’étudiant ", i+1, " :")
Lire (Classe[i].moyenne)
FinPour
Fin

Dans cet algorithme :

▪ Classe[0] représente le premier étudiant du tableau.
▪ Classe[0].nom est le champ correspondant au nom du premier étudiant.
▪ Lire(Classe[i].nom) permet de demander à l’utilisateur d’entrer le nom de l’étudiant à
l’indice i.
Remarques importantes :
Accès à un enregistrement dans un tableau : Chaque élément du tableau est un
enregistrement complet. Pour accéder à un enregistrement spécifique, on utilise l’indice du
tableau. Par exemple, Classe[1] correspond au premier étudiant.
▪ Manipulation d’un tableau d’enregistrements : Toutes les opérations (lecture, écriture,
modification) sur un enregistrement dans un tableau se font champ par champ. Il n'est
pas possible de manipuler un enregistrement complet d'un seul coup.
▪ Utilisation imbriquée de types structurés : Il est possible d’avoir des enregistrements
qui contiennent eux-mêmes des champs de type structuré. Par exemple, une personne
pourrait avoir un champ adresse qui est lui-même un enregistrement.

Un tableau d’enregistrements est donc une structure très puissante qui permet de manipuler
un groupe d’éléments structurés de manière ordonnée. Cela s’applique à de nombreux cas
concrets, comme la gestion d’une classe d’étudiants, la gestion des employés d’une
entreprise, ou encore le suivi de commandes dans une boutique en ligne.

4.2.1.5 EXERCICES SUR LES ENREGISTREMENTS

Exercice 1 : Remplir et afficher un tableau de contacts

Écrire un algorithme qui demande à l'utilisateur de saisir un nombre N, puis de remplir un

tableau d’enregistrements de N contacts, où chaque contact est représenté par un nom et un
numéro de téléphone. Ensuite, afficher la liste complète des contacts saisis.

Exercice 2 : Analyse des tremblements de terre

Écrire un algorithme qui demande à l'utilisateur de saisir un nombre N de tremblements de

terre dans un tableau d’enregistrements. Chaque tremblement de terre est défini par le lieu de
l'épicentre (nom, latitude, longitude), la magnitude et la durée. Il doit ensuite permettre à

36
l'utilisateur de rechercher un lieu et afficher la durée totale des tremblements de terre ayant eu
lieu à cet endroit.

Exercice 3 : Recherche d'un contact dans un tableau de structures

Écrire un algorithme qui demande à l'utilisateur de remplir un tableau de N contacts, où chaque

contact est défini par un nom, une adresse, un numéro de téléphone et un email. Ensuite,
l'utilisateur doit pouvoir rechercher un contact en saisissant son nom, et il doit afficher les
informations du contact correspondant. Si le contact n'existe pas, un message doit l'indiquer.

4.1 LES CHAINES DE CARACTERES

En algorithmique, une chaîne de caractères est une séquence de caractères (lettres, chiffres,
symboles, etc.) placée dans un ordre particulier. Chaque caractère est indexé, ce qui permet
de manipuler, rechercher ou modifier des portions de la chaîne.

Les chaînes de caractères sont omniprésentes en programmation, notamment pour gérer du

texte, des fichiers ou des entrées utilisateur. La majorité des langages de programmation
propose des outils pour manipuler ces chaînes. Dans cette partie du cours, nous explorerons
les principales opérations sur les chaînes de caractères en pseudo-code, incluant la
concaténation, l'accès aux caractères, la recherche de sous-chaînes, et plus encore.

4.1.1 DECLARATION ET INITIALISATION D’UNE CHAINE

4.1.1.1 DECLARATION
Pour déclarer une chaîne de caractères en pseudo-code, on utilise le mot-clé chaîne. Cela
permet de réserver un espace en mémoire pour contenir la chaîne.
VARIABLES
NOM : CHAINE
DEBUT
AFFICHER "ENTRER VOTRE NOM"
LIRE NOM
FIN

Explication : Ici, une variable nom de type chaîne est déclarée et l'utilisateur est invité à entrer
son nom qui sera stocké dans cette variable.

4.1.1.2 INITIALISATION
Une chaîne peut être initialisée soit par une valeur vide, soit par une valeur pré-définie.
VARIABLES
NOM : CHAINE
NOM ← "Eto’o"
NOM ← ""
DEBUT
AFFICHER NOM
FIN

37
Explication : La variable nom est directement initialisée avec la chaîne "Eto’o".

4.1.2 OPERATIONS DE BASE SUR LES CHAINES DE CARACTERES

4.1.2.1 CONCATENATION DE CHAINES
La concaténation est l’opération qui consiste à joindre deux ou plusieurs chaînes pour en
former une seule. En pseudo-code, cette opération est souvent représentée par l'opérateur +
ou Concat.

VARIABLES
S1 : CHAINE
S1 ← "BONJOUR"
S2 : CHAINE
S2 ← " LE MONDE"
S3 : CHAINE
DEBUT
S3 ← S1 + S2
AFFICHER S3 // AFFICHE: "BONJOUR LE MONDE"
FIN

Explication : Les deux chaînes s1 et s2 sont concaténées pour former la chaîne s3.

4.1.2.2 LONGUEUR D’UNE CHAINE

La fonction longueur(chaine) retourne le nombre de caractères contenus dans une chaîne.
VARIABLES
S : CHAINE
S ← "ALGORITHMIQUE"
ENTIER LEN
DEBUT
LEN ← LONGUEUR(S)
AFFICHER LEN // AFFICHE: 13
FIN

Explication : La chaîne "Algorithmique" contient 13 caractères.

4.1.2.3 ACCES A UN CARACTERE

Pour accéder à un caractère d'une chaîne à une position donnée, on utilise la syntaxe chaine[i],
où i représente l'indice du caractère souhaité (généralement à partir de 0).

VARIABLES
S : CHAINE
S ← "BONJOUR"
CARACTERE C
DEBUT
C ← S[1] // ACCEDE AU 2EME CARACTERE (INDICE 1)
AFFICHER C // AFFICHE: "O"
FIN

Explication : On accède ici au deuxième caractère de la chaîne s.

38
 4.1.3 MANIPULATION DES SOUS-CHAINES

4.1.3.1 EXTRACTION D’UNE SOUS-CHAINE

Une sous-chaîne est une portion extraite d'une chaîne de caractères. La fonction
SousChaîne(ch, i, L) retourne une chaîne de longueur L à partir de la position i de la chaîne
ch.

VARIABLES
S : CHAINE
S ← "INFORMATIQUE"
CHAINE SOUS
DEBUT
SOUS ← SOUSCHAINE(S, 6, 4)
AFFICHER SOUS // AFFICHE: "MATI"
FIN

Explication : La sous-chaîne extraite commence à la position 6 et a une longueur de 4

caractères.

4.1.4 COMPARAISON DE CHAINES

Il est souvent nécessaire de comparer des chaînes, par exemple pour trier des mots ou vérifier
une égalité. En pseudo-code, les opérateurs de comparaison usuels comme =, <, > peuvent
être utilisés sur les chaînes en fonction de l’ordre lexicographique (ordre alphabétique).

VARIABLES
S1 : CHAINE
S1 ← "APPLE"
S2 : CHAINE
S2 ← "ORANGE"
RESULTAT : BOOLEEN
DEBUT
RESULTAT ← S1 < S2 // VRAI CAR "APPLE" EST AVANT "ORANGE"
AFFICHER RESULTAT // AFFICHE: VRAI
FIN

Explication : Ici, s1 est comparé à s2 selon l’ordre lexicographique.

4.1.5 RECHERCHE DE SOUS-CHAINES

4.1.5.1 RECHERCHE SIMPLE

Pour vérifier si une chaîne contient une sous-chaîne, on peut utiliser une boucle pour parcourir
la chaîne principale et chercher une correspondance.

VARIABLES
CHAINE TEXTE ← "BONJOUR TOUT LE MONDE"
CHAINE MOT ← "TOUT"
BOOLEEN TROUVE ← FAUX
ENTIER I
DEBUT
I ← 0

39
 TANT QUE (I ≤ LONGUEUR(TEXTE) - LONGUEUR(MOT)) ET (NON TROUVE)
FAIRE
SI SOUSCHAINE(TEXTE, I, LONGUEUR(MOT)) = MOT ALORS
TROUVE ← VRAI
FIN SI
I ← I + 1
FIN TANT QUE
AFFICHER TROUVE // AFFICHE: VRAI
FIN
Explication : Cet algorithme parcourt la chaîne texte pour chercher si la sous-chaîne mot y est
présente.

4.1.6 RECHERCHE OPTIMISEE (KNUTH-MORRIS-PRATT, BOYER-

MOORE)

Pour des recherches plus efficaces, des algorithmes comme Knuth-Morris-Pratt ou Boyer-
Moore peuvent être utilisés. Ces algorithmes avancés sont recommandés pour les recherches
dans de grandes chaînes.
Résumé des Opérations sur les Chaînes

Les chaînes de caractères sont des structures essentielles en algorithmique, permettant de

manipuler du texte et des séquences de données. Les opérations telles que la concaténation,
la recherche et la manipulation des sous-chaînes sont largement utilisées dans de nombreux
algorithmes et programmes. Une bonne maîtrise de ces opérations est cruciale pour tout
programmeur.

4.2 EXERCICES SUR LES CHAINES DE CARACTERE

Exercice 1 : Manipulation de chaînes de caractères
Écrire un programme qui permet de :
▪ Saisir une chaîne de caractères.
▪ Calculer et afficher la longueur de cette chaîne.
▪ Afficher le premier et le dernier caractère de la chaîne.

40
Exercice 2 : Invitation personnalisée

Écrire un programme qui permet de :

▪ Saisir un nom et un prénom.

▪ Ajouter un espace à la fin du nom et concaténer le nom et le prénom.
▪ Inviter la personne à un rendez-vous avec une date et une heure prédéfinie.

Exemple :

- Si l'utilisateur entre le nom "Biya" et le prénom "Paul", le programme affiche : "Biya Paul,
vous êtes invité à un rendez-vous le 04/01/2025 à 19h."

Exercice 3 : Insertion dans une chaîne

Écrire un programme qui permet de :

▪ Saisir deux chaînes de caractères.

▪ Insérer la première chaîne dans la seconde.
▪ Afficher la longueur de la seconde chaîne après insertion.
▪ Afficher le caractère situé au milieu de la chaîne résultante.

Exercice 3 : Somme des carrés des chiffres

Écrire un programme qui permet de :
▪ Saisir un entier compris entre 100 et 999.
▪ Calculer la somme des carrés des chiffres des centaines, dizaines et unités de cet
entier.
▪ Convertir cette somme en chaîne de caractères et l'afficher.

Exemple :
- Si l'utilisateur saisit 295, le programme calcule : 2² + 9² + 5² = 110, et affiche "110".

Exercice 4 : Conversion chaîne en nombre

Écrire un programme qui permet de :
▪ Saisir une chaîne de caractères.
▪ Si la chaîne contient un nombre, convertir cette chaîne en un entier.
▪ Si la chaîne contient autre chose qu'un nombre, afficher 0.
Exemple :
- Pour "1024", le programme affiche 1024.
- Pour "Décembre2015", le programme affiche 0.

41
CHAPITRE 5: LES SOUS ALGORITHMES :
FONCTIONS ET PROCEDURES
5.1 GENERALITES
Un programme est une suite ordonnée d'instructions conçues pour résoudre un problème
particulier. Pour trouver la méthode de résolution, aussi appelée algorithme, le problème
principal est d'abord divisé en plusieurs sous-problèmes plus simples. Ensuite, chaque sous-
problème peut être résolu de manière autonome grâce à des sous-programmes, qui sont des
blocs d'instructions dédiés à une tâche précise.

5.2 DEFINITION

5.2.1 SOUS-PROGRAMMES
Un sous-programme est un bloc d'instructions autonome avec un nom, qui peut être exécuté
à la demande. Il est appelé depuis le programme principal ou un autre sous-programme.
Lorsqu’une instruction appelle le sous-programme, l'exécution du programme bascule
temporairement sur les instructions de ce sous-programme. Une fois le sous-programme
terminé, le programme reprend juste après l’appel initial.

Les sous-programmes sont également connus sous les noms de procédures, fonctions,
méthodes ou routines.

5.2.1.1 PROCEDURE
Une procédure est un sous-programme qui n’associe pas de valeur de retour à son nom, mais
qui peut produire des résultats par le biais de ses arguments. Le nom de la procédure peut
être utilisé comme une instruction complète dans le programme. Par exemple :

5.2.1.2 FONCTION
Une fonction est un sous-programme qui renvoie toujours une valeur, car son nom représente
une variable contenant cette valeur. On peut donc appeler une fonction dans une expression,
par exemple dans des opérations d’affectation. Par exemple :

Remarque : Toute procédure qui renvoie une valeur unique via un argument peut être
convertie en fonction.

42
 5.2.1.3 AVANTAGES DE L'UTILISATION DE SOUS-PROGRAMMES
L'utilisation de sous-programmes présente plusieurs avantages significatifs qui améliorent la
qualité et l'efficacité d'un programme. D'abord, ils contribuent à la lisibilité du code en
structurant les blocs de tâches distinctes, ce qui rend le programme plus clair et facile à
comprendre pour les développeurs. En termes de gain de temps, les sous-programmes
permettent d'éviter la répétition de séquences d'instructions similaires, ce qui accélère le
processus de développement. Ils participent également à la réduction de la taille du
programme en éliminant les redondances, rendant le code plus léger. Sur le plan de la
maintenance, ils facilitent les modifications en isolant les fonctionnalités, permettant des
ajustements ciblés sans impact majeur sur le reste du code. Enfin, les sous-programmes
favorisent la réutilisation des segments de code, puisqu'ils peuvent être stockés dans des
bibliothèques et employés dans divers autres programmes, offrant ainsi une approche
modulaire et durable pour les projets futurs.

5.2.2 DECLARATION DES SOUS-PROGRAMMES

Les sous-programmes, comprenant les procédures et les fonctions, jouent un rôle fondamental
dans la structuration et l’organisation du code. Il s’avère donc important de savoir les utiliser
en programmation. Ils doivent être déclarés avant d’être utilisés : une fonction appelée par une
autre doit être définie au préalable.

5.2.2.1 PROCEDURE
La déclaration d’une procédure permet de définir une série d’instructions qui réalisent une
tâche spécifique, sans renvoyer de résultat. Voici la syntaxe générale :
▪ Algorithme : `procedure nom_proc (paramètres)` suivi de `Debut` pour les
instructions, puis `Fin`.
▪ En C : `void nom_proc (paramètres) { instructions ; }`.

Exemple : La procédure ci-dessous, intitulée `som`, calcule et affiche la somme de deux

entiers. Dans l’algorithme, la procédure est définie par le mot-clé `procédure` suivi des
paramètres `a` et `b` de type entier. Elle affiche le résultat en additionnant `a` et `b` et en le
présentant sous la forme : "La somme vaut : [résultat]".
// Procédure permettant de calculer la somme de deux entiers
procédure som(a : entier, b : entier)
Début
Ecrire("La somme vaut :", a + b)
Fin procédure

43
En langage C, la procédure est déclarée avec le type `void`, indiquant qu'elle ne renvoie
aucune valeur. Les paramètres `a` et `b` de type `int` sont traités dans un bloc `printf` qui
affiche le texte avec le résultat de l’addition.
#include <stdio.h>
// Déclaration de la procédure en C
void som(int a, int b) {
printf("La somme vaut : %d\n", a + b);
}

5.2.2.2 FONCTION
Les fonctions sont similaires aux procédures, mais elles renvoient une valeur après
l’exécution. Le type de la valeur renvoyée doit être précisé :

▪ Algorithme : `fonction nom_fonc (paramètres) : type`, suivie de `Debut` et des

instructions, puis `Fin`.
▪ En C : `type nom_fonc (paramètres) { instructions ; return valeur ; }`.

Exemple : La fonction, ci-dessous nommée `som()’`, calcule et renvoie la somme de deux

entiers. Dans l'algorithme, la fonction est définie par le mot-clé `fonction`, avec des paramètres
`a` et `b` de type entier, et spécifie un type de retour `entier`. L'instruction `retourner a + b`
permet de renvoyer le résultat de l'addition.
// Fonction permettant de calculer la somme de deux entiers
fonction som(a : entier, b : entier) : entier
Début
retourner a + b
Fin fonction
En langage C, cette fonction est déclarée avec le type `int`, qui indique que la valeur renvoyée
est un entier. Les paramètres `a` et `b`, de type `int`, sont additionnés, et le résultat est retourné
par l'instruction `return a + b`.
// Déclaration de la fonction en C
int som(int a, int b) {
return a + b;
}

5.2.2.3 UTILISATION ET APPEL DES SOUS-PROGRAMMES

Pour appeler une procédure ou une fonction, on utilise simplement son nom, suivi des
arguments nécessaires entre parenthèses. Ces arguments doivent correspondre exactement
aux paramètres attendus par le sous-programme, en termes de type, de nombre et d'ordre.

44
Dans le langage C, l'utilisation de parenthèses est obligatoire, même si la procédure ou la
fonction ne prend pas d'arguments.
EXEMPLES PRATIQUES
✓ Déclaration et appel d’une procédure dans un programme principale
La procédure suivante, som(), calcule la somme de deux entiers et affiche le résultat. Dans le
programme principal, l’utilisateur saisit les valeurs à additionner, puis la procédure est appelée
pour afficher la somme.

a. PSEUDOCODE DE LA PROCEDURE
// Déclaration de la procédure
procédure som(a : entier, b : entier)
Début
Ecrire("La somme vaut :", a + b)
Fin procédure
// Le programme principal
Variables :
x, y : entier
Début
Ecrire("Entrez la valeur de x :")
Lire(x)
Ecrire("Entrez la valeur de y :")
Lire(y)
// Appel de la procédure
som(x, y)
Fin
En C, la procédure est implémentée sous la forme d'une fonction de type void, car elle n'a pas
de valeur de retour. Le programme principal permet à l'utilisateur de saisir deux entiers, puis
appelle som pour afficher leur somme.

#include <stdio.h>

// Déclaration de la procédure en C
void som(int a, int b) {
printf("La somme vaut : %d\n", a + b);
}
// Programme principal
int main() {

45
 int x, y;
printf("Entrez la valeur de x : ");
scanf("%d", &x);
printf("Entrez la valeur de y : ");
scanf("%d", &y);
// Appel de la procédure dans le main
som(x, y);
return 0;
}
✓ Déclaration et appel d’une procédure dans un programme principale
La fonction som() ci-dessous, retourne la somme de deux entiers, ce qui permet de l’utiliser
dans des calculs ou de stocker le résultat dans une variable. Dans le programme principal,
l’utilisateur saisit les valeurs, la fonction est appelée, et le résultat est ensuite affiché.
b. PSEUDOCODE DE LA FONCTION
// Déclaration de la fonction
fonction som(a : entier, b : entier) : entier
Début
retourner a + b
Fin fonction

// Le programme principal
Variables :
x, y, result : entier
Début
Ecrire("Entrez la valeur de x :")
Lire(x)
Ecrire("Entrez la valeur de y :")
Lire(y)
// Appel de la fonction dans le programme principal
result = som(x, y)
Ecrire("La somme de ce calcul vaut :", result)
Fin
En C, la fonction som() est déclarée avec le type int, ce qui signifie qu’elle renvoie un entier.
Dans le programme principal, l’utilisateur entre deux nombres, la fonction est appelée avec
ces valeurs, et le résultat de la somme est affiché.
#include <stdio.h>
// Déclaration de la fonction en C
int som(int a, int b) {
return a + b;
}
// La fonction main ou le programme principal
int main() {
int x, y, result;

46
 printf("Entrez la valeur de x : ");
scanf("%d", &x);
printf("Entrez la valeur de y : ");
scanf("%d", &y);
// Appel de la fonction dans le main
result = som(x, y);
printf("Le résultat du calcul est : %d\n", result);
return 0;
}
Exercice d’Application 1 : Utilisation de Procédures et Fonctions en pseudocode et
en C
Objectif : Écrire un petit programme qui utilise une procédure pour afficher une séquence de
nombres et une fonction pour calculer la somme de deux entiers.
1. Procédure `afficheNbrs()` : Créez une procédure appelée `afficheNbrs()` qui prend un
entier `n` en argument. Cette procédure affichera tous les nombres de 1 à `n` sur une
seule ligne. Par exemple, si `n` est égal à 5, la sortie sera : 1 2 3 4 5
2. Fonction `produitNbrs()` : Créez une fonction appelée `produitNbrs()` qui prend deux
entiers `x` et `y` en arguments. Cette fonction renvoie la somme de `x` et `y`. Par
exemple, si `x = 3` et `y = 4`, la fonction doit retourner `12`.
Programme Principal :
▪ Demandez à l'utilisateur de saisir un nombre entier pour `n`.
▪ Appelez la procédure `afficheNbrs()` avec ce nombre.
▪ Ensuite, demandez à l'utilisateur de saisir deux autres entiers, `a` et `b`.
▪ Appelez la fonction `produitNbrs()` avec ces deux nombres et affichez le résultat avec
un message tel que : La somme de a et b est : [résultat]
Exemple de Sortie du Programme :
Supposons que l’utilisateur entre les valeurs suivantes :
- Pour `n` : 5
- Pour `a` et `b` : 2 et 10
Le programme devrait afficher :
Séquence de nombres de 1 à 5 :
12345
Entrez la valeur de a et b :
Le produit de 2 et 10 est : 20
SOLUTION

❖ Pseudocode
Déclaration de la Procédure afficheNbrs() : Cette procédure afficheNbrs() prend un entier n en
argument et affiche tous les nombres de 1 à n.

47
procédure afficheNbrs(n : entier)
Début
pour i de 1 à n faire
Ecrire(i, " ")
finpour
Ecrire("\n")
Fin procédure

Equivalent en langage C

// Déclaration de la procédure afficheNbrs

void afficheNbrs(int n) {
int i;
for (i = 1; i <= n; i++) {
printf("%d ", i);
}
printf("\n");
}
Déclaration de la Fonction produitNbrs() : Cette fonction sommeNbrs prend deux entiers x et
y en arguments et renvoie leur somme.
fonction produitNbrs(x : entier, y : entier) : entier
Début
retourner x * y
Fin fonction
Equivalent en langage C

#include <stdio.h>
// Déclaration de la fonction sommeNbrs
int sommeNbrs(int x, int y) {
return x * y;
}
❖ UTILISATION DE LA FONCTION DE LA PROCEDURE DANS LE
PROGRAMME PRINCIPAL

▪ Demander à l’utilisateur d’entrer un nombre n.

▪ Appeler la procédure afficheNbrs pour afficher les nombres de 1 à n.
▪ Demander à l’utilisateur de saisir deux autres nombres, a et b.
▪ Appeler la fonction sommeNbrs avec a et b et afficher le résultat.
Variables :
n, a, b, resultat : entier
Début
Ecrire("Entrez la valeur de n :")
Lire(n)
Ecrire("Séquence de nombres de 1 à ", n, ":")
//appel de la procédure
afficheNbrs(n)
Ecrire("Entrez la valeur de a :")

48
 Lire(a)
Ecrire("Entrez la valeur de b :")
Lire(b)
//appel de la fonction
resultat = sommeNbrs(a, b)
Ecrire("La somme de ", a, " et ", b, " est : ", resultat)
Fin

Equivalent en langage C

// Programme principal
int main() {
int n, a, b, resultat;

// Saisie de la valeur pour n

printf("Entrez la valeur de n : ");
scanf("%d", &n);
printf("Séquence de nombres de 1 à %d :\n", n);
// appel de la procédure
afficheNbrs(n);
// Saisie des valeurs pour a et b
printf("Entrez la valeur de a : ");
scanf("%d", &a);
printf("Entrez la valeur de b : ");
scanf("%d", &b);
// appel de la fonction
resultat = sommeNbrs(a, b);
printf("La somme de %d et %d est : %d\n", a, b, resultat);
return 0;
}
❖ EXPLICATION DE L’EXERCICE
▪ Procédure afficheNbrs() : Affiche la séquence de nombres de 1 à n.
▪ Fonction produitNbrs() : Calcule et renvoie le produit de deux entiers x et y.
▪ Programme Principal : Coordonne l'interaction avec l'utilisateur, appelle la
procédure et la fonction, et affiche les résultats.
Exercice d’application N°2 : Ecrire un algorithme puis son équivalent en C qui utilise des
procédures et des fonctions pour manipuler des caractères et des chaînes de caractères. Le
programme doit inclure une procédure nommée afficheCaractres() qui affiche tous les
caractères de 'a' jusqu'à un caractère donné par l'utilisateur (par exemple, 'e'). De plus, il doit
contenir une fonction appelée sommeLongueurs() qui calcule et retourne la somme des
longueurs de deux chaînes de caractères saisies par l'utilisateur. Le programme principal doit
demander à l'utilisateur d'entrer un caractère de fin, puis afficher la séquence de caractères
correspondante. Ensuite, il doit demander deux chaînes de caractères, calculer la somme de
leurs longueurs à l'aide de la fonction, et afficher le résultat dans un format clair et
compréhensible.

49
 SOLUTION

❖ Pseudocode
// déclaration de la procédure
procédure afficheCaractres(fin : caractère)
Début
pour c allant de 'a' à fin faire
Ecrire(c, " ") // Affiche chaque caractère suivi d'un espace
Fin pour
Ecrire("\n") // Passe à la ligne suivante
Fin procédure
//Déclaration de la Fonction
fonction sommeLongueurs(chaine1 : chaîne, chaine2 : chaîne) : entier
Début
retourner longueur(chaine1) + longueur(chaine2) // Retourne la
somme des longueurs des chaînes
Fin fonction
// Le programme principal
Variables :
finCaractere : caractère
chaine1, chaine2 : chaîne
longueurTotale : entier
Début
Ecrire("Entrez un caractère de fin (par exemple 'e') :")
Lire(finCaractere)
// Appel de la procédure
afficheCaractres(finCaractere)
Ecrire("Entrez deux chaînes de caractères :")
Ecrire("Chaîne 1 :")
Lire(chaine1) // Lecture de la première chaîne
Ecrire("Chaîne 2 :")
Lire(chaine2) // Lecture de la deuxième chaîne
// Appel de la fonction pour calculer la somme des longueurs
longueurTotale := sommeLongueurs(chaine1, chaine2)
// Affiche le résultat
Ecrire("La somme des longueurs de '", chaine1, "' et '", chaine2,
"' est :", longueurTotale)
Fin

50
 ❖ Code en C
#include <stdio.h>
#include <string.h>
// Procédure pour afficher les caractères de 'a' à un caractère donné
void afficheCaractres(char fin) {
for (char c = 'a'; c <= fin; c++) {
printf("%c ", c);
}
printf("\n"); // Pour passer à la ligne suivante après l'affichage
}
// Fonction pour calculer la somme des longueurs de deux chaînes de
caractères
int sommeLongueurs(const char *str1, const char *str2) {
return strlen(str1) + strlen(str2); // Renvoie la somme des
longueurs
}
int main() {
char finCaractere;
char chaine1[100], chaine2[100];
// Demande à l'utilisateur de saisir un caractère de fin
printf("Entrez un caractère de fin (par exemple 'e') : ");
scanf(" %c", &finCaractere); // Espace avant %c pour ignorer les espaces
// Appelle la procédure pour afficher les caractères de 'a' à finCaractere
afficheCaractres(finCaractere);
// Demande à l'utilisateur de saisir deux chaînes de caractères
printf("Entrez deux chaînes de caractères :\n");
printf("Chaîne 1 : ");
scanf("%s", chaine1); // Lecture de la première chaîne
printf("Chaîne 2 : ");
scanf("%s", chaine2); // Lecture de la deuxième chaîne
// Appelle la fonction pour calculer la somme des longueurs
int longueurTotale = sommeLongueurs(chaine1, chaine2);
// Affiche le résultat
printf("La somme des longueurs de \"%s\" et \"%s\" est : %d\n", chaine1,
chaine2, longueurTotale);
return 0;
}

51
EXPLICATION DE CERTAINES FONCTIONS UTILISEES ICI EN C :
▪ afficheCaractres(char fin) : Affiche tous les caractères de 'a' jusqu'à un caractère
spécifié fin, suivi d'un espace.
▪ sommeLongueurs(const char *str1, const char *str2) : Calcule et retourne la somme
des longueurs des deux chaînes de caractères str1 et str2.
▪ strlen(const char *str) : Renvoie la longueur de la chaîne de caractères str, sans
inclure le caractère nul de fin (\0).
5.2.3 VARIABLES LOCALES ET VARIABLES GLOBALES
Dans un programme, les variables peuvent être globales ou locales. Leur portée et leur durée
de vie diffèrent, ce qui influence la manière dont elles sont utilisées dans les fonctions et sous-
programmes.

5.2.3.1 LES VARIABLES GLOBALES

Une variable globale est une variable déclarée en dehors de toutes les fonctions ou
procédures. Elle est accessible dans toutes les parties du programme, ce qui signifie que
toutes les fonctions peuvent y accéder directement sans qu'il soit nécessaire de la passer en
paramètre.
▪ Durée de vie : La variable globale est créée en mémoire dès le chargement du
programme et reste accessible jusqu'à la fin de l'exécution.
▪ Utilisation : Les variables globales peuvent être pratiques pour partager des
informations entre plusieurs parties du programme, mais il faut les utiliser avec
précaution pour éviter des erreurs de modification involontaires, surtout dans des
programmes complexes.
Exemple : Le code ci-dessous illustre l'utilisation d'une variable globale `glob` dans un
contexte de sous-programmes. La variable `glob` est initialisée à `10` dans le programme
principal, puis affichée à l’aide de la procédure `afficher_globale()`. Ensuite, la procédure
`modifier_globale()` modifie la valeur de `glob` pour qu’elle devienne `20`, et cette nouvelle
valeur est affichée.
❖ Pseudocode
// Déclaration de la variable globale
Var glob : entier
// Procédure pour afficher la valeur de la variable globale
Procedure afficher_globale()
Ecrire("La variable globale est : ", glob)
Fin procedure

// Procédure pour modifier la valeur de la variable globale

Procedure modifier_globale()
glob <- 20 // Modifie la valeur de la variable globale
Fin procedure

52
// Programme principal
Debut
glob <- 10 // Initialise la variable globale
afficher_globale() // Affiche : La variable globale est : 10
modifier_globale() // Modifie la valeur de glob
afficher_globale() // Affiche : La variable globale est : 20
Fin
❖ Code c
#include <stdio.h>

// Déclaration de la variable globale

int glob;
// Fonction pour afficher la valeur de la variable globale
void afficher_globale() {
printf("La variable globale est : %d\n", glob);
}

// Fonction pour modifier la valeur de la variable globale

void modifier_globale() {
glob = 20; // Modifie la valeur de la variable globale
}
// Fonction principale
int main() {
glob = 10; // Initialise la variable globale
afficher_globale(); // Affiche : La variable globale est : 10
modifier_globale(); // Modifie la valeur de glob
afficher_globale(); // Affiche : La variable globale est : 20
return 0;
}
Ce code illustre l'utilisation d'une variable globale glob dans un contexte de sous-programmes.
La variable glob est initialisée à 10 dans le programme principal, puis affichée à l’aide de la
procédure afficher_globale(). Ensuite, la procédure modifier_globale() modifie la valeur de glob
pour qu’elle devienne 20, et cette nouvelle valeur est affichée. Cet exemple montre comment
une variable globale peut être modifiée et accessible dans tout le programme, ce qui est
pratique pour partager des données entre différentes parties du code, mais doit être utilisé
avec prudence pour éviter des modifications inattendues dans des programmes complexes.
Cet exemple montre comment une variable globale peut être modifiée et accessible dans tout
le programme, ce qui est pratique pour partager des données entre différentes parties du code,
mais doit être utilisé avec prudence pour éviter des modifications inattendues dans des
programmes complexes.

5.2.3.2 LES VARIABLES LOCALES

Une variable locale est une variable déclarée à l'intérieur d'une fonction ou d'un sous-
programme. Elle est accessible uniquement dans ce bloc de code et n'est pas visible dans les
autres parties du programme.

53
 ▪ Durée de vie : La variable locale est créée au moment de l'appel de la fonction et est
supprimée une fois l'exécution de cette fonction terminée.
▪ Utilisation : Les variables locales sont préférables pour garantir l'indépendance des
fonctions et éviter des erreurs d’interférence avec d'autres fonctions.
Exemple : Le code ci-dessous présente l'utilisation d'une procédure calculer_carre() pour
calculer et afficher le carré d'un entier donné, ici 5. Dans la procédure, une variable locale
resultat est utilisée pour stocker le résultat du calcul de x * x. La procédure affiche ensuite le
carré de x avec un message. Cet exemple illustre comment utiliser des variables locales dans
une procédure pour des calculs temporaires, ce qui rend le code plus modulaire et évite de
modifier des valeurs en dehors du sous-programme.
❖ Pseudocode
Procedure calculer_carre(x : entier)
Var resultat : entier // Variable locale pour stocker le résultat
resultat <- x * x // Calcul du carré de x
Ecrire("Le carré de ", x, " est ", resultat) // Affichage du
résultat
Fin Procedure

Debut
calculer_carre(5) // Appel de la procédure pour afficher le carré
de 5
Fin
❖ Code c
#include <stdio.h>
// Déclaration de la fonction pour calculer le carré
void calculer_carre(int x) {
int resultat = x * x; // Variable locale pour stocker le
résultat
printf("Le carré de %d est %d\n", x, resultat); // Affichage du
résultat
}
int main() {
calculer_carre(5); // Appel de la fonction pour afficher le
carré de 5
return 0; // Indique que le programme s'est terminé avec succès
}

Dans cet exemple, la procédure calculer_carre() prend un entier x comme paramètre, calcule
son carré en multipliant x par lui-même et affiche le résultat. Dans le programme principal, la
procédure est appelée avec la valeur 5, ce qui affiche que le carré de 5 est 25. Ce code montre
comment encapsuler une logique de calcul dans une procédure et comment interagir avec
celle-ci à partir du programme principal.

54
 5.2.3.3 PARAMETRES FORMELS ET EFFECTIFS
En programmation, les sous-programmes (comme les fonctions) utilisent des paramètres pour
interagir avec le reste du code. Il existe deux types de paramètres : paramètres formels et
paramètres effectifs. Ces paramètres permettent aux fonctions ou aux procédures de recevoir
et de traiter des données.
▪ Paramètres formels : Ce sont les variables définies dans la fonction qui vont recevoir
les valeurs des paramètres effectifs. Elles servent uniquement dans le cadre de la
fonction pour manipuler les données.
▪ Paramètres effectifs : Ce sont les valeurs concrètes qu’on passe à la fonction lors de
son appel. Ces valeurs seront utilisées par la fonction pour effectuer des calculs ou
des opérations.
Exemple en C : Addition de deux nombres
Le code ci-dessous définit une fonction qui additionne deux nombres, utilise cette fonction
dans le programme principal pour additionner les valeurs 5 et 3, et affiche le résultat, qui est
8. C'est un exemple classique d'utilisation de paramètres formels et effectifs pour illustrer
comment les valeurs sont transmises à une fonction et comment le calcul est effectué.
❖ Pseudocode
Fonction somme(param1, param2) :
Retourner param1 + param2
Fin Fonction
//Programme principal
Début
Déclarer x ← 5
Déclarer y ← 3
Déclarer resultat ← somme(x, y)
Afficher resultat
Fin
❖ Code c
#include <stdio.h>
// Définition de la fonction avec des paramètres formels `a` et `b`
int somme(int a, int b) {
return a + b; // Calcul utilisant les paramètres formels
}
int main() {
int x = 5, y = 3; // Variables pour les paramètres effectifs
int resultat = somme(x, y); // `x` et `y` sont passés comme
paramètres effectifs

55
 printf("%d", resultat); // Affichage du résultat
return 0;
}
Ici, la fonction somme() utilise les paramètres formels a et b.
▪ Dans le programme principal (main), x et y sont les paramètres effectifs passés à
somme lors de l’appel somme(x, y).
▪ La fonction calcule la somme des valeurs de x et y, et retourne ce résultat.
▪ Appel de la fonction somme
o La fonction somme est appelée avec x et y comme arguments, ce qui signifie que
param1 prendra la valeur de x (5) et param2 prendra la valeur de y (3).
o La somme de x et y (5 + 3 = 8) est calculée à l'intérieur de la fonction et est stockée
dans la variable resultat.

De manière simple, les paramètres effectifs transmettent des valeurs précises à une fonction.
Les paramètres formels les reçoivent pour exécuter le code de la fonction.

5.2.4 PASSAGE DE PARAMETRES : PAR VALEUR ET PAR

REFERENCE
Les paramètres permettent d’échanger des informations entre le programme principal et les
fonctions. Il existe deux modes principaux de passage de paramètres : par valeur et par
référence.

5.2.4.1 PASSAGE PAR VALEUR

Dans le cadre d'un passage par valeur, le paramètre formel est traité comme une variable
locale au sein du sous-programme, dont la valeur est initialisée au début de chaque appel
avec celle du paramètre effectif correspondant. Ce mécanisme implique la duplication de la
valeur du paramètre effectif dans une zone mémoire spécifique réservée à la procédure, de
sorte que toutes les opérations réalisées sur le paramètre formel n'influent que sur cette
instance locale.

56
Ce mode de passage présente l'avantage de garantir la sécurité et la protection des données,
en évitant toute modification involontaire des valeurs d'origine. Cependant, il entraîne des
inconvénients, tels que la lenteur liée à la nécessité de recopier les données et une
augmentation de l'espace mémoire requis, bien que cela soit souvent acceptable pour des
variables simples.
Exemple en pseudocode :
Procedure doubler_valeur(valeur : entier)
valeur <- valeur * 2
Ecrire("Valeur doublée : ", valeur)
Fin procedure
// programme principal
Debut
Var x : entier
x <- 5
doubler_valeur(x) // Affiche : Valeur doublée : 10
Ecrire("Valeur originale : ", x) // Affiche : Valeur originale : 5
Fin
Cela signifie que, lorsque vous passez une variable (comme x) à une fonction (comme
doubler_valeur() ), une copie de cette variable est faite pour l'utilisation dans la fonction. Ainsi,
toute modification faite à cette copie n'affecte pas la variable d'origine.

Le tableau ci-dessous montre la trace ou séquence des opérations dans le contexte de la

procédure doubler_valeur(). Il illustre comment la valeur de x est copiée dans valeur,
comment valeur est modifiée à l'intérieur de la fonction, et comment la variable d'origine x reste
inchangée après l'appel de la fonction. Ici, la valeur de la variable d'origine est copiée dans le
paramètre de la procedure ou de la fonction. Toute modification de ce paramètre ne change
pas la valeur de la variable d'origine

57
Équivalent en C :
#include <stdio.h>
void doubler_valeur(int valeur) {
valeur = valeur * 2;
printf("Valeur doublée : %d\n", valeur);
}
int main() {
int x = 5;
doubler_valeur(x); // Affiche : Valeur doublée : 10
printf("Valeur originale : %d\n", x); // Affiche : Valeur
originale : 5
return 0;
}
5.2.4.2 PASSAGE PAR REFERENCE
Dans un passage par adresse, le paramètre formel est considéré comme une variable à
laquelle on transmet, lors de chaque appel, l'adresse du paramètre effectif correspondant.
Cette adresse permet d'accéder directement à la variable effective, autorisant ainsi toutes les
modifications immédiates sur celle-ci, peu importe sa localisation en mémoire. Ce mode de
passage présente l'avantage d'une rapidité d'accès aux données et d'une utilisation mémoire
optimisée, puisque seule l'adresse est transmise.

58
Cependant, il comporte des inconvénients, notamment un risque accru pour la sécurité des
données en raison de l'absence de protection, ainsi que la nécessité de bien comprendre
l'implantation physique des données sur la machine, ce qui peut complexifier le
développement et la maintenance du code.
Exemple 1 pseudocode :
// Déclaration de la procédure qui prend un pointeur sur un
entier
PROCEDURE doubler_en_place(valeur : POINTEUR vers ENTIER)
// Doubler la valeur pointée par 'valeur'
*valeur = *valeur * 2
FIN PROCEDURE

// Programme principal
DEBUT
DECLARER x COMME ENTIER
x = 5 // Initialiser x à 5

// Appeler la procédure en passant l'adresse de x

doubler_en_place(&x)

// Afficher la valeur doublée

AFFICHER "Valeur doublée : " + x // Affiche : Valeur doublée : 10
FIN
Le tableau ci-dessous montre comment, dans le cadre du passage par référence, l'adresse de
la variable x est transmise à la procédure doubler_en_place().
▪ À l'intérieur de la procédure, valeur (qui fait référence à l'adresse de x) est modifié, et
cela a un effet direct sur la variable d'origine x.
▪ Finalement, lorsque le programme principal affiche la valeur de x, elle montre 10,
illustrant comment la modification dans la fonction a impacté la variable d'origine.

Ici, au lieu de passer une copie de la valeur, on passe l'adresse mémoire de la variable
d'origine. Ainsi, toute modification du paramètre dans la fonction affecte directement la variable
d'origine.

59
Équivalent en C :
#include <stdio.h>
// La procédure prend un pointeur sur un entier
void doubler_en_place(int *valeur) {
*valeur = (*valeur) * 2; // On déreferencie le pointeur pour
modifier la valeur
}
// Programme principal
int main() {
int x = 5;
doubler_en_place(&x); // On passe l'adresse de x
printf("Valeur doublée : %d\n", x); // Affiche : Valeur doublée : 10
return 0;
}
NB : En C, le passage par référence s'effectue avec des pointeurs4, mais peut aussi être
réalisé en utilisant des variables globales.
Exemple 2 : Variables globales et locales, passage par référence
L’exemple ci-dessous illustre l'interaction entre les variables globales et locales, ainsi que
l'impact du passage de paramètres par valeur et par référence sur la modification des valeurs.
❖ PSEUDOCODE
// Déclaration de la variable globale
Var glob : entier

// Procédure pour afficher la valeur de la variable globale

Procedure afficher_globale()
Ecrire("La variable globale est : ", glob)
Fin procedure

// Procédure pour modifier la valeur de la variable globale

Procedure modifier_globale()
glob <- 20 // Modifie la valeur de la variable globale
Fin procedure

// Programme principal
Debut
glob <- 10 // Initialise la variable globale
afficher_globale() // Affiche : La variable globale est : 10
modifier_globale() // Modifie la valeur de glob
afficher_globale() // Affiche : La variable globale est : 20
Fin

❖ CODE C
#include <stdio.h>
// Déclaration de la variable globale
int glob;

// Fonction pour afficher la valeur de la variable globale

4
Un pointeur est une variable qui stocke l'adresse mémoire d'une autre variable, permettant ainsi un
accès direct et modifiable à sa valeur.

60
void afficher_globale() {
printf("La variable globale est : %d\n", glob);
}
// Fonction pour modifier la valeur de la variable globale
void modifier_globale() {
glob = 20; // Modifie la valeur de la variable globale
}
// Fonction principale
int main() {
glob = 10; // Initialise la variable globale
afficher_globale(); // Affiche : La variable globale est : 10
modifier_globale(); // Modifie la valeur de glob
afficher_globale(); // Affiche : La variable globale est : 20
return 0;
}

Ces deux modes de passage des paramètres sont présents dans plusieurs langages de
programmation tels que C++, Java, Ada, C#, Visual Basic.NET et Delphi, etc. Ainsi, il est
essentiel pour un débutant en programmation de bien comprendre ces concepts à travers
l’algorithmique puis le langage C, ce qui lui permettra de les appliquer par analogie dans
d'autres langages de programmation.

5.2.5 LA RECURSIVITE
La récursivité est une technique élégante et efficace pour résoudre certains problèmes
répétitifs. Contrairement aux méthodes itératives, qui utilisent des boucles pour répéter des
opérations, un algorithme récursif est un algorithme qui s'appelle lui-même pour accomplir une
tâche. Lorsqu'il s'appelle, il traite une partie du problème, puis délègue le reste à une nouvelle
instance de lui-même, jusqu'à ce qu'il atteigne un cas de base (ou condition d'arrêt) où il cesse
de se réappeler.

Exemple de transformation : Toute boucle "Pour" ou "TantQue" peut être réécrite en utilisant
la récursivité.

5.2.5.1 CONDITION D'ARRET

Le dépassement de pile (ou stack overflow en anglais) est une erreur qui se produit lorsqu'un
programme utilise plus de mémoire pour les appels de fonctions que ce qui est alloué pour la
pile d'exécution (ou stack). La pile d'exécution est une zone de mémoire qui stocke
temporairement les informations de chaque appel de fonction, telles que les paramètres, les
variables locales et l'adresse de retour.

Un programme récursif doit comporter une condition d'arrêt, soit un point où il cesse de
s'appeler lui-même. Sans cette condition, la récursion se poursuit indéfiniment, provoquant
une boucle infinie. À chaque appel récursif, le programme utilise un peu plus de mémoire dans
la pile d'exécution, qui stocke les informations des appels de fonction. Si la pile atteint sa

61
capacité maximale, un dépassement de pile (stack overflow) se produit, et le programme
plante faute de mémoire pour gérer de nouveaux appels.

Exemple de code sans condition d'arrêt : Le code ci-dessous définit une procédure
récursive appelée affiche() en pseudocode et en C. La fonction affiche prend un entier i en
paramètre, l'affiche, puis s'appelle de manière récursive en incrémentant i de 1 à chaque
appel. Cependant, il n'y a pas de condition d'arrêt, donc cette récursion est infinie. En
exécutant ce code, le programme afficherait une séquence infinie de nombres croissants, ce
qui provoquerait une erreur de dépassement de pile (stack overflow).

❖ Pseudocode :
Procédure affiche (i : entier)
début
écrire(i)
affiche(i + 1)
Fin.
❖ Langage C :

#include <stdio.h>
void affiche(int i) {
printf("%d\n", i);
affiche(i + 1);
}
int main() {
affiche(1); // Appel sans condition d'arrêt, boucle infinie
return 0;
}
Exemple avec condition d'arrêt : Le code ci-dessous est une version corrigée du premier.
Dans le premier code, l'absence de condition d'arrêt provoquait une récursion infinie,
entraînant un dépassement de pile. Dans ce deuxième code, la condition si (i < 10) empêche
la récursion infinie en s'assurant que la fonction s'arrête lorsque i atteint 10.
❖ Pseudocode :
Procédure affiche (i : entier)
début
si (i < 10) alors
écrire(i)
affiche(i + 1)
fsi
Fin.

62
 ❖ Langage C :

#include <stdio.h>
void affiche(int i) {
if (i < 10) {
printf("%d\n", i);
affiche(i + 1);
}
}
int main() {
affiche(1); // L'affichage s'arrête lorsque i atteint 10
return 0;
}

5.2.6 DIFFERENCE ENTRE ITERATION ET RECURSIVITE

▪ Itération : Avec une approche itérative, on utilise des boucles pour répéter une
opération jusqu'à ce qu'une condition soit remplie. La boucle traite le problème en
répétant directement les opérations dans le même bloc de code.
▪ Récursivité : Avec une approche récursive, la fonction s'appelle elle-même pour
résoudre le problème. Chaque appel récursif réduit le problème en sous-problèmes
plus simples, jusqu'à atteindre une condition d'arrêt.

Exemple : Calcul de la Somme des N Premiers Entiers

Prenons l'exemple de calculer la somme des N premiers entiers (par exemple, la somme de 1
à 5, soit 1 + 2 + 3 + 4 + 5 = 15). Nous verrons comment le résoudre avec une approche itérative
et une approche récursive.
Les codes ci-dessous calculent la somme des N premiers entiers de deux manières différentes
:
▪ Solution Itérative : La fonction utilise une boucle for pour additionner chaque entier de
1 à N, stockant le total dans la variable somme. À la fin, elle renvoie la somme totale.

▪ Solution Récursive : La fonction décompose le problème en calculant N +

somme_recursive(N - 1), et ce, jusqu'à ce que N atteigne 1 (cas de base). À chaque
appel récursif, elle additionne le nombre actuel à la somme des précédents jusqu'au
cas de base, puis renvoie la somme totale.

1. SOLUTION ITERATIVE
En utilisant une boucle Pour, on peut additionner chaque entier de 1 jusqu'à N.

63
Pseudocode Itératif :
Fonction somme_iterative(N : Entier) : Entier
début
somme ← 0
pour i ← 1 à N faire
somme ← somme + i
fpour
retourner somme
fin
Langage C :
#include <stdio.h>
int somme_iterative(int N) {
int somme = 0;
for (int i = 1; i <= N; i++) {
somme += i;
}
return somme;
}
int main() {
printf("Somme des 5 premiers entiers : %d", somme_iterative(5));
return 0;
}
Trace d'exécution : solution itérative
Pour N = 5, cette trace montre les étapes du calcul dans la méthode itérative
Étape i somme
Initialisation - 0
1 1 0+1=1
2 2 1+2=3
3 3 3+3=6
4 4 6 + 4 = 10
5 5 10 + 5 = 15
Fin - 15
Dans cette version itérative, la fonction utilise une boucle for pour additionner chaque entier
de 1 à N. La boucle s'arrête après avoir additionné tous les nombres de 1 à 5, et la fonction
renvoie la somme finale, 15.
2. SOLUTION RECURSIVE
Avec la récursivité, on peut formuler le problème en réduisant somme(N) à N + somme (N -
1). Cette décomposition se répète jusqu'à atteindre le cas de base où N = 1.

64
Pseudocode Récursif :
Fonction somme_recursive(N : Entier) : Entier
début
si N = 1 alors
retourner 1
sinon
retourner N + somme_recursive(N - 1)
fsi
fin
Langage C :
#include <stdio.h>
int somme_recursive(int N) {
if (N == 1) {
return 1; // Condition d'arrêt
}
return N + somme_recursive(N - 1); // Appel récursif
}
int main() {
printf("Somme des 5 premiers entiers : %d
", somme_recursive(5));
return 0;
}
Trace d'exécution : solution récursive
Pour N = 5, cette trace montre les étapes du calcul dans la méthode récursive
Appel N Résultat de l’appel somme_recursive(N) Calcul
1 5 5 + somme_recursive(5-1) 5 + (10)
2 4 4 + somme_recursive(4-1) 4 + (6)
3 3 3 + somme_recursive(3-1) 3 + (3)
4 2 2 + somme_recursive(2-1) 2 + (1)
5 1 1 1

Déroulement des Calculs:

somme_recursive(1) = 1
somme_recursive(2) = 2 + somme_recursive(1) = 2 + 1 = 3
somme_recursive(3) = 3 + somme_recursive(2) = 3 + 3 = 6
somme_recursive(4) = 4 + somme_recursive(3) = 4 + 6 = 10
Explication itérative de `la trace`

65
Nous allons suivre le déroulement de l'appel récursif étape par
étape, en montrant chaque itération et les calculs associés.
Étape 1 : Appel initial
- On commence par appeler `somme_recursive(4)` pour N=5.
Étape 2 : Décomposition
1. Pour `N = 4` :
- On a :
somme_recursive(4) = 4 + somme_recursive(3)
À ce stade, nous ne connaissons pas encore la valeur de
`somme_recursive(3)`, donc nous devons l'évaluer.
Étape 3 : Appel suivant
2. Appel de `somme_recursive(3)` :
- On appelle `somme_recursive(3)` :
somme_recursive(3) = 3 + somme_recursive(2)
Nous devons maintenant évaluer `somme_recursive(2)`.
Étape 4 : Appel suivant
3. Appel de `somme_recursive(2)` :
- On appelle `somme_recursive(2)` :
somme_recursive(2) = 2 + somme_recursive(1)
Nous devons maintenant évaluer `somme_recursive(1)`.
Étape 5 : Cas de base
4. Appel de `somme_recursive(1)` :
- On appelle `somme_recursive(1)` :
somme_recursive(1) = 1
- C'est le cas de base. On retourne simplement `1`.
Remontée des appels
Maintenant, nous allons remonter dans les appels et évaluer
chaque expression :
5. Évaluation de `somme_recursive(2)` :
- On a :
somme_recursive(2) = 2 + somme_recursive(1) = 2 + 1 = 3
- Donc, `somme_recursive(2)` vaut `3`.
6. Évaluation de `somme_recursive(3)` :
- On a :

66
 somme_recursive(3) = 3 + somme_recursive(2) = 3 + 3 = 6
- Donc, `somme_recursive(3)` vaut `6`.
7. Évaluation de `somme_recursive(4)` :
- On a :
somme_recursive(4) = 4 + somme_recursive(3) = 4 + 6 = 10
- Donc, `somme_recursive(4)` vaut `10`.
Pour résumer les résultats des appels :
- somme_recursive(1) = 1
- somme_recursive(2) = 3
- somme_recursive(3) = 6
- somme_recursive(4) = 10

Ainsi, lorsque vous appelez `somme_recursive(4)`, le résultat

final est 10, ce qui représente la somme des entiers de 1 à 4
(c'est-à-dire 1 + 2 + 3 + 4 = 10).

5.2.6.1 STRUCTURE D'UN PROGRAMME RECURSIF

La structure générale d'une fonction récursive se compose de deux parties principales :

1. Condition d'arrêt : instructions à exécuter si la condition est remplie.

2. Appel récursif : si la condition n'est pas remplie, on exécute certaines instructions,
puis la fonction se rappelle elle-même avec des paramètres modifiés.

Exemple de structure :

Pseudocode :

Procédure récursive (paramètres)

début
si (condition d’arrêt) alors
<instructions d'arrêt>
sinon
<instructions avant l'appel>
Appel récursif (paramètres modifiés)
<instructions après l'appel>
fsi
Fin.

Langage C :

void recursive(int param) {

if (condition_arret) {
// Instructions d'arrêt
} else {

67
 // Instructions avant l'appel récursif
recursive(param_modifie); // Appel récursif
// Instructions après l'appel récursif
}
}
Exemple de Fonction Factorielle

Le calcul de la factorielle d'un nombre est un exemple classique de récursivité.

Version itérative :

Pseudocode :

Fonction fact (n : Entier) : Entier

var i, f : Entier
début
f ← 1
pour i ← 2 à n faire
f ← f * i
fpour
fact ← f
fin.

Langage C :

#include <stdio.h>
int fact(int n) {
int f = 1;
for (int i = 2; i <= n; i++) {
f *= i;
}
return f;
}
int main() {
printf("Factorielle de 4 : %d\n", fact(4));
return 0;
}

Version récursive :

Pseudocode :
Fonction fact (n : Entier) : Entier
début
si (n = 0) alors
fact ← 1
sinon
fact ← n * fact(n - 1)
fsi
fin.

68
Langage C :

#include <stdio.h>
int fact(int n) {
if (n == 0) {
return 1;
}
return n * fact(n - 1);
}
int main() {
printf("Factorielle de 4 : %d\n", fact(4));
return 0;
}
Principe de fonctionnement : Pour calculer `fact(4)`, on appelle `fact(4)`, qui appelle `fact(3)`,
puis `fact(2)`, et ainsi de suite jusqu'à `fact(0)`, qui renvoie 1. Ensuite, chaque appel termine
son calcul en remontant la pile d'exécution, permettant de calculer le résultat final `4! `.

5.2.6.2 LA PILE D'EXECUTION

Lorsqu'une fonction récursive s'appelle, un espace mémoire (appelé pile d'exécution) est
alloué pour stocker les paramètres et les variables de chaque appel en attente. Cela peut
consommer beaucoup de mémoire si la récursion est profonde, comme pour le calcul de `4 !
`, où chaque appel nécessite une place pour `n` et le résultat temporaire, jusqu'à atteindre la
condition d'arrêt.

5.2.6.3 RECURSION MUTUELLE

Un programme récursif peut également s'appeler indirectement en invoquant un autre
programme qui, à son tour, rappelle le premier. C'est ce qu'on appelle la récursion mutuelle.

Exemple pour calculer π :

La formule π/4 = 1 - 1/3 + 1/5 - 1/7 + ... peut être implémentée en utilisant deux fonctions
récursives qui s'appellent l'une l'autre.

Pseudocode :

Fonction f1(n : entier) : réel

début
si n <= 0 alors
f1 ← 0
sinon
f1 ← 1 / n + f2(n - 2)
fsi
fin.
Fonction f2(n : entier) : réel
début
si n <= 0 alors

69
 f2 ← 0
sinon
f2 ← -1 / n + f1(n - 2)
fsi
fin.

Langage C :

#include <stdio.h>
float f2(int n); // Déclaration préalable de f2 pour éviter une
erreur
float f1(int n) {
if (n <= 0) return 0;
return 1.0 / n + f2(n - 2);
}
float f2(int n) {
if (n <= 0) return 0;
return -1.0 / n + f1(n - 2);
}
int main() {
printf("Valeur approximative de pi : %f\n", 4 * f1(2 * 100 +
1));
return 0;
}
Dans cet exemple, f1 et f2 s'appellent mutuellement jusqu'à ce que n’atteigne zéro. Pour
obtenir la valeur de π, on multiplie le résultat de f1 par 4.

A travers ces exemples en pseudocode et en C, nous avons une base importante pour
comprendre et implémenter la récursivité. La récursivité peut simplifier le code et le rendre
plus lisible, mais elle peut aussi consommer plus de mémoire, surtout si elle est utilisée sans
condition d'arrêt appropriée.

5.3 EXERCICES DE FIN CHAPITRE

Exercice 1
Écrire une fonction qui permet de calculer le prix TTC , cette fonction va recevoir un
paramètre de type Réel dont le nom est "prixHT" et un second paramètre de type Réel
dont le nom est "tva".
Exercice 2
Écrire une procédure qui permet d'afficher si un nombre entier passé en paramètre est
pair ou impair.
Exercice 3
Écrire une fonction qui permet de retourner le nombre de caractères d’une chaîne de
caractères passée en paramètre.

70
Exercice 4
Écrire une fonction qui cherche combien de fois un caractère est présent dans une
chaîne de caractères. Le caractère à chercher et la chaîne seront passés en
paramètres.
Exercice 5
Ecrire une fonction ou procédure qui calcule la valeur absolue d’un nombre.
Exercice 6
Ecrire une procédure qui affiche le tableau de multiplication d’un entier positif x.
Exercice 7
Ecrire une fonction qui calcule le PGCD de deux entiers strictement positifs en utilisant
en premier la méthode itérative et en second la méthode récursive.
Exercice 8
Ecrire une procédure qui permet de lire deux nombres, calculer la somme et le produit
et affiche si ces derniers sont positifs ou négatifs.

71
CHAPITRE 6 : ALGORITHMIQUE AVANCEE
6.1 ALGORITHMES DE TRI

6.1.1 INTRODUCTION
Le tri est un problème fondamental en informatique, consistant à organiser un ensemble
d'éléments dans un ordre spécifique, par exemple, du plus petit au plus grand ou inversement.
C'est une opération cruciale, car elle facilite l'accès et la gestion efficace des données, ce qui
est essentiel dans des domaines variés, notamment en programmation, où trier des données
avant de les utiliser est souvent indispensable.

Il existe divers algorithmes de tri, chacun avec ses particularités, ses avantages et ses limites.
Certains sont plus adaptés à de grandes quantités de données, tandis que d'autres offrent une
meilleure performance dans des situations spécifiques. Le tri est d’ailleurs l’un des domaines
les plus étudiés en algorithmique, ayant conduit à des avancées majeures dans la conception
et l’analyse des algorithmes.

Pour mieux comprendre la complexité du tri, imaginez ce défi : vous devez ranger plusieurs
tonneaux (de 3 à 10) par ordre croissant de poids. Le poids de chaque tonneau est attribué
aléatoirement, et vous ne disposez que d'une balance pour comparer les poids deux à deux,
ainsi que d’étagères pour poser des tonneaux en attente. Ce jeu illustre bien la manière dont
un ordinateur trie les données : en effectuant des comparaisons successives et en utilisant
des espaces de stockage intermédiaires.

L'objectif est de trier les tonneaux en effectuant le moins de comparaisons et de mouvements

possible, un principe de base que l’on cherche aussi à optimiser dans le tri informatique.

6.1.2 DEFINITION DU TRI

En programmation, le tri consiste à réorganiser un ensemble de données, comme un tableau,
en ordre croissant (du plus petit au plus grand) ou décroissant (du plus grand au plus petit). Il
existe de nombreux algorithmes pour trier les données, parmi lesquels le tri par sélection, le
tri à bulles, le tri par insertion, le tri fusion, et le tri rapide. Chacun de ces algorithmes possède
des caractéristiques, des avantages et des inconvénients spécifiques qui les rendent adaptés
à différents types de situations.

Dans un cours, nous allons explorer ces algorithmes de tri et apprendront à identifier celui qui
convient le mieux selon les exigences et les contraintes du tri.

6.1.2.1 LE TRI PAR SELECTION

Le tri par sélection est celui qui utilise le concept le plus simple. Étant donné qu’il existe un
algorithme qui permet de renvoyer la valeur la plus petite d’un tableau, on peut l’appliquer

72
systématiquement pour reconstruire un tableau trié. En d’autres termes, à chaque case du
tableau que l’on souhaite trier, on effectue une recherche dans la partie de droite pour
retrouver l’élément le plus petit. Une fois trouvé, on échange les valeurs.

On peut résumer le principe de fonctionnement de l'algorithme de tri par sélection avec le

schéma suivant :

État initial : t = [12, 8, 23, 10, 15]

Étapes détaillées :

1. i = 0, min = 0, j de 1 à 4
- Comparaisons : 12 avec 8, 8 avec 23, 8 avec 10, 8 avec 15
- min devient 1
- Échange t[0] et t[1] : t = [8, 12, 23, 10, 15]

2. i = 1, min = 1, j de 2 à 4
- Comparaisons : 12 avec 23, 12 avec 10, 10 avec 15
- min devient 3
- Échange t[1] et t[3] : t = [8, 10, 23, 12, 15]

3. i = 2, min = 2, j de 3 à 4
- Comparaisons : 23 avec 12, 12 avec 15
- min devient 3
- Échange t[2] et t[3] : t = [8, 10, 12, 23, 15]

4. i = 3, min = 3, j = 4
- Comparaison : 23 avec 15
- min devient 4
- Échange t[3] et t[4] : t = [8, 10, 12, 15, 23]

73
5. Tableau trié : t = [8, 10, 12, 15, 23]

Le pseudocode ci-dessous implémente l’algorithme de tri par sélection sur un tableau

d'entiers. Il parcourt le tableau pour chaque position i en cherchant l'élément minimum dans
la portion non triée (de i+1 à la fin du tableau). Lorsqu'il trouve un élément plus petit, il met à
jour l'indice min pour pointer sur cet élément. Si un minimum différent de l'élément actuel est
trouvé, le code échange l'élément à la position i avec ce minimum. Ensuite, il avance à la
position suivante et répète le processus jusqu'à ce que le tableau soit trié.
Algorithme : Tri par sélection
VARIABLES
t : tableau d'entiers
i, j, min, n, temp : nombre entier

DEBUT
n ← longueur(t) // définir la longueur du tableau
Pour i de 0 à n - 2 faire //boucle 1
min ← i
Pour j de i + 1 à n - 1 faire //boucle 2
si t[j] < t[min] alors
min ← j
fin si
Fin Pour
si min <> i alors
temp ← t[i]
t[i] ← t[min]
t[min] ← temp
fin si
Fin Pour
FIN
LA PROCEDURE
Procédure Tri-Sélection (T : tableau [1..n] d'entiers, n : entier)
Début
Entier i, j, min, temp
Pour i de 0 à n - 2 faire // pour chaque élément
min ← i
Pour j de i + 1 à n - 1 faire // trouver le minimum dans le
reste du tableau
Si T[j] < T[min] alors
min ← j
Fin Si
Fin Pour
Si min <> i alors // échanger si un plus petit élément a été
trouvé
temp ← T[i]

74
 T[i] ← T[min]
T[min] ← temp
Fin Si
Fin Pour
Fin
La raison pour laquelle on commence i à 0 et on va jusqu'à n - 2, et j de i + 1 à n - 1, est liée à
la gestion des indices du tableau pendant le processus de tri par sélection.
1. Pour la boucle i allant de 0 à n - 2:
▪ La boucle commence à 0 car les tableaux en programmation commencent
généralement à l'index 0.
▪ Elle va jusqu'à n-2 pour s'assurer que lorsque i est à l'avant-dernier élément, il n'y
a plus d'éléments restants à trier après cet élément. Cette borne limite le nombre
de comparaisons à effectuer dans la boucle interne.
2. Pour la boucle j allant de i + 1 à n - 1:
▪ j commence à i+1 pour comparer l'élément à la position i avec tous les éléments
suivants dans la portion non triée du tableau.
▪ j va jusqu'à n-1 car c'est l'index du dernier élément du tableau.
En C, les boucles for sont explicitement définies avec une syntaxe stricte et des limites claires.

Échelle des indices : En C, les indices des tableaux commencent à 0. La boucle for (i = 0; i <
n - 1; i++) signifie que i va de 0 à n-2 inclus, ce qui assure que toutes les positions sauf la
dernière sont triées.

Conditions de boucle : Les conditions des boucles doivent être précises pour éviter les
dépassements de limites du tableau, ce qui pourrait provoquer des erreurs d'exécution.
Comparaisons et efficacité : En C, il est essentiel d'éviter les comparaisons inutiles pour des
raisons d'efficacité. Les indices sont gérés de manière à minimiser le nombre total de
comparaisons effectuées.
#include <stdio.h>

int main() {
int t[] = {12, 8, 23, 10, 15};
int n = sizeof(t)/sizeof(t[0]);
int i, j, min, temp;

// Afficher le tableau initial

printf("Tableau initial :\n");
for (i = 0; i < n; i++) {
printf("%d ", t[i]);
}
printf("\n");
// Tri par sélection
for (i = 0; i < n - 1; i++) {

75
 min = i;
for (j = i + 1; j < n; j++) {
if (t[j] < t[min]) {
min = j;
}
}
if (min != i) {
temp = t[i];
t[i] = t[min];
t[min] = temp;
}
}
// Afficher le tableau trié
printf("Tableau trié :\n");
for (i = 0; i < n; i++) {
printf("%d ", t[i]);
}
printf("\n");

return 0;
}

PROCEDURE

#include <stdio.h>
void triSelection(int T[], int n) {
int i, j, min, temp;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++) {
if (T[j] < T[min]) {
min = j;
}
}
if (min != i) {
temp = T[i];
T[i] = T[min];
T[min] = temp;
}
}
}
int main() {
int T[] = {27, 10, 12, 8, 11};
int n = sizeof(T) / sizeof(T[0]);

triSelection(T, n);

printf("Tableau trié avec Tri par Sélection :\n");

for (int i = 0; i < n; i++) {
printf("%d ", T[i]);
}
printf("\n");

return 0;
}

76
Note 1 : En pseudocode, les boucles dans le présent cas sont écrites comme suit
Pour i de 0 à n - 2 faire
Pour j de i + 1 à n - 1 faire
En C, cela se traduit par :
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {

Cette traduction assure que toutes les comparaisons nécessaires sont effectuées sans
provoquer d'erreurs de dépassement de tableau.

Note 2 : Cette formule divise la taille totale du tableau t par la taille d'un élément individuel de
t, ce qui donne le nombre total d'éléments dans le tableau.
int n = sizeof(t) / sizeof(t[0]);
La taille d'un élément individuel dans le tableau `t` dépend du type des éléments du tableau.
Dans le cas de int t[] = {12, 8, 23, 10, 15};, les éléments sont de type int. La taille d'un `int` en
C est généralement de 4 octets (ou 4 bytes).
Donc, dans ce contexte, `sizeof(t[0])` donne 4 octets, qui est la taille d'un élément individuel
du tableau `t`.

La complexité d'un algorithme mesure le temps d'exécution ou l'espace mémoire

requis en fonction de la taille de l'entrée, souvent exprimée en notation Big-O.

Essayons maintenant de déterminer la complexité de l'algorithme de tri par sélection

:

Pour établir la complexité de cet algorithme, nous n'allons pas directement nous
intéresser au nombre d'opérations élémentaires. Nous allons comptabiliser les
comparaisons entre 2 entiers.

Si nous nous intéressons à l'étape qui nous permet de passer de t = [12, 8, 23, 10, 15]
à t = [8, 12, 23, 10, 15] (i = 1) nous avons 4 comparaisons : 12 avec 8, puis 8 avec 23,
puis 8 avec 10 et enfin 8 avec 15.

Si nous nous intéressons à l'étape qui nous permet de passer de t = [8, 12, 23, 10, 15]
à t = [8, 10, 23, 12, 15] (i = 2) nous avons 3 comparaisons : 12 avec 23, puis 12 avec
10, et enfin 10 avec 15.

Si nous nous intéressons à l'étape qui nous permet de passer de t = [8, 10, 23, 12, 15]
à t = [8, 10, 12, 23, 15] (i = 3) nous avons 2 comparaisons : 23 avec 12 et 12 avec 15

Si nous nous intéressons à l'étape qui nous permet de passer de t = [8, 10, 12, 23, 15]
à t = [8, 10, 12, 15, 23] (i = 4) nous avons 1 comparaison : 23 avec 15

77
Pour trier un tableau comportant 5 éléments nous avons : 4 + 3 + 2 + 1 = 10
comparaisons

Dans le cas où nous avons un tableau à trier qui contient n éléments, nous aurons : n-
1 + n-2 + n-3 +....+ 3 + 2 + 1 comparaisons. Si vous n'êtes pas convaincu, faites le test
avec un tableau de 6 éléments, vous devriez trouver 5 + 4 + 3 + 2 +1 = 15
comparaisons.

Comme pour le tri par insertion, l'algorithme de tri par sélection a une complexité
quadratique, soit O(n2).

Il est crucial de comprendre l'impact de ces complexités sur l'utilisation des algorithmes
: doubler la taille du tableau double le temps d'exécution pour un algorithme linéaire
O(n), mais quadruple le temps d'exécution pour un algorithme quadratique O(n 2).

6.1.2.2 LE TRI PAR INSERTION

Le tri par insertion est considéré comme le tri le plus efficace sur des entrées de petite taille.
Il est aussi très rapide lorsque les données sont déjà presque triées. C'est le tri du joueur de
cartes. On fait comme si les éléments à trier étaient donnés un par un, le premier élément
constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément
pour constituer une liste triée de longueur 2, puis on range le troisième élément pour avoir une
liste triée de longueur 3 et ainsi de suite.

Le principe du tri par insertion est donc d'insérer à la nième itération le nième élément à la
bonne place. L'algorithme divise la liste en une partie ordonnée et une partie non ordonnée.
La partie triée commence par le premier élément de la liste. A chaque itération, l'algorithme
supprime un élément de la partie non triée et l'insère au bon endroit dans la partie triée. Le tri
par insertion est donc un algorithme de tri qui consiste à parcourir un tableau en plaçant
chaque élément à sa place définitive, en le comparant aux éléments déjà triés. Pour chaque
élément du tableau, on le compare à tous les éléments qui le précèdent, jusqu'à trouver sa
place. Pour cela, on effectue des décalages successifs de tous les éléments plus grands que
l'élément en cours, afin de créer une place libre pour y insérer l'élément.

On peut résumer le principe de fonctionnement de l'algorithme de tri par insertion avec le

schéma suivant :

78
État initial : t = [27, 10, 12, 8, 11]
Étapes détaillées :
1. j = 1
o i = 0, k = 10
o Comparaisons : 27 avec 10
o Déplacement de 27 : t = [27, 27, 12, 8, 11]
o Insertion de 10 : t = [10, 27, 12, 8, 11]
2. j = 2
o i = 1, k = 12
o Comparaisons : 27 avec 12
o Déplacement de 27 : t = [10, 27, 27, 8, 11]
o Insertion de 12 : t = [10, 12, 27, 8, 11]
3. j = 3
o i = 2, k = 8
o Comparaisons : 27 avec 8, 12 avec 8, 10 avec 8
o Déplacement de 27 : t = [10, 12, 27, 27, 11]
o Déplacement de 12 : t = [10, 12, 12, 27, 11]
o Déplacement de 10 : t = [10, 10, 12, 27, 11]
o Insertion de 8 : t = [8, 10, 12, 27, 11]
4. j = 4
o i = 3, k = 11
o Comparaisons : 27 avec 11, 12 avec 11
o Déplacement de 27 : t = [8, 10, 12, 27, 27]
o Déplacement de 12 : t = [8, 10, 12, 12, 27]
o Insertion de 11 : t = [8, 10, 11, 12, 27]
5. Tableau trié : t = [8, 10, 11, 12, 27]
Le pseudocode ci-dessous, implémente l'algorithme de tri par insertion pour trier un tableau
`t` d'entiers en ordre croissant. Il commence par calculer la longueur `n` du tableau, puis
initialise l'index `j` à 1. Dans la première boucle (boucle 1), `j` parcourt le tableau à partir du
deuxième élément jusqu'au dernier. Pour chaque élément `t[j]`, l'algorithme le stocke dans `k`
et le compare aux éléments précédents dans le tableau (boucle 2), en commençant par `i = j
- 1`. Tant que `t[i]` est plus grand que `k`, il décale `t[i]` d'une position vers la droite. Quand un

79
emplacement approprié pour `k` est trouvé, il le place dans `t[i + 1]`. Cette méthode insère
ainsi chaque élément à sa place correcte dans la partie triée du tableau, le triant
progressivement.

VARIABLES
t : tableau d'entiers
i, j, k, n : nombres entiers

DEBUT
n ← longueur(t) // définir la longueur du tableau
j ← 1
TantQue j < n faire // boucle 1
i ← j - 1
k ← t[j]
TantQue i >= 0 et t[i] > k faire // boucle 2
t[i + 1] ← t[i]
i ← i - 1
fin tant que
t[i + 1] ← k
j ← j + 1
fin tant que
FIN
LA PROCEDURE
Procédure Tri-Insertion (T : tableau [1..n] d'entiers, n : entier)
Début
Entier i, j, k
Pour j de 1 à n - 1 faire
i ← j - 1
k ← T[j]
Tant que i >= 0 et T[i] > k faire // déplacer les éléments plus
grands que k vers la droite
T[i + 1] ← T[i]
i ← i - 1
Fin Tant que
T[i + 1] ← k // insérer k à sa position correcte
Fin Pour
Fin
Le code ci-dessous qui est la version du pseudocode en langage C, trie un tableau d'entiers
en utilisant l'algorithme de tri par insertion, puis affiche le tableau avant et après le tri. Le
tableau `t` est initialisé avec les valeurs `{27, 10, 12, 8, 11}`, et `n` calcule la longueur du
tableau. Le programme commence par afficher le tableau initial, puis exécute le tri en utilisant
une boucle `for` qui parcourt chaque élément, en partant du deuxième (indice 1). Pour chaque
élément, il trouve la bonne position dans la partie déjà triée du tableau en le comparant aux

80
éléments précédents dans une boucle `while`. Si un élément précédent est plus grand, il le
décale d'une position à droite, jusqu'à trouver l'emplacement adéquat pour l'élément en cours.
Une fois le tri terminé, le programme affiche le tableau trié.
#include <stdio.h>

int main() {
int t[] = {27, 10, 12, 8, 11};
int n = sizeof(t) / sizeof(t[0]);
int i, j, k;

// Afficher le tableau initial

printf("Tableau initial :\n");
for (i = 0; i < n; i++) {
printf("%d ", t[i]);
}
printf("\n");

// Algorithme de tri
for (j = 1; j < n; j++) {
i = j - 1;
k = t[j];
while (i >= 0 && t[i] > k) {
t[i + 1] = t[i];
i = i - 1;
}
t[i + 1] = k;
}

// Afficher le tableau trié

printf("Tableau trié :\n");
for (i = 0; i < n; i++) {
printf("%d ", t[i]);
}
printf("\n");

return 0;
}

PROCEDURE

#include <stdio.h>

void triInsertion(int T[], int n) {

int i, j, k;
for (j = 1; j < n; j++) {
k = T[j];
i = j - 1;
while (i >= 0 && T[i] > k) {
T[i + 1] = T[i];
i--;
}
T[i + 1] = k;
}
}

81
int main() {
int T[] = {27, 10, 12, 8, 11};
int n = sizeof(T) / sizeof(T[0]);

triInsertion(T, n);

printf("Tableau trié avec Tri par Insertion :\n");

for (int i = 0; i < n; i++) {
printf("%d ", T[i]);
}
printf("\n");

return 0;
}

La complexité d'un algorithme de tri par insertion

La complexité d'un algorithme mesure le temps d'exécution ou l'espace mémoire requis en
fonction de la taille de l'entrée, souvent exprimée en notation Big-O. Essayons maintenant de
déterminer la complexité de l'algorithme de tri par insertion en utilisant le tableau t[] = {27, 10,
12, 8, 11}.
Pour établir la complexité de cet algorithme, nous allons compter les comparaisons entre deux
entiers.
Étapes de l'algorithme de tri par insertion :

1. État initial : t = [27, 10, 12, 8, 11]

o j=1
▪ i = 0, k = 10
▪ Comparaison : 27 avec 10
▪ Déplacement de 27 : t = [27, 27, 12, 8, 11]
▪ Insertion de 10 : t = [10, 27, 12, 8, 11]
o Comparaisons : 1
2. j = 2
o i = 1, k = 12
o Comparaison : 27 avec 12
o Déplacement de 27 : t = [10, 27, 27, 8, 11]
o Insertion de 12 : t = [10, 12, 27, 8, 11]
o Comparaisons : 1
3. j = 3
o i = 2, k = 8
o Comparaison : 27 avec 8
o Déplacement de 27 : t = [10, 12, 27, 27, 11]
o Comparaison : 12 avec 8
o Déplacement de 12 : t = [10, 12, 12, 27, 11]
o Comparaison : 10 avec 8
o Déplacement de 10 : t = [10, 10, 12, 27, 11]
o Insertion de 8 : t = [8, 10, 12, 27, 11]
o Comparaisons : 3
4. j = 4
o i = 3, k = 11

82
 o Comparaison : 27 avec 11
o Déplacement de 27 : t = [8, 10, 12, 27, 27]
o Comparaison : 12 avec 11
o Déplacement de 12 : t = [8, 10, 12, 12, 27]
o Insertion de 11 : t = [8, 10, 11, 12, 27]
o Comparaisons : 2

Total des comparaisons : Pour trier un tableau comportant 5 éléments, nous avons effectué :
1 + 1 + 3 + 2 = 7 comparaisons.
Complexité générale
Dans le cas où nous avons un tableau de n éléments, nous aurons en moyenne environ
n(n-1)/2 comparaisons, ce qui donne une complexité quadratique : O(n^2).
6.1.2.3 LE TRI À BULLES

Le tri à bulles (ou tri par bulles) est un algorithme de tri simple qui compare chaque
paire d'éléments adjacents et les échange s'ils sont dans le mauvais ordre. Ce
processus est répété jusqu'à ce que le tableau soit trié. À chaque passage, l'élément
le plus grand "bulle" à la fin du tableau non trié.
On peut résumer le principe de fonctionnement de l'algorithme de tri à bulles avec le
schéma suivant :
État initial : t = [27, 10, 12, 8, 11]

Explication
▪ Parcours 1 : Le plus grand élément "flotte" vers la fin du tableau.
▪ Parcours 2 : Le deuxième plus grand élément est placé juste avant le dernier.

83
 ▪ Parcours 3 : Le tableau devient trié, car aucun échange supplémentaire n'est
nécessaire.
Étapes détaillées

1. i = 0
o Comparaison et échanges successifs :
▪ 27 avec 10 -> échange : t = [10, 27, 12, 8, 11]
▪ 27 avec 12 -> échange : t = [10, 12, 27, 8, 11]
▪ 27 avec 8 -> échange : t = [10, 12, 8, 27, 11]
▪ 27 avec 11 -> échange : t = [10, 12, 8, 11, 27]
2. i = 1
o Comparaison et échanges successifs :
▪ 10 avec 12 -> pas d'échange
▪ 12 avec 8 -> échange : t = [10, 8, 12, 11, 27]
▪ 12 avec 11 -> échange : t = [10, 8, 11, 12, 27]
3. i = 2
o Comparaison et échanges successifs :
▪ 10 avec 8 -> échange : t = [8, 10, 11, 12, 27]
▪ 10 avec 11 -> pas d'échange
4. i = 3
o
Comparaison :
▪ 8 avec 10 -> pas d'échange
5. Tableau trié : t = [8, 10, 11, 12, 27]
C'est l'algorithme de tri le plus simple :
1. Parcourir le tableau plusieurs fois, de gauche à droite.
2. À chaque passage, comparer chaque paire d'éléments consécutifs :
Si les deux éléments ne sont pas dans le bon ordre (c'est-à-dire, si tableau[i] > tableau[i+1]),
échanger leur position.
3. Recommencer ce processus jusqu'à ce qu'il n'y ait plus d'échanges nécessaires lors
d'un passage complet. Cela signifie que le tableau est trié.
Cet algorithme fonctionne en déplaçant progressivement les plus grands éléments vers la fin
du tableau, d'où son nom de "tri à bulles".Algorithme : Tri à bulles
VARIABLES
t : tableau d'entiers
i, j, n, temp : nombre entier

DEBUT
n ← longueur(t) // définir la longueur du tableau
Pour i de 0 à n - 2 faire //boucle 1
Pour j de 0 à n - 2 - i faire //boucle 2
si t[j] > t[j + 1] alors
temp ← t[j]
t[j] ← t[j + 1]
t[j + 1] ← temp
fin si
Fin Pour
Fin Pour
FIN

84
 LA PROCEDURE
Procédure Tri-Bulles (T : tableau [1..n] d'entiers, n : entier)
Début
Entier i, k, temp
Pour k de 0 à (n - 2) faire // pour chaque passe
Pour i de n - 1 à k + 1 faire // comparer les éléments
adjacents
Si (T[i] < T[i - 1]) alors
temp ← T[i]
T[i] ← T[i - 1]
T[i - 1] ← temp
Fin Si
Fin Pour
Fin Pour
Fin

Code en C pour le tri à bulles

#include <stdio.h>

int main() {
int t[] = {27, 10, 12, 8, 11};
int n = sizeof(t) / sizeof(t[0]);
int i, j, temp;

// Afficher le tableau initial

printf("Tableau initial :\n");
for (i = 0; i < n; i++) {
printf("%d ", t[i]);
}
printf("\n");

// Tri à bulles
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (t[j] > t[j + 1]) {
temp = t[j];
t[j] = t[j + 1];
t[j + 1] = temp;
}
}
}

// Afficher le tableau trié

printf("Tableau trié :\n");
for (i = 0; i < n; i++) {
printf("%d ", t[i]);
}
printf("\n");

return 0;
}

85
 PROCEDURE

#include <stdio.h>
void triBulles(int T[], int n) {
int temp;
for (int k = 0; k < n - 1; k++) {
for (int i = n - 1; i > k; i--) {
if (T[i] < T[i - 1]) {
temp = T[i];
T[i] = T[i - 1];
T[i - 1] = temp;
}
}
}
}

int main() {
int T[] = {27, 10, 12, 8, 11};
int n = sizeof(T) / sizeof(T[0]);

triBulles(T, n);

printf("Tableau trié avec Tri à Bulles :\n");

for (int i = 0; i < n; i++) {
printf("%d ", T[i]);
}
printf("\n");

return 0;
}

Complexité
La complexité d'un algorithme mesure le temps d'exécution ou l'espace mémoire requis en
fonction de la taille de l'entrée, souvent exprimée en notation Big-O5.
Pour l'algorithme de tri à bulles, chaque passage complet nécessite un nombre de
comparaisons décroissant :
1. n - 1 comparaisons au premier passage
2. n - 2 comparaisons au deuxième passage
3. Et ainsi de suite...
Pour trier un tableau de n éléments, nous avons : (n - 1) + (n - 2) + ... + 1 comparaisons.
Cela équivaut à environ n(n - 1)/2 comparaisons, soit une complexité quadratique : O(n^2).
Big-O aide à comparer et choisir des algorithmes en fonction de leur efficacité pour traiter des
grandes quantités de données.

5
La notation Big-O, notée O(⋅), est une façon de décrire la performance d'un algorithme en termes
de temps d'exécution ou d'utilisation de la mémoire en fonction de la taille de l'entrée. Elle se
concentre sur le comportement asymptotique, c’est-à-dire comment le temps ou la mémoire
nécessaires augmentent à mesure que la taille des données d'entrée (notée n) grandit.

86
Le tableau ci-dessous montre l’ordre de croissance et des exemples typiques pour chaque
complexité.

6.2 ALGORITHMES DE RECHERCHE

6.2.1 INTRODUCTION
Les algorithmes de recherche sont des outils essentiels pour trouver des informations dans de
vastes ensembles de données, utilisés dans des domaines variés comme l’informatique, les
bases de données et la recherche scientifique. Ils s’inspirent souvent de stratégies intuitives
que nous appliquons quotidiennement, comme retrouver des clés égarées ou chercher une
réponse précise, mais ces actions reposent sur des principes algorithmiques fondamentaux.
Par exemple, la recherche linéaire inspecte chaque élément d'une liste de manière
séquentielle, tandis que la recherche dichotomique, plus efficace, réduit le champ
d’investigation en éliminant des options à chaque étape, à condition que les données soient
triées. Dans ce cours, nous étudierons ces deux méthodes, leur fonctionnement et leurs
applications pratiques à travers du pseudocode et du C, en soulignant l'importance de
l'organisation des données pour optimiser les recherches.

6.2.2 ALGORITHMES DE RECHERCHE CLASSIQUES

6.2.2.1 RECHERCHE SEQUENTIELLE

L'algorithme de recherche séquentielle d'un élément « e » dans un tableau « tab » consiste à
examiner chaque élément du tableau, en le comparant successivement à l'élément recherché.

87
Dès que l'élément « e » est trouvé, il est possible de quitter immédiatement la boucle de
recherche, ce qui optimise le processus. Elle fonctionne sur des listes non triées ou triées
cependant, bien que la recherche séquentielle soit une méthode simple à mettre en œuvre,
elle peut s'avérer inefficace, surtout dans le cas de tableaux de grande taille. En effet, cet
algorithme parcourt le tableau un élément à la fois jusqu'à localiser l'élément désiré. Par
conséquent, si l'élément est positionné vers la fin du tableau ou n'y figure pas du tout, le temps
de recherche peut être considérable.
NOMBRE DE COMPARAISONS
▪ Dans le meilleur des cas, l'élément recherché est trouvé dès la première
comparaison.
▪ Dans le pire des cas, toutes les n comparaisons sont nécessaires (lorsque l'élément
est absent ou se trouve en dernière position).
Le temps de recherche est donc proportionnel à n, ce qui signifie que la recherche séquentielle
a une complexité temporelle de O(n).
CAS DE L'EGALITE ET ARRET ANTICIPE
L'algorithme de recherche séquentielle peut s'arrêter dès que l'élément recherché est trouvé.
Cet arrêt immédiat, appelé arrêt anticipé, est une caractéristique naturelle de cette méthode.

Toutefois, la condition "si l'élément actuel est supérieur à l'élément recherché, arrêter la
recherche" n'est applicable que si la liste est triée. Dans ce cas, dès qu'un élément supérieur
est rencontré, il devient inutile de continuer, car l'élément recherché ne peut plus apparaître.
En revanche, pour une liste non triée, cette condition ne peut pas être utilisée, car l'ordre des
éléments n'est pas garanti. La recherche séquentielle classique continue d'examiner tous les
éléments successivement jusqu'à trouver une correspondance ou parcourir la totalité de la
liste. Ainsi, la recherche séquentielle diffère légèrement dans son fonctionnement selon que
la liste est triée ou non, bien que sa complexité temporelle reste O(n) dans les deux cas.
1. Recherche séquentielle pour une liste non triée
Dans le cas d'une liste non triée, l'algorithme de recherche séquentielle parcourt chaque
élément sans pouvoir s'arrêter prématurément, car aucun ordre particulier ne garantit qu'un
élément trouvé ou ignoré indique quoi que ce soit sur les autres éléments. La recherche doit
donc aller jusqu'à trouver une correspondance ou atteindre la fin de la liste.
Exemple : Supposons que l'on recherche l'élément 5 dans la liste suivante : [9, 3, 7, 1, 5, 2, 6,
8, 4]
L'algorithme commence par examiner chaque élément, un par un, dans l'ordre où ils
apparaissent. Une fois que l'élément 5 est trouvé, l'algorithme s'arrête immédiatement.

88
Contrairement à une liste triée, il n'est pas possible d'arrêter la recherche avant de vérifier tous
les éléments précédents, même si des éléments plus grands ou plus petits sont rencontrés.
Le pseucode ci-dessous permet d’examiner chaque élément jusqu'à trouver une
correspondance ou atteindre la fin de la liste :

Algorithme RechercheSequentielleNonTriee
// Déclaration des variables globales
variable liste : tableau d'entiers
variable taille, elementRecherche, resultat : entier

// Fonction de recherche séquentielle

fonction recherche_sequentielle_non_triee(T : tableau d'entiers, n : entier,
x : entier) : entier
début
variable i : entier
pour i allant de 0 à n - 1 faire
si T[i] = x alors
retourner i // Retourner l'indice de l'élément trouvé
fin si
fin pour
retourner -1 // Retourner -1 si l'élément n'est pas trouvé
fin fonction

// Programme principal
Début
// Initialisation de la liste non triée
liste <- [9, 5, 2, 8, 1, 3, 7, 4, 6]
taille <- 9 // Nombre d'éléments dans la liste
elementRecherche <- 5
// Appel à la fonction de recherche séquentielle non triée
resultat<-recherche_sequentielle_non_triee(liste,taille,elementRecherche)
// Affichage du résultat
si resultat <> -1 alors
afficher "Élément ", elementRecherche, " trouvé à l'indice ", resultat
sinon
afficher "Élément ", elementRecherche, " non trouvé dans la liste"
fin si
Fin

Le code C ci-dessous est la matérialisation de ce pseudocode en langage de programmation

:
#include <stdio.h>
// Fonction de recherche séquentielle pour une liste non triée
int rechercheSequentielleNonTriee(int liste[], int taille, int element) {
for (int i = 0; i < taille; ++i) {
// Comparer l'élément actuel avec l'élément recherché
if (liste[i] == element) {
return i; // Élément trouvé, retourner l'indice
}
}
return -1; // Élément non trouvé
}

89
int main() {
int liste[] = {9, 5, 2, 8, 1, 3, 7, 4, 6};
int taille = sizeof(liste) / sizeof(liste[0]);
int elementRecherche = 5;
// Appeler la fonction de recherche séquentielle
int resultat = rechercheSequentielleNonTriee(liste, taille,
elementRecherche);
// Afficher le résultat
if (resultat != -1) {
printf("Element %d trouve a l'indice %d.\n", elementRecherche,
resultat);
} else {
printf("Element %d non trouve dans la liste.\n", elementRecherche);
}

return 0;
}

2. Recherche séquentielle pour une liste triée

Pour une liste triée, on peut optimiser en arrêtant la recherche si un élément plus grand que celui
recherché est trouvé. Cela réduit le nombre de comparaisons.
Exemple : Supposons que l'on recherche l'élément 5 dans la liste suivante :
[1, 2, 3, 4, 5, 6, 7, 8, 9]
L'algorithme de recherche séquentielle commencerait par examiner le premier élément de la
liste, soit 1. Comme 1 est inférieur à 5, l'algorithme examine le deuxième élément de la liste,
soit 2. Comme 2 est inférieur à 5, l'algorithme continue d'examiner les éléments suivants.
Lorsque l'algorithme atteint l'élément 5, il a trouvé l'élément recherché.
Si l'algorithme s'intéressait au cas de l'égalité, il aurait pu arrêter l'exploration de la liste dès
qu'il a trouvé l'élément 5.
Algorithme RechercheSequentielleTriee
// Déclaration des variables globales
variable liste : tableau d'entiers
variable taille, elementRecherche, resultat : entier
// Fonction de recherche séquentielle triée
fonction recherche_sequentielle_triee(T : tableau d'entiers, n : entier, x
: entier) : entier
Début
variable i : entier
pour i allant de 0 à n - 1 faire
si T[i] = x alors
retourner i // Retourner l'indice de l'élément trouvé
fin si
si T[i] > x alors
retourner -1 // Arrêter la recherche si l'élément courant est
plus grand que x
fin si
fin pour
retourner -1 // Retourner -1 si l'élément n'est pas trouvé
Fin fonction

90
// Programme principal
Début
// Initialisation de la liste triée
liste <- [1, 2, 3, 4, 5, 6, 7, 8, 9]
taille <- 9 // Nombre d'éléments dans la liste
elementRecherche <- 5
resultat <- -1 // Résultat initial (indice ou -1 si non trouvé)
// Appel à la fonction de recherche séquentielle triée
resultat <- recherche_sequentielle_triee(liste, taille, elementRecherche)
// Affichage du résultat
si resultat <> -1 alors
afficher "Élément ", elementRecherche, " trouvé à l'indice ", resultat
sinon
afficher "Élément ", elementRecherche, " non trouvé dans la liste"
fin si
Fin

Le code C ci-dessous est la matérialisation de ce pseudocode en langage de programmation

:
#include <stdio.h>
// Fonction de recherche séquentielle
int rechercheSequentielle(int liste[], int taille, int element) {
for (int i = 0; i < taille; ++i) {
// Comparer l'élément avec l'élément actuel de la liste
if (liste[i] == element) {
return i; // Élément trouvé, retourner l'indice
}
// Si l'élément actuel est supérieur à l'élément recherché, arrêter
la recherche
if (liste[i] > element) {
break;
}
}
return -1; // Élément non trouvé dans la liste
}

int main() {
int liste[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int taille = sizeof(liste) / sizeof(liste[0]);
int elementRecherche = 5;
// Appeler la fonction de recherche séquentielle
int resultat = rechercheSequentielle(liste, taille, elementRecherche);
// Afficher le résultat
if (resultat != -1) {
printf("Element %d trouve a l'indice %d.\n", elementRecherche,
resultat);
} else {
printf("Element %d non trouve dans la liste.\n", elementRecherche);
}
return 0;
}

91
La recherche séquentielle est un algorithme de recherche simple qui permet de trouver un
élément dans une liste non triée. Le cas de l'égalité permet de réduire le nombre de
comparaisons dans certains cas.

6.2.2.2 RECHERCHE DICHOTOMIQUE

Lorsque nous cherchons un élément dans un tableau, si ce tableau est trié, il existe une
méthode plus rapide pour effectuer la recherche. En effet, dans un tableau trié, il n’est pas
nécessaire de comparer l’élément à toutes les valeurs du tableau, ce qui permet de gagner
beaucoup de temps.

Une méthode efficace de recherche dans un tableau trié est appelée recherche dichotomique
(ou binary search en anglais). Cette méthode permet de trouver rapidement l'emplacement
d’un élément dans un tableau trié.
Exemple : Jeu entre A et B

Imaginons un jeu entre deux personnes, A et B. A choisit un nombre entre 0 et 100, mais ne
le dit pas à B. B doit deviner ce nombre en posant des questions auxquelles A répondra par
"oui" ou "non".
Pour poser le moins de questions possible, quelle stratégie B doit-il adopter ? La meilleure
stratégie est d’utiliser la recherche dichotomique. Plutôt que de poser des questions aléatoires,
B peut commencer par diviser l’intervalle possible en deux à chaque fois, réduisant ainsi
rapidement le nombre de possibilités.

Cette image illustre un exemple de recherche dichotomique (ou recherche binaire) dans un
tableau trié, avec pour objectif de trouver la valeur 10. Le processus est détaillé étape par
étape :
▪ Initialisation : Les indices gauche et droite sont initialisés à 0 et 12 (bornes du
tableau). Le milieu est calculé comme étant milieu = (gauche + droite)/2, soit
6, et la valeur correspondante au milieu est comparée à 10.
▪ Division de la recherche : Comme 10 est inférieur à la valeur au milieu (13), l'intervalle
de recherche est réduit à la partie gauche du tableau, en réajustant l'indice droit à 5.
Le processus est répété avec un nouveau calcul du milieu.
▪ Raffinement : À chaque itération, les indices gauche et droit convergent en fonction
de la comparaison entre la valeur recherchée (10) et la valeur au milieu du sous-
tableau. Cela réduit progressivement la largeur de l'intervalle de recherche (puissances
décroissantes de 2).
▪ Fin de la recherche : Lorsque la largeur atteint 0, il est constaté que la valeur 10 n'est
pas présente dans le tableau.

92
L'image montre également la vérification mathématique de la largeur restante à chaque étape,
illustrée par 2^k - 1, ce qui met en évidence l'efficacité logarithmique de cette méthode.

ALGORITHME DE RECHERCHE DICHOTOMIQUE

❖ SPECIFICATIONS

Considérons un tableau trié T de n éléments et une valeur x. L’algorithme prend en entrée le

tableau T et la valeur x. Il doit renvoyer la position de la valeur x dans le tableau si elle y est
présente, et -1 si elle n'y est pas.
❖ Principe général

Puisque le tableau est trié, une comparaison de la valeur recherchée x avec l'élément situé au
milieu du tableau permet de savoir si x se trouve dans la première moitié ou dans la seconde
moitié du tableau. L’algorithme procède ainsi :
1. On compare x à la valeur située au milieu du tableau.
2. Si x correspond à cette valeur, l’algorithme retourne la position du milieu.
3. Si x est plus grand que la valeur du milieu, la recherche se poursuit dans la
seconde moitié du tableau.
4. Si x est plus petit, la recherche continue dans la première moitié.

93
Ce processus est répété jusqu'à ce que l'élément soit trouvé ou que le tableau soit
complètement exploré.
Algorithme RechercheDichotomique
// Déclaration des variables globales
variable liste : tableau d'entiers
variable taille, elementRecherche, resultat : entier
// Fonction de recherche dichotomique
fonction recherche_dichotomique(T : tableau d'entiers, n : entier, x :
entier) : entier
Début
variable deb, fn, milieu : entier
deb <- 0
fn <- n - 1
TantQue deb <= fn faire
milieu <- (deb + fn) / 2
si T[milieu] = x alors
retourner milieu
sinon
si x > T[milieu] alors
debut <- milieu + 1
sinon
fin <- milieu - 1
fin si
fin si
fin TantQue
retourner -1
Fin fonction

// Programme principal
Début
// Initialisation de la liste triée
liste <- [1, 2, 5, 8, 9, 12, 14, 15]
taille <- 8 // Nombre d'éléments dans la liste
elementRecherche <- 7
// Appel à la fonction de recherche dichotomique
resultat <- recherche_dichotomique(liste, taille, elementRecherche)
// Affichage du résultat
si resultat != -1 alors
afficher "Élément ", elementRecherche, " trouvé à l'indice ", resultat
sinon
afficher "Élément ", elementRecherche, " non trouvé dans la liste"
fin si
Fin

❖ Explication du fonctionnement
- Initialisation : On commence avec deux indices, début et fin, qui délimitent les bornes de la
partie du tableau à explorer.
- Boucle de recherche : Tant que début est inférieur ou égal à fin, on continue à diviser le
tableau en deux parties.

94
- Comparaison : À chaque itération, on compare l'élément x à l'élément situé au milieu du
tableau. Selon la comparaison, on ajuste les indices pour explorer la moitié pertinente.
- Retour du résultat : Si l’élément est trouvé, l’indice est retourné. Si l'élément n’est pas présent
après avoir examiné toutes les possibilités, on renvoie -1.
L’équivalent de ce pseudocode en C est donné par le code ci-dessous :
#include <stdio.h>
// Fonction de recherche dichotomique
int recherche_dichotomique(int T[], int n, int x) {
int deb = 0, fn = n - 1, milieu;

while (deb <= fn) {

milieu = (deb + fn) / 2;

if (T[milieu] == x) {
return milieu; // Élement trouvé
} else if (x > T[milieu]) {
deb = milieu + 1; // Recherche dans la partie droite
} else {
fn = milieu - 1; // Recherche dans la partie gauche
}
}
return -1; // Élement non trouvé
}

int main() {
// Initialisation de la liste triée
int liste[] = {1, 2, 5, 8, 9, 12, 14, 15};
int taille = 8; // Nombre d'éléments dans la liste
int elementRecherche = 7; // Élément à rechercher
int resultat;
// Appel à la fonction de recherche dichotomique
resultat = recherche_dichotomique(liste, taille, elementRecherche);
// Affichage du résultat
if (resultat != -1) {
printf("Élément %d trouvé à l'indice %d\n", elementRecherche,
resultat);
} else {
printf("Élément %d non trouvé dans la liste\n", elementRecherche);
}

return 0;
}
La recherche dichotomique est un algorithme très efficace pour trouver un élément dans un
tableau trié, car il divise systématiquement l’intervalle de recherche par deux à chaque étape,
ce qui permet de réduire considérablement le nombre de comparaisons nécessaires, surtout
pour les grands tableaux.

95
 6.3 EXERCICES DE FIN CHAPITRE
6.3.1 EXERCICES SUR LES TRIS
Exercice 2 : tri par insertion

Soit la figure ci-dessous :

1. Implémenter l’algorithme de tri par insertion vu en cours.

2. Le tester en écrivant la trace correspondante.

Exercice 2 : tri par sélection

1. Pour le même problème implémenter l’algorithme de tri par sélection vu en cours.

2. Le tester en écrivant la trace correspondante.

6.3.2 EXERCICES SUR LES ALGORITHMES DE RECHERCHE

Exercice 1 : Recherche séquentielle dans une liste d’enregistrement d’étudiants

Étant donné une liste non triée d’étudiants représentée par des objets de type `Etudiant`,
contenant les champs suivants :
- `nip` : Numéro d’Identification Personnel (entier),
- `nom` : Nom de famille (chaîne de caractères),
- `prenom` : Prénom (chaîne de caractères),
- `naissance` : Date de naissance (un objet de type `Date`, composé de trois champs : `jour`,
`mois`, et `annee`),

Écrire les fonctions de comparaison suivantes permettant d’identifier les étudiants

correspondant aux critères ci-dessous. Chaque fonction devra retourner un booléen :
- Né le 29 janvier 1965,
- Né en 1986,
- Ayant son anniversaire aujourd’hui,

96
 - Dont le prénom est "Francis",
- Dont le nom commence par "Ngan",
- Dont le prénom contient exactement un caractère "a".

Implémenter une recherche séquentielle dans cette liste d’étudiants en utilisant chacune de
ces fonctions de comparaison pour vérifier si au moins un étudiant répond aux critères.
Pour chaque critère, vous devez :
- Expliquer la logique de la fonction de comparaison utilisée,
- Indiquer si la recherche est fructueuse avec les données fournies,
- Préciser le nombre d’appels effectués à la fonction de comparaison lors de la recherche.
Liste d’enregistrement d’étudiants fournie :
etudiants = [
Etudiant(99998132, "Eto'o", "Samuel", Date(10, 3, 1981)),
Etudiant(99994451, "Chantal", "Biya", Date(4, 12, 1970)),
Etudiant(99996348, "Foppa", "Francis", Date(12, 8, 1965)),
Etudiant(99995433, "Nnanga", "Nicole", Date(25, 9, 1987)),
Etudiant(99997674, "Ngannou", "Francis", Date(5, 9, 1986)),
Etudiant(99998324, "Rogobert", "Song", Date(1, 7, 1976))
]

Remarques importantes :
- Le programme doit être modulaire : chaque critère doit être implémenté dans une fonction
distincte, et les fonctions doivent être réutilisées dans la recherche séquentielle.
- Vous pouvez supposer que la date actuelle est disponible via une fonction ou une variable
appropriée.

97
CHAPITRE 7 : APPLICATIONS PRATIQUES
7.1 IMPLEMENTATION D’ALGORITHME EN LANGAGE DE
PROGRMAMTION C

Programmer consiste à traduire un algorithme en un ensemble d'instructions qu'un ordinateur

peut exécuter. Un algorithme est une série de tâches clairement définies pour résoudre un
problème donné. Contrairement aux langages de programmation, il s'exprime dans un pseudo-
langage qui reste indépendant des contraintes techniques.

7.1.1 ÉTAPES POUR DEVELOPPER UN PROGRAMME

7.1.1.1 TRADUCTION DE L'ALGORITHME

L'algorithme, écrit à l'origine sur papier, doit être converti dans un langage de programmation.
Cette traduction suit des règles spécifiques pour chaque langage. Par exemple, en langage
C, cela donne un programme structuré et compréhensible par le compilateur.

7.1.1.2 CREATION D'UN FICHIER TEXTE

Une fois traduit, le programme doit être enregistré sous forme informatique. Pour cela, on
utilise un éditeur de texte pour transcrire le code depuis le papier en un fichier texte.

7.1.1.3 COMPILATION
La compilation est une étape cruciale où le programme écrit en langage évolué (comme le C)
est traduit en langage machine. Cette tâche est assurée par un compilateur, qui vérifie
également les erreurs de syntaxe et génère un fichier exécutable.

7.1.1.4 EXECUTION ET TESTS

Le programme exécutable est ensuite testé. L'utilisateur entre des valeurs (appelées jeux
d'essais) pour valider le bon fonctionnement du programme. Cette étape permet d'identifier et
de corriger les erreurs logiques ou techniques.

7.1.1.5 DOCUMENTATION
Un document final est produit, combinant l'algorithme initial et le code en langage de
programmation.

7.1.2 DIFFERENTS TYPES DE LANGAGES

7.1.2.1 LANGAGES EVOLUES (OU DE HAUT NIVEAU)

Ces langages, comme C, Java, ou Pascal, permettent de créer des programmes lisibles et
indépendants des spécifications matérielles du processeur. Exemple : Déclaration d’un simple
programma permettant d’afficher un message en langage C.

98
int main(void) {
printf("Bonjour, vous êtes dans le monde C...\n");
return 0;
}

7.1.2.2 LANGAGES DE BAS NIVEAU (ASSEMBLEUR)

Proches du matériel, ces langages permettent des optimisations pointues mais sont difficiles
à lire pour un humain. Exemple : Le code en assembleur ci-dessous ajoute 1 à la valeur de
AX, copie cette nouvelle valeur dans CX, puis soustrait la valeur de CX de BX.
add ax, 1
mov cx, ax
sub bx, cx

7.1.2.3 LANGAGE MACHINE

C’est le seul langage directement compréhensible par le processeur, composé de suites
binaires complexes et illisibles pour un programmeur.

7.1.3 PARTICULARITES DU LANGAGE C

Le langage C, développé en 1972 par Brian Kernighan et Dennis Ritchie, est extrêmement
polyvalent. Conçu initialement pour écrire le système UNIX, il s'est rapidement imposé dans
de nombreux domaines grâce à ses caractéristiques uniques :

▪ Langage structuré : Utilisation de blocs délimités par des accolades {} pour une
meilleure organisation du code.
▪ Efficacité : Comparable à l'assembleur en termes de rapidité et de contrôle.
▪ Modularité : Prise en charge des modules et bibliothèques pour réutiliser du code.
▪ Portabilité : Un programme écrit en ANSI C peut être exécuté sur différents
systèmes (Linux, Windows) sans modification majeure.
▪ Spectre large d'applications : Le C est utilisé pour tout, des pilotes matériels aux
logiciels de gestion, en passant par les jeux vidéo.

7.1.4 QUELQUES INCONVENIENTS

Les messages d'erreur du compilateur peuvent être déroutants, surtout pour les débutants.
Une syntaxe parfois minimaliste, notamment pour les opérations d'entrée-sortie.

7.2 TRADUIRE UN ALGORITHME EN LANGAGE C

Certaines adaptations sont nécessaires pour convertir un algorithme en C :
▪ Type booléen (bool) : En C, il n'existe pas directement. On utilise des entiers (int), où
0 représente FALSE et toute autre valeur représente TRUE.
▪ Entrées et sorties : L'instruction afficher devient printf.
L'instruction demander est traduite par un duo printf + scanf.

99
Exemple

En langage algorithmique :

afficher("Prix total TTC des ", nbDVD, " DVDs: ", pTTCTot);
demander("Montant TVA: ", mTVA);

En langage C :

printf("Prix total TTC des %d DVDs: %f\n", nbDVD, pTTCTot);

printf("Montant TVA: ");
scanf("%d", &mTVA);

7.3 ENTREES-SORTIES EN LANGAGE C : COMPRENDRE,

SIMPLIFIER ET APPLIQUER

En langage C, les entrées-sorties permettent à un programme d’interagir avec l’utilisateur via

le clavier (entrée) et l’écran (sortie). Nous allons simplifier et structurer les concepts pour les
rendre accessibles à tous, même débutants.

7.3.1 CORRESPONDANCE ALGORITHME - C

❖ EN ALGORITHMIQUE
Afficher un message : afficher("un message");
Demander une valeur : afficher("un message", nomDeVariable);

❖ EN LANGAGE C
Afficher un message : printf("un message");
Afficher un message avec des données : printf("Texte avec format", variable1,
variable2, ...);
Exemple : printf("Le prix est %f FCFA et la quantité %d", prix, quantite);
Demander une valeur à l’utilisateur : printf("Texte pour demander une valeur");
scanf("format", &variable);
Exemple : printf("Entrez une quantité :"); scanf("%d", &quantite);

7.3.2 COMPRENDRE LES FORMATS

Les formats indiquent le type de donnée utilisé dans les fonctions printf et scanf :
Type de Variable Format

100
Exemple
float prix = 19.99;
int quantite = 3;
printf("Prix unitaire : %f, Quantité : %d", prix, quantite);

POURQUOI UTILISER & DANS SCANF ?

Le & permet d’obtenir l’adresse mémoire d’une variable, où la valeur saisie sera stockée. Par
exemple : scanf("%d", &variable);

Sans le &, le programme ne saurait pas où stocker la valeur.

Étude de Cas : Calcul du Prix Total TTC

Description du Problème
Demander le prix hors taxes (prixHT) d’un DVD.
Demander la quantité (nbDVD) de DVDs achetés.
Calculer :
Prix total hors taxes (pHTTot) : pHTTot = nbDVD * prixHT.
Prix total TTC (pTTCTot) : pTTCTot = pHTTot + (pHTTot * TVA / 100).
Afficher le prix TTC total.

Structure Complète du Programme

#include <stdio.h>
int main(void) {
// Déclaration des variables
float prixHT; // Prix hors taxes d'un DVD (> 0)
int nbDVD; // Nombre de DVDs achetés (> 0)
float mTVA = 20.6; // Montant de la TVA en %
float pHTTot, pTTCTot; // Calculs : HT et TTC
// Entrées utilisateur
printf("\nEntrez le prix hors taxe d'un DVD : ");
scanf("%f", &prixHT);
printf("\nEntrez le nombre de DVDs achetés : ");
scanf("%d", &nbDVD);
// Calculs
pHTTot = nbDVD * prixHT;
pTTCTot = pHTTot + (pHTTot * mTVA / 100);
// Affichage du résultat
printf("\nLe prix total TTC pour %d DVDs est : %.2f euros\n", nbDVD,
pTTCTot);

return 0;
}

EXPLICATIONS COMPLEMENTAIRES

1. VARIABLES
Lorsque le compilateur traduit les variables il doit réserver la place en mémoire qui lui
correspond. L'image ci-dessous représente une simplification de la façon dont un ordinateur
stocke et exécute un programme. Les variables du programme (nbDVD, pHT, cat) et le code
du programme lui-même sont traduits en une suite de 0 et de 1, appelés bits. Ces bits sont

101
regroupés en octets (8 bits) et stockés en mémoire. La taille en octets de chaque variable
dépend de son type (entier, flottant, caractère). Le code du programme, quant à lui, occupe
une zone mémoire plus importante et contient les instructions à exécuter. L'image illustre
également la modification de la valeur de la variable nbDVD en mémoire pendant l'exécution
du programme.

Chaque variable occupe un certain espace mémoire :

Structure Générale d’un Programme C :

#include <stdio.h>
int main(void) {
// Déclaration des variables
type variable;
// Instructions
instruction1;
instruction2;
return 0; // Fin du programme principal
}

JEU D’ESSAIS (TESTS)

102
 7.3.3 PRECISIONS SUR L'INSTRUCTION PRINTF EN LANGAGE C
L'instruction printf est utilisée pour afficher des messages ou des valeurs à l'écran. Voici
comment l'utiliser efficacement :
1. Afficher uniquement un message
Exemple : printf("Nous sommes le 22 juillet 2004");
Cela affiche simplement : Nous sommes le 22 juillet 2004
2. Afficher un message suivi d'une expression
Exemple : printf("Prix TTC d'un DVD : %f", pHT * (1 + mTVA / 100));
Ici, %f est un format spécifiant que la valeur calculée sera un nombre réel (de type float).
Résultat à l’écran (par exemple si pHT = 15 et mTVA = 20.6) : Prix TTC d'un DVD :
18.09
3. Afficher un message et plusieurs expressions
Exemple : printf("Le prix TTC pour %d DVD(s) au prix unitaire HT %f est
de : %f", nbDVD, pHT, pTotTTC);

4. Les formats spécifiant

▪ %d pour afficher un entier (nombre de DVD),
▪ %f pour afficher un réel (prix hors taxe et total TTC).
Résultat possible (par exemple si nbDVD = 5, pHT = 20, et pTotTTC = 120.6) :
Le prix TTC pour 5 DVD(s) au prix unitaire HT 20.000000 est de :
120.600000
5. Utiliser des caractères spéciaux pour améliorer l'affichage
Vous pouvez enrichir vos affichages avec des caractères spéciaux :
▪ \n : saut de ligne.
▪ \t : tabulation horizontale.
▪ \v : tabulation verticale.
Exemple :
int A = 5, B = 4;
printf("La valeur de A est: %d\nLa valeur de B est: %d\n\v\tEt leur
somme est: %d", A, B, A + B);
Résultat :
La valeur de A est: 5
La valeur de B est: 4
(tabulation verticale suivie d’une tabulation horizontale)
Et leur somme est: 9
Remarques utiles :
1. Les opérateurs d'incrémentation et de décrémentation

103
 ++ : augmente la valeur d'une variable de 1.
-- : diminue la valeur d'une variable de 1.
Exemple :
int a = 10;
a++; // a devient 11
a--; // a revient à 10
2. Déclaration de plusieurs variables
Vous pouvez déclarer plusieurs variables du même type sur une seule ligne : float pHT,
pTTCTot, pHTTot, mTVA = 20.6;

Cependant, cela peut réduire la lisibilité. Il est souvent préférable de déclarer chaque variable
sur une ligne séparée.

7.3.4 CAPTURE DES SORTIES DU PROGRAMME DANS UN FICHIER

Pour sauvegarder tout ce qui s’affiche à l’écran dans un fichier, utilisez la commande suivante
dans le terminal : nomduprogramme | tee nomdufichier

Exemple : prixTTC | tee resultat.txt

Cela exécute le programme prixTTC et enregistre tout son affichage dans le fichier resultat.txt.

7.3.5 CONSEILS
1. Traduction d'un algorithme en programme
Un programme en C se traduit facilement depuis un algorithme, mais prenez le temps de
commenter vos programmes pour les rendre plus lisibles.
2. Les erreurs de compilation
Les messages d’erreurs : Souvent peu clairs, une erreur peut entraîner plusieurs messages
différents. Prenez le temps de les analyser.
▪ Liens manquants : Si une librairie est oubliée, ajoutez-la avec #include.
Pour la documentation à fournir :
▪ L'algorithme : Présentez-le dans le format enseigné en cours.
▪ Le programme : Fournissez un listing complet et bien commenté.
▪ Trace d'exécution : Montrez le résultat obtenu pour chaque cas d'essai.
Exemple d’essai :
Entrée :
pHT = 15, nbDVD = 5
Sortie attendue :
Prix TTC des 5 DVDs : 90.45

104
 7.3.1 STRUCTURE D’UN PROGRAMME
7.3.1.1 EN ALGORITHMIQUE
déclaration des types et fonctions
déclaration des variables
début
instructions
// commentaire
autres_instructions
fin

7.3.1.2 EN LANGAGE C

#include <stdio.h> // Inclure les librairies nécessaires

int main(void) {
// Déclaration des variables
type nom_variable;

// Instructions
instruction1;
// Commentaire
instruction2;

return 0; // Fin du programme principal

}
7.3.2 TYPES DE DONNEES ET LEURS ÉQUIVALENTS
Algorithmique Langage C Description
entier int Nombres entiers (positifs/négatifs)
réel double Nombres à virgule flottante
booléen bool Valeur logique : TRUE ou FALSE
caractère char Un seul caractère ('a', 'B')
chaîne string Suite de caractères (tableau de char)
7.3.2.1 NOTE
Pour utiliser les booléens, ajoutez ceci en début de programme :
typedef int bool;
#define FALSE 0
#define TRUE 1

7.3.3 OPERATIONS
Algorithmique Langage C Description
Affectation : ← = Affecte une valeur à une
variable
Arithmétiques : +, -, *, +, -, *, /, % Opérations mathématiques
/, div, mod
Logiques : non, et, ou !, &&, `
Comparaison : =, ≠, <, >, ==, !=, <, >, Comparateurs de valeurs
≤, ≥ <=, >=
7.3.4 ENTREES ET SORTIES
Algorithmique Langage C
lire a scanf("%format", &a);
écrire a printf("%format", a);

105
 écrire "texte", a printf("texte %format", a);
7.3.4.1 CORRESPONDANCE DES FORMATS :
Type Format (C)
entier (int) %d
réel (double) %lf
chaîne (string) %s
caractère (char) %c
Exemple :
#include <stdio.h>
int main(void) {
int age;
printf("Entrez votre âge : ");
scanf("%d", &age);
printf("Votre âge est : %d ans\n", age);
return 0;
}

7.3.5 CONDITIONNELLES

7.3.5.1 Si…Sinon ou if else

Algorithmique Langage C
si (condition) alors if (condition) { instructions; }
sinon else { instructions; }
finsi Fin de la structure (pas nécessaire)
Exemple :

if (age >= 18) {

printf("Vous êtes majeur.\n");
} else {
printf("Vous êtes mineur.\n");
}
7.3.5.2 Structure Selon ou Switch en C
Le "selon" en algorithme ou « swithc » en C est utilisé pour choisir entre plusieurs branches d'exécution
en fonction de la valeur d'une variable. Voici la syntaxe générale :
Syntaxe algorithme :
selon (variable) faire
cas valeur1 :
instructions1
cas valeur2 :
instructions2
...
cas valeurN :
instructionsN
autre :
instructionsParDefaut
fin selon
Exemple: Un algorithme qui affiche le jour de la semaine en fonction d’un numéro entré (1 = Lundi, 7 =
Dimanche).
Début
Écrire "Entrez un numéro (1-7) :"
Lire jour

106
 selon (jour) faire
cas 1 :
Écrire "Lundi"
cas 2 :
Écrire "Mardi"
cas 3 :
Écrire "Mercredi"
cas 4 :
Écrire "Jeudi"
cas 5 :
Écrire "Vendredi"
cas 6 :
Écrire "Samedi"
cas 7 :
Écrire "Dimanche"
autre :
Écrire "Numéro invalide"
fin selon
Fin
Syntaxe du "switch" en C
Le switch en C est similaire au "selon" en algorithmique. Il évalue une expression et exécute les
instructions du cas correspondant.
switch (variable) {
case valeur1:
// Instructions pour valeur1
break;
case valeur2:
// Instructions pour valeur2
break;
...
case valeurN:
// Instructions pour valeurN
break;
default:
// Instructions par défaut si aucune valeur ne correspond
break;
}

Important :Le mot-clé break termine l'exécution du switch après un cas. Sans lui, le programme continue
dans les cas suivants (effet "fall-through").La clause default est facultative mais recommandée.

Exemple: Afficher un message en fonction d'un numéro correspondant à un jour de la semaine (1 =

Lundi, 7 = Dimanche).
#include <stdio.h>

int main() {
int jour;

// Demander un numéro de jour

printf("Entrez un numéro de jour (1-7) : ");
scanf("%d", &jour);

// Utiliser switch pour afficher le jour correspondant

switch (jour) {
case 1:
printf("Lundi\n");

107
 break;
case 2:
printf("Mardi\n");
break;
case 3:
printf("Mercredi\n");
break;
case 4:
printf("Jeudi\n");
break;
case 5:
printf("Vendredi\n");
break;
case 6:
printf("Samedi\n");
break;
case 7:
printf("Dimanche\n");
break;
default:
printf("Numéro invalide\n");
break;
}

return 0;
}
Comparaison des deux syntaxes

7.3.6 BOUCLES
7.3.6.1 BOUCLE POUR (FOR)
Algorithmique Langage C
pour (i allant de 1 à 10 pas 1) for (i = 1; i <= 10; i++) { ...
faire }
pour (i allant de 10 à 1 pas -1) for (i = 10; i >= 1; i--) { ...
faire }
Exemple :
for (int i = 1; i <= 10; i++) {
printf("Valeur de i : %d\n", i);
}
7.3.6.2 BOUCLE TANT QUE (WHILE)
Algorithmique Langage C
tantque (condition) faire while (condition) { ... }
fintantque Fin de la boucle (pas nécessaire)

108
Exemple :

int i = 1;
while (i <= 10) {
printf("Valeur de i : %d\n", i);
i++;
}

7.3.7 TABLEAUX
Algorithmique Langage C
Tableau à une dimension type tableau[n];
Tableau à deux dimensions type tableau[n][m];
Accéder à une case tableau[i] ou tableau[i][j]
Exemple :
#include <stdio.h>
int main(void) {
int tableau[5] = {1, 2, 3, 4, 5};
printf("Valeur à l'indice 2 : %d\n", tableau[2]);
return 0;
}
7.3.8 FONCTIONS
Algorithmique Langage C
fonction avec retour type nom(paramètres) { return valeur; }
fonction sans retour void nom(paramètres) { ... }
Exemple :
Fonction pour calculer le carré d’un nombre :
#include <stdio.h>
int carre(int x) {
return x * x;
}
int main(void) {
int n = 4;
printf("Le carré de %d est %d\n", n, carre(n));
return 0;
}
Le langage C, malgré son âge, reste un outil puissant et incontournable en programmation
grâce à sa flexibilité, sa portabilité et ses performances. Cependant, sa permissivité peut être
déroutante pour les débutants. Avec une méthode structurée et des exercices progressifs, il
devient possible de maîtriser cet outil pour concevoir des programmes robustes et efficaces.
Pour faciliter la compréhension et la mise en œuvre de programmes en langage C, voici une
version simplifiée et mieux structurée basée sur le document fourni. Chaque concept est
accompagné d'exemples concrets et de tableaux explicatifs pour plus de clarté.

7.4 EXERCICE DE FIN DE CHAPITRE

Exercice 1
Écrire un algorithme et son équivalent en langage C qui demande l'âge d'un enfant (entre 6 et
20 ans) et informe de sa catégorie sportive selon les règles suivantes :

109
"Poussin" : de 6 à 7 ans
"Pupille" : de 8 à 9 ans
"Minime" : de 10 à 11 ans
"Cadet" : de 12 à 15 ans
"Junior" : de 16 à 20 ans
Si l'âge est inférieur à 6 ou supérieur à 20, le programme doit afficher un message d'erreur :
"Âge hors catégorie".

Exercice 2 : Analyse et Résolution Simplifiée

On dispose d’un tableau TAB contenant au maximum 100 entiers (N <= 100). L'objectif est
de :
1. Remplir le tableau avec des valeurs fournies par l’utilisateur.
2. Vérifier si le tableau est trié en ordre croissant et afficher le résultat.
Si le tableau est trié :
3. Trouver et afficher le plus grand nombre pair (s’il existe).
4. Calculer et afficher la moyenne des nombres positifs (s’ils existent).
Remarques Importantes :
Si aucun nombre pair n’existe, afficher : "Aucun nombre pair existe dans le tableau TAB".
Si aucun nombre positif n’existe, afficher : "Aucun nombre positif existe dans le tableau
TAB".
Ecrire l’algorithme correspondant à ce problème et le traduire en langage C une fois réalisé.

110