 |
Articles
Commentaires
vendredi 30 novembre 2018
td de algorithme
PARTIE 1
Exercice 1.1
Quelles seront les valeurs des variables A et B après exécution des instructions suivantes ?
Variables A, B en Entier
Début
A ← 1
B ← A + 3
A ← 3
Fin
Exercice 1.2
Quelles seront les valeurs des variables A, B et C après exécution des instructions suivantes ?
Variables A, B, C en Entier
Début
A ← 5
B ← 3
C ← A + B
A ← 2
C ← B – A
Fin
Exercice 1.4
Quelles seront les valeurs des variables A, B et C après exécution des instructions suivantes ? Variables A, B, C en Entier
Début
A ← 3
B ← 10
C ← A + B
B ← A + B
A ← C
Fin
Exercice 1.5
Quelles seront les valeurs des variables A et B après exécution des instructions suivantes ?
Variables A, B en Entier
Début
A ← 5
B ← 2
A ← B
B ← A
Fin
Moralité : les deux dernières instructions permettent-elles d’échanger les deux valeurs de B et A ? Si l’on inverse les deux dernières instructions, cela change-t-il quelque chose ?
Exercice 1.6
Plus difficile, mais c’est un classique absolu, qu’il faut absolument maîtriser :
écrire un algorithme permettant d’échanger les valeurs de deux variables A et B, et ce quel que soit leur contenu préalable.
Exercice 1.7
Une variante du précédent : on dispose de trois variables A, B et C. Ecrivez un algorithme transférant à B la valeur de A, à C la valeur de B et à A la valeur de C (toujours quels que soient les contenus préalables de ces variables).
Exercice 1.8
Que produit l’algorithme suivant ?
Variables A, B, C en Caractères
Début
A ← "423"
B ← "12"
C ← A + B
Fin
Exercice 1.9
Que produit l’algorithme suivant ?
Variables A, B, C en Caractères
Début
A ← "423"
B ← "12"
C ← A & B
Fin
PARTIE 2
Exercice 2.1
Quel résultat produit le programme suivant ?
Variables val, double numériques
Début
Val ← 231
Double ← Val * 2
Ecrire Val
Ecrire Double
Fin
Exercice 2.2
Ecrire un programme qui demande un nombre à l’utilisateur, puis qui calcule et affiche le carré de ce nombre.
Exercice 2.3
Ecrire un programme qui lit le prix HT d’un article, le nombre d’articles et le taux de TVA, et qui fournit le prix total TTC correspondant. Faire en sorte que des libellés apparaissent clairement.
Exercice 2.4
Ecrire un algorithme utilisant des variables de type chaîne de caractères, et affichant quatre variantes possibles de la célèbre « belle marquise, vos beaux yeux me font mourir d’amour ». On ne se soucie pas de la ponctuation, ni des majuscules.
PARTIE 3
Exercice 3.1
Ecrire un algorithme qui demande un nombre à l’utilisateur, et l’informe ensuite si ce nombre est positif ou négatif (on laisse de côté le cas où le nombre vaut zéro).
Exercice 3.2
Ecrire un algorithme qui demande deux nombres à l’utilisateur et l’informe ensuite si leur produit est négatif ou positif (on laisse de côté le cas où le produit est nul). Attention toutefois : on ne doit pas calculer le produit des deux nombres.
Exercice 3.3
Ecrire un algorithme qui demande trois noms à l’utilisateur et l’informe ensuite s’ils sont rangés ou non dans l’ordre alphabétique.
Exercice 3.4
Ecrire un algorithme qui demande un nombre à l’utilisateur, et l’informe ensuite si ce nombre est positif ou négatif (on inclut cette fois le traitement du cas où le nombre vaut zéro).
Exercice 3.5
Ecrire un algorithme qui demande deux nombres à l’utilisateur et l’informe ensuite si le produit est négatif ou positif (on inclut cette fois le traitement du cas où le produit peut être nul). Attention toutefois, on ne doit pas calculer le produit !
Exercice 3.6
Ecrire un algorithme qui demande l’âge d’un enfant à l’utilisateur. Ensuite, il l’informe de sa catégorie :
- "Poussin" de 6 à 7 ans
- "Pupille" de 8 à 9 ans
- "Minime" de 10 à 11 ans
- "Cadet" après 12 ans
Peut-on concevoir plusieurs algorithmes équivalents menant à ce résultat ?
PARTIE 4
Exercice 4.1
Formulez un algorithme équivalent à l’algorithme suivant :
Si Tutu > Toto + 4 OU Tata = "OK" Alors
Tutu ← Tutu + 1
Sinon
Tutu ← Tutu – 1
Finsi
Exercice 4.2
Cet algorithme est destiné à prédire l'avenir, et il doit être infaillible !
Il lira au clavier l’heure et les minutes, et il affichera l’heure qu’il sera une minute plus tard. Par exemple, si l'utilisateur tape 21 puis 32, l'algorithme doit répondre :
"Dans une minute, il sera 21 heure(s) 33".
NB : on suppose que l'utilisateur entre une heure valide. Pas besoin donc de la vérifier.
Exercice 4.3
De même que le précédent, cet algorithme doit demander une heure et en afficher une autre. Mais cette fois, il doit gérer également les secondes, et afficher l'heure qu'il sera une seconde plus tard.
Par exemple, si l'utilisateur tape 21, puis 32, puis 8, l'algorithme doit répondre : "Dans une seconde, il sera 21 heure(s), 32 minute(s) et 9 seconde(s)".
NB : là encore, on suppose que l'utilisateur entre une date valide.
Exercice 4.4
Un magasin de reprographie facture 0,10 E les dix premières photocopies, 0,09 E les vingt suivantes et 0,08 E au-delà. Ecrivez un algorithme qui demande à l’utilisateur le nombre de photocopies effectuées et qui affiche la facture correspondante.
Exercice 4.5
Les habitants de Zorglub paient l’impôt selon les règles suivantes :
- les hommes de plus de 20 ans paient l’impôt
- les femmes paient l’impôt si elles ont entre 18 et 35 ans
- les autres ne paient pas d’impôt
Le programme demandera donc l’âge et le sexe du Zorglubien, et se prononcera donc ensuite sur le fait que l’habitant est imposable.
Exercice 4.6
Les élections législatives, en Guignolerie Septentrionale, obéissent à la règle suivante :
- lorsque l'un des candidats obtient plus de 50% des suffrages, il est élu dès le premier tour.
- en cas de deuxième tour, peuvent participer uniquement les candidats ayant obtenu au moins 12,5% des voix au premier tour.
Exercice 4.7
Une compagnie d'assurance automobile propose à ses clients quatre familles de tarifs identifiables par une couleur, du moins au plus onéreux : tarifs bleu, vert, orange et rouge. Le tarif dépend de la situation du conducteur :
- un conducteur de moins de 25 ans et titulaire du permis depuis moins de deux ans, se voit attribuer le tarif rouge, si toutefois il n'a jamais été responsable d'accident. Sinon, la compagnie refuse de l'assurer.
- un conducteur de moins de 25 ans et titulaire du permis depuis plus de deux ans, ou de plus de 25 ans mais titulaire du permis depuis moins de deux ans a le droit au tarif orange s'il n'a jamais provoqué d'accident, au tarif rouge pour un accident, sinon il est refusé.
- un conducteur de plus de 25 ans titulaire du permis depuis plus de deux ans bénéficie du tarif vert s'il n'est à l'origine d'aucun accident et du tarif orange pour un accident, du tarif rouge pour deux accidents, et refusé au-delà
- De plus, pour encourager la fidélité des clients acceptés, la compagnie propose un contrat de la couleur immédiatement la plus avantageuse s'il est entré dans la maison depuis plus d'un an.
Ecrire l'algorithme permettant de saisir les données nécessaires (sans contrôle de saisie) et de traiter ce problème. Avant de se lancer à corps perdu dans cet exercice, on pourra réfléchir un peu et s'apercevoir qu'il est plus simple qu'il n'en a l'air (cela s'appelle faire une analyse !)
Exercice 4.8
Ecrivez un algorithme qui a près avoir demandé un numéro de jour, de mois et d'année à l'utilisateur, renvoie s'il s'agit ou non d'une date valide. Cet exercice est certes d’un manque d’originalité affligeant, mais après tout, en algorithmique comme ailleurs, il faut connaître ses classiques ! Et quand on a fait cela une fois dans sa vie, on apprécie pleinement l’existence d’un type numérique « date » dans certains langages…).
Il n'est sans doute pas inutile de rappeler rapidement que le mois de février compte 28 jours, sauf si l’année est bissextile, auquel cas il en compte 29. L’année est bissextile si elle est divisible par quatre. Toutefois, les années divisibles par 100 ne sont pas bissextiles, mais les années divisibles par 400 le sont. Ouf !
Un dernier petit détail : vous ne savez pas, pour l’instant, exprimer correctement en pseudo-code l’idée qu’un nombre A est divisible par un nombre B. Aussi, vous vous contenterez d’écrire en bons télégraphistes que A divisible par B se dit « A dp B ».
PARTIE 5
Exercice 5.1
Ecrire un algorithme qui demande à l’utilisateur un nombre compris entre 1 et 3 jusqu’à ce que la réponse convienne.
Exercice 5.2
Ecrire un algorithme qui demande un nombre compris entre 10 et 20, jusqu’à ce que la réponse convienne. En cas de réponse supérieure à 20, on fera apparaître un message : « Plus petit ! », et inversement, « Plus grand ! » si le nombre est inférieur à 10.
Exercice 5.3
Ecrire un algorithme qui demande un nombre de départ, et qui ensuite affiche les dix nombres suivants. Par exemple, si l'utilisateur entre le nombre 17, le programme affichera les nombres de 18 à 27.
Exercice 5.4
Ecrire un algorithme qui demande un nombre de départ, et qui ensuite écrit la table de multiplication de ce nombre, présentée comme suit (cas où l'utilisateur entre le nombre 7) :
Table de 7 :
7 x 1 = 7
7 x 2 = 14
7 x 3 = 21
…
7 x 10 = 70
Exercice 5.5
Ecrire un algorithme qui demande un nombre de départ, et qui calcule la somme des entiers jusqu’à ce nombre. Par exemple, si l’on entre 5, le programme doit calculer :
1 + 2 + 3 + 4 + 5 = 15
NB : on souhaite afficher uniquement le résultat, pas la décomposition du calcul.
Exercice 5.6
Ecrire un algorithme qui demande un nombre de départ, et qui calcule sa factorielle.
NB : la factorielle de 8, notée 8 !, vaut
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
Exercice 5.7
Ecrire un algorithme qui demande successivement 20 nombres à l’utilisateur, et qui lui dise ensuite quel était le plus grand parmi ces 20 nombres :
Entrez le nombre numéro 1 : 12
Entrez le nombre numéro 2 : 14
etc.
Entrez le nombre numéro 20 : 6
Le plus grand de ces nombres est : 14
Modifiez ensuite l’algorithme pour que le programme affiche de surcroît en quelle position avait été saisie ce nombre :
C’était le nombre numéro 2
Exercice 5.8
Réécrire l’algorithme précédent, mais cette fois-ci on ne connaît pas d’avance combien l’utilisateur souhaite saisir de nombres. La saisie des nombres s’arrête lorsque l’utilisateur entre un zéro.
Exercice 5.9
Lire la suite des prix (en euros entiers et terminée par zéro) des achats d’un client. Calculer la somme qu’il doit, lire la somme qu’il paye, et simuler la remise de la monnaie en affichant les textes "10 Euros", "5 Euros" et "1 Euro" autant de fois qu’il y a de coupures de chaque sorte à rendre.
Exercice 5.10
Écrire un algorithme qui permette de connaître ses chances de gagner au tiercé, quarté, quinté et autres impôts volontaires.
On demande à l’utilisateur le nombre de chevaux partants, et le nombre de chevaux joués. Les deux messages affichés devront être :
Dans l’ordre : une chance sur X de gagner Dans le désordre : une chance sur Y de gagner
X et Y nous sont donnés par la formule suivante, si n est le nombre de chevaux partants et p le nombre de chevaux joués (on rappelle que le signe ! signifie "factorielle", comme dans l'exercice 5.6 ci-dessus) :
X = n ! / (n - p) !
Y = n ! / (p ! * (n – p) !)
NB : cet algorithme peut être écrit d’une manière simple, mais relativement peu performante. Ses performances peuvent être singulièrement augmentées par une petite astuce. Vous commencerez par écrire la manière la plus simple, puis vous identifierez le problème, et écrirez une deuxième version permettant de le résoudre.
PARTIE 6
Exercice 6.1
Ecrire un algorithme qui déclare et remplisse un tableau de 7 valeurs numériques en les mettant toutes à zéro.
Exercice 6.2
Ecrire un algorithme qui déclare et remplisse un tableau contenant les six voyelles de l’alphabet latin.
Exercice 6.3
Ecrire un algorithme qui déclare un tableau de 9 notes, dont on fait ensuite saisir les valeurs par l’utilisateur.
Exercice 6.4
Que produit l’algorithme suivant ?
Tableau Nb(5) en Entier
Variable i en Entier
Début
Pour i ← 0 à 5
Nb(i) ← i * i
i suivant
Pour i ← 0 à 5
Ecrire Nb(i)
i suivant
Fin
Peut-on simplifier cet algorithme avec le même résultat ?
Exercice 6.5
Que produit l’algorithme suivant ?
Tableau N(6) en Entier
Variables i, k en Entier
Début
N(0) ← 1
Pour k ← 1 à 6
N(k) ← N(k-1) + 2
k Suivant
Pour i ← 0 à 6
Ecrire N(i) i suivant
Fin
Peut-on simplifier cet algorithme avec le même résultat ?
Exercice 6.6
Que produit l’algorithme suivant ?
Tableau Suite(7) en Entier
Variable i en Entier
Début
Suite(0) ← 1
Suite(1) ← 1
Pour i ← 2 à 7
Suite(i) ← Suite(i-1) + Suite(i-2)
i suivant
Pour i ← 0 à 7
Ecrire Suite(i)
i suivant
Fin
Exercice 6.7
Ecrivez la fin de l’algorithme 6.3 afin que le calcul de la moyenne des notes soit effectué et affiché à l’écran.
Exercice 6.8
Ecrivez un algorithme permettant à l’utilisateur de saisir un nombre quelconque de valeurs, qui devront être stockées dans un tableau. L’utilisateur doit donc commencer par entrer le nombre de valeurs qu’il compte saisir. Il effectuera ensuite cette saisie. Enfin, une fois la saisie terminée, le programme affichera le nombre de valeurs négatives et le nombre de valeurs positives.
Exercice 6.9
Ecrivez un algorithme calculant la somme des valeurs d’un tableau (on suppose que le tableau a été préalablement saisi).
Exercice 6.10
Ecrivez un algorithme constituant un tableau, à partir de deux tableaux de même longueur préalablement saisis. Le nouveau tableau sera la somme des éléments des deux tableaux de départ.
Le Schtroumpf sera :
3 * 4 + 3 * 8 + 3 * 7 + 3 * 12 + 6 * 4 + 6 * 8 + 6 * 7 + 6 * 12 = 279
Exercice 6.12
Ecrivez un algorithme qui permette la saisie d’un nombre quelconque de valeurs, sur le principe de l’ex 6.8. Toutes les valeurs doivent être ensuite augmentées de 1, et le nouveau tableau sera affiché à l’écran.
Exercice 6.13
Ecrivez un algorithme permettant, toujours sur le même principe, à l’utilisateur de saisir un nombre déterminé de valeurs. Le programme, une fois la saisie terminée, renvoie la plus grande valeur en précisant quelle position elle occupe dans le tableau. On prendra soin d’effectuer la saisie dans un premier temps, et la recherche de la plus grande valeur du tableau dans un second temps.
Exercice 6.14
Toujours et encore sur le même principe, écrivez un algorithme permettant, à l’utilisateur de saisir les notes d'une classe. Le programme, une fois la saisie terminée, renvoie le nombre de ces notes supérieures à la moyenne de la classe.
PARTIE 7
Exercice 7.2
Ecrivez un algorithme qui trie un tableau dans l’ordre décroissant.
Vous écrirez bien entendu deux versions de cet algorithme, l'une employant le tri par insertion, l'autre le tri à bulles.
Exercice 7.3
Ecrivez un algorithme qui inverse l’ordre des éléments d’un tableau dont on suppose qu'il a été préalablement saisi (« les premiers seront les derniers… »)
Exercice 7.4
Ecrivez un algorithme qui permette à l’utilisateur de supprimer une valeur d’un tableau préalablement saisi. L’utilisateur donnera l’indice de la valeur qu’il souhaite supprimer. Attention, il ne s’agit pas de remettre une valeur à zéro, mais bel et bien de la supprimer du tableau lui-même ! Si le tableau de départ était :
Exercice 7.5
Ecrivez l'algorithme qui recherche un mot saisi au clavier dans un dictionnaire. Le dictionnaire est supposé être codé dans un tableau préalablement rempli et trié.
PARTIE 8
Exercice 8.1
Écrivez un algorithme remplissant un tableau de 6 sur 13, avec des zéros.
Exercice 8.2
Exercice 8.3
Exercice 8.4
Quel résultat produira cet algorithme ?
Tableau T(3, 1) en Entier
Variables k, m, en Entier
Début
Pour k ← 0 à 3
Pour m ← 0 à 1
T(k, m) ← k + m
m Suivant
k Suivant
Pour k ← 0 à 3
Pour m ← 0 à 1
Ecrire T(k, m)
m Suivant
k
Suivant Fin
Exercice 8.5
Mêmes questions, en remplaçant la ligne :
T(k, m) ← k + m
par
T(k, m) ← 2 * k + (m + 1)
puis par :
T(k, m) ← (k + 1) + 4 * m
Exercice 8.6
Soit un tableau T à deux dimensions (12, 8) préalablement rempli de valeurs numériques. Écrire un algorithme qui recherche la plus grande valeur au sein de ce tableau.
Exercice 8.7
Écrire un algorithme de jeu de dames très simplifié. L’ordinateur demande à l’utilisateur dans quelle case se trouve son pion (quelle ligne, quelle colonne). On met en place un contrôle de saisie afin de vérifier la validité des valeurs entrées.
Ensuite, on demande à l’utilisateur quel mouvement il veut effectuer : 0 (en haut à gauche), 1 (en haut à droite), 2 (en bas à gauche), 3 (en bas à droite).
Si le mouvement est impossible (i.e. on sort du damier ), on le signale à l’utilisateur et on s’arrête là . Sinon, on déplace le pion et on affiche le damier résultant, en affichant un « O » pour une case vide et un « X » pour la case où se trouve le pion.
PARTIE 9
Exercice 9.1
Parmi ces affectations (considérées indépendamment les unes des autres), lesquelles provoqueront des erreurs, et pourquoi ?
Variables A, B, C en Numérique
Variables D, E en Caractère
A ← Sin(B)
A ← Sin(A + B * C)
B ← Sin(A) – Sin(D)
D ← Sin(A / B)
C ← Cos(Sin(A)
Exercice 9.2
Ecrivez un algorithme qui demande un mot à l’utilisateur et qui affiche à l’écran le nombre de lettres de ce mot (c'est vraiment tout bête).
Exercice 9.3
Ecrivez un algorithme qui demande une phrase à l’utilisateur et qui affiche à l’écran le nombre de mots de cette phrase. On suppose que les mots ne sont séparés que par des espaces (et c'est déjà un petit peu moins bête).
Exercice 9.4
Ecrivez un algorithme qui demande une phrase à l’utilisateur et qui affiche à l’écran le nombre de voyelles contenues dans cette phrase. On pourra écrire deux solutions. La première déploie une condition composée bien fastidieuse. La deuxième, en utilisant la fonction Trouve, allège considérablement l'algorithme.
Exercice 9.5
Ecrivez un algorithme qui demande une phrase à l’utilisateur. Celui-ci entrera ensuite le rang d’un caractère à supprimer, et la nouvelle phrase doit être affichée (on doit réellement supprimer le caractère dans la variable qui stocke la phrase, et pas uniquement à l’écran).
Exercice 9.6 - Cryptographie
1 Un des plus anciens systèmes de cryptographie (aisément déchiffrable) consiste à décaler les lettres d’un message pour le rendre illisible. Ainsi, les A deviennent des B, les B des C, etc. Ecrivez un algorithme qui demande une phrase à l’utilisateur et qui la code selon ce principe. Comme dans le cas précédent, le codage doit s’effectuer au niveau de la variable stockant la phrase, et pas seulement à l’écran.Exercice 9.7 - Cryptographie 2 - le chiffre de César
Une amélioration (relative) du principe précédent consiste à opérer avec un décalage non de 1, mais d’un nombre quelconque de lettres. Ainsi, par exemple, si l’on choisit un décalage de 12, les A deviennent des M, les B des N, etc.
Réalisez un algorithme sur le même principe que le précédent, mais qui demande en plus quel est le décalage à utiliser. Votre sens proverbial de l'élégance vous interdira bien sûr une série de vingt-six "Si...Alors"
Exercice 9.8 - Cryptographie 3
Une technique ultérieure de cryptographie consista à opérer non avec un décalage systématique, mais par une substitution aléatoire. Pour cela, on utilise un alphabet-clé, dans lequel les lettres se succèdent de manière désordonnée, par exemple :
HYLUJPVREAKBNDOFSQZCWMGITX
C’est cette clé qui va servir ensuite à coder le message. Selon notre exemple, les A deviendront des H, les B des Y, les C des L, etc.
Ecrire un algorithme qui effectue ce cryptage (l’alphabet-clé sera saisi par l’utilisateur, et on suppose qu'il effectue une saisie correcte).
Exercice 9.9 - Cryptographie 4 - le chiffre de Vigenère
Un système de cryptographie beaucoup plus difficile à briser que les précédents fut inventé au XVIe siècle par le français Vigenère. Il consistait en une combinaison de différents chiffres de César.
On peut en effet écrire 25 alphabets décalés par rapport à l’alphabet normal :
- l’alphabet qui commence par B et finit par …YZA
- l’alphabet qui commence par C et finit par …ZAB
- etc.
Le codage va s’effectuer sur le principe du chiffre de César : on remplace la lettre d’origine par la lettre occupant la même place dans l’alphabet décalé. Mais à la différence du chiffre de César, un même message va utiliser non un, mais plusieurs alphabets décalés. Pour savoir quels alphabets doivent être utilisés, et dans quel ordre, on utilise une clé. Si cette clé est "VIGENERE" et le message "Il faut coder cette phrase", on procèdera comme suit : La première lettre du message, I, est la 9e lettre de l’alphabet normal. Elle doit être codée en utilisant l’alphabet commençant par la première lettre de la clé, V. Dans cet alphabet, la 9e lettre est le D. I devient donc D.
La deuxième lettre du message, L, est la 12e lettre de l’alphabet normal. Elle doit être codée en utilisant l’alphabet commençant par la deuxième lettre de la clé, I. Dans cet alphabet, la 12e lettre est le S. L devient donc S, etc. Quand on arrive à la dernière lettre de la clé, on recommence à la première.
Ecrire l’algorithme qui effectue un cryptage de Vigenère, en demandant bien sûr au départ la clé à l’utilisateur.
Exercice 9.10
Ecrivez un algorithme qui demande un nombre entier à l’utilisateur. L’ordinateur affiche ensuite le message "Ce nombre est pair" ou "Ce nombre est impair" selon le cas.
Exercice 9.11
Ecrivez les algorithmes qui génèrent un nombre Glup aléatoire tel que …
- 0 =< Glup < 2
- –1 =< Glup < 1
- 1,35 =< Glup < 1,65
- Glup émule un dé à six faces
- –10,5 =< Glup < +6,5
- Glup émule la somme du jet simultané de deux dés à six faces
PARTIE 10
Exercice 10.3
On travaille avec le fichier du carnet d’adresses en champs de largeur fixe.
Ecrivez un algorithme qui permet à l’utilisateur de saisir au clavier un nouvel individu qui sera ajouté à ce carnet d’adresses.
Exercice 10.4
Même question, mais cette fois le carnet est supposé être trié par ordre alphabétique. L’individu doit donc être inséré au bon endroit dans le fichier.
Exercice 10.5
Ecrivez un algorithme qui permette de modifier un renseignement (pour simplifier, disons uniquement le nom de famille) d’un membre du carnet d’adresses. Il faut donc demander à l’utilisateur quel est le nom à modifier, puis quel est le nouveau nom, et mettre à jour le fichier. Si le nom recherché n'existe pas, le programme devra le signaler.
Exercice 10.6
Ecrivez un algorithme qui trie les individus du carnet d’adresses par ordre alphabétique.
Exercice 10.7
Soient Toto.txt et Tata.txt deux fichiers dont les enregistrements ont la même structure. Ecrire un algorithme qui recopie tout le fichier Toto dans le fichier Tutu, puis à sa suite, tout le fichier Tata (concaténation de fichiers).
Exercice 10.8
Ecrire un algorithme qui supprime dans notre carnet d'adresses tous les individus dont le mail est invalide (pour employer un critère simple, on considèrera que sont invalides les mails ne comportant aucune arobase, ou plus d'une arobase).
Exercice 10.9
Les enregistrements d’un fichier contiennent les deux champs Nom (chaîne de caractères) et Montant (Entier). Chaque enregistrement correspond à une vente conclue par un commercial d’une société.
On veut mémoriser dans un tableau, puis afficher à l'écran, le total de ventes par vendeur. Pour simplifier, on suppose que le fichier de départ est déjà trié alphabétiquement par vendeur.
NOTIONS COMPLEMENTAIRES
PARTIE 12
NOTIONS COMPLEMENTAIRES
Une fois n’est pas coutume, ce chapitre ne sera l’objet d’aucun exercice. Cela ne veut pas dire pour autant que ce qui s’y trouve n’est pas intéressant. Non mais des fois.
1. PROGRAMMATION STRUCTUREE
Petit retour sur une notion très rapidement survolée plus haut : celle de « programmation structurée ». En fait, nous avons jusqu’à présent, tels Monsieur Jourdain, fait de la programmation structurée sans le savoir. Aussi, plutôt qu’expliquer longuement en quoi cela consiste, je préfère prendre le problème par l'autre bout : en quoi cela ne consiste pas.
Dans certains langages (historiquement, ce sont souvent des langages anciens), les lignes de programmation portent des numéros. Et les lignes sont exécutées par la machine dans l’ordre de ces numéros. Jusqu’ici, en soi, pas de problème. Mais l’astuce est que tous ces langages, il existe une instruction de branchement, notée aller à en pseudo-code, instruction qui envoie directement le programme à la ligne spécifiée. Inversement, ce type de langage ne comporte pas d’instructions comme FinTantQue, ou FinSi, qui « ferment » un bloc.
Prenons l’exemple d’une structure « Si … Alors … Sinon »
Vous voyez le topo : un programme écrit dans ce type de langages se présente comme une suite de branchements emmêlés les uns dans les autres. D’une part, on ne peut pas dire que cela favorise la lisibilité du programme. D’autre part, c’est une source importante d’erreurs, car tôt ou tard on oublie un « aller à », ou on un met un de trop, etc. A fortiori lorsqu’on complique un algorithme existant, cela peut devenir un jungle inextricable.
A l’inverse, la programmation structurée, surtout si l’on prend soin de rationaliser la présentation en mettant des lignes de commentaires et en pratiquant l’indentation, évite des erreurs, et révèle sa structure logique de manière très claire.
Le danger est que si la plupart des langages de programmation utilisés sont structurés, ils offrent tout de même la plupart du temps la possibilité de pratiquer la programmation non structurée. Dans ce cas, les lignes ne sont pas désignées par des numéros, mais certaines peuvent être repérées par des noms (dits « étiquettes ») et on dispose d’une instruction de branchement.
Une règle d’hygiène absolue est de programmer systématiquement de manière structurée, sauf impératif contraire fixé par le langage (ce qui est aujourd'hui de plus en plus rare).
Autrement dit, même quand un langage vous offre une possibilité de faire des entorses à la programmation structurée, il ne faut s’en saisir sous aucun prétexte.
2. INTERPRETATION ET COMPILATION
Avec ce paragraphe, on sort un peu de l’algorithmique proprement dite pour entrer dans le domaine plus technique de la réalisation pratique. Ou, si l’on préfère, ces dernières lignes sont l’apothéose, le bouquet final, l’extase ultime, la consécration grandiose, de ce cours. En toute modestie, bien sûr.
Jusqu’ici, nous avons travaillé sur la première étape de la réalisation d’un programme : la rédaction de l'algorithme.
C’est à cela que sert un langage : à vous épargner la programmation en binaire (une pure horreur, vous vous en doutez) et vous permettre de vous faire comprendre de l’ordinateur d’une manière (relativement) lisible. C’est pourquoi tout langage, à partir d’un programme écrit, doit obligatoirement procéder à une traduction en langage machine pour que ce programme soit exécutable.
Il existe deux stratégies de traduction, ces deux stratégies étant parfois disponibles au sein du même langage.
- le langage traduit les instructions au fur et à mesure qu’elles se présentent. Cela s’appelle la compilation à la volée, ou l’interprétation.
- le langage commence par traduire l’ensemble du programme en langage machine, constituant ainsi un deuxième programme (un deuxième fichier) distinct physiquement et logiquement du premier. Ensuite, et ensuite seulement, il exécute ce second programme. Cela s’appelle la compilation
Toute application destinée à un usage professionnel (ou même, tout simplement sérieux) est forcément une application compilée.
3. UNE LOGIQUE VICELARDE : LA PROGRAMMATION RECURSIVE
Vous savez comment sont les informaticiens : on ne peut pas leur donner quoi que ce soit sans qu’ils essayent de jouer avec, et le pire, c’est qu’ils y réussissent.
La programmation des fonctions personnalisées a donné lieu à l'essor d’une logique un peu particulière, adaptée en particulier au traitement de certains problèmes mathématiques (ou de jeux) : la programmation récursive. Pour vous expliquer de quoi il retourne, nous allons reprendre un exemple cher à vos coeurs : le calcul d’une factorielle (là, je sentais que j’allais encore me faire des copains).
Rappelez-vous : la formule de calcul de la factorielle d’un nombre n s’écrit :
N ! = 1 x 2 x 3 x … x n
Nous avions programmé cela aussi sec avec une boucle Pour, et roule Raoul. Mais une autre manière de voir les choses, ni plus juste, ni moins juste, serait de dire que quel que soit le nombre n : n ! = n x (n-1) !
En bon français : la factorielle d’un nombre, c’est ce nombre multiplié par la factorielle du nombre précédent. Encore une fois, c’est une manière ni plus juste ni moins juste de présenter les choses ; c’est simplement une manière différente.
Si l’on doit programmer cela, on peut alors imaginer une fonction Fact, chargée de calculer la factorielle. Cette fonction effectue la multiplication du nombre passé en argument par la factorielle du nombre précédent. Et cette factorielle du nombre précédent va bien entendu être elle-même calculée par la fonction Fact.
Autrement dit, on va créer une fonction qui pour fournir son résultat, va s’appeler elle-même un certain nombre de fois. C’est cela, la récursivité.
Toutefois, il nous manque une chose pour finir : quand ces auto-appels de la fonction Fact vont-ils s’arrêter ? Cela n’aura-t-il donc jamais de fin ? Si, bien sûr, rassure-toi, ô public, la récursivité, ce n’est pas Les Feux de L’Amour. On s’arrête quand on arrive au nombre 1, pour lequel la factorielle est par définition 1.
Cela produit l’écriture suivante, un peu déconcertante certes, mais parfois très pratique :
PROCEDURES ET FONCTIONS
PARTIE 11
PROCEDURES ET FONCTIONS
1. FONCTIONS PERSONNALISEES
1.1 De quoi s'agit-il ?
Une application, surtout si elle est longue, a toutes les chances de devoir procéder aux mêmes traitements, ou à des traitements similaires, à plusieurs endroits de son déroulement. Par exemple, la saisie d’une réponse par oui ou par non (et le contrôle qu’elle implique), peuvent être répétés dix fois à des moments différents de la même application, pour dix questions différentes.
La manière la plus évidente, mais aussi la moins habile, de programmer ce genre de choses, c'est bien entendu de répéter le code correspondant autant de fois que nécessaire. Apparemment, on ne se casse pas la tête : quand il faut que la machine interroge l'utilisateur, on recopie les lignes de codes voulues en ne changeant que le nécessaire, et roule Raoul. Mais en procédant de cette manière, la pire qui soit, on se prépare des lendemains qui déchantent...
déchantent... D'abord, parce que si la structure d'un programme écrit de cette manière peut paraître simple, elle est en réalité inutilement lourdingue. Elle contient des répétitions, et pour peu que le programme soit joufflu, il peut devenir parfaitement illisible. Or, le fait d'être facilement modifiable donc lisible, y compris - et surtout - par ceux qui ne l'ont pas écrit est un critère essentiel pour un programme informatique ! Dès que l'on programme non pour soi-même, mais dans le cadre d'une organisation (entreprise ou autre), cette nécessité se fait sentir de manière aiguë. L'ignorer, c'est donc forcément grave.
En plus, à un autre niveau, une telle structure pose des problèmes considérables de maintenance : car en cas de modification du code, il va falloir traquer toutes les apparitions plus ou moins identiques de ce code pour faire convenablement la modification ! Et si l'on en oublie une, patatras, on a laissé un bug.
Il faut donc opter pour une autre stratégie, qui consiste à séparer ce traitement du corps du programme et à regrouper les instructions qui le composent en un module séparé. Il ne restera alors plus qu'à appeler ce groupe d'instructions (qui n'existe donc désormais qu’en un exemplaire unique) à chaque fois qu’on en a besoin. Ainsi, la lisibilité est assurée ; le programme devient modulaire, et il suffit de faire une seule modification au bon endroit, pour que cette modification prenne effet dans la totalité de l’application.
Le corps du programme s’appelle alors la procédure principale, et ces groupes d’instructions auxquels on a recours s’appellent des fonctions et des sous-procédures (nous verrons un peu plus loin la différence entre ces deux termes).
On le voit bien, il y a là une répétition quasi identique du traitement à accomplir. A chaque fois, on demande une réponse par Oui ou Non, avec contrôle de saisie. La seule chose qui change, c'est le nom de la variable dans laquelle on range la réponse. Alors, il doit bien y avoir un truc.
La solution, on vient de le voir, consiste à isoler les instructions demandant une réponse par Oui ou Non, et à appeler ces instructions à chaque fois que nécessaire. Ainsi, on évite les répétitions inutiles, et on a découpé notre problème en petits morceaux autonomes.
Nous allons donc créer une fonction dont le rôle sera de renvoyer la réponse (oui ou non) de l'utilisateur. Ce mot de "fonction", en l'occurrence, ne doit pas nous surprendre : nous avons étudié précédemment des fonctions fournies avec le langage, et nous avons vu que le but d'une fonction était de renvoyer une valeur. Eh bien, c'est exactement la même chose ici, sauf que c'est nous qui allons créer notre propre fonction, que nous appellerons RepOuiNon :
On remarque au passage l’apparition d’un nouveau mot-clé : Renvoyer, qui indique quelle valeur doit prendre la fonction lorsqu'elle est utilisée par le programme. Cette valeur renvoyée par la fonction (ici, la valeur de la variable Truc) est en quelque sorte contenue dans le nom de la fonction lui-même, exactement comme c’était le cas dans les fonctions prédéfinies.
Une fonction s'écrit toujours en-dehors de la procédure principale. Selon les langages, cela peut prendre différentes formes. Mais ce qu'il faut comprendre, c'est que ces quelques lignes de codes sont en quelque sorte des satellites, qui existent en dehors du traitement lui-même. Simplement, elles sont à sa disposition, et il pourra y faire appel chaque fois que nécessaire. Si l'on reprend notre exemple, une fois notre fonction RepOuiNon écrite, le programme principal comprendra les lignes :
1.2 Passage d'arguments
Reprenons l’exemple qui précède et analysons-le. On écrit un message à l'écran, puis on appelle la fonction RepOuiNon pour poser une question ; puis, un peu plus loin, on écrit un autre message à l'écran, et on appelle de nouveau la fonction pour poser la même question, etc. C’est une démarche acceptable, mais qui peut encore être améliorée : puisque avant chaque question, on doit écrire un message, autant que cette écriture du message figure directement dans la fonction appelée. Cela implique deux choses :
- lorsqu’on appelle la fonction, on doit lui préciser quel message elle doit afficher avant de lire la réponse
- la fonction doit être « prévenue » qu’elle recevra un message, et être capable de le récupérer pour l’afficher
. Une remarque importante : là, on n'a passé qu’un seul argument en entrée. Mais bien entendu, on peut en passer autant qu’on veut, et créer des fonctions avec deux, trois, quatre, etc. arguments ; Simplement, il faut éviter d'être gourmands, et il suffit de passer ce dont on en a besoin, ni plus, ni moins !
Dans le cas que l'on vient de voir, le passage d'un argument à la fonction était élégant, mais pas indispensable. La preuve, cela marchait déjà très bien avec la première version. Mais on peut imaginer des situations où il faut absolument concevoir la fonction de sorte qu'on doive lui transmettre un certain nombre d'arguments si l'on veut qu'elle puisse remplir sa tâche. Prenons, par exemple, toutes les fonctions qui vont effectuer des calculs. Que ceux-ci soient simples ou compliqués, il va bien falloir envoyer à la fonction les valeurs grâce auxquelles elle sera censé produire son résultat (pensez tout bêtement à une fonction sur le modèle d'Excel, telle que celle qui doit calculer une somme ou une moyenne). C'est également vrai des fonctions qui traiteront des chaînes de caractères. Bref, dans 99% des cas, lorsqu'on créera une fonction, celle-ci devra comporter des arguments.
1.3 Deux mots sur l'analyse fonctionnelle
Comme souvent en algorithmique, si l'on s'en tient à la manière dont marche l'outil, tout cela n'est en réalité pas très compliqué. Les fonctions personnalisées se déduisent très logiquement de la manière nous nous avons déjà expérimenté les fonctions prédéfinies.
Le plus difficile, mais aussi le plus important, c'est d'acquérir le réflexe de constituer systématiquement les fonctions adéquates quand on doit traiter un problème donné, et de flairer la bonne manière de découper son algorithme en différentes fonctions pour le rendre léger, lisible et performant.
Cette partie de la réflexion s'appelle d'ailleurs l'analyse fonctionnelle d'un problème, et c'est toujours par elle qu'il faut commencer : en gros, dans un premier temps, on découpe le traitement en modules (algorithmique fonctionnelle), et dans un deuxième temps, on écrit chaque module (algorithmique classique). Cependant, avant d'en venir là, il nous faut découvrir deux autres outils, qui prennent le relais là où les fonctions deviennent incapables de nous aider.
2. SOUS-PROCEDURES
2.1 Généralités
Les fonctions, c'est bien, mais dans certains cas, ça ne nous rend guère service.
Il peut en effet arriver que dans un programme, on ait à réaliser des tâches répétitives, mais que ces tâches n'aient pas pour rôle de générer une valeur particulière, ou qu'elles aient pour rôle d'en générer plus d'une à la fois. Vous ne voyez pas de quoi je veux parler ? Prenons deux exemples.
Premier exemple. Imaginons qu'au cours de mon application, j'aie plusieurs fois besoin d'effacer l'écran et de réafficher un bidule comme un petit logo en haut à gauche. On pourrait se dire qu'il faut créer une fonction pour faire cela. Mais quelle serait la valeur renvoyée par la fonction ? Aucune ! Effacer l'écran, ce n'est pas produire un résultat stockable dans une variable, et afficher un logo non plus. Voilà donc une situation ou j'ai besoin de répéter du code, mais où ce code n'a pas comme rôle de produire une valeur.
Deuxième exemple. Au cours de mon application, je dois plusieurs fois faire saisir un tableau d'entiers (mais à chaque fois, un tableau différent). Là encore, on serait tenté d'effectuer toutes ces saisies de tableaux dans une seule fonction. Mais problème, une fonction ne peut renvoyer qu'une seule valeur à la fois. Elle ne peut donc renvoyer un tableau, qui est une série de valeurs distinctes.
Alors, dans ces deux cas, faute de pouvoir traiter l'affaire par une fonction, devra-t-on en rester au code répétitif dont nous venons de dénoncer si vigoureusement les faiblesses ? Mmmmmh ? Vous vous doutez bien que non. Heureusement, tout est prévu, il y a une solution. Et celle-ci consiste à utiliser des sous-procédures.
En fait, les fonctions - que nous avons vues - ne sont finalement qu'un cas particulier des sous-procédures - que nous allons voir : celui où doit être renvoyé vers la procédure appelante une valeur et une seule. Dans tous les autres cas (celui où on ne renvoie aucune valeur, comme celui ou en en renvoie plusieurs), il faut donc avoir recours non à la forme particulière et simplifiée (la fonction), mais à la forme générale (la sous-procédure).
Parlons donc de ce qui est commun aux sous-procédures et aux fonctions, mais aussi de ce qui les différencie.
2.2 Le problème des arguments
En effet, il nous reste à examiner ce qui peut bien se trouver dans les parenthèses, à la place des points de suspension, aussi bien dans la déclaration de la sous-procédure que dans l'appel. Vous vous en doutez bien : c'est là que vont se trouver les outils qui vont permettre l'échange d'informations entre la procédure principale et la sous-procédure (en fait, cette dernière phrase est trop restrictive : mieux vaudrait dire : entre la procédure appelante et la procédure appelée. Car une sous-procédure peut très bien en appeler elle-même une autre afin de pouvoir accomplir sa tâche)
De même qu'avec les fonctions, les valeurs qui circulent depuis la procédure (ou la fonction) appelante vers la sous-procédure appelée se nomment des arguments, ou des paramètres en entrée de la sous-procédure. Comme on le voit, qu'il s'agisse des sous-procédure ou des fonctions, ces choses jouant exactement le même rôle (transmettre une information depuis le code donneur d'ordres jusqu'au code sous-traitant), elle portent également le même nom. Unique petite différence, on a précisé cette fois qu'il s'agissait d'arguments, ou de paramètres, en entrée. Pourquoi donc ?
Tout simplement parce que que dans une sous-procédure, on peut être amené à vouloir renvoyer des résultats vers le programme principal ; or, là, à la différence des fonctions, rien n'est prévu : la sous-procédure, en tant que telle, ne "renvoie" rien du tout (comme on vient de le voir, elle est d'ailleurs dépourvue de l'instruction "renvoyer"). Ces résultats que la sous-procédure doit transmettre à la procédure appelante devront donc eux aussi être véhiculés par des paramètres. Mais cette fois, il s'agira de paramètres fonctionnant dans l'autre sens (du sous-traitant vers le donneur d'ordres) : on les appellera donc des paramètres en sortie.
Ceci nous permet de reformuler en d'autres termes la vérité fondamentale apprise un peu plus haut : toute sous-procédure possédant un et un seul paramètre en sortie peut également être écrite sous forme d'une fonction (et entre nous, c'est une formulation préférable car un peu plus facile à comprendre et donc à retenir).
Jusque là, ça va ? Si oui, prenez un cachet d'aspirine et poursuivez la lecture. Si non, prenez un cachet d'aspirine et recommencez depuis le début. Et dans les deux cas, n'oubliez pas le grand verre d'eau pour faire passer l'aspirine.
Il nous reste un détail à examiner, détail qui comme vous vous en doutez bien, a une certaine importance : comment fait-on pour faire comprendre à un langage quels sont les paramètres qui doivent fonctionner en entrée et quels sont ceux qui doivent fonctionner en sortie...
2.3 Comment ça marche tout ça ?
En fait, si je dis qu'un paramètre est "en entrée" ou "en sortie", j'énonce quelque chose à propos de son rôle dans le programme. Je dis ce que je souhaite qu'il fasse, la manière dont je veux qu'il se comporte. Mais les programmes eux-mêmes n'ont cure de mes désirs, et ce n'est pas cette classification qu'ils adoptent. C'est toute la différence entre dire qu'une prise électrique sert à brancher un rasoir ou une cafetière (ce qui caractérise son rôle), et dire qu'elle est en 220 V ou en 110 V (ce qui caractérise son type technique, et qui est l'information qui intéresse l'électricien). A l'image des électriciens, les langages se contrefichent de savoir quel sera le rôle (entrée ou sortie) d'un paramètre. Ce qu'ils exigent, c'est de connaître leur voltage... pardon, le mode de passage de ces paramètres. Il n'en existe que deux :
- le passage par valeur
- le passage par référence
...Voyons de plus près de quoi il s'agit.
Reprenons l'exemple que nous avons déjà utilisé plus haut, celui de notre fonction RepOuiNon. Comme nous l'avons vu, rien ne nous empêche de réécrire cette fonction sous la forme d'une procédure (puisqu'une fonction n'est qu'un cas particulier de sous-procédure). Nous laisserons pour l"instant de côté la question de savoir comment renvoyer la réponse (contenue dans la variable Truc) vers le programme principal. En revanche, nous allons
déclarer que Msg est un paramètre dont la transmission doit se faire par valeur. Cela donnera la chose suivante :
Lorsque le programme principal arrive sur la première ligne, il affecte la variable M avec le libellé "Êtes-vous marié". La ligne suivante déclenche l'exécution de la sous-procédure. Celle-ci crée aussitôt une variable Msg. Celle-ci ayant été déclarée comme un paramètre passé par valeur, Msg va être affecté avec le même contenu que M. Cela signifie que Msg est dorénavant une copie de M. Les informations qui étaient contenues dans M ont été intégralement recopiées (en double) dans Msg. Cette copie subsistera tout au long de l'exécution de la sous-procédure RepOuiNon et sera détruite à la fin de celle-ci.
Une conséquence essentielle de tout cela est que si d'aventure la sous-procédure RepOuiNon contenait une instruction qui modifiait le contenu de la variable Msg, cela n'aurait aucune espèce de répercussion sur la procédure principale en général, et sur la variable M en particulier. La sous-procédure ne travaillant que sur une copie de la variable qui a été fournie par le programme principal, elle est incapable, même si on le souhaitait, de modifier la valeur de celle-ci. Dit d'une autre manière, dans une procédure, un paramètre passé par valeur ne peut être qu'un paramètre en entrée.
C'est en même temps une limite (aggravée par le fait que les informations ainsi recopiées occupent dorénavant deux fois plus de place en mémoire) et une sécurité : quand on transmet un paramètre par valeur, on est sûr et certain que même en cas de bug dans la sous-procédure, la valeur de la variable transmise ne sera jamais modifiée par erreur (c'est-à-dire écrasée) dans le programme principal.
Admettons à présent que nous déclarions un second paramètre, Truc, en précisant cette fois qu'il sera transmis
par référence. Et adoptons pour la procédure l'écriture suivante :
Dès lors, toute modification de Truc sera immédiatement redirigée, par ricochet en quelque sorte, sur T. Truc n'est pas une variable ordinaire : elle ne contient pas de valeur, mais seulement la référence à une valeur, qui elle, se trouve ailleurs (dans la variable T). Il s'agit donc d'un genre de variable complètement nouveau, et différent de ce que nous avons vu jusque là. Ce type de variable porte un nom : on l'appelle un pointeur. Tous les paramètres passés par référence sont des pointeurs, mais les pointeurs ne se limitent pas aux paramètres passés par référence (même si ce sont les seuls que nous verrons dans le cadre de ce cours). Il faut bien comprendre que ce type de variable étrange est géré directement par les langages : à partir du moment où une variable est considérée comme un pointeur, toute affectation de cette variable se traduit automatiquement par la modification de la variable sur laquelle elle pointe.
Passer un paramètre par référence, cela présente donc deux avantages. Et d'une, on gagne en occupation de place mémoire, puisque le paramètre en question ne recopie pas les informations envoyées par la procédure appelante, mais qu'il se contente d'en noter l'adresse. Et de deux, cela permet d'utiliser ce paramètre tant en lecture (en entrée) qu'en écriture (en sortie), puisque toute modification de la valeur du paramètre aura pour effet de modifier la variable correspondante dans la procédure appelante. Nous pouvons résumer tout cela par un petit tableau :
3. VARIABLES PUBLIQUES ET PRIVEES
Résumons la situation. Nous venons de voir que nous pouvions découper un long traitement comportant éventuellement des redondances (notre application) en différents modules. Et nous avons vu que les informations pouvaient être transmises entre ces modules selon deux modes :
- si le module appelé est une fonction, par le retour du résultat
- dans tous les cas, par la transmission de paramètres (que ces paramètres soient passés par valeur ou par référence)
Par défaut, une variable est déclarée au sein d'une procédure ou d'une fonction. Elle est donc créée avec cette procédure, et disparaît avec elle. Durant tout le temps de son existence, une telle variable n'est visible que par la procédure qui l'a vu naître. Si je crée une variable Toto dans une procédure Bidule, et qu'en cours de route, ma procédure Bidule appelle une sous-procédure Machin, il est hors de question que Machin puisse accéder à Toto, ne serait-ce que pour connaître sa valeur (et ne parlons pas de la modifier). Voilà pourquoi ces variables par défaut sont dites privées, ou locales.
Mais à côté de cela, il est possible de créer des variables qui certes, seront déclarées dans une procédure, mais qui du moment où elles existeront, seront des variables communes à toutes les procédures et fonctions de l'application. Avec de telles variables, le problème de la transmission des valeurs d'une procédure (ou d'une fonction) à l'autre ne se pose même plus : la variable Truc, existant pour toute l'application, est accessible et modifiable depuis n'importe quelle ligne de code de cette application. Plus besoin donc de la transmettre ou de la renvoyer. Une telle variable est alors dite publique, ou globale.
La manière dont la déclaration d'une variable publique doit être faites est évidemment fonction de chaque langage de programmation.
En pseudo-code algorithmique, on pourra utiliser le mot-clé Publique :
Variable Publique Toto en Numérique
Alors, pourquoi ne pas rendre toutes les variables publiques, et s'épargner ainsi de fastidieux efforts pour passer des paramètres ? C’est très simple, et c'est toujours la même chose : les variables globales consomment énormément de ressources en mémoire. En conséquence, le principe qui doit présider au choix entre variables publiques et privées doit être celui de l’économie de moyens : on ne déclare comme publiques que les variables qui doivent absolument l’être. Et chaque fois que possible, lorsqu’on crée une sous-procédure, on utilise le passage de paramètres plutôt que des variables publiques.
4. PEUT-ON TOUT FAIRE ?
A cette question, la réponse est bien évidemment : oui, on peut tout faire. Mais c'est précisément la raison pour laquelle on peut vite en arriver à faire aussi absolument n'importe quoi.
N'importe quoi, c'est quoi ? C'est par exemple, comme on vient de le voir, mettre des variables globales partout, sous prétexte que c'est autant de paramètres qu'on n'aura pas à passer.
Mais on peut imaginer d'autres atrocités.
Par exemple, une fonction, dont un des paramètres d'entrée serait passé par référence, et modifié par la fonction. Ce qui signifierait que cette fonction produirait non pas un, mais deux résultats. Autrement dit, que sous des dehors de fonctions, elle se comporterait en réalité comme une sous-procédure.
Ou inversement, on peut concevoir une procédure qui modifierait la valeur d'un paramètre (et d'un seul) passé par référence. Il s'agirait là d'une procédure qui en réalité, serait une fonction. Quoique ce dernier exemple ne soit pas d'une gravité dramatique, il participe de la même logique consistant à embrouiller le code en faisant passer un outil pour un autre, au lieu d'adopter la structure la plus claire et la plus lisible possible.
Enfin, il ne faut pas écarter la possibilité de programmeurs particulièrement vicieux, qui par un savant mélange de paramètres passés par référence, de variables globales, de procédures et de fonctions mal choisies, finiraient par accoucher d'un code absolument illogique, illisible, et dans lequel la chasse à l'erreur relèverait de l'exploit.
Trèfle de plaisanteries : le principe qui doit guider tout programmeur est celui de la solidité et de la clarté du code. Une application bien programmée est une application à l'architecture claire, dont les différents modules font ce qu'ils disent, disent ce qu'il font, et peuvent être testés (ou modifiés) un par un sans perturber le reste de la construction. Il convient donc :
- 1. de limiter au minimum l'utilisation des variables globales. Celles-ci doivent être employées avec nos célèbres amis italo-arméniens, c'est-à-dire avec parcimonie et à bon escient.
- 2. de regrouper sous forme de modules distincts tous les morceaux de code qui possèdent une certaine unité fonctionnelle (programmation par "blocs"). C'est-à-dire de faire la chasse aux lignes de codes redondantes, ou quasi-redondantes.
- 3. de faire de ces modules des fonctions lorsqu'ils renvoient un résultat unique, et des sous-procédures dans tous les autres cas (ce qui implique de ne jamais passer un paramètre par référence à une fonction : soit on n'en a pas besoin, soit on en a besoin, et ce n'est alors plus une fonction).
5. ALGORITHMES FONCTIONNELS
Pour clore ce chapitre, voici quelques mots supplémentaires à propos de la structure générale d’une application. Comme on l'a dit à plusieurs reprises, celle-ci va couramment être formée d’une procédure principale, et de fonctions et de sous-procédures (qui vont au besoin elles-mêmes en appeler d’autres, etc.). L’exemple typique est celui d’un menu, ou d’un sommaire, qui « branche » sur différents traitements, donc différentes sous-procédures.
L’algorithme fonctionnel de l’application est le découpage et/ou la représentation graphique de cette structure générale, ayant comme objectif de faire comprendre d’un seul coup d’oeil quelle procédure fait quoi, et quelle procédure appelle quelle autre. L’algorithme fonctionnel est donc en quelque sorte la construction du squelette de l’application. Il se situe à un niveau plus général, plus abstrait, que l’algorithme normal, qui lui, détaille pas à pas les traitements effectués au sein de chaque procédure.
Dans la construction – et la compréhension – d’une application, les deux documents sont indispensables, et constituent deux étapes successives de l’élaboration d’un projet. La troisième – et dernière – étape, consiste à écrire, pour chaque procédure et fonction, l’algorithme détaillé.
Exemple de réalisation d’un algorithme fonctionnel : Le Jeu du Pendu
Vous connaissez tous ce jeu : l’utilisateur doit deviner un mot choisi au hasard par l’ordinateur, en un minimum d’essais. Pour cela, il propose des lettres de l’alphabet. Si la lettre figure dans le mot à trouver, elle s’affiche. Si elle n’y figure pas, le nombre des mauvaises réponses augmente de 1. Au bout de dix mauvaises réponses, la partie est perdue.
Ce petit jeu va nous permettre de mettre en relief les trois étapes de la réalisation d’un algorithme un peu complexe ; bien entendu, on pourrait toujours ignorer ces trois étapes, et se lancer comme un dératé directement dans la gueule du loup, à savoir l’écriture de l’algorithme définitif. Mais, sauf à être particulièrement doué, mieux vaut respecter le canevas qui suit, car les difficultés se résolvent mieux quand on les saucissonne…
Etape 1 : le dictionnaire des données
Le but de cette étape est d’identifier les informations qui seront nécessaires au traitement du problème, et de choisir le type de codage qui sera le plus satisfaisant pour traiter ces informations. C’est un moment essentiel de la réflexion, qu’il ne faut surtout pas prendre à la légère… Or, neuf programmeurs débutants sur dix bâclent cette réflexion, quand ils ne la zappent pas purement et simplement. La punition ne se fait généralement pas attendre longtemps ; l’algorithme étant bâti sur de mauvaises fondations, le programmeur se rend compte tout en l’écrivant que le choix de codage des informations, par exemple, mène à des impasses. La précipitation est donc punie par le fait qu’on est obligé de tout reprendre depuis le début, et qu’on a au total perdu bien davantage de temps qu’on en a cru en gagner…
Donc, avant même d’écrire quoi que ce soit, les questions qu’il faut se poser sont les suivantes :
- de quelles informations le programme va-t-il avoir besoin pour venir à bout de sa tâche ?
- pour chacune de ces informations, quel est le meilleur codage ? Autrement dit, celui qui sans gaspiller de la place mémoire, permettra d’écrire l’algorithme le plus simple ?
Pour le jeu du pendu, voici la liste des informations dont on va avoir besoin :
- une liste de mots (si l’on veut éviter que le programme ne propose toujours le même mot à trouver, ce qui risquerait de devenir assez rapidement lassant…)
- le mot à deviner
- la lettre proposée par le joueur à chaque tour
- le nombre actuel de mauvaises réponses
- et enfin, last but not least, l’ensemble des lettres déjà trouvées par le joueur. Cette information est capitale ; le programme en aura besoin au moins pour deux choses : d’une part, pour savoir si le mot entier a été trouvé. D’autre part, pour afficher à chaque tour l’état actuel du mot (je rappelle qu’à chaque tour, les lettres trouvées sont affichées en clair par la machine, les lettres restant à deviner étant remplacées par des tirets).
- à cela, on pourrait ajouter une liste comprenant l’ensemble des lettres déjà proposées par le joueur, qu’elles soient correctes ou non ; ceci permettra d’interdire au joueur de proposer à nouveau une lettre précédemment jouée.
Cette liste d’informations n’est peut-être pas exhaustive ; nous aurons vraisemblablement besoin au cours de l’algorithme de quelques variables supplémentaires (des compteurs de boucles, des variables temporaires, etc.). Mais les informations essentielles sont bel et bien là. Se pose maintenant le problème de choisir le mode de codage le plus futé. Si, pour certaines informations, la question va être vite réglée, pour d’autres, il va falloir faire des choix (et si possible, des choix intelligents !). C’est parti, mon kiki :
- Pour la liste des mots à trouver, il s’agit d’un ensemble d’informations de type alphanumérique. Ces informations pourraient faire partie du corps de la procédure principale, et être ainsi stockées en mémoire vive, sous la forme d’un tableau de chaînes. Mais ce n’est certainement pas le plus judicieux. Toute cette place occupée risque de peser lourd inutilement, car il n’y a aucun intérêt à stocker l’ensemble des mots en mémoire vive. Et si l’on souhaite enrichir la liste des mots à trouver, on sera obligé de réécrire des lignes de programme… Conclusion, la liste des mots sera bien plus à sa place dans un fichier texte, dans lequel le programme ira piocher un seul mot, celui qu’il faudra trouver. Nous constituerons donc un fichier texte, appelé dico.txt, dans lequel figurera un mot par ligne (par enregistrement).
- Le mot à trouver, lui, ne pose aucun problème : il s’agit d’une information simple de type chaîne, qui pourra être stocké dans une variable appelée mot, de type caractère.
- De même, la lettre proposée par le joueur est une information simple de type chaîne, qui sera stockée dans une variable appelée lettre, de type caractère.
- Le nombre actuel de mauvaises réponses est une information qui pourra être stockée dans une variable numérique de type entier simple appelée MovRep.
- L’ensemble des lettres trouvées par le joueur est typiquement une information qui peut faire l’objet de plusieurs choix de codage ; rappelons qu’au moment de l’affichage, nous aurons besoin de savoir pour chaque lettre du mot à deviner si elle a été trouvée ou non. Une première possibilité, immédiate, serait de disposer d’une chaîne de caractères comprenant l’ensemble des lettres précédemment trouvées. Cette solution est loin d’être mauvaise, et on pourrait tout à fait l’adopter. Mais ici, on fera une autre choix, ne serait-ce que pour varier les plaisirs : on va se doter d’un tableau de booléens, comptant autant d’emplacements qu’il y a de lettres dans le mot à deviner. Chaque emplacement du tableau correspondra à une lettre du mot à trouver, et indiquera par sa valeur si la lettre a été découverte ou non (faux, la lettre n’a pas été devinée, vrai, elle l’a été). La correspondance entre les éléments du tableau et le mot à deviner étant immédiate, la programmation de nos boucles en sera facilitée. Nous baptiserons notre tableau de booléens du joli nom de « verif ».
- Enfin, l’ensemble des lettres proposées sera stockée sans soucis dans une chaîne de caractères nommée Propos.
Etape 2 : l’algorithme fonctionnel
On peut à présent passer à la réalisation de l’algorithme fonctionnel, c’est-à-dire au découpage de notre problème en blocs logiques. Le but de la manoeuvre est multiple :
- faciliter la réalisation de l’algorithme définitif en le tronçonnant en plus petits morceaux.
- Gagner du temps et de la légèreté en isolant au mieux les sous-procédures et fonctions qui méritent de l’être. Eviter ainsi éventuellement des répétitions multiples de code au cours du programme, répétitions qui ne diffèrent les unes des autres qu'à quelques variantes près.
- Permettre une division du travail entre programmeurs, chacun se voyant assigner la programmation de sous-procédures ou de fonctions spécifiques (cet aspect est essentiel dès qu’on quitte le bricolage personnel pour entrer dans le monde de la programmation professionnelle, donc collective).
Cette procédure principale, justement, va ensuite avoir nécessairement la forme d’une boucle Tantque : en effet , tant que la partie n’est pas finie, on recommence la série des traitements qui représentent un tour de jeu. Mais comment, justement, savoir si la partie est finie ? Elle peut se terminer soit parce que le nombre de mauvaises réponses a atteint 10, soit parce que toutes les lettres du mot ont été trouvées. Le mieux sera donc de confier l’examen de tout cela à une fonction spécialisée, PartieFinie, qui renverra une valeur numérique (0 pour signifier que la partie est en cours, 1 en cas de victoire, 2 en cas de défaite).
Passons maintenant au tour de jeu.
La première chose à faire, c’est d’afficher à l’écran l’état actuel du mot à deviner : un mélange de lettres en clair (celles qui ont été trouvées) et de tirets (correspondant aux lettres non encore trouvées). Tout ceci pourra être pris en charge par une sous-procédure spécialisée, appelée AffichageMot. Quant à l’initialisation des différentes variables, elle pourra être placée, de manière classique, dans la procédure principale elle-même.
Ensuite, on doit procéder à la saisie de la lettre proposée, en veillant à effectuer les contrôles de saisie adéquats. Là encore, une fonction spécialisée, SaisieLettre, sera toute indiquée.
Une fois la proposition faite, il convient de vérifier si elle correspond ou non à une lettre à deviner, et à en tirer les conséquences. Ceci sera fait par une sous-procédure appelée VérifLettre.
Enfin, une fois la partie terminée, on doit afficher les conclusions à l’écran ; on déclare à cet effet une dernière procédure, FinDePartie.
Nous pouvons, dans un algorithme fonctionnel complet, dresser un tableau des différentes procédures et fonctions, exactement comme nous l’avons fait juste avant pour les données (on s’épargnera cette peine dans le cas présent, ce que nous avons écrit ci-dessus suffisant amplement. Mais dans le cas d’une grosse application, un tel travail serait nécessaire et nous épargnerait bien des soucis).
On peut aussi schématiser le fonctionnement de notre application sous forme de blocs, chacun des blocs représentant une fonction ou une sous-procédure :
A ce stade, l’analyse dite fonctionnelle est terminée. Les fondations (solides, espérons-le) sont posées pour finaliser l’application.
Etape 3 : Algorithmes détaillés
Normalement, il ne nous reste plus qu’à traiter chaque procédure isolément. On commencera par les sous-procédures et fonctions, pour terminer par la rédaction de la procédure principale.
ATTENTION ! les liens ci-dessous mènent directement aux corrigés !
Fonction ChoixDuMot
Fonction PartieFinie
Procédure Affichage Mot
Procédure SaisieLettre
Procédure VérifLettre
Procédure Epilogue
Procédure Principale
Inscription à :
Commentaires (Atom)