INTRODUCTION COURS BASIQUE D'ALGORITHMIQUE 2011 et 2012
Un algorithme est une suite d’instructions élémentaires qui une
fois exécutées par l'ordinateur donne le résultat cherché.
Exemples :
Une notice de montage d'un meuble en KIT.
Un algorithme ne contient que des instructions de bases, faciles à comprendre
par l'homme ou l'ordinateur .
Il faut systématiquement tester un algorithme à la main pour vérifier qu’il conduit
bien au résultat voulu avant de le faire "tourner" sur l'ordinateur.
Un algorithme doit être écrit dans un langage le plus clair possible, pour être
ensuite traduit en langage de programmation.
Des CONVENTIONS ( codes ) d’écritures et de présentation permettent le passage au langage.
---------------------------------------------------
-I- PARTIE : LES VARIABLES.
1.Définition.
Un programme informatique utilise des données ( placées dans un fichier,
saisies au clavier ), il les utilise, en crée de nouvelles…
Toutes ces valeurs sont appelées des VARIABLES.
Il faut leur attribuer une place dans la mémoire de l’ordinateur qui dépend de leur
nature. Les variables sont donc des emplacements dans la mémoire.
(Les nombres réels prennent plus de place que les entiers ).
Pour cela, on déclare les variables en début de programme (et d’algorithme).
On choisit un nom simple et explicite :
par exemple, nom , ou nomclient pour le nom d’un client, age pour son âge …
Les principaux types de variables sont :
( En algorithmique, on notera toujours les chaînes de caractères entre guillemets )
Dans l’exemple précédent, nom sera une chaîne de caractères, et âge
sera un entier.
2. AFFECTATION
On affecte les données aux variables en utilisant une flèche : ←
L’affectation ne modifie que le contenu de ce qui est à gauche de la flèche.
Exemple :
nom ← « Dupont » affecte le nom de Dupont à la variable nom.
Si plus loin on a : nom ← « Durant », alors, Dupont disparaîtra et sera remplacé par Durant.
Si age est déclaré en entier, on pourra avoir, age ← 15
On pourra effectuer des opérations sur les variables :
2. Exemple : age ← age +3.
Alors, age contiendra l’entier 18 au lieu de 15.
Les opérations sont celles que l’on utilise habituellement, mais doivent être faites
sur des types de nombres (entier ou réel).
D’autres actions sont effectuées avec les types alphanumérique ou booléen.
3. Incrémentation.
Cela consiste à augmenter de 1 la valeur contenue dans une mémoire.
Soit i une variable numérique.
i ←i + 1 est une incrémentation
C'est très souvent utilisé pour une variable qui sert de compteur.
4. Variable non initialisée.
On met n.i. pour le signaler dans un algorithme "papier".
i est une variable n.i. signifie qu'on n'a pas attribué explicitement
de valeur à j.
Pour qu'une incrémentation soit faite , i ←i + 1 , il est indispensable que i
soit déjà initialisée en posant par exemple i = 0.
5. Littéral.
La représentation de la" valeur" d'une variable.
6. EXEMPLE.
Quelles sont les valeurs des variables A , B , C , D après
exécution des instructions suivantes ? Pour cela compléter le tableau.
A ← 1
B ← 2
C ← 3
D ← A
A ← C + 1
B ← D + C
C ← D + 1
Instructions | A | B | C | D |
Début | n.i. | n.i. | n.i. | n.i. |
A ← 1 | 1 | n.i. | n.i. | n.i. |
B ← 2 | ||||
C ← 3 | ||||
D ← A | ||||
A ← C+1 | ||||
B ← D+C | ||||
C ← D+1 |
Réponse:
instructions | A | B | C | D |
Début | n.i. | n.i. | n.i. | n.i. |
A ← 1 | 1 | n.i. | n.i. | n.i. |
B ← 2 | 1 | 2 | n.i. | n.i. |
C ← 3 | 1 | 2 | 3 | n.i. |
D ← A | 1 | 2 | 3 | 1 |
A ← C+1 | 4 | 2 | 3 | 1 |
B ← D+C | 4 | 4 | 3 | 1 |
C ← D+1 | 4 | 4 | 2 | 1 |
7.Présentation d'un algorithme.
Il y a trois parties dans un algorithme" papier" .
( C'est aussi le cas avec ALGOBOX qui est très proche
de l'écriture "papier" )
1. Le tître: Il décrit le but de l'algorithme
2. Déclaration de variables. ( Avec Python ce n'est pas nécessaire )
3. Les instructions. C'est le moteur de l'algorithme.
----------------------------------------------------------------
- II - PARTIE : ENTREE - SORTIE
•ENTREE. ( De l'utilisateur vers l'ordinateur )
On utilise l’instruction " Saisir" ( c-à-d "LIRE" avec ALGOBOX ) pour que l'ordinateur
demande une information à l’utilisateur qu’il tapera au clavier.
( Cela remplace le" INPUT" en Basic )
• SORTIES. ( Elles sont à destination de l'utilisateur )
On utilise l’instruction ECRIRE ou AFFICHER pour afficher un résultat à l’écran.
Ces instructions sont à comprendre comme étant exprimées par la machine.
On peut afficher une "message en français" ou des "valeurs" de variables.
Par exemple : Afficher " Vous avez saisi a = " , a , "."
Exemple:
Algorithme: Ajouter 1 à un nombre
VARIABLES:
numériques: a , b
DEBUT:
Afficher " Saisissez une valeur numérique "
Saisir a
b ← a + 1
Afficher " Vous avez considéré la valeur " , a , "."
Afficher a, " + 1 = " , b
FIN
-III-PARTIE : LES TESTS ou structures alternatives
La logique intervient très vite .
Les tests sont utilisés lorsqu’on a plusieurs éventualités, et que l’on veut que le programme
agisse différemment dans tel ou tel cas.
La structure d’un test est :
Si booléen Alors
Instructions 1
Sinon
Instructions 2
Finsi
( Lorsqu’il n’y a pas d’instruction 2, le sinon ne se met pas . )
Un booléen est une expression qui ne peut prendre que deux valeurs :
Vrai ou Faux c-à-d 1 ou 0
Le booléen est donc soit une variable de type booléen, soit une condition qui est vérifiée ou non
Exécution :
si le booléen est vrai, on effectue l’instruction 1 puis on va à la fin du si ;
si le booléen est faux, on va à l’instruction du sinon
Test imbriqués :
Dans la partie sinon, on peut de nouveau avoir une condition
si on a de nouveau deux possibilités
Exemple : pour savoir si de l’eau est liquide, solide ou gazeuse en fonction de sa température :
Tests successifs Variable Temp en Entier |
Tests imbriqués Variable Temp en Entier |
En imbriquant les tests, on gagne en efficacité et rapidité.
On peut encore gagner en fusionant le sinon et le si qui donne un sinonsi comme ci dessous :
VARIABLE
Temp en Entier
DEBUT
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp =< 0 Alors
Ecrire "C’est de la glace"
SinonSi Temp < 100 Alors
Ecrire "C’est du liquide"
Sinon
Ecrire "C’est de la vapeur"
Finsi
FIN
Les conditions
Une condition est une comparaison entre deux valeurs de même nature, et elle utilise
un opérateur de comparaison .
( égal, différent, inférieur strictement , inférieur ou égal, supérieur strictement
ou supérieur ou égal)
Une condition sera soit Vraie soit Fausse
Exemple :
i < 3 est une condition qui peut être V ou F suivant la valeur de i.
On pourra si besoin utiliser des conditions composées en les combinant
avec des opérateurs logiques qui sont :
OU, ET, NON, XOR
Le OU nécessite quau moins une des deux conditions au moins soit vraie
pour que la composée le soit.
Le ET nécessite que les deux soient vraies pour que la composée le soit.
Le XOR est vrai si l’une ou l’autre mais pas les deux sont vraies
On traduit ceci dans les tables de vérités : ( Règles de logiques)
C1 |
C2 |
C1 ET C2 |
C1 OU C2 |
C1 XOR C2 |
Vrai |
Vrai |
Vrai |
Vrai |
Faux |
Vrai |
Faux |
Faux |
Vrai |
Vrai |
Faux |
Vrai |
Faux |
Vrai |
Vrai |
Faux |
Faux |
Faux |
Faux |
Faux |
-IV- TANT QUE ..... FAIRE ......
La stucture est la suivante:
Tant que booléen Alors
Instruction
Fin de tant Que
Cela signifie que tant que la condition est vraie l'intruction est réalisée.
Par exemple avec ALGOBOX
VARIABLES
A EST_DU_TYPE NOMBRE
i EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE A ( Saisir la valeur de A . C'est une entrée )
i PREND_LA_VALEUR 0 ( initialisation de la variable qui sert de compteur )
TANT_QUE (i<5) FAIRE ( La condition booléenne est i < 5 )
DEBUT_TANT_QUE
A PREND_LA_VALEUR 2*A+1
AFFICHER "A = " ( Instruction)
Afficher* A ( Instruction) ( * est mis pour aller à la ligne )
i PREND_LA_VALEUR i+1 ( incrémentation: On ajoute 1 à la variable de comptage )
FIN_TANT_QUE
FIN_ALGORITHME
--------------------------------------------------------------------------------------------------------