Cours d’Algorithmique

1
Objectif:
 Apprendre les concepts de base de l'algorithmique et de la
programmation
 Être capable de mettre en œuvre ces concepts pour
analyser des problèmes simples et écrire les algorithmes
correspondants

[Link] 2
 Plan du cours

 Introduction à l’algorithmique
 Notion de variable, affectation, lecture et
écriture
 Expressions et opérateurs
 Instructions conditionnels et instructions
itératives
 Les tableaux

[Link] 3
 Algorithmique (1)

 Le terme algorithme vient du nom du mathématicien arabe Al-

Khawarizmi (820 après J.C.)
 Définition(1) : Un algorithme est une description complète et
détaillée des actions à effectuer et de leur séquencement pour
arriver à un résultat donné.
 Définition(2) : Un algorithme est une suite d’actions précises et
finies qui doivent être exécutées sur un ensemble de données dans
un ordre bien déterminé en vue de la résolution d’un problème.

 Intérêt: séparation analyse/codage (pas de préoccupation de syntaxe)

 Qualités: exact (fournit le résultat souhaité), efficace (temps
d’exécution, mémoire occupée), clair (compréhensible), général (traite
le plus grand nombre de cas possibles), …

[Link] 4
 Algorithmique (2)

 Algorithme = méthode de résolution

 L’algorithmique désigne aussi la discipline qui
étudie les algorithmes et leurs applications en
Informatique
 Une bonne connaissance de l’algorithmique
permet d’écrire des algorithmes exacts et
efficaces

[Link] 5
 Algorithmique (3)

 La résolution d’un problème est caractérisé par 4

étapes :

 Comprendre la nature du problème posé

 Préciser les données fournies (Entrées)
 Préciser les résultats que l’on désire obtenir (Sorties)
 Déterminer le processus de transformation des
données en résultats.

[Link] 6
 Exemple(1)
 Un algorithme peut se comparer à une recette
de cuisine
 Le résultat c’est comme le plat à cuisiner
 Les données sont l’analogues des ingrédients de
la recette
 Les règles de transformations se comparent aux
directives ou instructions de la recette

[Link] 7
 Exemple(2)
 Robot domestique avec un algorithme de
préparation d’une tasse de café soluble

1. Faire bouillir l’eau

2. Mettre le café
3. Ajouter l’eau dans la tasse

[Link] 8
 Exemple(3)
 "Faites prendre la moitié du nombre pair
pensé, puis ajouter 1 et multiplier le résultat
par 6; demandez le quotient par 3 du résultat
obtenu. Ce quotient diminué de 2 est le
nombre pensé."

[Link] 9
 Objectifs d’un algorithme
 Un algorithme sert à transmettre un savoir faire.
 Il décrit les étapes à suivre pour réaliser un
travail.
 Il permet d'expliciter clairement les idées de
solution d’un problème indépendamment d'un
langage de programmation.
 L'utilisateur d'un algorithme n'aura qu'à suivre
les instructions, dans l'ordre pour arriver au
résultat que doit donner l'algorithme.

[Link] 10
 Propriétés d’un algorithme
 Un algorithme doit:
 avoir un nombre fini d’étapes,
 avoir un nombre fini d’opérations par étape,
 se terminer après un nombre fini d’opérations,
 fournir un résultat.

 les séquences (étapes) se succèdent dans un certain ordre

 Chaque opération doit être définie rigoureusement et
sans ambiguïté
 Un algorithme est caractérisé par un début et une fin
 Le comportement d'un algorithme est déterministe.

[Link] 11
 Algorithme et programme
 L’élaboration d’un algorithme précède l’étape de programmation
 Un programme est un algorithme
 Un langage de programmation est un langage compris par l'ordinateur
 Comment exécuter un algorithme sur ordinateur?
 Il faut traduire cet algorithme à l’aide d’un langage de
programmation connu par l’ordinateur.

 L’élaboration d’un algorithme est une démarche de résolution de

problème exigeante
 La rédaction d’un algorithme est un exercice de réflexion qui se fait
sur papier
 L'algorithme est indépendant du langage de programmation
 Par exemple, on utilisera le même algorithme pour une implantation
en Java, ou bien en C++ ou en Visual Basic
 L’algorithme est la résolution brute d’un problème informatique

[Link] 12
 Représentation d’un algorithme
Historiquement, deux façons pour représenter un
algorithme:
 L’Organigramme: représentation graphique avec des
symboles (carrés, losanges, etc.)
 Offre une vue d’ensemble de l’algorithme
 Représentation quasiment abandonnée aujourd’hui.

 Le Pseudo-code: représentation textuelle avec une

série de conventions ressemblant à un langage de
programmation (sans les problèmes de syntaxe)
 Plus pratique pour écrire un algorithme
 Représentation largement utilisée

[Link] 13
 I. Algorithmique : Notions de base

14
[Link]
 Notion de variable (1)

 Dans les langages de programmation une variable sert à

stocker la valeur d’une donnée

 Une variable désigne en fait un emplacement mémoire dont

