Instructions et types élémentaires

Introduction à l'algorithmique

 

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 toutes les instructions, dans l'ordre (en séquence) pour arriver au résultat que doit donner l'algorithme.

Le "langage algorithmique" que nous utilisons est un compromis entre un langage naturel et un langage de programmation. Nous présentons les algorithmes comme une suite d'instructions dans l'ordre des traitements. Ils sont toujours accompagnés d'un lexique qui indique, pour chaque variable, son type et son rôle. Un algorithme est délimité par les mots clés début et fin. Nous manipulerons les types couramment rencontrés dans les langages de programmation : entier, réel, booléen, caractère, chaîne, tableau et type composite.

Par convention, toutes les identifiants de variables seront notés en minuscule et auront un nom mnémonique. Il en va de même pour les fonctions, dont leur identifiant doit être le plus explicite sur son rôle. Ce dernier peut être une contraction de plusieurs mots, par conséquet pour rendre la lecture plus facile, la première lettre de chaque mot est mis en majuscule (sauf pour le premier, exemple : calculerAireRectangle).

 

 

Notions de variables, types et valeurs

 

Les variables d'un algorithme contiennent les informations nécessaires à son déroulement. Chaque variable a un nom (identifiant) et un type. Ce dernier correspond au genre d'information que l'on souhaite utiliser :
_ entier pour manipuler des entiers,
_ réel pour manipuler des nombres réels,
_ booléen pour manipuler des valeurs booléennes vrai ou faux,
_ caractère pour manipuler des caractès alphabétiques et numériques,
_ chaîne pour manipuler des chaînes de caractères permettant de représenter des mots ou des phrases.

Il faut noter qu'à un type donné, correspond un ensemble d'opérations définies pour ce type. Une variable est l'associtation d'un nom avec un type, permettant de mémoriser une valeur de ce type.




Le type entier

Les opérations utilisables sur les entiers sont :
_ les opérateurs arithmétiques classiques : + (addition), - (soustraction), * (produit)
_ la division entière, notée ÷, telle que n ÷ p donne la partie entière du quotient de la dividion entière de n par p
_ le modulo, noté mod, telle que n mod p donne le reste de la division entière de n par p
_ Les opérateurs de comparaison classiques : <, >, =, ...




Le type réel

Les opérations utilisables sur les réels sont :
_ les opérations arithmétiques classiques : + (addition), - (soustraction), * (produit), / (division)
_ Les opérateurs de comparaison classiques : <, >, =, ...




Le type booléen

Il s'agit du domaine dont les seules valeurs sont vrai ou faux. Les opérations utilisables sur les booléens sont réalisées à l'aide des connecteurs logiques : et (pour le et logique), ou (pour le ou logique), non (pour le non logique).


Rappel des équations logiques :



Non vrai faux faux vrai

Et vrai faux vrai vrai faux faux faux faux

Ou vrai faux vrai vrai vrai faux vrai faux





Le type caractère

Il s'agit du domaine constitué des caractères alphabétiques et numériques. Une variable de ce type ne peut contenir qu'un seul et unique caractère. Les opérations élémentaires réalisables sont les comparaisons : >, <, =, ...




Le type chaîne

Une chaîne est une séquence de plusieurs caractères. Les opérations élémentaires réalisables sont les comparaisons : <, >, =, ... selon l'ordre lexicographique.

 

 

Instructions d'affectation et expressions

 

Une instruction est la spécification d'une ou de plusieurs actions portant sur une ou des variables. L'instruction la plus commune est l'affectation. Elle consiste à doter une variable d'une valeur appartenant à son domaine, c'est à dire à lui donner une première valeur ou à changer sa valeur courante. Elle se note <-.

Une expression est une suite finie bien formée d'opérateurs portant sur des variables ou des valeurs et qui a une valeur. La valeur de l'expression doit être conforme au domaine de la variable affectée.




Exemple d'algorithme

