GENERALITES SUR LES ALGORITHMES
INTRODUCTION
Définitions
Un
algorithme est une suite d’actions ou d’instructions qui doivent
être exécutées dans un ordre bien déterminé pour résoudre un problème (ou
réaliser un travail) en un temps fini.
L'algorithmique
est l’ensemble des règles et des techniques qui sont impliquées dans la
définition et la conception d'algorithmes.
Si les
instructions d'un algorithme s’exécutent les unes après les autres,
l'algorithme est dit séquentiel, si elles s’exécutent
en même temps, il est parallèle. Si l'algorithme
exploite des tâches s’exécutant sur un réseau de processeurs on parle d’algorithme
réparti, ou distribué.
Caractéristiques d’un bon algorithme
Un algorithme
doit avoir les propriétés suivantes :
-clarté : il doit être
facile à comprendre et à interpréter
-documenté : On doit
insérer des commentaires qui étayent la compréhension du programme.
-précis : chaque élément
de l’algorithme ne doit pas prêter à confusion, il est donc important de lever
toute ambiguïté ;
-efficacité : Les
opérations doivent être suffisamment simples et s’exécuter le plus rapidement
possible.
Importance de l’algorithme.
Un algorithme, traduit dans un langage
compréhensible par l’ordinateur (ou langage de programmation), donne un programme
informatique, qui peut ensuite être exécuté pour effectuer le traitement
souhaité. Donc l’algorithme facilite l’écriture des programmes informatiques.
Si un programme informatique était une dissertation, l’algorithme devait
constituer le plan de cette dissertation.
L’écriture algorithmique est un travail de programmation à visée «universelle». En effet, un algorithme ne dépend pas :
-du langage dans lequel il est implanté,
-ni de la machine qui exécutera le programme correspondant.
Etapes de résolution d’un algorithme
Les trois étapes de résolution d’un algorithme
sont :
-Préparation du
traitement : Recherche des données nécessaires à la résolution du problème
-Traitement : résolution
pas à pas, après décomposition en sous-problèmes si nécessaire
-Edition des résultats :
impression à l’écran, dans un fichier, etc.
Représentation des algorithmes
On
utilise généralement une série de conventions appelées LDA (Langage de Description
des Algorithme), ou par un algorigramme
(représentation graphique des algorithmes).
TYPES DE DONNEES UTILISEES EN
ALGORITHMIQUE
Les données sont des informations nécessaires
au déroulement d’un algorithme. .
Les constantes
Définition
Une constante est une donnée fixe qui ne varie pas durant l’exécution d’un
algorithme.
Une constante est caractérisée par son nom et sa valeur (fixe).
Déclaration des constantes
Pour
déclarer une constante, on écrit le mot-clé const, suivi du nom de la
constante et de sa valeur.
Syntaxe :
const nom _Constante = valeur
;
Exemples:
const Pi=3,14 ;
const
Max=100 ;
const
Mois= ‘Avril’ ;
Codification des objets
|
|
Objet |
Type/Nature |
Rôle |
|
Général |
Nom |
Constante=valeur de la constante |
Rôle |
|
Exemple |
Pi |
3,14 |
|
Les variables
Définition
Une
variable est un objet dont le contenu peut être modifié par une action
durant l’exécution d’un algorithme.
Une
variable est caractérisée par son nom, sa valeur et son type :
Exemple : age_du_visiteur =17.
Nom :
pour pouvoir reconnaitre la variable (age_du_visiteur).
Valeur :
c'est l'information qu'elle contient, qui peut changer. (17).
Type :
entier
Remarques :
1) Le nom d’une variable doit commencer obligatoirement par
une lettre. Il doit être formé d’une ou de plusieurs lettres, les chiffres sont
également autorisés. Aucun espace ne doit figurer dans le nom d’une variable.
Il vaut mieux remplacer les espaces par la touche (underscore)
« _ » du clavier. De même, il est préférable que le nom donné à une
variable soit évocateur de l’information qu’elle contient.
2) On peut modifier quand on veut la valeur d’une variable,
faire des opérations dessus, etc.
Les différents types de variables
Les variables sont capables de stocker
différents types d'informations. On parle de types de données. Voici les principaux types à connaître :
Les types numériques :
Les types numériques les plus connus sont l’entier et le
réel :
·
Le type entier (int)
: ce sont les nombres
du type 1, 2, 3, 4, etc. On compte aussi parmi eux les nombres relatifs : -1,
-2, -3...
Exemple
:
42
·
Le type réel :
Le type réel recouvre un ensemble de nombres réels qui ne
correspond pas toujours aux réels en mathématiques. Il comprend les nombres décimaux (float) qui sont des nombres à virgule, comme 14,738.
Le traitement et l’affichage des données de ce type se font à virgule
flottante, c’est à-dire qu’il est possible de les écrire en déplaçant le point
à volonté et en utilisant une
puissance appropriée dans la base choisie.
Exemple :
235.67= 0.23567.103=23467.10-2
On note aussi 0.23567E3
ou 23467E-2.
Le type booléen (bool) :
C’est un type très important qui ne permet de
stocker que deux valeurs, par exemple vrai ou faux (on écrit true pour vrai,
et false pour faux).
Une variable type booléen ne peut prendre que deux valeurs
représentées par les identificateurs Vrai ou Faux.
Exemple :
14>5 est Vrai
14<5 est Faux …. sont des
expressions booléennes.
Le type caractère :
Il appartient à l’une des catégories suivantes :
- Les chiffres de 0 à 9
- Les lettres de l’alphabet (de A à Z)
majuscules et minuscules.
- Les caractères spéciaux +,-,*,
/ ; etc. qui correspondent aux
touches du clavier, y compris les touches de fonction telles que la barre
d’espacement et la touche entrée.
Une
variable caractère occupe un octet en mémoire. A chaque caractère correspond un code
(appelé code ASCII) qui est un entier compris entre 0 et 255.
Remarques :
-Un caractère est généralement placé
entre 2 guillemets.
Exemple :
‘’ a ‘’ ; ‘’ g’’ ; ‘’ 128 ‘’.
-Un caractère vide est représenté par
deux paires de guillemets ‘’ ‘’
-Une variable de type caractère ne peut
contenir qu’un et un seul caractère
-Tous les caractères sont ordonnés selon
leur code ASCII variant de 0 à 255.
Le
type chaine de caractères
Une chaine
de caractère est un regroupement de plusieurs caractères. La chaîne de
caractères est le nom informatique qu'on donne au texte. On peut stocker des textes courts comme de
très longs textes au besoin.
Exemples:
·
"Je
suis un texte". Une chaîne de caractères est habituellement écrite entre
guillemets ou entre apostrophes (on parle de guillemets simples) : 'Je suis un
texte'. Les deux fonctionnent mais il ne faut pas les mélanger.
·
« bonjour »
Attention : 234 peut désigner le
nombre deux cent trente- quatre comme il peut désigner une suite de caractère
2, 3,4. Dans ce dernier cas, on écrit entre guillemets ‘’ 234 ‘’ pour
faire la différence.
Déclaration d’une variable
Pour
déclarer une variable, on écrit le mot-clé var, suivi du nom de la variable et
du type.
Syntaxe :
var nom_de_la_variable :
type ;
Exemples :
var age :
entier ;
var a : caractère ;
var nom : chaine de
caractères ;
var i,j,k :entiers ;
Tableau de codification des objets
|
|
Objet |
Type/Nature |
Role |
|
General |
Nom |
Type de la variable |
Rôle
joué par la variable |
|
Exemple |
M |
Reel |
|
INSTRUCTIONS SIMPLES
Une
structure est dite simple (appelée encore une séquence), si elle ne contient que des instructions :
- d’entrée de
données,
- d’affectation
- de sortie de
résultats.
Instruction de lecture (ou opérations d’entrée des données)
L’instruction
de lecture demande à la machine de lire une valeur saisie par un utilisateur à
partir du clavier ou de lire une valeur contenue dans une mémoire de stockage.
Elle se réduit au verbe LIRE. Lire
est donc un ordre de traitement ou une action simple à exécuter.
Ainsi Lire
une valeur « a » donne un ordre à l’utilisateur d’entrer ou de saisir cette valeur
à l’aide du clavier de l’ordinateur ou à
partir d’une mémoire de stockage.
Syntaxe : Lire (variable) ;
Exemples : Lire (note) ;
Lire (A, B) ; A et B étant des variables.
Instruction d’écriture (ou opération de sortie des résultats)
L’instruction d’écriture demande à la machine
d’afficher le résultat d’un traitement à l’écran. Elle se réduit au verbe ECRIRE. Comme Lire, Ecrire est une
action à exécuter , un ordre de traitement dont le sens traduit en quelque
sorte l’action d’afficher un résultat
ou autre chose dans une unité de sortie de l’ordinateur comme le moniteur,
l’imprimante ou un support de stockage.
Syntaxe : Ecrire(variable) ;
Ecrire (‘’ message’’, variable)
Exemples : Ecrire(Résultat) ;
Ecrire ('’Le
résultat est :'’, Résultat) ;
Instruction d’affectation
Cette
instruction permet de ranger une
valeur dans une variable. Elle se symbolise par ←.
Syntaxe : Variable
← valeur
Exemples :
x ← 35 veut dire que x prend la valeur 35.
A
←2 : la
variable A reçoit la valeur 2
B←A+1 :
la variable B reçoit le contenu de A plus 1
Nom←'Mohamed' : la
variable Nom reçoit la valeur Mohamed
LES PARTIES D’UN ALGORITHME
Le profil (en-tête)
La
première ligne d’un algorithme est le profil. Elle donne essentiellement le nom
de l’algorithme. Les débuts de mots sont en lettres majuscules.
Exemple : Algorithme_CalculSurface
Déclaration des variables et des constantes
Après
le profil, suivent les déclarations des variables. Ces variables sont de divers
ordres : les réels, les entiers, les chaines de caractère…
En
général, ces variables sont des valeurs d’entrée de l’algorithme. Après
traitement, ce sont les mêmes variables qui permettent d’obtenir des valeurs de
sortie. Les variables d’entrée et de sortie doivent être précisées entre le
profil et le délimiteur du début de l’algorithme, ensuite les constantes, les
fonctions et les tableaux suivront.
Les délimiteurs de début et de fin.
Comme
leur nom indique, les délimiteurs
représentent le début et la fin
de l’algorithme.
Le corps de l’algorithme
Le
corps de l’algorithme représente la zone
où les différentes actions de l’algorithme se situent. En général, le patron
d’un algorithme ou structure peut se résumer par les lignes suivantes.
|
Algorithme Nom_
Algorithme.
Variables Entrée
Sortie. Début Action1
Action2 Action n Fin |
← profil ←
variable d’entrée ←variable de sortie
← différentes actions ← délimiteur de fin |
Les commentaires
Les commentaires
sont souvent utilisés pour permettre une interprétation aisée de l’algorithme.
On les place entre /* et */ ou (ou entre
co et fco).
1-Ecrire (« Entrer la valeur de l’entier a :») ;
2- Lire
(a) ; /* on saisit la valeur de l’entier a au
clavier */
3-Ecrire
(« Entrer la valeur de l’entier b : ») ;
4-
Lire (b) ; /* on saisit la valeur de l’entier b au clavier
*/
4-S← a+b;
5-Ecrire (« La somme S est : », S); /*
On affiche le résultat à l’écran */
OPERATEURS ET EXPRESSIONS
Operateur
Un opérateur est un signe qui relie deux
valeurs, pour produire un résultat.
Les opérateurs possibles
dépendent du type des valeurs qui sont en jeu.
Opérateurs numériques
Ce
sont les quatre opérations arithmétiques et
tout ce qu’il y a de classique.
+ : addition
- : soustraction
* : multiplication
/ : division
^ : qui signifie
« puissance ». 45 au carré s’écrira donc 45 ^ 2.
DIV
(A, B) : donne le quotient de la division entière de A par B
MOD
(A, B) : donne le reste de la division entière de A par B
Exemples : A=5
et B=2
A/B=2.5
DIV(5,2)=2 ;
MOD(5,2)=1.
Operateurs de comparaison
<strictement
inférieur > strictement supérieur
<=
inférieur ou égal >= supérieur ou égal
= égal
<> différent de
Opérateur
alphanumérique : &
Cet
opérateur permet de concaténer,
autrement dit d’agglomérer, deux chaînes de caractères.
Exemples
. Variable : A ;
B ; C en caractères
A← ‘’Michel’’
B← ‘’ Amougou’’
C← A &B
//La valeur de C à la fin de l’algorithme est "MichelAmougou"
Opérateurs logiques
Il
s’agit du ET, du OU, du NON et de XOR.
Opérateurs de type booléen
Ils sont de la
forme :
-VRAI ou FAUX
-OUI ou NON
On obtient un résultat de type booléen quand on
est amené à comparer des expressions entre elles, au moyen des opérateurs de
comparaison.
Expression
Une expression est un ensemble de valeurs,
reliées par des opérateurs, et équivalent à une seule valeur. Par exemple,
voici quelques expressions de type numérique :
7
5+4
123-45+844
Toto-12+5-Riri
…sont toutes des expressions
valides, pour peu que Toto et Riri soient bien des
nombres car dans le cas contraire, la quatrième expression n’a pas de sens.
|
Expression |
Résultat |
|
20>4 |
Vrai |
|
12<=5 |
Faux |
|
30>5 et 5<3 |
Faux |
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).
( ) : Les parenthèses.
^ : Élévation à la
puissance
*,/ :multiplication,
division.
+,- : addition,
soustraction
En cas de besoin, on utilise les
parenthèses pour indiquer les opérations à effectuer en priorité. A priorité
égale, l’évaluation de l’expression se fait de la gauche vers la droite.
Exemples :
1+ (2*3)=7
1*(2+3)=5 /* les
parenthèses sont prioritaires */
1*2+3=5
1+2*3=7 . /* la multiplication est prioritaire
sur l’addition */
3*3^2=27
3^3*2=54 /* la puissance est
prioritaire sur la multiplication */
1+3-2=2
1-3+2=0 /* à priorité
égale, l’évaluation se fait de la gauche vers la droite*/
On a
le droit d’utiliser les parenthèses, avec les mêmes règles qu’en mathématiques.
La multiplication et la division ont « naturellement » priorité sur
l’addition et la soustraction. Les parenthèses ne sont ainsi utiles que pour
modifier cette priorité naturelle.
Cela signifie qu’en
informatique, 12 * 3 + 5 et (12 * 3) + 5 valent strictement la même chose, à
savoir 41
En revanche, 12 * (3 + 5) vaut
12 * 8 soit 96.
LES ALGORIGRAMMES
1-Définition
C’est la représentation
graphique des algorithmes avec des figures géométriques (rectangles,
parallélogrammes, losanges, etc.). On les appelle souvent logigramme, organigramme
et rarement ordinogramme.
2-Symboles
|
Marque
le début ou la fin d’un algorithme.
Marque les instructions de lecture ou d’écriture
Marque une action simple à exécuter.
Représente un sous-programme
Marque
une question posée par l’évaluation d’une condition C qui a la valeur soit
« vrai », soit « faux ». O Anneau numéroté utilisé pour les algorithmes longs de plus
d’une page. Il permet de repérer la fin de la première page et le début de la
seconde. |
|
Flèche de connexion pour indiquer le sens de
lecture
Exemple :
EXERCICES
EXERCICE I : Soit le corps de l’algorithme
suivant :
Algorithme valeur
Var A, B, C, D : réel ;
Début
A ⃪ 3
C ⃪ 4
B ⃪ A+2*5
D ⃪ A*B+C
A ⃪ D
FIN
Quelles seront les contenus des
variables A, B, C et D après exécution de cet algorithme ?
EXERCICE II :
Soit l’algorithme suivant :
Algorithme CaFaitQuoi
Variables A, B : réels ;
Début
Ecrire
(‘’Donnez-moi deux valeurs ‘’) ;
Lire
(A, B) ;
Ecrire
(‘’ Vous m’avez donné ‘’, A,
‘’ et ‘’, B) ;
A ← B
B ← A
Ecrire (‘’Maintenant, mes données
sont : ‘’, A, ‘’ et ‘’, B) ;
Fin
Question: Supposons qu’au début, on avait : A = 5
et B = 8, donner les contenus de A et B à la fin de l’exécution de cet
algorithme.
EXERCICE III:
Algorithme
Variables A, B, C : réels ;
// Cet algorithme permet de permuter les
valeurs de deux variables A et B //
Début
Ecrire ("A = ") ;
Lire(A) ;
Ecrire ("B = ") ;
Lire(B) ;
C ← A ;
A ← B ;
B ← C ;
Ecrire (A, B) ;
Fin
Question : Supposons qu’au début, on avait A = 5
et B= 8, donner les contenus de A et B à la fin de l’exécution de cet
algorithme.
EXERCICE
IV :
soit l’algorithme ci-dessous :
Algorithme
Var nb, pht, ttva ; pttc : Numérique ;
Début
Ecrire ‘’Entrez le prix
hors taxes :’’ ;
Lire (pht) ;
Ecrire (‘’Entrez le
nombre d’article :’’) ;
Lire (nb) ;
Ecrire (‘’Entrez le
taux de TVA :’’) ;
Lire (ttva) ;
pttc⃪nb*pht*(1+ttva) ;
Ecrire (‘’ Le prix
toutes taxes confondues est :’’, pttc) ;
Fin
Questions :
1.1-Que vaut pttc
lorsque nb=5, pht=7500 fcfa
et ttva=7% ?
1.2-Que fait cet
algorithme ?
EXERCICE V :
Votre
grand-père détient une parcelle sous forme rectangulaire au village. Il
sollicite votre aide pour connaitre la superficie de son terrain
- Analyse du problème
a-Identifier le(s) éléments en entrée
b-Quels sont les opérations
(traitements)
c-Identifier le(s) éléments en sortie
- Faire un tableau récapitulatif des objets (nom de
l’objet, type/nature et le rôle joué par chaque objet) nécessaire à la
réalisation de ces opérations.
- Ecrire un algorithme qui permet de résoudre ce
problème
EXERCICES
VI :
1-On se propose de déterminer l’allongement Δl d’un ressort de raideur K sur lequel est accrochée
une masse m. Sachant que :
Δl *K=m*g avec g=9,8 N/Kg.
2-Faire un tableau récapitulatif des différents
objets (nom de l’objet, type/nature, rôle joué par l’objet.
3-Faire la déclaration des différents
objets.
4-En déduire l’algorithme qui permet de
calculer l’allongement de ce ressort.
EXERCICE VII :
On se propose
de calculer le volume V d’un cylindre de hauteur h ayant pour rayon de base R.
On sait que le volume est égal à la surface de base que multiplie la hauteur
(V=π.R2h).
Propose un
algorithme qui te permet de résoudre ce problème
EXERCICE VIII : On se propose de calculer la surface S
d’un rectangle de longueur L et de largeur l. Proposer un algorithme permettant
de réaliser ce travail (S=L*l).
EXERCICES IX :
1-Ecrire un algorithme permettant de calculer la surface
d’un cercle de rayon R.
2-Concevez un
algorithme qui calcule le carré d’un nombre qu’on lui fournit.
3-Ecrire un algorithme
qui calcule le prix TTC (toutes taxes comprises) lorsqu’on lui fournit le prix
HT (Hors taxes) lorsqu’on connait le taux de la TVA.
On rappelle que le prix
TTC=prix HT + prix HT*TVA/100=prix HT*(1 + TVA/100).
4-Ecrire un algorithme qui permet de Calculer et afficher le
quotient et le reste de la division de A par B, A et B étant des réels entiers
non nuls
CORRIGES
EXERCICE I :
Après
exécution : A=43 ; B=13 ; C=4 ; D=43
EXERCICE II :
Après
exécution, on a : A=8 ; B=8
EXERCICE III:
1.
Après exécution, on a : A=8 ; B=5
2. Cet algorithme permet de permuter
les valeurs de deux variables A et B
EXERCICE IV :
1-pttc
=5x7500x (1 + 7/100) =40 125
2-Cet algorithme
calcule et affiche le prix toutes taxes comprises d’un article en fonction de
la quantité, du prix hors taxe et de la tva
3-Calcul_pttc
EXERCICE V :
1. a-Longueur
L, largeur l
b-Multiplier la longueur par la largeur (L
* l)
c-Surface (S)
2.
|
Objet |
Type/Nature |
Rôle |
|
L |
Réel |
Longueur de la parcelle |
|
l |
Réel |
Largeur de la parcelle |
|
S |
Réel |
Surface de la parcelle |
3.
Algorithme surfaceRectangle
Var L, l : Réel ;
Début
Écrire ("Entrer la longueur du rectangle :") ; Lire
(L) ;
Écrire
("Entrer la largeur du rectangle :") ; Lire (l) ;
S ß
L x l ;
Écrire ("La surface du
rectangle est :", S) ;
FinAlgo
EXERCICE VI :
1.
|
Objet |
Type/Nature |
Rôle |
|
g |
Constante=9,8 |
Intensité de la pesanteur |
|
m |
Réel |
Masse de l’objet |
|
K |
Réel |
Raideur du ressort |
|
Δl |
Réel |
Allongement du ressort |
2. Const g=9,8 ;
Var m, k, Δl: reels;
3. Algorithme AllongementRessort
Const g=9,8 ;
Var
m, k, Δl: réels;
Début
Ecrire (“Donner la valeur de la
masse m:”), Lire(m) ;
Ecrire (‘’Donner la valeur de la
raideur K : ‘’), Lire(K) ;
Δl ← m*g/K ;
Ecrire (‘’ L’allongement du
ressort est : ‘’, Δl) ;
Fin
EXERCICE
VII :
Algorithme VolumeCylindre
Var h, R,V:
Réels ;
Const
PI=3,14 ;
Début
Écrire ("Entrer la hauteur du cylindre :") ; Lire
(h) ;
Écrire ("Entrer le rayon
:") ; Lire (R) ;
V ß
PI*R*R*h ;
Écrire ("Le volume du cylindre
est:", V) ;
FinAlgo
EXERCICE VIII :
Algorithme surfaceRectangle
Var L, l :
Réel ;
Début
Écrire ("Entrer la longueur du rectangle :") ; Lire
(L) ;
Écrire ("Entrer la
largeur du rectangle :") ; Lire (l) ;
S ß
L x l ; Écrire ("La
surface du rectangle est :", S) ;
FinAlgo
EXERCICES IX
1.Algorithme SurfaceCercle
Const Pi = 3,14 ;
Var R, S : réels ;
Début
LIRE (R) ;
S ← R*R*Pi ;
ECRIRE
(’’La surface de ce cercle est ‘’: S) ;
Fin
2.Algorithme ElèveAuCarré
Var unNombre, sonCarré :
entiers ;
Début
Ecrire (‘’ Quel nombre
voulez-vous élever au carré ? ‘’) ;
Lire (unNombre) ;
Son Carré ← unNombre*unNombre ;
Ecrire (‘’ Le carré de ‘’, unNombre) ;
Ecrire (‘’ c’est ‘’, sonCarré) ;
Fin
2. Algorithme FaitLeTotal
Var nbVal, cpt :
entiers ;
Valeur, totalValeurs :
réels ;
Début
Ecrire (‘’ Combien de valeurs
voulez-vous saisir ? ‘’) ;
Lire (nbVal) ;
totalValeurs
← 0 ;
Pour cpt ← 1 à nbVal Faire
Ecrire (‘’ Donnez
une valeur ‘’) ;
Lire
(valeur) ;
totalValeurs
← totalValeurs + valeur ;
Fin Pour
Ecrire (‘’Le total des », nbVal, »valeurs est ‘’) ;
Fin
3-Algorithme ParExemple
Constante :
(TVA : réel) ← 20,6 ;
(titre : chaine) ← Resultat ;
Variable prix
HT, prixTTC : réels ;
Début
Ecrire (‘’ Donnez-moi le prix
hors taxes ; ‘’) ;
Lire (prixHT) ;
prixTTC ←
prixHT*(1+ TVA/100);
Ecrire (titre) ;
Ecrire (prixHT,”FCFA
HT devient”, prixTTC, “euros TTC) ;
Fin
4.Algorithme DivisionEuclidienne
// Cet algorithme permet de calculer
puis d’afficher le quotient et le reste de la division
Euclidienne de deux variables A par
B //
Variables A, B : entiers ;
Début
Ecrire ("A = "), Lire(A) ;
Ecrire ("B = "),
Lire(B) ;
q← A DIV B
r← A MOD B
Ecrire (« Le quotient est ", q, " et le reste est ",
r)
Fin