le contenu peut changer au cours d’un programme (d’où le
nom variable)

 Règle : Les variables doivent être déclarées avant d’être

utilisées, elle doivent être caractérisées par :
 un nom (Identificateur)
 un type (entier, réel, caractère, chaîne de caractères, …)
 Une valeur

[Link] 15
 Choix des identificateurs (1)

Le choix des noms de variables est soumis à quelques règles qui

varient selon le langage, mais en général:
 Un nom doit commencer par une lettre alphabétique
exemple valide: A1 exemple invalide: 1A

 Doit être constitué uniquement de lettres, de chiffres et du

soulignement _ (Eviter les caractères de ponctuation et les espaces)
valides: Info2011, Info_2011 invalides: Info 2011,Info-2011,Info;2011

 Doit être différent des mots réservés du langage (par exemple en Java:
int, float, else, switch, case, default, for, main, return, …)

 La longueur du nom doit être inférieure à la taille maximale spécifiée

par le langage utilisé.

[Link] 16
 Choix des identificateurs (2)

Conseil: pour la lisibilité du code choisir des noms significatifs qui

décrivent les données manipulées
exemples: TotalVentes2004, Prix_TTC, Prix_HT

Remarque: en pseudo-code algorithmique, on va respecter

les règles citées, même si on est libre dans la syntaxe

[Link] 17
 Types des variables (1)

Le type d’une variable détermine l’ensemble des valeurs qu’elle peut prendre,
les types offerts par la plus part des langages sont :
 Type numérique : entier

 Byte (codé sur 1 octet): de 0 à 255

 Entier court (codé sur 2 octets) : -32 768 à 32 767
 Entier long (codé sur 4 ou 8 octets)

 Type numérique : réel

 Réel simple précision (codé sur 4 octets)

 Réel double précision (codé sur 8 octets)

[Link] 18
 Types des variables (2)

 Type logique ou booléen: deux valeurs VRAI ou FAUX

 Type caractère: lettres majuscules, minuscules, chiffres, symboles, …

exemples: ’A’, ’a’, ’1’, ’?’, …

 Type chaîne de caractère: toute suite de caractères,

exemples: " Nom, Prénom", "code postale: 1000", …

[Link] 19
 Valeur des variables

 Une valeur

 La valeur d'une variable(contenu) peut varier au

cours du programme. L'ancienne valeur est tout
simplement écrasée et remplacée par la nouvelle.

[Link] 20
 Déclaration des variables

 Rappel : toute variable utilisée dans un programme doit

avoir fait l’objet d’une déclaration préalable,
 En pseudo-code, la déclaration de variables est
effectuée par la forme suivante :
Variables liste d'identificateurs : type
 Exemple:
Variables
i, j, k : entier
x, y : réel
OK : booléen
Ch1, ch2 : chaîne de caractères
[Link] 21
 Constante

 Une constante est une variable dont la valeur ne change

pas au cours de l'exécution du programme, elle peut être
un nombre, un caractère, ou une chaine de caractères.
 En pseudo-code, Constante identificateur=valeur : type,…
(par convention, les noms de constantes sont en majuscules)
 Exemple : pour calculer la surface des cercles, la valeur de
pi est une constante mais le rayon est une variable.
Constante PI=3.14 : réel, MAXI=32 : entier
 Une constante doit toujours recevoir une valeur dès sa
déclaration.

