Instructions et types élémentaires

Date de publication : 16/03/2002 , Date de mise à jour : 27/01/2007

L'algorithmique est une base essentielle puisqu'elle permet d'implémenter une solution générique à un problème.

Ce tutoriel vous donnera les bases en algorithmique : les différents types de variables qu'il existe, opérateurs, instructions conditionnelles, écriture d'une fonction.

1. Introduction à l'algorithmique
2. Notions de variables, types et valeurs
2.1. Le type entier
2.2. Le type réel
2.3. Le type booléen
2.4. Le type caractère
2.5. Le type chaîne
3. Instructions d'affectation et expressions
3.1. Exemple d'algorithme
4. Instructions de lecture et d'écriture
4.1. Instruction de lecture
4.2. Instruction d'écriture
4.3. Exemple d'algorithme
5. Notion de fonctions
5.1. Exemple de fonction
6. Instructions conditionnelles
6.1. Exemple 1
6.2. Exemple 2

1. 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équent pour rendre la lecture plus facile, la première lettre de chaque mot est mis en majuscule (sauf pour le premier, exemple : calculerAireRectangle).

2. 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ères 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'association d'un nom avec un type, permettant de mémoriser une valeur de ce type.

2.1. 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 division 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 : <, >, =, ...

2.2. 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 : <, >, =, ...

2.3. 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

2.4. 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 : <, >, =, ...

2.5. 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.

3. 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.

3.1. Exemple d'algorithme

Algorithme
    début
        x <- 12    // 1
        y <- x + 4 // 2
        x <- 3     // 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.

Schéma de l'évolution de l'état des variables instruction par instruction :

Instructions	x	y
1	12
2		16
3	3

4. Instructions de lecture et d'écriture

4.1. Instruction 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.

4.2. 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")

4.3. 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()                 // 1
        b100 <- somme ÷ 100             // 2
        r100 <- somme mod 100           // 3
        b50 <- r100 ÷ 50                // 4
        r50 <- r100 mod 50              // 5
        b10 <- r50 ÷ 10                 // 6
        r10 <- r50 mod 10               // 7
        p2 <- r10 ÷ 2                   // 8
        r2 <- r10 mod 2                 // 9
        p1 <- r2                        // 10
        écrire (b100, b50, b10, p2, p1) // 11
    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

Schéma de l'évolution de l'état des variables instruction par instruction :

On suppose que la valeur introduite par l'utilisateur pour somme est 988 Euros.

Instructions	somme	b100	b50	b10	p2	p1	r100	r50	r10	r2
1	988
2		9
3							88
4			1
5								38
6				3
7									8
8					4
9										0
10						0
11		écrire()	écrire()	écrire()	écrire()	écrire()

5. 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écution. 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 retournée, nous la noterons :

retourne expression

5.1. Exemple de fonction

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

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

6. Instructions conditionnelles

Les exemples 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

6.1. Exemple 1

Ecrire 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çu")
            sinon écrire ("refusé")
        fsi
    fin

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

6.2. 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.

fonction calculerSalaire (sh:réel, nbh:entier):réel
    début
        si 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é

Copyright © 2007 . Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts. Cette page est déposée à la SACD.