Algorithme

début

x <- 12

y <- x + 4

x <- 3

fin



Lexique
- x : entier
- y : entier


Cet algorithme est constitué de trois instructions successives qui seront effectuées les unes après les autres. Les variables x et y sont entières. La première instruction consiste à affecter à la variable x la valeur 12. A la fin de cette instruction, la variable x vaut 12.

La deuxième instruction est un peu plus complexe. C'est l'affectation d'une expression non réduite à une valeur à une variable entière. L'expression x + 4 est d'abord reconnue comme une somme à effectuer portant sur deux valeurs entières. La première valeur est celle de la variable x, qui existe, puisque l'instruction précédente a affecté 12 à x. Ainsi, l'addition a bien ses deux opérandes entiers et elle peut être effectuée. Elle l'est, et la valeur entière 16 est affectée à la variable y.

La troisième instruction modifie la valeur de la variable x, qui devient 3. L'ancienne valeur de x, qui était 12, est définitivement perdue. Le déroulement séquentiel fait naturellement oublier les instructions effectuées en ne conservant que les valeurs courantes des variables. On remarque que les deux premières instructions ne sont pas permutables car x n'aurait alors pas de valeur au moment du calcul.

 

 

Instructions de lecture et d'écriture

 

Instructions de lecture

L'instruction de prise de données sur le périphérique d'entrée (en général le clavier) est :



variable <- lire()



L'exécution de cette instruction consiste à affecter une valeur à la variable en prenant cette valeur sur le périphérique d'entrée. Avant l'exécution de cette instruction, la variable avait ou n'avait pas de valeur. Après, elle a la valeur prise sur le périphérique d'entrée.




Instruction d'écriture

L'instruction de restitution de résultats sur le périphérique de sortie (en général l'écran) est :



