Algorithme:Algorithmes fonctionnels

Un article de WikiTuto.

Jump to: navigation, search

Algorithmes

Introduction à l'algorithmique

Les Variables

Lecture et écritures

Les tests

Logique

Boucles

Les tableaux

Techniques Rusées

Tableaux multidimensionnels

Les fonctions prédéfinies

Les Fichiers

Procédures et fonctions

Notions complémentaires

modifier Tdm Algorithmique

Source : Christophe Darmangeat

[modifier]

Explication

L Pour clore ce chapitre, quelques mots à propos de la structure générale d’une application. 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’œil 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é.

[modifier]

Exemple

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…

[modifier]

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 ?

Encore une fois, il ne faut pas hésiter à passer du temps sur ces questions, car certaines erreurs, ou certains oublis, se payent cher par la suite. Et inversement, le temps investi à ce niveau est largement rattrapé au moment du développement proprement dit.

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.

Nous avons maintenant suffisamment gambergé pour dresser le tableau final de cette étape, à savoir le dictionnaire des données proprement dit :

 
 Nom  	        Type            Description
 Dico.txt 	Fichier texte 	Liste des mots à deviner
 Mot 	        Caractère 	Mot à deviner
 Lettre 	Caractère 	Lettre proposée
 MovRep 	Entier 	        Nombre de mauvaises réponses
 Verif() 	Tableau 
                de Booléens 	Lettres précédemment devinées, en correspondance avec Mot
 Propos 	Caractère 	Liste des lettres proposées

[modifier]

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 manœuvre 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).

Dans notre cas précis, un premier bloc se détache : il s’agit de ce qu’on pourrait appeler les préparatifs du jeu (choix du mot à deviner). Puisque le but est de renvoyer une valeur et une seule (le mot choisi par la machine), nous pouvons confier cette tâche à une fonction spécialisée ChoixDuMot (à noter que ce découpage est un choix de lisibilité, et pas une nécessité absolue ; on pourrait tout aussi bien faire cela dans la procédure principale).

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.

[modifier]

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 !