[Link] 22
 L’instruction d’affectation

 l’affectation consiste à attribuer une valeur à une variable (ça consiste en

fait à remplir où à modifier le contenu d'une zone mémoire)

 En pseudo-code, l'affectation se note avec le signe ←

Var← e: attribue la valeur de e à la variable Var
 e peut être une valeur, une autre variable ou une expression
 Var et e doivent être de même type
 L’affectation ne modifie que ce qui est à gauche de la flèche

 Ex valides: i ←1 j ←i k ←i+j
x ←10.3 OK ←FAUX ch1 ←"SMI"
ch2 ←ch1 x ←4 x ←j
(voir la déclaration des variables dans le transparent précédent)
 Non valides: i ←10.3 OK ←"SMI" j ←x

[Link] 23
 Quelques remarques

 Beaucoup de langages de programmation (C/C++, Java, …) utilisent le signe

égal = pour l’affectation
 Attention aux confusions:
 l'affectation n'est pas commutative : A=B est différente de B=A
 l'affectation est différente d'une équation mathématique :

• A=A+1 a un sens en langages de programmation

• A+1=2 n'est pas possible en langages de programmation et n'est pas
équivalente à A=1

 Certains langages donnent des valeurs par défaut aux variables déclarées.
Pour éviter tout problème il est préférable d'initialiser les variables
déclarées

[Link] 24
 Syntaxe générale de l’algorithme (1)
 Le moule d’un algorithme
Un algorithme comportera :
• Une partie déclaration
• Une partie encadrée par ’’Début’’ ’’ Fin’’ où sont décrites les actions

Algorithme Nom_de_l_algorithme
Déclaration
Début
Actions
Fin
[Link] 25
 Syntaxe générale de l’algorithme(2)
Algorithme exemple
Constantes
Const1=20 : entier
const2="bonjour!" : chaîne de caractères
Variables
var1 : entier
var3, var4 : réel
var5 : chaîne de caractères
Début
/* instructions */
Fin

[Link] 26
 Exercices simples sur l'affectation (1)

Donnez les valeurs des variables A, B et C après exécution des

instructions suivantes ?

Variables A, B, C: entier
Début
A ← -3
B←7
A←B
B ← A-5
C←A+B
C←B–A
Fin

[Link] 27
 Exercices simples sur l'affectation (2)

Donnez les valeurs des variables A et B après exécution des instructions

suivantes ?

Variables A, B : entier
Début
A←4
B←9
A←B
B←A
Fin

Les deux dernières instructions permettent-elles d’échanger les valeurs

de A et B ?

[Link] 28
 Exercices simples sur l'affectation (3)

Ecrire un algorithme permettant d’échanger les valeurs de

deux variables A et B

[Link] 29
 Expressions et opérateurs

 Une expression peut être une valeur, une variable ou une opération
constituée de variables reliées par des opérateurs exemples: 1, b, a*2, a+
3*b-c, …
 L'évaluation de l'expression fournit une valeur unique qui est le résultat de
l'opération
 Les opérateurs dépendent du type de l'opération, ils peuvent être :
 des opérateurs arithmétiques: +, -, *, /, % (modulo), ^ (puissance)
 des opérateurs logiques: NON, OU, ET
 des opérateurs relationnels: =, 
, <, >, <=, >=
 des opérateurs sur les chaînes: & (concaténation)

 Une expression est évaluée de gauche à droite mais en tenant compte de

priorités

[Link] 30
 Priorité des opérateurs

 Pour les opérateurs arithmétiques donnés ci-dessus, l'ordre de priorité est

le suivant (du plus prioritaire au moins prioritaire) :

^ : (élévation à la puissance)
* , / (multiplication, division)
% (modulo)
+ , - (addition, soustraction)
exemple : 2+3*7 vaut 23

 En cas de besoin (ou de doute), on utilise les parenthèses pour indiquer

les opérations à effectuer en priorité
exemple : (2 + 3) * 7 vaut 35

[Link] 31
 Les instructions d'entrées-sorties:
lecture et écriture (1)
 Considérons l’algorithme suivant :
Variable A : entier
Début
A ← 12 *12
Fin

[Link] 32
 Les instructions d'entrées-sorties:
lecture et écriture (1)
 Considérons le programme suivant:
Variable A : entier
Début
A ← 12 *12
Fin
Permet de calculer le carré de 12.
 Comment faire pour calculer le carré d’un autre nombre que
12 ?, il faut réécrire le programme.
 La machine calcule le résultats, mais l’utilisateur qui fait
exécuter ce programme ne saura pas que le résultats
correspond au carré de 12.
[Link] 33
Les instructions d'entrées-sorties: lecture
et écriture (2)

 Les instructions de lecture et d'écriture permettent à la machine de

communiquer avec l'utilisateur

 La lecture permet d'entrer des donnés à partir du clavier

 En pseudo-code, on note: lire (var)

la machine met la valeur entrée au clavier
dans la zone mémoire nommée var

 Remarque: Le programme s'arrête lorsqu'il rencontre une instruction

Lire et ne se poursuit qu'après la frappe d’une valeur au clavier et de la
touche Entrée

[Link] 34
Les instructions d'entrées-sorties: lecture
et écriture (3)

 L'écriture permet d'afficher des résultats à l'écran (ou de les écrire dans un
fichier)

 En pseudo-code, on note: écrire (var)

la machine affiche le contenu de la
zone mémoire var

 Conseil: Avant de lire une variable, il est fortement conseillé d’écrire

des messages à l’écran, afin de prévenir l’utilisateur de ce qu’il doit
frapper

[Link] 35
 Exemple 1 (lecture et écriture)

 Ecrire un algorithme qui demande un nombre entier à l'utilisateur, puis

qui calcule et affiche le double de ce nombre

Algorithme Calcul_double
variables A, B : entier
Début
Ecrire("entrer le nombre ")
Lire(A)
B ← 2*A
Ecrire("le double de ", A, "est :", B)
Fin

[Link] 36
 Exemple 2 (lecture et écriture)

 Exercice
Ecrire un algorithme qui demande deux
nombres entiers à l’utilisateur, puis qui calcule et
affiche la somme de ces nombres.

[Link] 37
Exemple 3 (lecture et écriture)
 Solution