écrire (liste d'expressions)



Cette instruction réalise simplement l'affichage des valeurs des expressions décrites dans la liste. Ces instructions peuvent être simplement des variables ayant des valeurs ou même des nombres ou des commentaires écrits sous forme de chaînes de caractères.

Exemple d'utilisation : écrire (x, y+2, "bonjour")




Exemple d'algorithme

On désire écrire un algorithme qui lit sur l'entrée standard une valeur représentant une somme d'argent et qui calcule et affiche le nombre de billets de 100 Euros, 50 Euros et 10 Euros, et de pièces de 2 Euros et 1 Euro qu'elle représente.

Principe :
L'algorithme commence par lire sur l'entrée standard l'entier qui représente la somme d'argent et affecte la valeur à une variable somme. Pour obtenir la décomposition en nombre de billets et de pièces de la somme d'argent, on procède par des divisions successives en conservant chaque fois le reste.

Algorithme

début

somme <- lire()

b100 <- somme ÷ 100

r100 <- somme mod 100

b50 <- r100 ÷ 50;

r50 <- r100 mod 50

b10 <- r50 ÷ 10

r10 <- r50 mod 10

p2 <- r10 ÷ 2

r2 <- r10 mod 2

p1 <- r2

écrire (b100, b50, b10, p2, p1)

fin



Lexique
- somme : entier, la somme d'argent à décomposer
- b100 : entier, le nombre de billets de 100 Euros
- b50 : entier, le nombre de billets de 50 Euros
- b10 : entier, le nombre de billets de 10 Euros
- p2 : entier, le nombre de pièces de 2 Euros
- p1 : entier, le nombre de pièces de 1 Euro
- r100 : entier, reste de la division entière de somme par 100
- r50 : entier, reste de la division entière de r100 par 50
- r10 : entier, reste de la division entière de r50 par 10
- r2 : entier, reste de la division entière de r10 par 2


 

 

Notion de fonctions

 

Une fonction est un algorithme autonome, réalisant une tâche précise, auquel on transmet des valeurs lors de son appel et qui retourne une valeur à la fin de son exéution. La notion de fonction est très intéressante car elle permet, pour résoudre un problème, d'employer une méthode de décomposition en sous-problèmes distincts. Elle facilite aussi la réutilisation d'algorithmes déjà développés par ailleurs. Mais nous n'apprendrons pas dans ce chapitre à les appeler !

Une fonction est introduite par un en-tête, appelé aussi signature ou prototype, qui spécifie :
- le nom de la fonction
- les paramètres donnés et leur type
- le type du résultat

La syntaxe retenue pour l'en-tête est la suivante :



fonction nomFonction (liste des paramètres) : type du résultat




La liste des paramètres précise, pour chaque paramètre, son nom et son type. La dernière instruction de la fonction indique la valeur retounée, nous la noterons :



retourne expression









Exemple de fonction

Ecrire une fonction calculant le périmètre d'un rectangle dont on lui donne la longueur et la largeur.

Algorithme

fonction calculerPérimètreRectangle (longueur:réel, largeur:réel):réel

début

périmètre <- 2 * (longueur + largeur)

retourne périmètre

fin



Lexique
- longueur : réel, longueur du rectangle
- largeur : réel, largeur du rectangle
- périmètre : réel, périmètre du rectangle


 

 

Instructions conditionnelles

 

Les exemple précédents montrent des algorithmes dont les instructions doivent s'exécuter dans l'ordre, de la première à la dernière. Nous allons introduire une instruction précisant que le déroulement ne sera plus séquentiel. Cette instruction est appelée une conditionnelle. Il s'agit de représenter une alternative où, selon les cas, un bloc d'instructions est exécuté plutôt qu'un autre. La syntaxe de cette instruction est :



si condition

alors liste d'instructions

sinon liste d'instructions

fsi




Cette instruction est composé de trois partie distinctes : la condition introduite par si, la clause alors et la clause sinon. La condition est une expression dont la valeur est de type booléen. Elle est évaluée. Si elle est vraie, les instructions de la clause alors sont exécutées. Dans le cas contraire, les instructions de la clause sinon sont exécutées.

On peut utiliser une forme simplifiée de la conditionnelle, sans clause sinon. La syntaxe est alors :



si condition

alors liste d'instructions

fsi




Exemple 1

Ecire un algorithme qui permet d'imprimer le résultat d'un étudiant à un module sachant que ce module est sanctionné par une note d'oral de coefficient 1 et une note d'écrit de coefficient 2. La moyenne obtenue doit être supérieure ou égale à 10 pour valider le module.

Données : la note d'orale et la note d'écrit

Résultat : impression du résultat pour le module (reçu ou refusé)

Principe : on calcule la moyenne et on la compare à 10

Algorithme

début

ne <- lire()

no <- lire()

moy <- (2 * ne + no)/3

si moy < 10

alors écrire ("reç")

sinon écrire ("refusé")

fsi

fin



Lexique
- ne : réel, note d'écrit (coeeficient 2)
- no : réel, note d'oral (coefficient 1)
- moy : réel, moyenne du module





Exemple 2

On veut écrire une fonction permettant de calculer le salaire d'un employé payé à l'heure à partir de son salaire horaire et du nombre d'heures de travail.

Les règles de calcul sont les suivantes : le taux horaire est majoré pour les heures supplémentaires : 25% au-delà de 160 heures et 50% au-delà de 200 heures.

Algorithme

fonction calculerSalaire (sh:réel, nbh:entier):réel

début

nbh < 160

alors salaire <- sh * nbh

sinon si nbh < 200

alors salaire <- 160 * sh + (nbh - 160) * 1,25 * sh

sinon salaire <- 160 * sh + 40 * sh * 1,25 + (nbh - 200) * sh * 1,5

fsi

fsi

retourne salaire

fin



Lexique
- sh : réel, salaire horaire
- nbh : entier, nombre d'heures de l'employé
- salaire : réel, salaire de l'employé

© Aflo Informatique , 2003-2004