Algorithmique impérative/Théorie
Qu'est ce qu'un algorithme impératif
modifierPremière approche
modifierOn peut faire le parallèle entre un algorithme et une recette de cuisine. La recette donne les indications nécessaires pour transformer, étape par étape, des ingrédients de départ en un plat prêt à servir. En suivant la recette, le cuisinier en transpose le texte en actions concrètes. Il en va de même pour l'algorithme : une fois qu'on l'a écrit, on le donne à l'ordinateur qui va le suivre étape par étape, cette fois-ci pour transformer des données de départ en données d'arrivée : les résultats.
Attention toutefois, ce parallèle donne une idée générale mais cache quelques subtilités. En effet, si le cuisinier peut faire deux choses en même temps (faire cuire quelque chose au four pendant qu'il épluche autre chose), l'ordinateur, lui, ne fait qu'une seule chose à la fois.
L'objectif de ce livre est donc d'apprendre à écrire des recettes qu'un ordinateur pourra comprendre. Cela implique le respect des règles d'un langage que nous allons apprendre. Nous pourrons ainsi écrire des recettes qui seront en fait des méthodes pour résoudre des problèmes ou calculer des résultats. L'ordinateur pourra alors suivre la recette et donner les résultats, après avoir effectué tous les calculs (fastidieux) à votre place. Un objectif concret est tout simplement de pouvoir assigner à un ordinateur une tâche trop rébarbative pour en débarrasser un humain.
Définition
modifierTout d'abord, un algorithme impératif est une séquence d'actions. C'est une séquence car les actions s'effectuent les unes après les autres et non en même temps.
Un algorithme a une fonction, un objectif. Pour cela, il transforme des entrées (aucune, une ou plusieurs) en sorties (une ou plusieurs) : vous lui entrez des données, il vous en sort d'autres.
Distinction algorithme / programme : de l'algorithme découle un programme informatique que l'on peut exécuter sur une machine. Le programme informatique est une traduction de l'algorithme dans un langage de programmation (par exemple Pascal). On peut créer plusieurs programmes informatiques différents à partir d'un même algorithme car chaque langage de programmation a ses particularités. On peut donc dire que l'algorithme est théorique, il est l'abstraction du programme informatique.
Par exemple, l'algorithme par lequel on entre deux nombres entiers et qui donne en sortie la somme de ces deux nombres a pour objectif de faciliter le calcul des sommes de deux nombres, opérations qui peuvent être fastidieuses à faire de tête pour un humain.
Il y a dans la vie courante de nombreux exemples d'algorithmes impératifs qui nous donnent des marches à suivre (mathématiques, recettes de cuisine, ...).
Un algorithme complet, pris ci-dessous comme exemple, donne une idée simple de ce qu'on pourra produire à la fin de l'étude de l'algorithmique impérative. Tous les concepts mis en œuvre dans cet algorithme sont expliqués plus loin, ne vous inquiétez donc pas si certains aspects vous échappent pour l'instant.
Cet algorithme calcule et affiche le périmètre, l'aire et le volume du cercle ou de la sphère dont le rayon est donné par l'utilisateur :
Algorithme cercle
Constantes
pi = 3,1416
Lexique
rayon : réel (* le rayon donné par l'utilisateur *)
périmètre : réel (* le périmètre du cercle *)
Début
Afficher("Donner le rayon : ")
Lire(rayon)
périmètre ← 2 * pi * rayon
Afficher("Le périmètre est de : ", périmètre)
Afficher("L'aire du cercle est de ", pi * rayon²)
Afficher("Le volume de la sphère est de ",(4/3) * pi * rayon³)
Fin
À la fin de l'apprentissage proposé dans ce livre, vous serez à même de créer ce genre d'algorithme et d'autres bien plus complexes.
Les types, les opérateurs et les expressions
modifier
Nous entrons maintenant dans le vif du sujet. Cette première partie est plutôt abstraite et une fois que vous l'aurez étudiée, peut entrainer une sensation de confusion sans application pratique concrète. À cet effet, vous trouverez en fin de document une partie « Ce qu'il faut retenir ». Lors de votre première lecture, n'essayez pas de comprendre mais plutôt d'admettre. Une seconde lecture vous permettra d'avoir une vue d'ensemble et de constater qu'en fait, tout se tient.
Première approche
modifierUn type est la façon de comprendre la signification d'une donnée. Prenons la donnée 4 : elle peut être de type entier (de valeur 4 : 3+1), de type caractère (le caractère "4"), est-ce un réel... ?
Un opérateur transforme des données. Par exemple, la somme est un opérateur qui transforme des données en une autre donnée. Il convient de se demander sur quel(s) type(s) un opérateur fonctionne. Par exemple, la somme de deux données de type "entier" est de type "entier". On peut donc supposer que la somme de deux données de type "réel" sera de type "réel" (rassurez-vous : ce sera le cas). Qu'en est-il de la somme de deux données de type "caractère" et de la somme d'une donnée de type "réel" et d'une autre de type "entier" ?
Une expression est une combinaison d'opérateur et de données. Par exemple "4+3" est une expression comportant un opérateur et deux données de type "entier". Toutes les expressions ont une valeur, "4+3" a la valeur 7 ; 7 est une donnée de type "entier".
Nous avons donc trois notions différentes, mais liées entre elles par des règles que nous allons voir.
Spécification
modifierChaque type a donc son ensemble de valeurs possibles et des opérateurs qui lui sont propres. Par exemple, le type entier
qui peut prendre des valeurs telles que 10
ou 12345
...
Les opérateurs sont des fonctions mathématiques et à ce titre, ils ont un espace de départ et un espace d'arrivée. Cette propriété s'étend aux opérateurs puisque chaque opérateur à un ou plusieurs types de départ (fonction à une ou plusieurs variables) et un type d'arrivée.
Prenons la fonction mathématique « somme ». On pourrait noter : somme : ℕ² → ℕ : x,y → x+y. De la même façon, l'opérateur somme ajoute deux données de type "entier" et renvoie un "entier". Remarquez que "a+b" est une notation de somme(a,b).
Pour chaque opérateur que vous découvrez ou utilisez, demandez-vous toujours quels sont les types de départ et d'arrivée. Beaucoup d'erreurs sont dues à des opérateurs mal utilisés.
Une expression est donc une suite d'opérateurs et de données qui doit respecter les règles imposées par l'usage des opérateurs.
Dans notre cours nous allons introduire cinq types, les plus couramment utilisés en informatique :
- entier
- réel
- caractère
- chaîne de caractères
- booléen
Ce(s) dernier(s) vous est (sont) probablement étrangers : ne vous inquiétez pas, nous allons y revenir.
Les entiers et les réels
modifierVoici deux types fidèles à leur définition mathématique.
Les opérateurs sur les entiers sont "+", "-" "*" "/", respectivement la somme, la différence, la multiplication et la division entière. Un dernier opérateur est l'opérateur mod, donnant le reste de la division entière. Tous ces opérateurs prennent deux données de type "entier" pour en renvoyer une autre du même type. (Rappel : a = (a / b)*b + a mod b)
Les opérateurs sur les réels sont "+", "-" "*" "/", respectivement la somme, la différence, la multiplication et la division. Tous ces opérateurs prennent deux données de type "réel" pour en renvoyer une autre du même type.
Il convient de se demander ce qu'il se passe quand on considère l'expression "a+b" avec a entier et b réel. Cela est censé ne jamais arriver. Néanmoins, on pourra considérer que l'entier se transforme en réel avant l'opération.
Les caractères et les chaînes de caractères
modifierUn caractère est tout simplement une lettre, un chiffre ou un symbole : par exemple, "1", "a", "A", "|" sont des caractères.
Aucun opérateur n'existe sur les caractères, ayant un caractère pour résultat. Dans certains langages de programmation, il peut exister des opérateurs pour ajouter un caractère à une chaîne de caractères.
Une chaîne de caractères est une suite de caractères telle que décrite précédemment. "1", "1abc" (par exemple) sont des chaînes de caractères. À noter que "" est une chaîne de caractères (la seule comportant 0 caractère).
Il n'existe qu'un seul opérateur sur les chaînes. Il s'agit de l'opérateur de concaténation qu'on notera "+". La concaténation revient à mettre la seconde chaîne à la suite de la première.
Par exemple "abc"+"def" est équivalente a "abcdef". Remarquez que l'opérateur de concaténation, même s'il est noté "+", n'est pas commutatif comme l'est la somme, nous n'avons évidemment pas a+b=b+a.
Attention, par la suite, à ne pas confondre 1+2 qui est l'entier de valeur 3 avec "1"+"2" qui est la concaténation des chaînes "1" et "2" qui vaut "12" (et sûrement pas "3").
Il n'existe pas de convention pour désigner l'opérateur de concaténation. Nous pourrons également utiliser la notation ".".
Bien que cela ne doive pas arriver, nous pouvons considérer que l'opération de concaténation effectuée sur des caractères fonctionne et donne une chaîne de caractères.
Introduction à l'arithmétique booléenne
modifierEn informatique on introduit un nouveau type un peu moins familier : le booléen
. Au même titre que les entiers ou les réels : un booléen peut prendre un ensemble de valeurs et possède ses propres opérateurs.
Il n'est donné ici que quelques explications (nécessaires et suffisantes pour la suite du cours) sur le booléen. Il existe cependant toute une algèbre permettant de travailler sur les booléens. Un complément essentiel de ce cours d'algorithmique impérative est l'étude de l'algèbre de Boole.
Première approche
modifierEn mathématiques, les entiers ont été invités pour dénombrer, les réels pour représenter les distances, les volumes, etc... Le booléen a également pour utilité de représenter le réel. Il sert à représenter la véracité, c'est à dire à déclarer si une chose est vraie ou fausse.
L'ensemble des valeurs possibles d'un booléen est de deux (!). Ces deux valeurs sont notées VRAI
et FAUX
.
Voici deux exemples comportant des informations représentées par des booléens :
Premier exemple : Supposons que E soit en ensemble qui contient les éléments a, b, c et d.
- L'information cardinal de E est une information qui peut être représentée par un entier (ici 4).
- L'information b appartient à E est une information qui peut être représentée par un booléen (ici VRAI).
- L'information e appartient à E est une information qui peut être représentée par un booléen (ici FAUX).
- L'information 'E comporte au moins 2 éléments est une information qui peut être représentée par un booléen (ici VRAI).
Second exemple : Prenons l'ascenseur d'un immeuble.
- L'information nombre de personnes dans l'ascenseur peut être représentée par un entier.
- L'information il y a au moins une personne dans l'ascenseur peut être représentée par un booléen.
- L'information l'ascenseur est au premier étage peut être représentée par un booléen.
- etc.
Vous voyez donc qu'un booléen peut servir à représenter une multitude d'informations différentes mais ne remplace pas les entiers, les réels ou tout autre type. Chaque type à un usage et il convient d'user du booléen a bon escient tout comme on ne représente pas une distance avec un entier ou un dénombrement avec un réel.
Opérateurs booléens
modifierAu même titre que pour les autres types, il existe des opérateurs sur les booléen. Nous avons vu que la somme était un opérateur qui prenait deux entiers et renvoyait un résultat de type entier également. Il en va de même pour les booléen.
Opérateur | noté | Type des paramètres | Type du résultat | Valeur du résultat | Exemple | Remarque |
---|---|---|---|---|---|---|
négation | non ou ¬
|
un booléen | un booléen | Si VRAI alors FAUX . Si FAUX alors VRAI
|
|
non() est une fonction mathématique dite réciproque : non(non(truc)) vaut truc .
|
conjonction | et
|
deux booléens | un booléen | Le résultat vaut VRAI seulement si les deux paramètres sont VRAI . FAUX sinon.
|
|
On pourra aussi dire "Pour que le résultat soit VRAI il faut que tous les paramètres soient VRAI ".
|
disjonction | ou
|
deux booléens | un booléen | Le résultat vaut VRAI si au moins un des deux paramètres est VRAI . FAUX si tous les paramètres sont FAUX
|
|
Vous en serez déjà arrivé à ces conclusions : si b est un booléen,
b et FAUX
vautFAUX
quel que soitb
b ou VRAI
vautVRAI
quel que soitb
Ces opérateurs peuvent bien sûr former des expressions. Quelques exemples :
non(non(FAUX))
vaut FAUX((VRAI et FAUX) ou VRAI)
vautVRAI
La négation est prioritaire sur la conjonction. La conjonction est prioritaire sur la disjonction.
Tableau récapitulatif
modifierType | Ensemble de valeurs | Opérateurs |
---|---|---|
Entier | ℕ | + (somme), - (différence), * (multiplication), / (division entière)
|
Réel | ℝ | + (somme), - (différence), * (multiplication), / (division)
|
Booléen | {VRAI ; FAUX} | ¬ (négation), et (conjonction), ou (disjontion)
|
Caractère | ||
Chaîne de caractères | Concaténation |
Ce qu'il faut retenir
modifierCe chapitre est abstrait et ne donne rien de concret. N'apprenez pas par cœur, tout ceci se tient et est assez cohérent par rapport à ce que vous avez appris sur les mathématiques. Voici ce qui doit retenir votre attention :
- Retenez les noms des différents types et de leurs opérateurs en retenant bien quel opérateur fait quoi et avec quoi. Vous devriez pouvoir reconstruire de tête le tableau récapitulatif (encore une fois, vous ne devriez pas avoir à l'apprendre, vous devriez pouvoir le déduire des types).
- Retenez que les booléen, les caractères et les chaînes de caractères et leurs opérateurs fonctionnent exactement de la même façon que les entiers et les réels. Ce sont des types, qui ont un ensemble de valeurs possibles et des opérateurs spécifiques. On peut écrire des expressions à condition de respecter certaines règles.
- Essayez de voir un peu comment on manipule cette arithmétique booléenne qui, comme l'arithmétique entière, vous permet de calculer des expressions et d'en simplifier d'autres. Remarquez que cette arithmétique est plus simple puisque vous n'avez que deux valeurs possibles (c'est peu par rapport à l'infinité d'entiers...).
- Vous pouvez déjà faire les exercices sur ce chapitre. Si vous avez su les résoudre sans relire ce cours.
Les constantes, les variables
modifier
Dans un algorithme, il faut stocker les données à traiter. Certaines de ces données sont connues et ne varieront pas tout le long de l'algorithme : il s'agit des constantes. D'autres données peuvent être inconnues (elle seront fonction du choix de l'utilisateur, ou du temps...) ou susceptibles d'évoluer au cours de l'algorithme : il s'agit des variables.
Les variables
modifierToutes les variables ont un type. Dans chaque algorithme, toutes les variables et leurs types sont explicitées dans le lexique. On dit que la variable est déclarée.
D'un point de vue mathématique, la déclaration revient à l'expression "Soit ... un ...".
Le lexique est noté comme suit :
Variables identifiant_de_la_variable : type de la variable; ...
Un exemple
modifierVariables n : entier 1 : réel une réponse : booléen un nom de famille : chaîne de caractère
Dans cet exemple, nous avons cinq variables.
Du point de vue mathématique, on aurait pu énoncer "Soit n un entier", "Soit 1 un réel", "Soit vrai ou faux booléen", etc.
Les constantes
modifierDe la même façon, les constantes sont déclarées dans une partie Constantes
de cette façon :
Constantes nom_de_la_constante = valeur
Un exemple
modifierÀ priori, on peut considérer que PI ne risque pas de changer de valeur pendant un algorithme. On peut donc déclarer PI en tant que constante.
Constantes pi = 3.14 ...
Une seule constante est déclarée.
Les instructions, les blocs d'instructions
modifier
Nous avons vu qu'un algorithme est une séquence d'instructions ; de quoi s'agit-il exactement ? Les instructions sont les actions devant être effectuées par l'algorithme. Elle peuvent requérir que l'on précise certaines informations.
Deux instructions de base
modifierVoici expliquées deux instructions que l'on retrouvera très fréquemment dans des algorithmes. Il s'agit des instructions Afficher
et Lire
.
Afficher
modifierAfficher
permet d'afficher des données à l'écran et ainsi de communiquer avec l'utilisateur. Pour cette instruction, on doit préciser une expression qui sera évaluée avant d'être affichée.
Quelques exemples :
Afficher ("ceci est un exemple : on affiche une chaîne, sans utiliser de variables")
Ce programme affiche :
ceci est un exemple : on affiche une chaîne, sans utiliser de variables
Si l'algorithme contient
Constantes PI = 9
Le programme
Afficher(PI)
affiche
9
Lire
modifierLa fonction Lire
permet de demander à l'utilisateur de fournir des informations. Chaque information donnée par l'utilisateur est stockée dans une variable (attention au type !). Vous précisez cette variable dans les parenthèses.
Un exemple : nous réalisons un algorithme qui demande à l'utilisateur d'entrer son âge. Tout d'abord il apparaîtra dans le lexique :
Lexique age : entier (* l'âge donné par l'utilisateur *)
Pour demander l'âge :
Lire(age)
Les blocs d'instructions
modifierSouvent, l'exécution d'une seule instruction ne suffit pas pour faire un algorithme complet. Nous pouvons faire en sorte que plusieurs instructions soient considérées comme une seule. Pour cela, il faut créer un bloc d'instructions. Partout où l'on peut mettre une instruction, on peut mettre un bloc d'instructions.
Concrètement, on procède ainsi : les instructions sont séparées par un saut de ligne ou par ;
. Le bloc d'instruction est précédé de Début
et suivi de Fin
.
Un exemple :
Début instruction1 instruction2 Afficher("Cet affichage est la troisième instruction") instruction4 Fin
Une autre notation, courante dans les langages de programmation, est plus courte. Les instructions formant un bloc sont entre {
et }
.
L'assignation
modifier
L'assignation est une instruction qui consiste à inscrire dans une variable une valeur calculée depuis une expression. Attention : la nouvelle valeur affectée « écrase » la précédente.
C'est donc la deuxième façon que nous apprenons de donner une valeur à une variable. La première était d'utiliser l'instruction Lire
qui permet de demander la valeur à l'utilisateur. On peut dire que l'instruction Lire
est une forme particulière d'affectation.
Pour effectuer une assignation, on utilise l'instruction Assigner
. On précise entre parenthèses la variable affectée ainsi que l'expression de la valeur de l'affectation.
On pourra également noter l'affectation ←
ou :=
. Ce symbole peut être énoncé « prend pour valeur ». Attention toutefois à ne pas la noter =
bien que certains langages utilisent cette notation. Ce serait un dangereux raccourci de pensée avec les mathématiques (voir la mise en garde ci-dessous).
Un exemple : voici notre lexique
Lexique n : entier
On assigne n :
Assigner(n, 12)
À partir de maintenant la variable n vaut 12. Ainsi, l'instruction
Afficher(n)
provoquera l'affichage suivant :
12
Dans la suite du cours, nous utiliserons la notation ←
, moins lourde.
Mise en garde sur le parallèle avec les mathématiques
modifierAu moment de l'affectation, la valeur affecté est évaluée, c'est-à-dire calculée, les constantes et les variables sont donc remplacées par leurs valeurs respectives.
Exemple : dans le lexique nous avons :
Lexique a,b,c : entiers
a←1 b←2 c←a+b (* équivaut à c←2+1 et à c←3 *) afficher(c) (* affiche 3 *) b←5 afficher(c) (* affiche toujours 3 et non 6 *)
c conserve sa valeur tant qu'elle n'a pas été affectée, le changement de la valeur de b n'affecte pas la valeur de c.
Certains seraient tentés de noter l'affectation avec l'opérateur "=", elle est d'ailleurs notée ainsi dans le langage de programmation C. C'est pourtant une erreur vis-à-vis du sens mathématique de ce symbole. En effet, cette expression :
x = x+1
est tout à fait correcte en informatique si on considère l'affectation notée ainsi ; cela revient à incrémenter x. Mais du point de vue mathématique c'est une aberration. Voyons cela en appliquant une résolution d'équation du premier degré :
par soustraction de x dans les deux membres :
donc
En revanche, l'affectation notée := est valide en mathématique comme en informatique. En prenant cette convention, tout le monde est content...
Les exécutions conditionnelles
modifier
Vous savez que les instructions s'exécutent les unes après les autres. C'est intéressant mais insuffisant pour élaborer des algorithmes complexes. En effet, nous pourrions avoir besoin d'exécuter certaines instructions seulement dans un certain contexte. Les structures permettant d'imposer la succession des instructions sont appelées structures de contrôles. L'exécution conditionnelle, que nous allons voir ici, est la plus simple de ces structures de contrôles.
SI...ALORS...
modifierL'exécution conditionnelle permet de n'exécuter une instruction que si une certaine condition est remplie. La syntaxe est la suivante :
SI condition ALORS instruction FINSI
condition
est une expression booléenne. L'instruction n'est exécutée que si cette l'expression booléenne est évaluée àVRAI
. Sicondition
est évaluée àFAUX
aucune instruction n'est exécutée. Dans les deux cas, le programme poursuit son exécution par ce qui se trouve après le FINSI.instruction
est une instruction normale. Vous pouvez bien sûr exécuter plusieurs instructions : il suffit pour cela d'un bloc d'instructions.
Exemples
modifierSI FAUX ALORS Afficher("Cet affichage ne se produira jamais, la condition n'étant jamais VRAI") FINSI
Cet extrait d'algorithme n'a aucun intérêt. S'il est effacé du programme, on obtient un programme équivalent.
SI VRAI ALORS Afficher("Cet affichage se produit toujours") FINSI
Cet extrait d'algorithme n'a aucun intérêt. Il aurait évidemment suffit d'écrire :
Afficher ("Cet affichage se produit toujours")
...SINON
modifierIl est possible de préciser une instruction à exécuter si la condition n'est pas vérifiée, c'est-à-dire si elle est évaluée à FAUX
. Il suffit pour cela d'ajouter une partie SINON
entre ALORS
et FINSI
. Cette partie SINON
n'est pas toujours utile, elle est donc facultative.
SI condition ALORS instruction SINON instruction FINSI
Exemples
modifierSI condition ALORS Afficher("La condition vaut VRAI") SINON Afficher("La condition vaut FAUX") FINSI
Une équivalence utile
modifierRemarquez que ces deux blocs conditionnels sont équivalents :
SI condition ALORS instruction_A SINON instruction_B FINSI
SI non(condition) ALORS instruction_B SINON instruction_A FINSI
Les structures itératives
modifier
Les structures de contrôle itératives permettent d'exécuter plusieurs fois de suite une ou plusieurs instructions. Il en existe trois distinctes.
Structure POUR
modifierLa structure POUR permet d'exécuter une instruction un nombre connu de fois. Voici la syntaxe :
POUR i DE deb A fin FAIRE instruction FINPOUR
i
est l'identifiant d'une variable (qui doit bien sûr être déclarée).
deb
et fin
sont deux expressions de même type que i
: ce sont les valeurs entre lesquelles i va parcourir l'ensemble des valeurs intermédiaires.
La structure s'exécute de la façon suivante :
i
est affecté à la valeur dedeb
(i←deb
)- si
i
est différent defin
alors on exécuteinstruction
- incrémenter
i
(i←i+1
) - revenir au point 2
Il est évident que pour que le programme fonctionne deb
<fin
.
Exemples
modifierDix itérations
modifierLexique i : entier Début POUR i de 1 à 10 FAIRE Afficher(i); FINPOUR FIN
Ce programme va afficher :
1 2 3 4 5 6 7 8 9 10
Structure TANTQUE
modifierTANTQUE condition instruction FINTANTQUE
condition
est une expression booléenne, comme dans la structure SI condition ALORS...
Cette structure est exécutée comme suit :
- si
condition
est vraie : exécuterinstruction
sinon, continuer aprèsFINTANTQUE
- reprendre au point 1
La boucle infinie
modifierIl est possible grâce à cette structure de créer une boucle infinie :
TANTQUE VRAI instruction FTQ
Une boucle POUR
modifierIl est possible de simuler une boucle POUR
à l'aide d'un TANTQUE
i←deb TANTQUE i <= fin instruction i←i+1 FTQ
Exemples
modifierStructure REPETER
modifierREPETER instruction JUSQU'A condition
condition
est une expression booléenne.
Cette structure s'exécute comme suit :
- exécuter
instruction
- si
condition
est vrai : continuer au point 3 sinon, reprendre au point 1 - exécuter ce qui suit le
JUSQU'A
La boucle infinie
modifierIl est possible grâce à cette structure de créer une boucle infinie :
REPETER instruction JUSQU'A FAUX
Une boucle POUR
modifierIl est possible de simuler une boucle POUR
à l'aide d'un REPETER
i←deb REPETER instuction i←i+1 JUSQU'A i=fin
Exemples
modifierComment déterminer la structure à utiliser ?
modifierLe choix de la structure de contrôle se fait en fonction du nombre d'itérations à effectuer :
- si le nombre d'itérations est déterminé à l'avance, une boucle POUR est la plus appropriée,
- sinon :
- si la condition de boucle ne peut être évaluée avant la première itération, ou si au moins une itération doit être exécutée, la boucle REPETER est la plus appropriée,
- sinon la boucle TANT QUE est la plus appropriée.
Les tableaux
modifierPremière approche
modifierLe tableau est un nouveau type. Il contient un ensemble d'éléments indicés par des entiers ; on peut donc utiliser des variables tableaux.
Nous n'étudierons que les tableaux à une dimension également appelés vecteurs.
Spécification
modifierLes tableaux sont déclarés comme suit :
Lexique tab : tableau DEBUT à FIN de TYPE
- tab est l'identifiant de la variable tableau
- DEBUT est un entier : l'indice du premier élément du tableau, généralement 0 ou 1.
- FIN est un entier : l'indice du dernier élément, cela peut être un entier fixé ou, plus intéressant, une constante déclarée.
- On a évidemment FIN > DEBUT
- TYPE est le type de chacun des éléments du tableau.
Par exemple, un tableau d'entiers de 10 cases
Lexique tab : tableau 1 à 10 de entier
On accède au ième du tableau comme suit
tab[i]
- i est un entier qui doit évidemment être compris entre DEBUT et FIN (précisés dans la déclaration de tab)
- la variable
tab[i]
est donc du type TYPE (précisé dans la déclaration de tab)
Utilisation
modifierLa tableau est utilisé lorsqu'il faut stocker des suites de variables de même rôle. Par exemple, les notes d'un groupe d'étudiants en algorithmique impérative.
La structure POUR se prête très bien au parcours d'un tableau. En supposant le tableau tab déclarer comme suit :
Lexique tab : tableau MIN à MAX de TYPE
Il suffit pour afficher ses éléments de
Pour i de MIN à MAX Afficher(tab[i]) FP
Les procédures et les fonctions
modifierPremière approche
modifierLes procédures et les fonctions sont des sous-programmes qui permettent une réutilisation du code plus facile. En effet, si par exemple on code l'algorithme de calcul de T.V.A. et qu'on l'utilise à divers endroits du programme, plutôt que de recopier le code à chaque fois, il est préférable de créer un sous-programme de calcul. La recopie a toutefois les inconvénients suivants :
- La recopie du code s'accompagne souvent d'un changement des noms de variables, voire de la valeur de certains paramètres,
- Chaque copie du code augmente la taille des programmes source et compilé,
- La maintenance est plus difficile : s'il faut modifier l'algorithme, il faut modifier toutes les copies sans en oublier une seule.
L'utilisation d'un sous-programme évite tous ces problèmes :
- Les sous-programmes utilisent des variables locales et des paramètres formels, c'est-à-dire qu'on leur passe les valeurs (voire les variables, par adresse ou référence) qu'ils doivent utiliser.
- L'algorithme n'est codé qu'une seule fois, ce qui n'augmente pas la taille du programme.
- La maintenance est facilitée par le point précédent : s'il faut modifier l'algorithme, la modification n'a lieu qu'en un seul endroit.
Procédure et fonction : quelle différence ?
modifierUne procédure traite les informations qu'on lui passe, mais ne retourne, en général, aucun résultat. En général, cette procédure a un effet de bord.
Une fonction traite les informations qu'on lui passe, et retourne un résultat. Si la fonction n'a aucun effet de bord, on peut la comparer à une fonction mathématique.
- Effet de bord
- un sous-programme avec effet de bord modifie l'état global de l'application. En général, appeler deux fois un même sous-programme avec effet de bord en lui passant les mêmes paramètres ne produit pas le même résultat.
Le type enregistrement
modifierPremière approche
modifierL'enregistrement est une façon de créer un nouveau type, ou encore un méta-type, c'est-à-dire un type qui contient d'autres variables de types déjà définis.
Spécification
modifierOn déclare un nouveau type dans la partie Types
comme suit :
identifiant_du_type = enregistrement identifiant_première_sous_valeur : type_de_la_première_sous_valeur identifiant_deuxième_sous_valeur : type_de_la_deuxième_sous_valeur ... fin
on peut ensuite déclarer normalement les variables de ce nouveau type :
identifiant_variable : identifiant_du_type
Pour accéder à une sous-valeur de la variable, nous utiliserons l'expression :
identifiant_variable.identifiant_sous_valeur
Cette expression est du type de identifiant_sous_valeur
.
Exemple
modifierSupposons que nous voulions un nouveau type couple (de deux entiers). Nous allons déclarer le type couple comme suit :
couple = enregistrement a : entier b : entier fin
Supposons maintenant que nous avons le lexique suivant :
Lexique c : couple
Si nous assignons :
c.a ← 1 c.b ← 2 afficher(c.a) (* affichera 1 *)
Le projet sur les dates propose un travail complet sur le sujet.
Utilisation
modifierCela n'est pas obligatoire en algorithmique impérative, mais pour travailler sur un nouveau type , il convient de définir quelques fonctions élémentaires pour créer une variable à partir de ses sous-valeurs. Remarquez que les types de paramètres seront semblables aux types des sous-variables de nouveau type (exception faite dans le cas de sous-valeurs par défaut...).
Exemple
modifierPour reprendre notre exemple, nous pourrions créer une fonction :
fonction creerCouple(m, n : entiers) (* créer un couple à partir de ses deux éléments *) lexique NouveauCouple : couple debut NouveauCouple.a ← m NouveauCouple.b ← n renvoyer NouveauCouple fin
L'algorithme au final : vue d'ensemble
modifierAu final, l'algorithme se compose de la façon suivante :
Algorithme
suivi du nom de l'algorithme- De la déclaration des procédures et des fonctions
- De la déclaration des constantes de l'algorithme principal
- De la déclaration des variables de l'algorithme principal
- De l'algorithme principal
Algorithme nom_de_l'algorithme Fonction1(paramètre1 : type du paramètre 1 (* objet du paramètre1 *) paramètre2 : type du paramètre 1 (* objet du paramètre2 *)) : type de la valeur de retour Constantes locales de la Fonction1 constante1 = valeur_de_la_constante1 constante2 = valeur_de_la_constante2 constante3 = valeur_de_la_constante3 Variables locales de la Fonction1 variable1 : type_de_la_variable1 variable2 : type_de_la_variable2 variable3 : type_de_la_variable3 Début instruction1 instruction2 Retourner valeur Fin Procédure1(E|S|ES paramètre1 : type du paramètre 1 (* objet du paramètre1 *) E|S|ES paramètre1 : type du paramètre 2 (* objet du paramètre2 *) E|S|ES paramètre1 : type du paramètre 3 (* objet du paramètre3 *)) Constantes locales de la Procédure1 constante1 = valeur_de_la_constante1 constante2 = valeur_de_la_constante2 constante3 = valeur_de_la_constante3 Variables locales de la Procédure1 variable1 : type_de_la_variable1 variable2 : type_de_la_variable2 variable3 : type_de_la_variable3 Début instruction1 instruction2 Fin Constantes de l'algorithme principal constante1 = valeur_de_la_constante1 constante2 = valeur_de_la_constante2 constante3 = valeur_de_la_constante3 Variables de l'algorithme principal variable1 : type_de_la_variable1 variable2 : type_de_la_variable2 variable3 : type_de_la_variable3 Début instruction1 instruction2 Fin
Exercices
modifierTypes, expressions et opérateurs
modifierQuestions théoriques
modifier- Citez des exemples de types
- Donnez un opérateur polymorphe
- Écrire un programme qui saisit trois nombres dans un ordre donné et les fait sortir dans l'ordre inverse d'entrée.
Solutions :
- booléen, entier, réel, caractère, chaîne de caractères
- + (polymorphe car fonctionne avec des entiers et des réels)
Types et valeurs
modifierDonner le type des expressions suivantes et leur valeur
- 0
- 1+2
- 0.0+1.0
- "a"
- "a"."b"="b"
- "a"."b"
Donner le type de a et de l'expression :
- a+1
- a."b"
- a=1.0
Solutions
modifier- entier : 0
- entier : 3
- réel : 1.0
- caractère : "a"
- booléen : FAUX
- chaîne de caractères : "ab"
Questions avec la variable a :
- entier ; a entier
- chaîne de caractères : a caractère ou chaîne de caractères
- booléen : a réel
Calcul booléen
modifierQuelle est la valeur de ces expressions booléennes ?
- non(VRAI)
- VRAI et FAUX
- FAUX ou FAUX
- VRAI et VRAI
- non(FAUX ou VRAI)
- FAUX et ((VRAI et VRAI) ou (VRAI et (FAUX ou (VRAI et FAUX)))))
- VRAI ou (VRAI et (FAUX ou ((FAUX et VRAI) ou VRAI)))
a
et b
sont des booléens, simplifier les expressions :
- non(non(a))
- non(non(non(b)))
- faux ou a
- faux et a
- vrai et a
- vrai ou a
- a et non(a)
- a ou non(a)
- non(a=b) et (a=b)
Solutions
modifier- FAUX
- FAUX
- FAUX
- VRAI
- FAUX
- Il suffit de lire "FAUX et ..." au début de l'expression pour savoir tout de suite le résultat. Quel que soit ce qu'il y avait après le
et
cela aurait été FAUX. - De même, il suffit de lire "VRAI ou ..." au début de l'expression pour savoir tout de suite le résultat : peu importe ce qu'il y a après le
ou
, cela aurait été VRAI - ...
Simplifications :
- a
- non(b)
- a
- faux
- a
- vrai
- faux
- vrai
- faux
Condition
modifierDonner un extrait d'algorithme équivalent à celui-ci sans utiliser de sinon
:
si condition alors instruction1 sinon instruction2
Solution
modifiersi condition alors instruction1 finsi si non(condition) alors instruction2 finsi
Boucles
modifier13 à 47
modifierDonner une boucle qui affiche les entiers de 13 à 47
Solution:
Pour i de 13 à 37 Afficher(i) FP
de 5 en 5
modifierDonner une boucle affichant les entiers de 5 en 5 et de 5 à 100
Solutions :
i←0 Répéter i←i+5 afficher(i) Jusqu'à i=100
i←5 Répéter afficher(i) i←i+5 Jusqu'à i=105
pour i de 5 à 100 si i mod 5 = 0 alors afficher i fp
pour i de 1 à 20 afficher(5*i) fp
Remarque : ces algorithmes fonctionnent tous mais certains sont plus efficaces que d'autres. Cette réflexion est laissée au lecteur.
Tableaux
modifierSelon la déclaration suivante
tab : tableau 0 à 10 de T
Le tableau contient 11 éléments.
Procédures et fonctions
modifierÉcrire des fonctions en procédures, des procédures en fonctions.