Support de cours algorithmique instructions de lecture et d’écriture, tutoriel & guide de travaux pratiques algorithmes en pdf.

Instructions de lecture et d’écriture

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.
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 expressions peuvent être simplement des variables ayant des valeurs ou même des nombres ou des commentaires écrits sous forme de chaîne de caractères.
Exemple d’utilisation : écrire (x, y+2, « bonjour »)
Exemple d’algorithme
Écrire un algorithme qui décompose une somme d’argents en billets de 100 euros, 50 euros et 10 euros, et de pièces de 2 euros et 1 euro. La somme sera lue au clavier, et les valeurs affichées une par ligne.
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
Notion de fonction
Une fonction est un algorithme autonome, réalisant une tâche précise. Il reçoit des paramètres (valeurs) en entrée et retourne une valeur en sortie (résultat). 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.
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
Exemple de fonction
Ecrire une fonction calculant le périmètre d’un rectangle dont on 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
 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ée de trois parties 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 (conditionnelle simple)
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’oral 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, no ← lire ( )
moy← (ne * 2 + no) / 3
si moy ≥ 10
alors écrire (« reçu »)
sinon écrire (« refusé »)
fsi
fin
lexique :
– moy : réel, moyenne
– ne : réel, note d’écrit
– no : réel, note d’oral
Exemple 2 (conditionnelles imbriquées)
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 h et 50% au-delà de 200 h.
fonction calculerSalaire ( sh : réel, nbh : entier) : réel
début
si nbh ≤ 160
alors salaire ← nbh * sh
sinon si nbh ≤ 200
alors salaire ← 160 * sh + (nbh – 160) * sh * 1.25
sinon salaire ← 160 * sh + 40 * sh * 1,25 + (nbh – 200) * sh * 1.5
fsi fsi
retourne salaire
fin
lexique
– sh : réel, salaire horaire de l’employé
– nbh : entier, nombre d’heures de travail de l’employé
– salaire : réel, salaire de l’employé
Itérations
Il arrive souvent dans un algorithme que la même action soit répétée plusieurs fois, avec éventuellement quelques variations dans les paramètres qui précisent le déroulement de l’action. Il est alors fastidieux d’écrire un algorithme qui contient de nombreuses fois la même instruction. De plus, ce nombre peut dépendre du déroulement de l’algorithme. Il est alors impossible de savoir à l’avance combien de fois la même instruction doit être décrite. Pour gérer ces cas, on fait appel à des instructions en boucle qui ont pour effet de répéter plusieurs fois une même action. Deux formes existent : la première, si le nombre de répétitions est connu avant l’exécution de l’instruction de répétition, la seconde s’il n’est pas connu. On appellera itération l’exécution de la liste des instructions.
Répétitions inconditionnelles
Il est fréquent que le nombre de répétitions soit connu à l’avance, et que l’on ait besoin d’utiliser le numéro de l’itération afin d’effectuer des calculs ou des tests. Le mécanisme permettant cela est la boucle Pour.
Forme de la boucle Pour :
Pour variable de valeur initiale à valeur finale faire
liste d’instructions
fpour
La variable dont on donne le nom va prendre successivement toutes les valeurs entières entre valeur initiale et valeur finale. Pour chaque valeur prise par la variable, la liste des instructions est exécutée. La variable utilisée pour énumérer les itérations est appelée variable d’itération, indice d’itération ou compteur. L’incrémentation par 1 de la variable est implicite.
Autre forme de la boucle Pour :
Pour variable décroissant de valeur initiale à valeur finale faire liste d’instructions fpour
La variable d’itération est décrémentée de 1 après chaque itération.
Exemple 1 (cas simple, compteur croissant)
Ecrire l’algorithme permettant d’afficher la table de multiplication par 9.
Un algorithme possible est le suivant :
Algorithme
début
écrire(1*9)
écrire(2*9)
écrire(3*9)
écrire(4*9)
écrire(5*9)
écrire(6*9)
écrire(7*9)
écrire(8*9)
écrire(9*9)
écrire(10*9)
fin
Il est plus simple d’utiliser une boucle avec un compteur prenant d’abord la valeur 1, puis augmentant peu à peu jusqu’à atteindre 10.
algorithme
début
pour i de 1 à 10 faire
écrire (i*9)
fpour
fin
lexique
– i : entier, indice d’itération
Exemple 2 (compteur décroissant)
Compte à rebours : écrire l’algorithme de la fonction qui, à partir d’un nombre entier positif n , affiche tous les nombres par ordre décroissant jusqu’à 0.
Exemple : pour n = 5, le résultat sera 5 4 3 2 1 0.
fonction compteARebours ( n : entier)
début
pour i décroissant de n à 0 faire
écrire (i)
fpour
fin
lexique
– n : entier,
– i : entier, indice d’itération
Exemple 3 (calcul par récurrence : cas de la somme)
On veut imprimer, pour n donné, la somme des carrés des n premiers entiers.
Cette somme, notée s, est obtenue en calculant le n-ième terme d’une suite définie par récurrence : sn = sn-1 + i2
Algorithmiquement, le calcul d’une telle suite se fait en deux étapes :
– initialisation (ici, s0 = 0),
– répétition de : calcul du ième terme en fonction du terme d’indice i-1
algorithme
début
n ← lire ( ) // 1
s ← 0 // 2
pour i de 1 à n faire // 3
s ← s + i2 // 4
fpour // 5
écrire (s)
fin
lexique
– s : entier, somme des carrés des n premiers entiers
– n : entier,
– i : entier, indice d’itération
Schéma de l’évolution de l’état des variables instruction par instruction :
On suppose que la valeur introduite par l’utilisateur est 4.