Algorithme Calcul_Somme
variables A, B, SOMME : entier
Début
" Ecrire "Entrez le premier nombre
(Lire(A
" Ecrire "Entrez le deuxième nombre
(Lire(B
SOMME ← A + B
Ecrire ("La somme de ces deux nombres est : ")
(Ecrire (SOMME
Fin [Link] 38
 Exemple 3 (lecture et écriture)

 Écrire l’algorithme permettant le calcul de la surface d’un

cercle connaissant son rayon : Surface =  * Rayon2
Algorithme Surface _cercle
Constante
Pi=3.14 : réel
variables
Rayon : entier
Surface : réel
Début
Ecrire (" Saisir la valeur du rayon ")
Lire(Rayon)
Surface  Rayon * Rayon * Pi
Ecrire (" La surface du cercle est : ", Surface)
Fin
[Link] 39
 Tests: instructions conditionnelles (1)

 Les instructions conditionnelles servent à n'exécuter une instruction ou

une séquence d'instructions que si une condition est vérifiée
 On utilisera la forme suivante:
Si condition alors
instruction ou suite d'instructions1
Sinon
instruction ou suite d'instructions2
Finsi
 La condition ne peut être que vraie ou fausse
 Si la condition est vraie, se sont les instructions1 qui seront exécutées
 Si la condition est fausse, se sont les instructions2 qui seront exécutées
 La condition peut être une condition simple ou une condition composée de
plusieurs conditions

[Link] 40
Tests: instructions conditionnelles(2)

[Link] 41
 Exemple

Titre : Test
Variable X : entier
Début
Écrire (" Saisir un entier X ")
Lire (X)
Si (x > 0) alors
Écrire (" X est un nombre positif ")
Sinon
Écrire (" X est un nombre négatif ou nul ")
Finsi
Fin

[Link] 42
 Exercice

Ecrire un algorithme qui permet de lire et

d'afficher la valeur absolue d'un réel.

[Link] 43
 Solution

Algorithme Affichage_Valeur_Absolue (version1)

Variable x : réel
Début
Ecrire (" Entrez un réel : ")
Lire (x)
Si (x < 0) alors
Ecrire ("La valeur absolue de ", x, "est :",-x)
Sinon
Ecrire ("La valeur absolue de ", x, "est :",x)
Finsi
Fin

[Link] 44
 Tests: instructions conditionnelles (2)

 La partie Sinon n'est pas obligatoire, quand elle n'existe pas et que la
condition est fausse, aucun traitement n'est réalisé

 On utilisera dans ce cas la forme simplifiée suivante:

Si condition alors
instruction ou suite d'instructions
Finsi

[Link] 45
 Exemple

Algorithme Affichage_Valeur_Absolue (version2)

Variable x,y : réel
Début
Ecrire (" Entrez un réel : ")
Lire (x)
y← x
Si (x < 0) alors
y ← -x
Finsi
Ecrire ("La valeur absolue de ", x, "est :",y)
Fin

[Link] 46
 Exercice (tests)

Ecrire un algorithme qui demande un nombre entier à l'utilisateur, puis

teste et affiche s'il est divisible par 3.

[Link] 47
 Exercice (tests)

Algorithme Divsible_par3
Variable n : entier
Début
Ecrire " Entrez un entier : "
Lire (n)
Si (n%3=0) alors
Ecrire (n," est divisible par 3")
Sinon
Ecrire (n," n'est pas divisible par 3")
Finsi
Fin

[Link] 48
 Conditions composées

 Une condition composée est une condition formée de plusieurs conditions

simples reliées par des opérateurs logiques:
ET, OU, OU exclusif (XOR) et NON

 Exemples :
 x compris entre 2 et 6 : (x > 2) ET (x < 6)

 n divisible par 3 ou par 2 : (n%3=0) OU (n%2=0)

 L'évaluation d'une condition composée se fait selon des règles présentées

généralement dans ce qu'on appelle tables de vérité

[Link] 49
 Tables de vérité
C1 C2 C1 ET C2 C1 C2 C1 OU C2

VRAI VRAI VRAI VRAI VRAI VRAI

VRAI FAUX VRAI
VRAI FAUX FAUX
FAUX VRAI VRAI
FAUX VRAI FAUX
FAUX FAUX FAUX
FAUX FAUX FAUX

C1 C2 C1 XOR C2 C1 NON C1

VRAI VRAI FAUX VRAI FAUX

VRAI FAUX VRAI
FAUX VRAI
FAUX VRAI VRAI
FAUX FAUX FAUX [Link] 50
 Exemple

Expression Résultat
(4 <7) ET (9>0) Vrai
(1 < 0) OU (1<>1) Faux
Non(13.4 < 15) Faux

[Link] 51
 Tests imbriqués

 Les tests peuvent avoir un degré quelconque d'imbrications

Si condition1 alors
Si condition2 alors
instructionsA
Sinon
instructionsB
Finsi
Sinon
Si condition3 alors
instructionsC
Finsi
Finsi

[Link] 52
 Tests imbriqués: exemple (version 1)

Variable n : entier
Début
Ecrire ("entrez un nombre : ")
Lire (n)
Si (n < 0) alors
Ecrire ("Ce nombre est négatif")
Sinon
Si (n = 0) alors
Ecrire ("Ce nombre est nul")
Sinon
Ecrire ("Ce nombre est positif")
Finsi
Finsi
Fin

[Link] 53
 Tests imbriqués: exemple (version 2)

Variable n : entier
Début
Ecrire ("entrez un nombre : ")
Lire (n)
Si (n < 0) alors Ecrire ("Ce nombre est négatif")
Finsi
Si (n = 0) alors Ecrire ("Ce nombre est nul")
Finsi
Si (n > 0) alors Ecrire ("Ce nombre est positif")
Finsi
Fin

[Link] 54
 Tests imbriqués: exemple (version 2)

Variable n : entier
Début
Ecrire ("entrez un nombre : ")
Lire (n)
Si (n < 0) alors Ecrire ("Ce nombre est négatif")
Finsi
Si (n = 0) alors Ecrire ("Ce nombre est nul")
Finsi
Si (n > 0) alors Ecrire ("Ce nombre est positif")
Finsi
Fin
Remarque : dans la version 2 on fait trois tests systématiquement alors que dans la
version 1, si le nombre est négatif on ne fait qu'un seul test

Conseil : utiliser les tests imbriqués pour limiter le nombre de tests et placer d'abord
les conditions les plus probables
55
[Link]
 Exercice 1
Ecrivez un algorithme qui demande à
l’utilisateur d’entrer la température de l’eau, et
affiche ensuite l’état de l’eau selon la
température (on rappelle que l’état de l’eau est
glace pour une température inférieure ou égale
à 0, est vapeur pour une température
supérieure ou égale à 100 et liquide pour une
température comprise strictement entre 0 et
100).
[Link] 56
 Solution
Variable Temp : réel
Début
Ecrire (" Entrez la température de l’eau : ")
Lire (Temp)
Si (Temp <= 0 ) alors
Ecrire ("C’est de la glace ")
Sinon
Si (Temp < 100) alors
Ecrire ("C’est du liquide ")
Sinon
Ecrire ("C’est de la vapeur ")
Finsi
Finsi
Fin
[Link] 57
 Exercice 2
Ecrire un algorithme qui lit trois entiers A, B et C,
et affiche le plus grand.

[Link] 58
 Solution
Algorithme Plus_grand_nombre
Variables A, B, C : entiers
Début
Ecrire ("Donner A, B et C ") ;
Lire (A, B, C) ;
Si (A > B) alors
Si (A > C) alors
Ecrire ("Le plus grand nombre est : ", A)
Sinon
Ecrire ("Le plus grand nombre est : ", C)
FinSi
Sinon
Si (B > C) alors
Ecrire ("Le plus grand nombre est : ", B)
Sinon
Ecrire ("Le plus grand nombre est : ", C)
FinSi
FinSi
Fin [Link] 59
Tests imbriqués : Autre Forme
La structure alternative peut prendre une autre forme qui permet
d’imbriquer plusieurs conditions.
Selon Expression
Valeur1: action1
Valeur2: action2
• .........
ValeurN: actionN
Sinon : action
FinSelon
Si expression est égale à valeuri, on exécute actioni et on passe à
la suite de l’algorithme. Sinon on exécute action et on passe à la
suite de l’algorithme.
On l’appelle «structure choix»
60
[Link]
 Exemple
Variable X : entier
Début
X←1
Selon X
0:X←1
1 : X ← 11
2 : X ← 111
Sinon : écrire (" X n’est pas un entier compris entre 0 et 2")
FinSelon
Fin

[Link] 61
 Exercice
Ecrire un algorithme qui affiche selon un
numéro compris entre 1 et 12 le mois équivalent

[Link] 62
 Exercice
Algorithme Mois
Variable mois : entier
Début
Ecrire ("Entrez le numéro du mois : ")
Lire (mois)
Selon mois
1 : écrire ("C'est Janvier")
2 : écrire ("C'est Février")
3 : écrire ("C'est Mars")
4 : écrire ("C'est Avril")
5 : écrire ("C'est Mai")
6 : écrire ("C'est Juin")
7 : écrire ("C'est Juillet")
8 : écrire ("C'est Août")
9 : écrire ("C'est Septembre")
10 : écrire ("C'est Octobre")
11 : écrire ("C'est Novembre")
12 : écrire ("C'est Décembre")
Sinon : écrire ("Erreur, Tapez un numéro entre 1 et 12")
FinSelon
 Fin [Link] 63
 Instructions itératives (les boucles)

 Les boucles servent à répéter l'exécution d'un groupe d'instructions un

certain nombre de fois.

 On distingue trois sortes de boucles en langages de programmation :

 Les boucles tant que : on y répète des instructions tant qu'une certaine
condition est réalisée.

 Les boucles répéter …. jusqu'à : on y répète des instructions jusqu'à ce qu'une

certaine condition soit réalisée.

 Les boucles pour ou avec compteur : on y répète des instructions en faisant

évoluer un compteur (variable particulière) entre une valeur initiale et une
valeur finale.

[Link] 64
 Les boucles Tant que

TantQue (condition)
instructions condition Vrai Instructions

FinTantQue Faux

 La condition (dite condition de contrôle de la boucle) est évaluée avant chaque

itération.

 Si la condition est vraie, on exécute instructions (corps de la boucle), puis, on

retourne tester la condition. Si elle est encore vraie, on répète l'exécution, …

 Si la condition est fausse, on sort de la boucle et on exécute l'instruction qui est

après FinTantQue.

[Link] 65
 Les boucles Tant que : remarques

 Le nombre d'itérations dans une boucle TantQue n'est pas connu au

moment d'entrée dans la boucle. Il dépend de l'évolution de la valeur de
condition.

 Une des instructions du corps de la boucle doit absolument changer la

valeur de condition de vrai à faux (après un certain nombre d'itérations),
sinon le programme tourne indéfiniment

Attention aux boucles infinies

 Exemple de boucle infinie :
i←2
TantQue (i > 0)
i ← i+1 (attention aux erreurs de frappe : + au lieu de -)
FinTantQue
[Link] 66
 Boucle Tant que : exemple1

Variable i : entier
Début
i 0
TantQue (i < 3)
Ecrire ("Bonjour tout le monde ")
i  i+1
FinTanTque
Fin

[Link] 67
 Boucle Tant que : exemple 2

Variable A : entier
Début
A  10
TantQue (A > 0)
A  A-2
FinTantQue
Ecrire (" La valeur de A est : ", A)
Fin

[Link] 68
 Les boucles Répéter … jusqu’à …

Répéter Instructions
instructions

Jusqu'à (condition) Faux

condition

Vrai

 Condition est évaluée après chaque itération

 Les instructions entre Répéter et jusqu’à sont exécutées au moins une fois et
leur exécution est répétée jusqu’à ce que condition soit vrai (tant qu'elle est
fausse)

[Link] 69
 Boucle Répéter jusqu’à : exemple(1)

Variables c : entier
Début
Répéter
Lire( c)
c←c*c
Ecrire(c)
Jusqu' à (c= 0)
Ecrire ("Fin")
Fin

[Link] 70
 Boucle Répéter jusqu’à : exemple(2)

Variables a , somme , moyenne , compteur : entier

Début
compteur ← 0
somme ← 0
Répéter
Ecrire (" Entrez un nombre : " )
Lire (a)
compteur ← compteur + 1
somme ← somme + a
Jusqu' à (a = 0)
Moyenne ← somme / compteur
Ecrire (" La moyenne de valeurs saisies est : " , moyenne)
Fin
[Link] 71
 La boucle pour
Pour compteur = initiale à finale pas valeur du pas
instructions
FinPour

i  initiale

Vrai
i n'a pas atteint finale Instructions i  i + pas

Faux

[Link] 72
 Les Boucles pour

 Remarque : le nombre d'itérations dans une boucle Pour est connu avant
le début de la boucle.

 La variable compteur est en général de type entier. Elle doit être déclarée.

 Pas est un entier qui peut être positif ou négatif. Pas peut ne pas être
mentionné, car par défaut sa valeur est égal à 1. Dans ce cas, le nombre
d'itérations est égal à finale - initiale + 1 .

 Initiale et finale peuvent être des valeurs, des variables définies avant le
début de la boucle ou des expressions de même type que compteur .

[Link] 73
 Déroulement des boucles Pour

1) La valeur initiale est affectée à la variable compteur.

2) On compare la valeur du compteur et la valeur de finale :

a) Si la valeur du compteur est > à la valeur finale dans le cas d'un pas positif
(ou si compteur est < à finale pour un pas négatif), on sort de la boucle et
on continue avec l'instruction qui suit FinPour.

b) Si compteur est <= à finale dans le cas d'un pas positif (ou si compteur est
>= à finale pour un pas négatif), instructions seront exécutées.

i. Ensuite, la valeur de compteur est incrémentée de la valeur du pas si

pas est positif (ou décrémenté si pas est négatif) .

ii. On recommence l'étape 2 : La comparaison entre compteur et finale

est de nouveau effectuée, et ainsi de suite …
[Link] 74
 Boucle Pour : exemple1

Calcul de x à la puissance n où x est un réel non nul et n un entier

positif ou nul
Variables x, puiss : réel
n, i : entier
Début
Ecrire (" Entrez la valeur de x ")
Lire (x)
Ecrire (" Entrez la valeur de n ")
Lire (n)
puiss ← 1
Pour i = 1 à n
puiss← puiss*x
FinPour
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin
[Link] 75
 Boucle Pour : exemple1 (version 2)

Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou

nul (version 2 avec un pas négatif)
Variables x, puiss : réel
n, i : entier
Début
Ecrire (" Entrez respectivement les valeurs de x et n ")
Lire (x,n)
puiss ← 1
Pour i = n à 1 pas -1
puiss← puiss*x
FinPour
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin

[Link] 76
 Boucle Pour : remarque

 Il faut éviter de modifier la valeur du compteur (et de finale) à

l'intérieur de la boucle. En effet, une telle action :

 Perturbe le nombre d'itérations prévu par la boucle Pour

 Rend difficile la lecture de l'algorithme
 Présente le risque d'aboutir à une boucle infinie

Exemple :
Pour i =1 à 5
i  i -1
Ecrire(" i = ", i)
FinPour

[Link] 77
 Lien entre Pour et TantQue

La boucle Pour est un cas particulier de Tant Que (cas où le nombre d'itérations est
connu et fixé) . Tout ce qu'on peut écrire avec Pour peut être remplacé avec
TantQue (la réciproque est fausse)

Pour compteur = initiale à finale pas valeur du pas

instructions

FinPour
peut être remplacé par : compteur ← initiale
(cas d'un pas positif) TantQue (compteur <= finale)
instructions
compteur ← compteur + pas
FinTantQue

[Link] 78
 Lien entre Pour et TantQue:exemple

Calcul de x à la puissance n où x est un réel non nul et n un entier positif ou nul (version
avec TantQue)

Variables x, puiss : réel

n, i : entier
Début
Ecrire (" Entrez la valeur de x ")
Lire (x)
Ecrire (" Entrez la valeur de n ")
Lire (n)
puiss ← 1
i←1
TantQue (i<=n)
puiss← puiss*x
i ← i+1
FinTantQue
Ecrire (x, " à la puissance ", n, " est égal à ", puiss)
Fin

[Link] 79
 Boucles imbriquées

• Les instructions d'une boucle peuvent être des instructions itératives. Dans ce cas, on
aboutit à des boucles imbriquées

Exemple(1): Écrire un carré de 8 fois 8 caractères ’x’

[Link] 80
 Boucles imbriquées

• Les instructions d'une boucle peuvent être des instructions itératives. Dans ce cas, on
aboutit à des boucles imbriquées
Exemple(1): Écrire un carré de 8 fois 8 caractères ’x’

Pour i =1 à 8
Pour j =1 à 8
Ecrire("x")
FinPour
FinPour
[Link] 81
 Boucles imbriquées

• Exemple (2): Exécution

Pour i = 1 à 5
Pour j =1 à i
Ecrire("O")
FinPour
Ecrire("X")
FinPour

[Link] 82
 Boucles imbriquées

• Exemple (2): Exécution

Pour i = 1 à 5
Pour j =1 à i
Ecrire("O") OOOX
FinPour OOOOX
Ecrire("X") OOOOOX
FinPour

[Link] 83
 Choix d'un type de boucle(1)

 Si on peut déterminer le nombre d'itérations avant l'exécution de la

boucle, il est plus naturel d'utiliser la boucle Pour.

 S'il n'est pas possible de connaître le nombre d'itérations avant

l'exécution de la boucle, on fera appel à l'une des boucles TantQue ou
Répéter jusqu'à.

 Pour le choix entre TantQue et jusqu'à :

 Si on doit tester la condition de contrôle avant de commencer les instructions

de la boucle, on utilisera TantQue.

 Si la valeur de la condition de contrôle dépend d'une première exécution des

instructions de la boucle, on utilisera Répéter jusqu'à.

[Link] 84
 Choix d'un type de boucle(2)

Si nombre d'itérations connu Alors

Boucle Pour
Sinon

Si itération exécutée au moins une fois Alors

Boucle Répéter jusqu’à
Sinon
Boucle Tant que
Finsi

Finsi
[Link] 85
 II. Algorithmique : Les tableaux

[Link]
86
 Exemple introductif

 Supposons qu'on veut conserver les notes d'une classe de 30 étudiants pour
extraire quelques informations. Par exemple : calcul du nombre d'étudiants ayant
une note supérieure à 10
 Le seul moyen dont nous disposons actuellement consiste à déclarer 30 variables,
par exemple N1, …, N30. Après 30 instructions lire, on doit écrire 30 instructions Si
pour faire le calcul
nbre ← 0
Si (N1 >10) alors nbre ←nbre+1 FinSi
….
Si (N30>10) alors nbre ←nbre+1 FinSi
c'est lourd à écrire
 Heureusement, les langages de programmation offrent la possibilité de
rassembler toutes ces variables dans une seule structure de donnée appelée
tableau

[Link] 87
 Tableaux

 Un tableau est un ensemble d'éléments de même type désignés par un

identificateur unique.
 Une variable entière nommée indice permet d'indiquer la position d'un
élément donné au sein du tableau et de déterminer sa valeur.
 La déclaration d'un tableau s'effectue en précisant le type de ses
éléments et sa dimension (le nombre de ses éléments).
– En pseudo code :
variable tableau identificateur[dimension] : type
– Exemple :
variable tableau notes[30] : réel
 On peut définir des tableaux de tous types : tableaux d'entiers, de réels,
de caractères, de booléens, de chaînes de caractères, …

[Link] 88
 Tableaux : remarques

 L'accès à un élément du tableau se fait au moyen de l'indice. Par exemple,

notes[i] donne la valeur de l'élément i du tableau notes.

 Selon les langages, le premier indice du tableau est soit 0, soit 1. Le plus
souvent (au niveau algorithmique) c'est 1 (c'est ce qu'on va adopter en pseudo-
code).

 Un grand avantage des tableaux est qu'on peut traiter les données qui y sont
stockées de façon simple en utilisant des boucles.

[Link] 89
 Tableaux

Un tableau peut être représenté graphiquement par (exemple Note[15]) :

Note[1] Note[4]

 Note[2] ← 15 met la valeur 15 dans la 2 ème case du tableau.

 En considérant le cas où a est une variable de type entier, a ← Note [2] met la valeur de la 2
ème case du tableau dans a, c’est- à- dire 15.

 Lire (Note [1]) met l’entier saisi par l’utilisateur dans la première case du tableau.

 Ecrire (Note [1]) affiche la valeur de la première case du tableau.

[Link] 90
 Tableaux : saisie et affichage

 Algorithme qui permet de saisir et d'afficher les éléments d'un tableau de

30 notes:

[Link] 91
 Tableaux : saisie et affichage

 Algorithme qui permet de saisir et d'afficher les éléments d'un tableau de 30 notes :
Variables i : entier
Tableau notes[30] : réel
Début

Pour i = 1 à 30
Ecrire ("Saisie de l'élément ", i )
Lire (notes[i] )
FinPour

Pour i = 1 à 30
Ecrire (" notes[",i, "] =", notes[i])
FinPour

Fin

[Link] 92
 Tableaux : exemples (1)

 Pour le calcul du nombre d'étudiants ayant une note supérieure strictement à 10

avec les tableaux, on peut écrire :

[Link] 93
 Tableaux : exemples (1)

 Pour le calcul du nombre d'étudiants ayant une note supérieure strictement à 10

avec les tableaux, on peut écrire :

Variables i ,nbre : entier

Tableau notes[30] : réel
Début
nbre ← 0
Pour i = 1 à 30
Si (notes[i] >10) alors
nbre ←nbre+1
Finsi
FinPour
Ecrire (" Le nombre de notes supérieures à 10 est : ", nbre)
Fin

[Link] 94
 Tableaux : exemples (2)

 Soit T un tableau de vingt éléments de types entiers. Un algorithme qui permet de

calculer la somme des éléments de ce tableau.

[Link] 95
 Tableaux : exemples (2)

 Soit T un tableau de vingt éléments de types entiers. Un algorithme qui permet de

calculer la somme des éléments de ce tableau.

Variables i , somme : entier

Tableau T[20] : entier
Début
somme ← 0
Pour i = 1 à 20
somme ← somme + T[i]
FinPour
Ecrire(" La somme de tous les éléments du tableau est : " , somme)
Fin

[Link] 96
 Tableaux

 Exercice :

Soit T un tableau de N entiers. Ecrire l’algorithme qui détermine le plus grand élément
de ce tableau.

[Link] 97
 Tableaux

 Solution :
Variables i , max : entier
Tableau T[N] : entier
Début
max ← T[1]
Pour i = 2 à N
Si (T (i) > max) alors
max ← T[i]
Finsi
FinPour
Ecrire(" Le plus grand élément de ce tableau : " , max)
Fin

[Link] 98
 Tableaux à deux dimensions

 Les langages de programmation permettent de déclarer des tableaux dans

lesquels les valeurs sont repérées par deux indices. Ceci est utile par
exemple pour représenter des matrices.

 En pseudo code, un tableau à deux dimensions se déclare ainsi :

variable tableau identificateur[dimension1] [dimension2] : type

– Exemple : une matrice A de 3 lignes et 4 colonnes dont les éléments sont

réels
variable tableau A[3][4] : réel

 A[i][j] permet d'accéder à l’élément de la matrice qui se trouve à

l’intersection de la ligne i et de la colonne j
[Link] 99
 Exemples:lecture d’une matrice

 Algorithme qui permet de saisir les éléments d'une matrice de vingt lignes
et cinquante colonnes:
Algorithme Saisie_Matrice
variables i, j : entier
Tableau A [20][50] : réel
Début
Pour i =1 à 20
Ecrire ("saisie de la ligne ", i )
Pour j =1 à 50
Ecrire ("Entrez l'élément de la ligne ", i , " et de la colonne ", j)
Lire (A[i][j])
FinPour
FinPour
Fin

[Link] 100
 Exemples:affichage d’une matrice

 Algorithme qui permet d'afficher les éléments d'une matrice de vingt lignes
et cinquante colonnes:

Algorithme Affiche_Matrice
Variables i, j : entier
Tableau A [20][50] : réel
Début
Pour i=1 à 20
Pour j=1 à 50
Ecrire ("A[",i, "] [",j,"]=", A[i][j])
FinPour
FinPour
Fin

[Link] 101
 Exemples:somme de deux matrice

 Algorithme qui calcule la somme de deux matrices de vingt lignes et

cinquante colonnes :

[Link] 102
 Exemples:somme de deux matrice

 Algorithme qui calcule la somme de deux matrices de vingt lignes et

cinquante colonnes :

Algorithme Somme_Matrices
Variables i, j : entier
Tableau A [20][50] , B[20][50] , C [20][50] : réel
Début
Pour i = 1 à 20
Pour j = 1 à 50
C[i][j] ← A[i][j]+B[i][j]
FinPour
FinPour
Fin

[Link] 103