Algorithmique
=Cours d'algorithmique pour débutants = 
Ce cours algorithmique pour débutants est très largement inspiré du cours d'algorithmique proposé à École supérieure d'informatique de Bruxelles.
Ce cours est en licence Creative Commons paternité partage à l’identique (CC-BY-SA) et est développé collectivement par les enseignants, parfois avec l'aide des étudiants sur github dans DEV1-ALG-Syllabus-Algo
La version présente ici doit encore être fortement réorganisée pour les besoins de ce travail collaboratif en wiki.
Conçu à l'origine pour les étudiants de l'enseignement post-secondaire belge, ce cours expérimental s'efforce de présenter l'apprentissage de l'algorithmique sous une forme adaptée à la logique d'un langage
pour lequel la déclaration préalable de l'existence et du type des variables est nécessaire (ex java) à la différence de python et octave/matlab où la déclaration et la définition du type sont implicites lors de la première affectation.
Ce cours contient de nombreux exemples et exercices, si possible.
Ce livre a été rédigé par essentiellement par des professeurs de École supérieure d'informatique avec l'aide des étudiants pour les corrections des exercices. Il est sous licence CCBYSA.
Sommaire.
Modifier le sommaire
Haute École de Bruxelles - École Supérieure d’Informatique
Bachelier en Informatique
Rue Royale, 67. 1000 Bruxelles - esi@heb.be
Cours DEV 1 - Algorithmique - 2015
Ce document est distribué sous licence Creative Commons - Paternité - Partage à l’Identique 2.0 Belgique.
Les autorisations au-delà du champ de cette licence peuvent être demandées à codice_1.
= Résoudre des problèmes =
« L’algorithmique est le permis de conduire de l’informatique. Sans elle, il n’est pas concevable d’exploiter sans risque un ordinateur. » 
Ce chapitre a pour but de vous faire comprendre ce qu’est une "procédure de résolution de problèmes".
La notion de problème.
Préliminaires : utilité de l’ordinateur.
L’ordinateur est une machine. Mais une machine intéressante dans la mesure où elle est destinée d’une part, à nous décharger d’une multitude de tâches peu valorisantes, rébarbatives telles que le travail administratif répétitif, mais surtout parce qu’elle est capable de nous aider, voire nous remplacer, dans des tâches plus ardues qu’il nous serait impossible de résoudre sans son existence (conquête spatiale, prévision météorologique, jeux vidéo…).
En première approximation, nous pourrions dire que l’ordinateur est destiné à nous remplacer, à faire à notre place (plus rapidement et probablement avec moins d’erreurs) un travail nécessaire à la résolution de problèmes auxquels nous devons faire face. Attention ! Il s’agit bien de résoudre des "problèmes" et non des mystères (celui de l’existence, par exemple). Il faut que la question à laquelle on souhaite répondre soit accessible à la raison.
Poser le problème.
Un préalable à l’activité de résolution d’un problème est de bien définir d’abord quel est le problème posé, en quoi il consiste exactement ; par exemple, faire un baba au rhum, réussir une année d’études, résoudre une équation mathématique…
Un problème bien posé doit mentionner l’objectif à atteindre, c’est-à-dire la situation d’arrivée, le but escompté, le résultat attendu. Généralement, tout problème se définit d’abord explicitement par ce que l’on souhaite obtenir.
La formulation d’un problème ne serait pas complète sans la connaissance du cadre dans lequel le problème est posé : de quoi dispose-t-on, quelles sont les hypothèses de base, quelle est la situation de départ ? Faire un baba au rhum est un problème tout à fait différent s’il faut le faire en plein désert ou dans une cuisine super équipée ! D’ailleurs, dans certains cas, la première phase de la résolution d’un problème consiste à identifier et mettre à sa disposition les éléments nécessaires à sa résolution :  dans notre exemple, ce serait se procurer les ingrédients et les ustensiles de cuisine.
Un problème ne sera véritablement bien spécifié que s’il s’inscrit dans le schéma suivant :
étant donné [la situation de départ] on demande [l’objectif]
Parfois, la première étape dans la résolution d’un problème est de préciser ce problème à partir d’un énoncé flou :  il ne s’agit pas nécessairement d’un travail facile !
Exercice..
Un problème flou.Soit le problème suivant :  « Calculer la moyenne de nombres entiers. ».Ce problème est-il bien posé ?Expliquez pourquoi cet énoncé n’est pas bon.Proposez un énoncé qui soit acceptable.
Une fois le problème correctement posé, on passe à la recherche et la description d’une méthode/procédure de résolution, afin de savoir comment faire pour atteindre l’objectif demandé à partir de ce qui est donné. Le nom donné à une méthode de résolution varie en fonction du cadre dans lequel se pose le problème :  "façon de procéder, mode d’emploi, marche à suivre, guide, patron, modèle, recette de cuisine, méthode ou plan de travail, algorithme mathématique, programme, directives d’utilisation…"
Procédure de résolution.
Une procédure de résolution est une description en termes compréhensibles par l’exécutant de la marche à suivre pour résoudre un problème donné.
On trouve beaucoup d’exemples dans la vie courante : recette de cuisine, mode d’emploi d’un GSM, description d’un itinéraire, plan de montage d’un jeu de construction, etc. Il est clair qu’il y a une infinité de rédactions possibles de ces différentes marches à suivre. Certaines pourraient être plus précises que d’autres, d’autres par contre pourraient s’avérer exagérément explicatives.
Des différents exemples de procédures de résolution se dégagent les caractéristiques suivantes :
On pourra donc définir, en première approximation, une procédure de résolution comme un texte, écrit dans un certain langage, qui décrit une suite d’actions à exécuter dans un ordre précis, ces actions opérant sur des objets issus des données du problème.
Traduite en termes informatiques, une telle procédure d’exécutions d’actions dans un contexte précis, sera appelée un algorithme. Nous y reviendrons et le définirons tout à fait précisément plus loin, dans notre contexte.
Chronologie des opérations.
Pour ce qui concerne l’ordinateur, le travail d’exécution d’une marche à suivre est impérativement séquentiel. C’est-à-dire que les instructions d’une procédure de résolution sont exécutées une et une seule fois dans l’ordre où elles apparaissent. Cependant certains artifices d’écriture permettent de répéter l’exécution d’opérations ou de la conditionner (c’est-à-dire de choisir si l’exécution aura lieu oui ou non en fonction de la réalisation d’une condition).
Les opérations élémentaires.
Dans la description d’une marche à suivre, la plupart des opérations sont introduites par un verbe ("remplir", "verser, prendre, peler", etc.). L’exécutant ne pourra exécuter une action que s’il la comprend : cette action doit, pour lui, être une action élémentaire, une action qu’il peut réaliser sans qu’on ne doive lui donner des explications complémentaires. Ce genre d’opération élémentaire est appelée primitive.
Ce concept est évidement relatif à ce qu’un exécutant est capable de réaliser. Cette capacité, il la possède d’abord parce qu’il est construit d’une certaine façon (capacité innée). Ensuite parce que, par construction aussi, il est doté d’une faculté d’apprentissage lui permettant d’assimiler, petit à petit, des procédures non élémentaires qu’il exécute souvent. Une opération non élémentaire pourra devenir une primitive un peu plus tard.
Les opérations bien définies.
Il arrive de trouver dans certaines marches à suivre des opérations qui peuvent dépendre d’une certaine manière de l’appréciation de l’exécutant. Par exemple, dans une recette de cuisine on pourrait lire :  "ajouter" un peu "de vinaigre, saler et poivrer" à volonté, "laisser cuire une" bonne " heure dans un four" bien "chaud, etc."
Des instructions floues de ce genre sont dangereuses à faire figurer dans une bonne marche à suivre car elles font appel à une appréciation arbitraire de l’exécutant. Le résultat obtenu risque d’être imprévisible d’une exécution à l’autre. De plus, les termes du type "environ, beaucoup, pas trop" et "à peu près" sont intraduisibles et proscrites au niveau d’un langage informatique ! 
Une opération bien définie est donc une opération débarrassée de tout vocabulaire flou et dont le résultat est entièrement prévisible. Des versions « bien définies » des exemples ci-dessus pourraient être :  "ajouter 2 cl de vinaigre, ajouter 5 g de sel et 1 g de poivre, laisser cuire 65 minutes dans un four chauffé à 220C, etc."
Afin de mettre en évidence la difficulté d’écrire une marche à suivre claire et non ambiguë, on vous propose l’expérience suivante.
Expérience..
Le dessin.
Cette expérience s’effectue en groupe. Le but est de faire un dessin et de permettre à une autre personne, qui ne l’a pas vu, de le reproduire fidèlement, au travers d’une « marche à suivre ».
Quelles réflexions cette expérience vous inspire-t-elle ? Quelle analogie voyez-vous avec une marche à suivre donnée à un ordinateur ?
Dans cette expérience, nous imposons que la « marche à suivre » ne mentionne aucun mot expliquant le sens du dessin (mettre « rond » et pas « roue » par exemple). Pourquoi, à votre avis, avons-nous imposé cette contrainte ?
Opérations soumises à une condition.
En français, l’utilisation de conjonctions ou locutions conjonctives du type "si", "selon que", "au cas où"… présuppose la possibilité de ne pas exécuter certaines opérations en fonction de certains événements. D’une fois à l’autre, certaines de ses parties seront ou non exécutées.
Exemple :  Si la viande est surgelée, la décongeler à l’aide du four à micro-ondes.
Opérations à répéter.
De la même manière, il est possible d’exprimer en français une exécution répétitive d’opérations en utilisant les mots "tous", "chaque", "tant que", "jusqu’à ce que", "chaque fois que", "aussi longtemps que", "faire x fois"…
Dans certains cas, le nombre de répétitions est connu à l’avance ("répéter 10 fois") ou déterminé par une durée ("faire cuire pendant 30 minutes") et dans d’autres cas il est inconnu. Dans ce cas, la fin de la période de répétition d’un bloc d’opérations dépend alors de la réalisation d’une condition ("lancer le dé jusqu’à ce qu’il tombe sur 6", "faire cuire jusqu’à évaporation complète" …).
En informatique, lorsqu’il y a répétition organisée, on parle de boucle. On en retrouve beaucoup, sous différentes formes, dans les codes informatiques.
L’exemple ci-dessous permet d’illustrer le danger de boucle infinie, due à une mauvaise formulation de la condition d’arrêt. Si l’on demande de "lancer le dé jusqu’à ce que la valeur obtenue soit 7", un humain doté d’intelligence comprend que la condition est impossible à réaliser, mais un robot appliquant cette directive à la lettre lancera le dé perpétuellement.
À propos des données.
Les types d’objets figurant dans les diverses procédures de résolution sont fonction du cadre dans lequel s’inscrivent ces procédures, du domaine d’application de ces marches à suivre. Par exemple, pour une recette de cuisine, ce sont les ingrédients. Pour un jeu de construction ce sont les briques.
L’ordinateur, quant à lui, manipule principalement des données numériques et textuelles. Nous verrons plus tard comment on peut combiner ces données élémentaires pour obtenir des données plus complexes.
Ressources.
Pour prolonger votre réflexion sur le concept d’algorithme nous vous proposons quelques ressources en ligne :
= Une approche ludique : Code Studio =
l14mm -4mm -2mm
Il existe de nombreux programmes qui permettent de s’initier à la création d’algorithmes. Nous voudrions mettre en avant le projet "Code Studio". Soutenu par des grands noms de l’informatique comme , , et , il permet de s’initier aux concepts de base au travers d’exercices ludiques faisant intervenir des personnages issus de jeux que les jeunes connaissent bien comme ou .
Sur le site http://studio.code.org/ nous avons sélectionné pour vous :
Nous vous conseillons de créer un compte sur le site ainsi vous pourrez retenir votre progression et reprendre rapidement votre travail là où vous l’avez interrompu.
Votre professeur va vous guider dans votre apprentissage pendant le cours et vous pourrez approfondir à la maison.
= Les algorithmes informatiques =
Notre but étant de faire de l’informatique, il convient de restreindre notre étude à des notions plus précises, plus spécialisées, gravitant autour de la notion de "traitement automatique de l’information". Voyons ce que cela signifie.
Algorithmes et programmes.
Décrivons la différence entre un algorithme et un programme et comment un ordinateur peut exécuter un programme.
Algorithme.
Un algorithme appartient au vaste ensemble des "marches à suivre".
Algorithme :  Procédure de résolution d’un problème contenant des opérations bien définies portant sur des informations, s’exprimant dans une séquence définie sans ambiguïté, destinée à être traduite dans un langage de programmation.
Comme toute marche à suivre, un algorithme doit s’exprimer dans un certain langage :  à priori le langage naturel, mais il y a d’autres possibilités :  ordinogramme, arbre programmatique, pseudo-code ou LDA (langage de description d’algorithmes) que nous allons utiliser dans le cadre de ce cours.
Programme.
Un programme n’est rien d’autre que la représentation d’un algorithme dans un langage plus technique compris par un ordinateur (par exemple : Assembleur, Cobol, Java, C++…). Ce type de langage est appelé langage de programmation.
Écrire un programme correct suppose donc la parfaite connaissance du langage de programmation et de sa syntaxe, qui est en quelque sorte la grammaire du langage. Mais ce n’est pas suffisant ! Puisque le programme est la représentation d’un algorithme, il faut que celui-ci soit correct pour que le programme le soit. Un programme correct résulte donc d’une démarche logique correcte (algorithme correct) et de la connaissance de la syntaxe d’un langage de programmation.
 Il est donc indispensable d’élaborer des algorithmes corrects avant d’espérer concevoir des programmes corrects. 
Les constituants principaux de l’ordinateur.
Les constituants d’un ordinateur se divisent en hardware (matériel) et software d’exploitation (logiciel).
Le hardware est constitué de l’ordinateur proprement dit et regroupe les entités suivantes :
Le software d’exploitation est l’ensemble des procédures (programmes) s’occupant de la gestion du fonctionnement d’un système informatique et de la gestion de l’ensemble des ressources de ce système (le matériel – les programmes – les données). Il contient notamment des logiciels de traduction permettant d’obtenir un programme écrit en langage machine (langage technique qui est le seul que l’ordinateur peut comprendre directement, c’est-à-dire exécuter) à partir d’un programme écrit en langage de programmation plus ou moins « évolué » (c’est-à-dire plus ou moins proche du langage naturel).
Exécution d’un programme.
Isolons (en les simplifiant) deux constituants essentiels de l’ordinateur afin de comprendre ce qui se passe quand un ordinateur exécute un programme. D’une part, la mémoire contient le programme et les données manipulées par ce programme. D’autre part, le processeur va « exécuter » ce programme.
m0.46m0.46
& Comment fonctionne le processeur ?
De façon très simplifiée, on passe par les étapes suivantes :
 On voit qu’il s’agit d’un travail automatique ne laissant aucune place à l’initiative ! 
Les phases d’élaboration d’un programme.
Voyons pour résumer un schéma simplifié des phases par lesquelles il faut passer quand on développe un programme.
m0.20m0.75
Notons que ce processus n’est pas linéaire. À chaque phase, on pourra détecter des erreurs, imprécisions ou oublis des phases précédentes et revenir en arrière.
Pourquoi passer par la phase « algorithmique » et ne pas directement passer à la programmation ?
Voilà une question que vous ne manquerez pas de vous poser pendant votre apprentissage cette année. Apportons quelques éléments de réflexion.
Bien sûr, cela n’a de sens que si le problème présente une réelle difficulté algorithmique. Certains problèmes (en pratique, certaines parties de problèmes) sont suffisamment simples que pour être directement programmés. Mais qu’est-ce qu’un problème simple ? Cela va évidemment changer tout au long de votre apprentissage. Un problème qui vous paraîtra difficile en début d’année vous paraîtra (enfin, il faut l’espérer !) une évidence en fin d’année.
Conclusion.
L’informatisation de problèmes est un processus essentiellement dynamique, contenant des allées et venues constantes entre les différentes étapes. Codifier un algorithme dans un langage de programmation quelconque n’est certainement pas la phase la plus difficile de ce processus. Par contre, élaborer une démarche logique de résolution d’un problème est probablement plus complexe.
Le but du cours d’algorithmique est double :
Le tout devrait avoir pour résultat l’élaboration de "bons programmes", c’est-à-dire "des programmes dont il est facile de se persuader qu’ils sont corrects" et des programmes dont la maintenance est la plus aisée possible. Dans ce sens, ce cours se situe idéalement en aval d’un cours d’analyse, et en amont des cours de langage de programmation. Ceux-ci sont idéalement complétés par les notions de système d’exploitation et de persistance des données.
Afin d’envisager la résolution d’une multiplicité de problèmes prenant leur source dans des domaines différents, le contenu minimum de ce cours envisage l’étude des points suivants (dans le désordre) :
Voilà bien un programme trop vaste pour un premier cours. Un choix devra donc être fait et ce, en fonction de critères tels que la rapidité d’assimilation, l’intérêt des étudiants et les besoins exprimés pour des cours annexes. Les matières non traitées ici, le seront dans les cours d’Algorithmique II et III.
Ressources.
Pour prolonger votre réflexion sur les notions vues dans ce chapitre, nous vous proposons quelques ressources en ligne :
= Spécifier le problème =
Comme nous l’avons dit, un problème ne sera véritablement bien spécifié que s’il s’inscrit dans le schéma suivant :
étant donné [les données] on demande [résultat]
La première étape dans la résolution d’un problème est de préciser ce problème à partir de l’énoncé, c-à-d de déterminer et préciser les données et le résultat. Il ne s’agit pas d’un travail facile et c’est celui par lequel nous allons commencer.
Déterminer les données et le résultat.
La toute première étape est de parvenir à extraire d’un énoncé de problème, quelles sont les données et quel est le résultat attendu .
Exemple..
Soit l’énoncé suivant : Calculer la surface d’un rectangle à partir de sa longueur et sa largeur .
Quelles sont les données ? Il y en a deux :
Quel est le résultat attendu ? la surface du rectangle.
Les noms.
Pour identifier clairement chaque donnée et pouvoir y faire référence dans le futur algorithme nous devons lui attribuer un nom . Il est important de bien choisir les noms. Le but est de trouver un nom qui soit suffisamment court, tout en restant explicite et ne prêtant pas à confusion.
Exemple..
Quel nom choisir pour la longueur d’un rectangle ?
On peut envisager les noms suivants :
Nous allons également donner un nom à l’algorithme de résolution du problème. Cela permettra d’y faire référence dans les explications mais également de l’utiliser dans d’autres algorithmes. Généralement, un nom d’algorithme est :
Exemple..
Quel nom choisir pour l’algorithme qui calcule la surface d’un rectangle ?
On peut envisager le verbe ou le nom (notre préféré). On pourrait aussi simplifier en s’il est évident qu’on traite des rectangles.
Notons que les langages de programmation imposent certaines limitations (parfois différentes d’un langage à l’autre) ce qui peut nécessiter une modification du nom lors de la traduction de l’algorithme en un programme.
Les types.
Nous allons également attribuer un type à chaque donnée ainsi qu’au résultat. Le type décrit la nature de son contenu, quelles valeurs elle peut prendre.
Dans un premier temps, les seuls types autorisés sont les suivants :
[t]p1.1cm|p12cm & pour les nombres entiers & pour les nombres réels & pour les chaînes de caractères, les textes (par exemple : , , , …) & quand la valeur ne peut être que ou
Il n’y a pas d’unité.
Un type numérique indique que les valeurs possibles seront des nombres. Il n’y a là aucune notion d’unité. Ainsi, la longueur d’un rectangle, un réel, peut valoir formula_1 mais certainement pas formula_2. Si cette unité a de l’importance, il faut la spécifier dans le nom de la donnée ou en commentaire.
Exemple..
Faut-il préciser les unités pour les dimensions d’un rectangle ?
Si la longueur d’un rectangle vaut formula_3, on ne peut pas dire s’il s’agit de centimètres, de mètres ou encore de kilomètres. Pour notre problème de calcul de la surface, ce n’est pas important ; la surface n’aura pas d’unité non plus.
Si, par contre, il est important de préciser que la longueur est donnée en centimètres, on pourrait l’expliciter en la nommant .
Préciser les valeurs possibles.
Nous aurions pu introduire un seul type numérique mais nous avons choisi de distinguer les entiers et les réels. Pourquoi ? Préciser qu’une donnée ne peut prendre que des valeurs entières (par exemple dans le cas d’un numéro de mois) aide le lecteur à mieux la comprendre. Nous allons aussi pouvoir définir des opérations propres aux entiers (le reste d’une division par exemple). Enfin, pour des raisons techniques, beaucoup de langages font cette distinction.
Même ainsi, le type choisi n’est pas toujours assez précis. Souvent, la donnée ne pourra prendre que certaines valeurs.
Exemples..
Ces précisions pourront être données en commentaire pour aider à mieux comprendre le problème et sa solution.
Le type des données complexes.
Parfois, aucun des types disponibles ne permet de représenter la donnée. Il faut alors la décomposer.
Exemple..
Quel type choisir pour la date de naissance d’une personne ?
On pourrait la représenter dans une chaîne (par ex: “17/3/1985”) mais cela rendrait difficile le traitement, les calculs (par exemple, déterminer le numéro du mois). Le mieux est sans doute de la décomposer en trois parties : le jour, le mois et l’année, tous des entiers.
Plus loin dans le cours, nous verrons qu’il est possible de définir de nouveaux types de données grâce aux "structures" . On pourra alors définir et utiliser un type et il ne sera plus nécessaire de décomposer une date en trois morceaux.
Exercice.
Quel(s) type(s) de données utiliseriez-vous pour représenter
Résumé graphique.
Toutes les informations déjà collectées sur le problème peuvent être représentées graphiquement.
Exemple..
Pour le problème, de la surface du rectangle, on fera le schéma suivant :
Exemples numériques.
Une dernière étape pour vérifier que le problème est bien compris est de donner quelques exemples numériques. On peut les spécifier en français, via un graphique ou via une notation compacte que nous allons présenter.
Exemples..
Voici différentes façons de présenter des exemples numériques pour le problème de calcul de la surface d’un rectangle :
Exercices.
Pour les exercices suivants, nous vous demandons d’imiter la démarche décrite dans ce chapitre, à savoir :
Somme de 2 nombres Calculer la somme de deux nombres donnés.
Solution..
 Il y a ici clairement 2 données. Comme elles n’ont pas de rôle précis, on peut les appeler simplement et ( et sont aussi de bons choix). L’énoncé ne dit pas si les nombres sont entiers ou pas; restons le plus général possible en prenant des réels. Le résultat sera de même type que les données. Le nom de l’algorithme pourrait être simplement . Ce qui donne :
Et voici quelques exemples numériques : donne formula_5 donne formula_6 donne formula_7 donne formula_8.
Moyenne de 2 nombres Calculer la moyenne de deux nombres donnés.
Surface d’un triangle Calculer la surface d’un triangle connaissant sa base et sa hauteur.
Périmètre d’un cercle Calculer le périmètre d’un cercle dont on donne le rayon.
Surface d’un cercle Calculer la surface d’un cercle dont on donne le rayon.
TVA Si on donne un prix hors TVA, il faut lui ajouter 21% pour obtenir le prix TTC. Écrire un algorithme qui permet de passer du prix HTVA au prix TTC.
Les intérêts Calculer les intérêts reçus après 1 an pour un montant placé en banque à du 2% d’intérêt.
Placement Étant donné le montant d’un capital placé (en ) et le taux d’intérêt annuel (en %), calculer la nouvelle valeur de ce capital après un an.
Prix TTC Étant donné le prix unitaire d’un produit (hors TVA), le taux de TVA (en %) et la quantité de produit vendue à un client, calculer le prix total à payer par ce client.
Durée de trajet Étant donné la vitesse moyenne en m/s d’un véhicule et la distance parcourue en km par ce véhicule, calculer la durée en secondes du trajet de ce véhicule.
Allure et vitesse L’allure d’un coureur est le temps qu’il met pour parcourir 1 km (par exemple, formula_9). On voudrait calculer sa vitesse (en km/h) à partir de son allure. Par exemple, la vitesse d’un coureur ayant une allure de formula_9 est de formula_11 km/h.
Cote moyenne Étant donné les résultats (cote entière sur 20) de trois examens passés par un étudiant (exprimés par six nombres, à savoir, la cote et la pondération de chaque examen), calculer la moyenne globale exprimée en pourcentage.
Somme des chiffres Calculer la somme des chiffres d’un nombre entier de 3 chiffres.
Conversion HMS en secondes Étant donné un moment dans la journée donné par trois nombres, à savoir, heure, minute et seconde, calculer le nombre de secondes écoulées depuis minuit.
Conversion secondes en heures Étant donné un temps écoulé depuis minuit. Si on devait exprimer ce temps sous la forme habituelle (heure, minute et seconde), que vaudrait la partie “heure”.
Ex : 10000 secondes donnera 2 heures.
Conversion secondes en minutes Étant donné un temps écoulé depuis minuit. Si on devait exprimer ce temps sous la forme habituelle (heure, minute et seconde), que vaudrait la partie “minute”.
Ex : 10000 secondes donnera 46 minutes.
Conversion secondes en secondes Étant donné un temps écoulé depuis minuit. Si on devait exprimer ce temps sous la forme habituelle (heure, minute et seconde), que vaudrait la partie “seconde”.
Ex : 10000 secondes donnera 40 secondes.
= Premiers algorithmes =
Dans le chapitre précédent, vous avez appris à analyser un problème et à clairement le spécifier. Il est temps d’écrire des solutions. Pour cela, nous allons devoir trouver comment passer des données au résultat et l’exprimer dans un langage compris de tous, le "Langage de Description d’Algorithmes" (ou "LDA").
Un problème simple.
Trouver l’algorithme.
Illustrons notre propos sur l’exemple qui a servi de fil conducteur tout au long du chapitre précédent. Rappelons l’énoncé et l’analyse qui en a été faite.
Problème..
Calculer la surface d’un rectangle à partir de sa longueur et sa largeur.
Analyse..
Nous sommes arrivés à la spécification suivante :
Exemples.
2
Comment résoudre ce problème ?
La toute première étape est de comprendre le lien entre les données et le résultat. Ici, on va se baser sur la formule de la surface : formula_14 La surface s’obtient donc en multipliant la longueur par la largeur .
En LDA, la solution s’écrit :
longueur * largeur
La paire permet de délimiter l’algorithme. La première ligne est appelée l’entête de l’algorithme. On y retrouve :
Les paramètres recevront des valeurs concrètes au début de l’exécution de l’algorithme.
L’instruction permet d’indiquer la valeur du résultat, ce que l’algorithme "retourne". Si on spécifie une formule, un calcul, c’est le résultat (on dit l’"évaluation") de ce calcul qui est retourné et pas la formule.
Pour indiquer le calcul à faire, écrivez-le, pour le moment, naturellement comme vous le feriez en mathématique. La seule différence notable est l’utilisation de pour indiquer une multiplication. Nous donnerons plus de détails plus loin.
Pour indiquer qu’on veut exécuter un algorithme (on dit aussi "appeler") il suffit d’indiquer son nom et les valeur concrètes à donner aux paramètres. Ainsi, fait appel à l’algorithme correspondant pour calculer la surface d’un rectangle dont la longueur est formula_3 et la largeur est formula_16.
Vérifier l’algorithme.
Lorsque vous avez terminé un exercice, vous le montrez à votre professeur pour qu’il vous dise s’il est correct ou pas. Fort bien ! Mais vous pourriez trouver la réponse tout seul. Il vous suffit d’exécuter l’algorithme avec des exemples numériques et de vérifier que la réponse fournie est correcte. Votre professeur reste indispensable pour :
Vous éprouvez souvent des difficultés à tester un algorithme car vous oubliez d’éteindre votre cerveau. Il faut agir comme une machine et exécuter ce qui est écrit pas ce que vous pensez avoir écrit, ce qu’il est censé faire. Cela demande un peu de pratique.
Exemple..
Vérifions notre solution pour le calcul de la surface du rectangle en reprenant les exemples choisis.
Attention : Dans tous les exercices qui suivront, chaque fois qu’on vous demandera d’écrire un algorithme, on attendra de vous : de spécifier le problème, de fournir des exemples, d’écrire l’algorithme et de le vérifier sur vos exemples. Ce n’est que si tous ces éléments sont présents que votre solution pourra être considérée comme complète.
Exercices.
Les exercices suivants ont déjà été analysés dans un précédent chapitre et des exemples numériques ont été choisis. Il ne vous reste plus qu’à écrire l’algorithme et à le vérifier pour les exemples choisis.
Vous pouvez vous baser sur la fiche qui résume la résolution du calcul de la surface d’un rectangle, depuis l’analyse de l’énoncé jusqu’à l’algorithme et à sa vérification.
Somme de 2 nombres Calculer la somme de deux nombres donnés.
Solution..
Rappelons ce que nous avons obtenus lors de la phase d’analyse du problème.
Sommer deux nombres est un problème trivial. L’algorithme s’écrit simplement :
nombre1 + nombre2
Cet exercice est plutôt simple et il est facile de vérifier qu’il fournit bien les bonnes réponses pour les exemples choisis.
Moyenne de 2 nombres Calculer la moyenne de deux nombres donnés.
Surface d’un triangle Calculer la surface d’un triangle connaissant sa base et sa hauteur.
Périmètre d’un cercle Calculer le périmètre d’un cercle dont on donne le rayon.
Surface d’un cercle Calculer la surface d’un cercle dont on donne le rayon.
TVA Si on donne un prix hors TVA, il faut lui ajouter 21% pour obtenir le prix TTC. Écrire un algorithme qui permet de passer du prix HTVA au prix TTC.
Les intérêts Calculer les intérêts reçus après 1 an pour un montant placé en banque à du 2% d’intérêt.
Placement Étant donné le montant d’un capital placé (en ) et le taux d’intérêt annuel (en %), calculer la nouvelle valeur de ce capital après un an.
Conversion HMS en secondes Étant donné un moment dans la journée donné par trois nombres, à savoir, heure, minute et seconde, calculer le nombre de secondes écoulées depuis minuit.
Prix TTC Étant donné le prix unitaire d’un produit (hors TVA), le taux de TVA (en %) et la quantité de produit vendue à un client, calculer le prix total à payer par ce client.
Décomposer les calculs.
Dans les exercices de la section précédente, vous avez écrit quelques longues formules . Pour que cela reste lisible, il serait bon de pouvoir "décomposer" le calcul en étapes. Pour ce faire, nous devons introduire deux nouvelles notions : les "variables locales" et "l’assignation".
Les variables.
Une variable locale (ou simplement variable) est une zone mémoire à laquelle on a donné un nom et qui contiendra des valeurs d’un type donné. Elles vont servir à retenir des étapes intermédiaires de calculs.
Pour être utilisable, une variable doit être "déclarée" au début de l’algorithme. La déclaration d’une variable est l’instruction qui définit son nom et son type. On pourrait écrire :
longueur et largeur seront les noms de deux objets destinés à recevoir les longueur et largeur du rectangle, c’est-à-dire des nombres à valeurs réelles.
Mais, bien entendu, cette formulation, trop proche du langage parlé, serait trop floue et trop longue. Dès lors, nous abrégerons par :
Pour choisir le nom d’une variable, les règles sont les mêmes que pour les données d’un problème.
L’assignation.
L’assignation (on dit aussi "affectation interne") est une instruction qui donne une valeur à une variable ou la modifie.
Cette instruction est probablement la plus importante car c’est ce qui permet de retenir les résultats de calculs intermédiaires.
nomVariable expression
Une expression est un calcul faisant intervenir des variables, des valeurs explicites et des opérateurs (comme +, -, <…). Une expression a une valeur.
Exemples..
Quelques assignations correctes :
denRes den1 * den2 cpt cpt + 1 moyenne (nombre1 + nombre2) / 2 test a < b pour une variable logique maChaine “bonjour” maChaine bonjour comprenez-vous la différence ?
Et d’autres qui ne le sont pas :
somme + 1 3 somme + 1 n’est pas une variable somme 3n 3n n’est ni un nom de variable correct ni une expression correcte
Tracer un algorithme.
Pour vérifier qu’un algorithme est correct, on sera souvent amené à le tracer. Cela consiste à suivre l’évolution des variables et à vérifier qu’elles contiennent bien à tout moment la valeur attendue.
Exemple..
Traçons des bouts d’algorithmes.
4cm
[1] a 12 b 5 c a - b a a + c b a
7cm
4cm
[1] a 12 c a - b d c - 2
7cm
ne peut pas être calculé car b n’a pas été initialisé; quant à , il n’est même pas déclaré !
Tracer des bouts de code Suivez l’évolution des variables pour les bouts d’algorithmes donnés.
4cm
[1] a 42 b 24 c a + b c c - 1 a 2 * b c c + 1
7cm
4cm
[1] a 2 b aformula_34 c b - aformula_35 a formula_36 a a / a
7cm
Calcul de vitesse Soit le problème suivant : Calculer la vitesse (en km/h) d’un véhicule dont on donne la durée du parcours (en secondes) et la distance parcourue (en mètres). .
Voici une solution :
[1] distanceKM 1000 * distanceM duréeH 3600 * duréeS formula_37
L’algorithme, s’il est correct, devrait donner une vitesse de 1 km/h pour une distance de 1000 mètres et une durée de 3600 secondes. Testez cet algorithme avec cet exemple.
Si vous trouvez qu’il n’est pas correct, voyez ce qu’il faudrait changer pour le corriger.
Exercices de décomposition.
Savoir, face à un cas concret, s’il est préférable de décomposer le calcul ou pas, n’est pas toujours évident. La section sur la lisibilité vous apportera des arguments qui permettront de trancher.
Les exercices qui suivent sont suffisamment complexes que pour mériter une décomposition du calcul. Ils ont déjà été analysés dans un précédent chapitre. On vous demande à présent d’en rédiger une solution et de la tracer pour vérifier que le résultat est correct. Vous pouvez vous baser sur la fiche qui présente un exemple complet.
Durée de trajet [algo:durée] Étant donné la vitesse moyenne non nulle en m/s d’un véhicule et la distance parcourue en km par ce véhicule, calculer la durée en secondes du trajet de ce véhicule.
Solution..
L’analyse du problème aboutit à :
La formule qui lie les trois éléments est : formula_38 pour autant que les unités soient compatibles. Dans notre cas, il faut d’abord convertir la distance en mètres, selon la formule : formula_39 quelques exemples numériques :
2
L’algorithme s’écrit :
[1] distanceM 1000 * distanceKM distanceM / vitesseMS
Vérifions l’algorithme pour
et pour
Allure et vitesse L’allure d’un coureur est le temps qu’il met pour parcourir 1 km (par exemple, formula_9). On voudrait calculer sa vitesse (en km/h) à partir de son allure. Par exemple, la vitesse d’un coureur ayant une allure de formula_9 est de formula_56 km/h.
Cote moyenne Étant donné les résultats (cote entière sur 20) de trois examens passés par un étudiant (exprimés par six nombres, à savoir, la cote et la pondération de chaque examen), calculer la moyenne globale exprimée en pourcentage.
Quelques difficultés liées au calcul.
Vous êtes habitués à effectuer des calculs. L’expérience nous montre toutefois que certains calculs vous posent des difficultés. Soit parce que ce sont des opérations que vous utilisez peu, soit parce que vous n’avez pas l’habitude de les voir comme des calculs. Citons :
Parfois, le problème se site au niveau de la compréhension du vocabulaire. Examinons ces situations une à une en fournissant des exemples et des exercices pour que cela devienne naturel pour vous.
Un peu de vocabulaire.
Une première difficulté que vous rencontrez généralement est liée au vocabulaire utilisé. Qu’entend-on exactement par un opérateur ? un opérande ? Fixons ces notions.
Analyse d’expression Voici une série d’expressions. On vous demande d’identifier tous les opérateurs et leurs opérandes, d’indiquer si les opérateurs sont unaires ou binaires et d’identifier les littéraux. On vous demande aussi de fournir une version de l’expression avec le moins de parenthèses possibles et une autre avec un maximum de parenthèses (tout en respectant le sens de l’expression bien sûr).
Les comparaisons et les assignations de variables booléennes.
Si je vous dis que formula_57 est un calcul dont le résultat est formula_58, un entier vous n’aurez aucun mal à me croire ; cela vous parait évident. Ce qui l’est peut-être moins c’est que formula_59 est aussi un calcul dont le résultat est un "booléen", vrai en l’occurrence. Ce résultat peut être assigné à une variable booléenne.
Exemples. Voici quelques assignations correctes (les variables à gauche du sont des variables booléennes) :
positif nb > 0 positif est mis à vrai si le nb est positif adulte âge formula_60 21 adulte est vrai si l’âge est 21 ou plus réussi cote formula_60 10 réussi est mis à vrai si la cote est supérieure ou égale à 10 parfait nbFautes = 0 c’est parfait si le nombre de fautes est 0
Écrire des expressions booléennes Pour chacune des phrases suivantes, écrivez l’assignation qui lui correspond.
Les opérations logiques.
Les opérateurs logiques agissent sur des expressions booléennes (variables ou expressions à valeurs booléennes) pour donner un résultat du même type.
m15mm|m3cm|m8cm opérateur & nom & description & négation & vrai devient faux et inversement & conjonction logique & vrai si les 2 conditions sont vraies & disjonction logique & vrai si au moins une des 2 conditions est vraie
Ce qu’on peut résumer par les tableaux suivants :
On peut les utiliser pour donner une valeur à une variable booléenne. Par exemple :
2
Écrire des calculs utilisant ces opérateurs n’est pas facile car le français nous induit souvent en erreur en nous poussant à utiliser un ET pour un OU et inversement ou bien à utiliser des raccourcis d’écriture ambigus .Par exemple, ne pas écrire :
Loi de De Morgan..
Lorsqu’on a une expression complexe faisant intervenir des négations, on peut utiliser la "Loi de De Morgan" pour la simplifier. Cette loi stipule que : formula_62 formula_63
Par exemple :peut s’écrire aussi :ce qui se simplifie en :
Priorités et parenthèses..
Lorsqu’on écrit une expression mêlant les opérateurs logiques, on considère que NON est prioritaire sur ET qui l’est sur OU.
Ainsi l’expression : doit se comprendre : . Vous pouvez toujours ajouter des parenthèses non nécessaires pour vous assurer d’être bien compris.
Évaluation court-circuitée..
[court-circuit]
Les opérateurs ET et OU sont des opérateurs court-circuités. Cela signifie que le calcul s’arrête dès qu’on peut être sûr de la réponse finale. En particulier, si la première partie d’un ET est fausse, on est sûr que le résultat sera faux quelle que soit la suite. Et si la première partie d’un OU est vraie on est sûr que le résultat sera vrai.
Pourquoi un tel comportement ? Cela permet de gagner du temps bien sûr, mais cela permet également d’éviter des erreurs d’exécution.
Exemples.
ok 1/b < 0.1 provoque une erreur et un arrêt de l’algorithme si . ok bformula_640 ET 1/b < 0.1 donne la valeur à si (court-circuit). ok 1/b < 0.1 ET bformula_640 provoque une erreur et un arrêt de l’algorithme si .
Cette propriété sera abondamment utilisée dans le parcours de tableaux.
Simplifier des expressions booléennes Voici quelques assignations correctes du point de vue de la syntaxe mais contenant des lourdeurs d’écriture. Trouvez des expressions plus simples qui auront un effet équivalent.
Expressions logiques Pour chacune des phrases suivantes, écrivez l’assignation qui lui correspond.
La division entière et le reste.
La division entière consiste à effectuer une division en ne gardant que la partie entière du résultat. Dans ce cours, nous la noterons . Dit autrement, indique combien de fois on peut "mettre" b dans a.
2cm Exemples :
9cm
2
Le reste de la division entière de a par b est ce qui n’a pas été repris dans la division. On va le noter et on dira "a modulo b".
Un exemple vous aidera à comprendre. Imaginons qu’une classe comprend 14 étudiants qu’il faut réunir par 3 dans le cadre d’un travail de groupe. On peut former 4 groupes mais il restera 2 étudiants ne pouvant former un groupe complet. C’est le reste de la division de 14 par 3.
2cm Exemples :
9cm
2
Calculs Voici quelques petits calculs à compléter faisant intervenir la division entière et le reste. Par exemple : “14 DIV 3 = 4 reste 2” siginifie que 14 DIV 3 = 4 et 14 MOD 3 = 2.
2
Les prix ronds Voici un algorithme qui reçoit une somme d’argent exprimée en centimes et qui calcule le nombre (entier) de centimes qu’il faudrait ajouter à la somme pour tomber sur un prix rond en euros. Testez-le avec des valeurs numériques. Est-il correct ?
100 - (prixCentimes MOD 100)
Tester la divisibilité.
Les deux opérateurs et sont-ils vraiment utiles ? Oui ! Ils vont servir pour tester si un nombre est un multiple d’un autre et pour extraire des chiffres d’un nombre. Commençons par la divisibilité.
Imaginons qu’on veuille tester qu’un nombre est pair. Qu’est-ce qu’un nombre pair ? Un nombre qui est multiple de 2. C’est-à-dire dont le reste de la division par 2 est nul.
formula_66
On peut donc écrire : .
Extraire les chiffres d’un nombre.
Faisons une petite expérience numérique.
On voit que les DIV et MOD avec des puissances de 10 permettent de garder les chiffres de droite (MOD) ou d’enlever les chiffres de droite (DIV). Combinés, ils permettent d’extraire n’importe quel chiffre d’un nombre.
Exemple : (65536 DIV 100) MOD 10 = 5.
Le hasard.
Il existe de nombreuses applications qui font intervenir le hasard. Par exemple dans les jeux où on doit mélanger des cartes, lancer des dés, faire apparaitre des ennemis de façon aléatoire…
Le vrai hasard n’existe pas en algorithmique puisqu’il s’agit de suivre des étapes précises dans un ordre fixé. Pourtant, on peut concevoir des algorithmes qui "simulent" le hasard . À partir d’un nombre donné (qu’on appelle "graine" ou "seed" en anglais) ils fournissent une suite de nombres qui "ont l’air" aléatoires. Concevoir de tels algorithmes est très compliqué et dépasse largement le cadre de ce cours. Nous allons juste supposer qu’on dispose, sans devoir l’écrire, d’un algorithme qui fournit un entier aléatoire.
Dans nos algorithmes, nous pourrons donc écrire pour obtenir un nombre entier aléatoire entre formula_67 et formula_68 inclus.
Exemple.
hasard(6)
Cet algorithme peut être utilisé pour générer des nombres appartenant à d’autres intervalles.
Chiffre aléatoire Écrivez un algorithme qui donne un chiffre (de 0 à 9 donc) aléatoire.
Nombre aléatoire entre min et max Écrivez un algorithme qui donne un nombre entier aléatoire compris entre et inclus.
Exercices récapitulatifs sur les difficultés de calcul.
[prem-ex-cplx]
Les exercices qui suivent n’ont pas tous été déjà analysés et ils demandent des calculs faisant intervenir des divisions entières, des restes et/ou des expressions booléennes. Comme d’habitude, écrivez la spécification si ça n’a pas encore été fait, donnez des exemples, rédigez un algorithme et vérifiez-le.
Nombre multiple de 5 [algo:mult5] Calculer si un nombre entier positif donné est un multiple de 5.
Solution..
Dans ce problème, il y a une donnée, le nombre à tester. La réponse est un booléen qui est à vrai si le nombre donné est un multiple de 5.
Exemples.
4
La technique pour vérifier si un nombre est un multiple de 5 est de vérifier que le reste de la division par 5 donne 0. Ce qui donne :
[1] nombre MOD 5 = 0
Vérifions sur nos exemples :
Nombre entier positif se terminant par un 0 Calculer si un nombre donné se termine par un 0.
Les centaines Calculer la partie "centaine" d’un nombre entier positif quelconque.
Somme des chiffres Calculer la somme des chiffres d’un nombre entier positif inférieur à 1000.
Conversion secondes en heures Étant donné un temps écoulé depuis minuit. Si on devait exprimer ce temps sous la forme habituelle (heure, minute et seconde), que vaudrait la partie “heure”.
Ex : 10000 secondes donnera 2 heures.
Aide : L’heure n’est qu’un nombre exprimé en base 60 !
Conversion secondes en minutes Étant donné un temps écoulé depuis minuit. Si on devait exprimer ce temps sous la forme habituelle (heure, minute et seconde), que vaudrait la partie “minute”.
Ex : 10000 secondes donnera 46 minutes.
Conversion secondes en secondes Étant donné un temps écoulé depuis minuit. Si on devait exprimer ce temps sous la forme habituelle (heure, minute et seconde), que vaudrait la partie “seconde”.
Ex : 10000 secondes donnera 40 secondes.
Un double au dés Écrire un algorithme qui simule le lancer de deux dés et indique s’il y a eu un double (les deux dés montrant une face identique).
Année bissextile [ex:bissextile] Écrire un algorithme qui vérifie si une année est bissextile. Pour rappel, les années bissextiles sont les années multiples de 4. Font exception, les multiples de 100 (sauf les multiples de 400 qui sont bien bissextiles). Ainsi formula_69 et formula_70 sont bissextiles mais pas formula_71 ni formula_72.
Des algorithmes de qualité.
Dans la section précédente, nous avons vu qu’il est possible de décomposer un calcul en étapes. Mais quand faut-il le faire ? Ou, pour poser la question autrement :
Puisqu’il existe plusieurs algorithmes qui résolvent un problème, lequel préférer ?
Répondre à cette question, c’est se demander ce qui fait la qualité d’un algorithme ou d’un programme informatique. Quels sont les critères qui permettent de juger ?
C’est un vaste sujet mais nous voudrions aborder les principaux.
L’efficacité.
L’efficacité désigne le fait que l’algorithme (le programme) résout bien le problème donné. C’est un minimum !
La lisibilité.
La lisibilité indique si une personne qui lit l’algorithme (ou le programme) peut facilement percevoir comment il fonctionne. C’est crucial car un algorithme (un programme) est souvent lu par de nombreuses personnes :
C’est un critère très important qu’il ne faut surtout pas sous-évaluer. Vous en ferez d’ailleurs l’amère expérience : si vous négligez la lisibilité d’un algorithme, vous-même ne le comprendrez plus quand vous le relirez quelque temps plus tard !
Comparer la lisibilité de deux algorithmes n’est pas une tâche évidente car c’est une notion subjective. Il faut se demander quelle version va être le plus facilement comprise par la majorité des lecteurs. La section explique ce qui peut être fait pour rendre ses algorithmes plus lisibles.
La rapidité.
La rapidité indique si l’algorithme (le programme) permet d’arriver plus ou moins vite au résultat.
C’est un critère qui est souvent sur-évalué, essentiellement pour deux raisons.
Ce critère est un cas particulier de l’"efficience" qui traite de la gestion économe des ressources. Nous reparlerons de rapidité dans le chapitre consacré à la "complexité" des algorithmes.
La taille.
Nous voyons parfois des étudiants contents d’avoir pu écrire un algorithme en moins de lignes. Ce critère n’a aucune importance ; un algorithme plus court n’est pas nécessairement plus rapide ni plus lisible.
Conclusion.
Tout ces critères n’ont pas le même poids. Le point le plus important est bien sûr d’écrire un algorithme correct mais ne vous arrêtez pas là ! Demandez-vous s’il n’est pas possible de le retravailler pour améliorer sa lisibilité .
Améliorer la lisibilité d’un algorithme.
On vient de le voir, la lisibilité est une qualité essentielle que doivent avoir nos algorithmes. Qu’est ce qui permet d’améliorer la lisibilité d’un algorithme ?
Les commentaires.
Commenter un algorithme signifie lui ajouter du texte explicatif destiné au lecteur pour l’aider à mieux comprendre le fonctionnement de l’algorithme. Un commentaire n’est pas utilisé par celui qui exécute l’algorithme; il ne modifie pas ce que l’algorithme fait.
Habituellement, on distingue deux sortes de commentaires :
Commenter correctement un programme est une tâche qui n’est pas évidente et qu’il faut travailler. Il faut arriver à apporter au lecteur une information utile qui n’apparait pas directement dans le code. Par exemple, il est contre-productif de répéter ce que l’instruction dit déjà. Voici quelques mauvais commentaires
somme 0
Notez qu’un excès de commentaires peut être le révélateur des problèmes de lisibilité du code lui-même. Par exemple, un choix judicieux de noms de variables peut s’avérer bien plus efficace que des commentaires. Ainsi, l’instruction
nouveauCapital ancienCapital * (1 + taux / 100)
dépourvue de commentaires est bien préférable aux lignes suivantes :
c1 c0 * (1 + t / 100) calcul du nouveau capital. c1 est le nouveau capital, c0 est l’ancien capital, t est le taux
Pour résumer :
N’hésitez pas à documenter votre programme pour expliquer ce qu’il fait et à le retravaillez pour que tout commentaire à l’intérieur de l’algorithme devienne superflu. 
Exemple..
Voici comment on pourrait documenter un de nos algorithmes.
longueur * largeur
Commenter la durée du trajet Commentez l’algorithme qui calcule la durée d’un trajet (exercice ).
Constantes.
Une constante est une information pour laquelle nom, type et valeur sont figés. La liste des constantes utilisées dans un algorithme apparaitra dans la section déclaration des variables sous la forme suivante  :
Il est inutile de spécifier leur type, celui-ci étant défini implicitement par la valeur de la constante. L’utilisation de constantes dans vos algorithmes présente les avantages suivants :
Utiliser une constante Trouvez un algorithme que vous avez écrit où l’utilisation de constante pourrait améliorer la lisibilité de votre solution.
Interagir avec l’utilisateur.
Reprenons l’algorithme qui nous a souvent servi d’exemple. Il permet de calculer la surface d’un rectangle dont on connait la longueur et la largeur. Mais d’où viennent ces données ? Et que faire du résultat ?
Tout d’abord, un algorithme peut utiliser (on dit appeler) un autre algorithme . Pour ce faire, il doit spécifier les valeurs des paramètres ; il peut alors utiliser le résultat. L’appel s’écrit ainsi :
surface surfaceRectangle(122,3.78)
L’appel d’un algorithme est considéré comme une expression, un calcul qui, comme toute expression, possède une valeur (la valeur retournée) et peut intervenir dans un calcul plus grand, être assignée à une variable…
Afficher un résultat.
Si on veut écrire un programme concret (en Java par exemple) qui permet de calculer des surfaces de rectangles, il faudra bien que ce programme communique le résultat à l’utilisateur du programme. On va l’indiquer avec la commande . Ce qui donne :
surface surfaceRectangle(122,3.78)
ou, plus simplement :
L’instruction signifie que l’algorithme doit, à cet endroit de l’algorithme communiquer une information à l’utilisateur. La façon dont il va communiquer cette information (à l’écran dans une application texte, via une application graphique, sur un cadran de calculatrice ou de montre, sur une feuille de papier imprimée, via un synthétiseur vocal…) ne nous intéresse pas ici .
Demander des valeurs.
Le bout d’algorithme qu’on vient d’écrire n’est pas encore très utile puisqu’il calcule toujours la surface du même rectangle. Il serait intéressant de demander à l’utilisateur ce que valent la longueur et la largeur. C’est le but de la commande .
L’instruction signifie que l’utilisateur va, à cet endroit de l’algorithme, être sollicité pour donner une valeur qui sera affectée à une variable. À nouveau, la façon dont il va indiquer cette valeur (au clavier dans une application texte, via un champ de saisie ou une liste déroulante dans une application graphique, via une interface tactile, via des boutons physiques, via la reconnaissance vocale…) ne nous intéresse pas ici.
On peut combiner les demandes :
Préférer les paramètres.
Un algorithme avec paramètres est toujours plus intéressant qu’un algorithme qui demande les données et affiche le résultat car il peut être utilisé (appelé) dans un autre algorithme pour résoudre une partie du problème.
Rien n’empêche d’écrire, à partir de là, un algorithme qui interagit avec l’utilisateur et fait appel à l’algorithme qui réalise le calcul. Par exemple :
Conversion en heures-minutes-secondes Écrire un algorithme qui permet à l’utilisateur de donner le nombre de secondes écoulées depuis minuit et qui affiche le moment de la journée correspondant en heures-minutes-secondes. Par exemple, si on est 3726 secondes après minuit alors il est 1h2’6”.
= Une question de choix =
Vous avez déjà eu l’occasion d’aborder les alternatives lors de votre initiation aux algorithmes sur le site code.org. Par exemple, vous avez indiqué au zombie quelque chose comme : S’il existe un chemin à gauche alors tourner à gauche.
Les alternatives permettent de n’exécuter des instructions que si une certaine "condition" est vérifiée. Avec le zombie, vous testiez son environnement ; dans nos algorithmes, vous allez tester les données.
Les algorithmes vus jusqu’à présent ne proposent qu’un seul chemin, une seule histoire. À chaque exécution de l’algorithme, les mêmes instructions s’exécutent dans le même ordres. Les alternatives permettent de créer des histoires différentes, d’adapter les instructions aux valeurs concrètes des données. Procédons par étapes.
Le si.
Il existe des situations où des instructions ne doivent pas toujours être exécutées et un test va nous permettre de le savoir.
Exemple..
Supposons que la variable contienne un nombre positif ou négatif, on ne sait pas. Et supposons qu’on veuille le rendre positif. On peut tester son signe. S’il est négatif on peut l’inverser. Par contre, s’il est positif, il n’y a rien à faire. Voici comment on peut l’écrire, graphiquement et en LDA :
6cm
[node distance = 1.5cm, auto] (Test) nb<0 ?; (Instr) nb -nb; (Empty) ; (End) ; (Test) – (Instr) node[near start] Vrai; (Instr) – (End); (Test) to[out=0,in=0] node[near start] Faux (End);
6cm
[1] nb -nb
Traçons-le dans deux cas différents pour bien illustrer son déroulement.
La condition peut être n’importe quelle expression (calcul) dont le résultat est un booléen (vrai ou faux).
Attention ! Vous faites parfois la confusion. Un si n’est pas une règle que l’ordinateur doit apprendre et exécuter à chaque fois que l’occasion se présente. La condition n’est testée que lorsqu’on arrive à cet endroit de l’algorithme.
Compréhension Tracez cet algorithme et donnez la valeur de retour.
c 2 * a c c - b c
2
Simplification d’algorithmes Voici quelques extraits d’algorithmes corrects du point de vue de la syntaxe mais contenant des lourdeurs d’écriture. Simplifiez-les.
nombre
nombre
nombre
nombre
Le si-sinon.
La construction permet d’exécuter certaines instructions ou d’autres en fonction d’un test. Pour illustrer cette instruction, nous allons nous pencher sur un grand classique, la recherche de maximum.
Exemple..
Supposons qu’on veuille déterminer le maximum de deux nombres, c’est-à-dire la plus grande des deux valeurs. Dans la solution, il y a deux chemins possibles. Le maximum devra pendre la valeur du premier nombre ou du second selon que le premier est plus grand que le second ou pas.
6cm
[node distance = 1.5cm, auto] (Test) nb1>nb2 ?; (Empty) ; (If) max nb1; (Else) max nb2; (End) ; (Test) -| (If) node[left, midway] Vrai; (If) |- (End); (Test) -| (Else) node[right, midway] Faux; (Else) |- (End);
6cm
[1] max nb1 max nb2
Traçons-le dans différentes situations.
Le cas où les deux nombres sont égaux est également géré.
Compréhension Tracez ces algorithmes et donnez la valeur de retour.
c a DIV b c b MOD a c
2
ok x1 > x2 ok ok ET x1 = 4 ok ok OU x2 = 3 x1 x1 * 1000 x1 + x2
2
Simplification d’algorithmes Voici quelques extraits d’algorithmes corrects du point de vue de la syntaxe mais contenant des lignes inutiles ou des lourdeurs d’écriture. Remplacer chacune de ces portions d’algorithme par un minimum d’instructions qui auront un effet équivalent.
[t]7cm
ok vrai ok faux
[t]7cm
ok faux ok vrai
Maximum de 2 nombres Écrire un algorithme qui, étant donné deux nombres quelconques, recherche et retourne le plus grand des deux. Attention ! On ne veut pas savoir si c’est le premier ou le deuxième qui est le plus grand mais bien quelle est cette plus grande valeur. Le problème est donc bien défini même si les deux nombres sont identiques.
Solution. Une solution complète est disponible dans la fiche .
Calcul de salaire Dans une entreprise, une retenue spéciale de 15% est pratiquée sur la partie du salaire mensuel qui dépasse 1200 . Écrire un algorithme qui calcule le salaire net à partir du salaire brut. En quoi l’utilisation de constantes convient-elle pour améliorer cet algorithme ?
Fonction de Syracuse Écrire un algorithme qui, étant donné un entier formula_68 quelconque, retourne le résultat de la fonction formula_88
Tarif réduit ou pas Dans une salle de cinéma, le tarif plein pour une place est de 8. Les personnes ayant droit au tarif réduit payent 7. Écrire un algorithme qui reçoit un booléen indiquant si la personne peut bénéficier du tarif réduit et qui retourne le prix à payer.
Le si-sinon-si.
Avec cette construction, on peut indiquer à un endroit de l’algorithme plus que deux chemins possibles. Partons à nouveau d’un exemple pour illustrer cette instruction.
Exemple..
On voudrait mettre dans la chaine la valeur , ou selon qu’un nombre donné est positif, négatif ou nul.
Ici, lorsqu’on va examiner le nombre, trois chemins vont s’offrir à nous.
9cm
[auto] (Test)   ; (nul) signe “nul”; (pos) signe “positif”; (neg) signe “négatif”; (End) ; (Test) -| (pos) node[left, near end] nb>0; (Test) – (nul) node[midway] nb=0; (Test) -| (neg) node[right, near end] nb<0; (pos) |- (End); (nul) – (End); (neg) |- (End);
4cm
[1] signe “positif” signe “nul” signe “négatif”
Traçons-le
Remarques..
Maximum de 3 nombres Écrire un algorithme qui, étant donné trois nombres quelconques, recherche et retourne le plus grand des trois.
Le signe Écrire un algorithme qui affiche un message indiquant si un entier est strictement négatif, nul ou strictement positif.
Le type de triangle Écrire un algorithme qui indique si un triangle dont on donne les longueurs de ses 3 côtés est : équilatéral (tous égaux), isocèle (2 égaux) ou quelconque.
Dés identiques Écrire un algorithme qui lance trois dés et indique si on a obtenu 3 dés de valeur identique, 2 ou aucun.
Grade Écrire un algorithme qui retourne le grade d’un étudiant suivant la moyenne qu’il a obtenue.
Un étudiant ayant obtenu
Le selon-que.
Cette nouvelle instruction permet d’écrire plus lisiblement "certains" , plus précisément quand le choix d’une branche dépend de la valeur précise d’une variable (ou d’une expression).
Exemple..
Imaginons qu’une variable () contienne un numéro de jour de la semaine et qu’on veuille mettre dans une variable () le nom du jour correspondant (“lundi” pour 1, “mardi” pour 2…)
On peut écrire une solution avec un mais le est plus lisible.
6cm
nomJour “lundi” nomJour “mardi” nomJour “mercredi” nomJour “jeudi” nomJour “vendredi” nomJour “samedi” nomJour “dimanche”
remplace avantageusement
nomJour “lundi” nomJour “mardi” nomJour “mercredi” nomJour “jeudi” nomJour “vendredi” nomJour “samedi” nomJour “dimanche”
Remarques..
La syntaxe générale est :
Instructions Instructions … Instructions Instructions
Numéro du jour Écrire un algorithme qui retourne le numéro du jour de la semaine reçu en paramètre (1 pour “lundi”, 2 pour “mardi”…).
Tirer une carte Écrire un algorithme qui affiche l’intitulé d’une carte tirée au hasard dans un paquet de 52 cartes. Par exemple, “As de cœur”, “3 de pique”, “Valet de carreau” ou encore “Roi de trèfle”.
Nombre de jours dans un mois Écrire un algorithme qui retourne le nombre de jours dans un mois. Le mois est lu sous forme d’un entier (1 pour janvier…). On considère dans cet exercice que le mois de février comprend toujours 28 jours.
Exercices de synthèse.
Dans les exercices qui suivent, à vous de déterminer si une instruction de choix est nécessaire et laquelle est la plus adaptée.
Réussir DEV1 Pour réussir l’UE (unité d’enseignement) DEV1, il faut que la cote attribuée à cette UE soit supérieure ou égale à 50%. Cette cote tient compte de votre examen intégré et de vos interrogations. Écrire un algorithme qui reçoit la cote finale (sur 100) d’un étudiant pour l’UE DEV1 et qui indique si l’étudiant a réussi cette UE.
Réussir GEN1 [algo:réussirGEN1] Pour réussir l’unité d’enseignement GEN1, il faut que la cote attribuée à chaque AA (activité d’apprentissage) soit supérieure ou égale à 50%. Écrire un algorithme qui reçoit les 3 cotes (sur 20) d’AA d’un étudiant pour l’UE GEN1 et qui affiche un message indiquant si l’étudiant a réussi ou pas. S’il a réussi, l’algorithme affiche également sa moyenne (cherchez quelle est la pondération entre ces AA).
La fourchette Écrire un algorithme qui, étant donné trois nombres, retourne vrai si le premier des trois appartient à l’intervalle donné par le plus petit et le plus grand des deux autres (bornes exclues) et faux sinon. Qu’est-ce qui change si on inclut les bornes ?
Le prix des photocopies Un magasin de photocopies facture 0,10 les dix premières photocopies, 0,09 les vingt suivantes et 0,08 au-delà. Écrivez un algorithme qui reçoit le nombre de photocopies effectuées et qui affiche la facture correspondante.
Le stationnement alternatif Dans une rue où se pratique le stationnement alternatif, du 1 au 15 du mois, on se gare du côté des maisons ayant un numéro impair, et le reste du mois, on se gare de l’autre côté. Écrire un algorithme qui, sur base de la date du jour et du numéro de maison devant laquelle vous vous êtes arrêté, retourne vrai si vous êtes bien stationné et faux sinon.
= Décomposer le problème =
Motivation.
Jusqu’à présent, les problèmes que nous avons abordés étaient relativement petits. Nous avons pu les résoudre avec un algorithme d’un seul tenant.
Dans la réalité, les problèmes sont plus gros et il devient nécessaire de les décomposer en sous-problèmes. On parle d’une "approche modulaire". Les avantages d’une telle décomposition sont multiples.
Parmis les autres avantages, que vous pourrez moins percevoir en début d’apprentissage, citons la possibilité de répartir le travail dans une équipe.
Un algorithme qui résout une partie de problème est parfois appelé fonction, procédure, méthode ou encore module en fonction du langage et du contexte. Il y a quelques nuances mais elles importent peu ici.
Exemple.
Illustrons l’approche modulaire sur le calcul du maximum de 3 nombres.
Commençons par écrire la solution du problème plus simple :  le maximum de 2 nombres.
6cm
7cm
max a max b max
Pour le maximum de 3 nombres, il existe plusieurs approches. Voyons celle-ci :
1) Calculer le maximum des deux premiers nombres, soit 2) Calculer le maximum de et du troisième nombre, ce qui donne le résultat.
qu’on peut illustrer ainsi :
[auto] (a) at (0,4) a (réel); (b) at (0,2) b (réel); (c) at (0,0) c (réel); (max2a) at (2,3) max2; (max2b) at (4,2) max2; (r) at (6,2) réel; (1,0) rectangle (5,4) node[above] max3; (a) to (max2a); (b) to (max2a); (c) to (max2b); (max2a) to (max2b); (max2b) to (r);
Sur base de cette idée, on voit que calculer le maximum de trois nombres peut se faire en calculant deux fois le maximum de deux nombres. On ne va évidemment pas "recopier" dans notre solution ce qu’on a écrit pour le maximum de deux nombres ; on va plutôt y faire référence, c’est-à-dire appeler l’algorithme . Ce qui donne :
maxab max2(a,b) max max2(maxab,c) max
qu’on peut encore simplifier en :
max2( max2(a,b) ,c)
Les paramètres.
Jusqu’à présent, nous avons considéré que les paramètres d’un algorithme (ou "module") correspondent à ses données et que le résultat, unique, est retourné.
Il s’agit d’une situation fréquente mais pas obligatoire que nous pouvons généraliser. En pratique, on peut rencontrer trois sortes de paramètres.
Le paramètre en entrée.
Le paramètre en entrée est ce que nous connaissons déjà. Il correspond à une donnée de l’algorithme. Une valeur va lui être attribuée en début d’algorithme et elle ne sera pas modifiée. On pourra faire suivre le nom du paramètre d’une flèche vers le bas () pour rappeler son rôle.
Lors de l’appel, on fournit la valeur ou, plus généralement une expression dont la valeur sera donnée au paramètre. Voici un cas général de paramètre en entrée.
4cm
monAlgo(expr)
8cm
C’est comme si l’algorithme commençait par l’affectation .
Exemple. Reprenons l’exemple de en ajoutant un petit test.
[1] max max3(3, 2, 5) max maxab max2(a,b) max max2(maxab,c) max
Traçons son exécution.
Note : Dans cet exemple, on trouve deux fois la variable . Il s’agit bien de deux variables différentes ; l’une est définie et connue dans  ; l’autre l’est dans .
Le paramètre en sortie.
Le paramètre en sortie correspond à un résultat de l’algorithme. Avec la notation que nous utilisons, un algorithme ne peut retourner qu’une seule valeur ce qui est parfois une contrainte trop forte. Les paramètres en sortie vont permettre à l’algorithme de fournir plusieurs réponses. On fera suivre le nom du paramètre d’une flèche vers le haut () pour rappeler son rôle. Un tel paramètre n’aura pas de valeur au début de l’algorithme mais s’en verra attribuer une par l’algorithme.
Lors de l’appel, on fournit une variable qui recevra la valeur finale du paramètre. Voici un cas général de paramètre en sortie.
4cm
monAlgo(variable)
8cm
Il n’y a pas de puisque les résultats sont en paramètres de sortie et pas comme valeur "retournée". C’est comme si, à la fin de l’algorithme appelé, on avait l’assignation : .
Exemple..
On peut envisager un algorithme qui reçoit une durée exprimée en seconde et fournisse trois paramètres en sortie correspondant à cette même durée exprimée en heures, minutes et secondes. En voici le schéma et la solution :
Voici une solution et un appel possible.
[1] heuresÉcoulées totalSec DIV (60*60) minutesÉcoulées totalSec MOD (60*60) DIV 60 secondesÉcoulées totalSec MOD 60 versHMS(65536, heure, minute, seconde)
Traçons-le.
Le paramètre en entrée-sortie.
Le paramètre en entrée-sortie correspond à une situation mixte. Il est à la fois une donnée et un résultat de l’algorithme. Cela signifie que l’algorithme a pour but de le modifier. Un tel paramètre sera suivi d’une double flèche ().
Lors de l’appel, on fournit une variable. Sa valeur est donnée au paramètre au début de l’algorithme. À la fin de l’algorithme, la variable reçoit la valeur du paramètre. Voici un cas général de paramètre en sortie.
4cm
monAlgo(variable)
8cm
C’est comme si, dans le code appelé, on avait une première ligne pour donner sa valeur au paramètre () et une dernière ligne pour effectuer l’assignation opposée (). Il n’y a pas de .
Exemple..
On a déjà vu un algorithme qui retourne la valeur absolue d’un nombre. On pourrait imaginer une variante qui modifie le nombre reçu. En voici le schéma et la solution avec un appel possible :
6cm
6cm
[1] nb -nb température -12.5 valAbsolue(température) température
Traçons-le.
La valeur de retour.
Une valeur de retour est toujours possible, mais jamais obligatoire, quelles que soient les sortes de paramètres. Ainsi, on peut imaginer un algorithme qui possède un paramètre en sortie et qui retourne également une valeur.
Attention ! Un algorithme qui ne retourne rien (pas de ) n’a pas de valeur ; il ne peut pas apparaitre dans une expression ou être assigné à une variable. Ainsi, les utilisations suivantes de l’algorithme , décrit plus haut, sont incorrectes.
valAbsolue(température) + 1 tempAbsolue valAbsolue(température)
Si un algorithme possède une seule valeur en sortie, on préférera toujours une valeur en retour à un paramètre en sortie; le code appelant sera plus lisible.
Résumons.
Reprenons tout ce qu’on vient de voir avec un exemple d’algorithme qui possède tous les types de paramètres.
[1] quotient resteDiv compteurAppels quotient resteDiv compteurAppels Le code proprement dit de l’algorithme quotient
Traçons-le.
Pour mieux se comprendre, il est utile d’introduire un peu de vocabulaire. Les paramètres déclarés dans l’entête d’un algorithme sont appelés paramètres formels. Les paramètres donnés à l’appel de l’algorithme sont appelés paramètres effectifs.
Les instructions en gris dans l’exemple ne sont pas écrites mais c’est comme si elles étaient présentes pour initialiser les paramètres formels et en début d’algorithme et pour donner des valeurs aux paramètres effectifs et en fin d’algorithme.
À la fin de l’algorithme, c’est comme si la valeur retournée "remplaçait" l’appel. Dans notre exemple, c’est donc cette valeur retournée qui sera affichée.
Les figures [fig:parin], [fig:parout] et [fig:parinout] résument de manière graphique les trois types de passage de paramètres.
[fig:parin]
[fig:parout]
[fig:parinout]
Exercices.
Tracer des algorithmes Indiquer quels nombres sont successivement affichés lors de l’exécution des algorithmes ex1, ex2, ex3 et ex4.
addition(3, 4, x) x x 3 y 5 addition(x, y, y) y somme a + b c somme
addition(3, 4, a) voir ci-dessus a a 3 b 5 addition(b, a, b) b
calcul(3, 4, c) c a 3 b 4 c 5 calcul(b, c, a) a, b, c a 2 * a b 3 * b c a + b
a 3 b 4 c f(b) c calcul2(a, b, c) a, b, c a f(a) c 3 * b c a + c b 2 * a + 1 b
Appels de module Parmi les instructions suivantes (où les variables , et sont des entiers), lesquelles font correctement appel à l’algorithme d’en-tête suivant ?
a PGCD(24, 32) a PGCD(a, 24) b 3 * PGCD(a + b, 2*c) + 120 PGCD(20, 30) a PGCD(a, b, c) a PGCD(a, b) + PGCD(a, c) a PGCD(a, PGCD(a, b)) PGCD(a, b) PGCD(a, b) PGCD(a, b) c
Maximum de 4 nombres Écrivez un algorithme qui calcule le maximum de 4 nombres.
Écart entre 2 durées Étant donné deux durées données chacune par trois nombres (heure, minute, seconde), écrire un algorithme qui calcule le délai écoulé entre ces deux durées en heure(s), minute(s), seconde(s) sachant que la deuxième durée donnée est plus petite que la première.
Réussir GEN1 Reprenons l’exercice . Cette fois-ci on ne veut rien afficher mais fournir deux résultats : un booléen indiquant si l’étudiant a réussi ou pas et un entier indiquant sa cote (qui n’a de sens que s’il a réussi).
Tirer une carte L’exercice suivant a déjà été résolu. Refaites une solution modulaire.
Écrire un algorithme qui affiche l’intitulé d’une carte tirée au hasard dans un paquet de 52 cartes. Par exemple, “As de cœur”, “3 de pique”, “Valet de carreau” ou encore “Roi de trèfle”.
Nombre de jours dans un mois Écrire un algorithme qui donne le nombre de jours dans un mois. Il reçoit en paramètre le numéro du mois (1 pour janvier…) ainsi que l’année. Pour le mois de février, il faudra répondre 28 ou 29 selon que l’année fournie est bissextile ou pas. Vous devez réutiliser au maximum ce que vous avez déjà fait lors d’exercices précédents (cf. exercice ).
Valider une date Écrire un algorithme qui valide une date donnée par trois entiers :  l’année, le mois et le jour. Vous devez réutiliser au maximum ce que vous avez déjà fait lors d’exercices précédents.
Généraliser un algorithme Dans l’exercice , nous avons écrit un algorithme pour tester si un nombre est divisible par 5. Si on vous demande à présent un algorithme pour tester si un nombre est divisible par 3, vous le feriez sans peine. Idem pour tester la divisibilité par 2, 4, 6, 7, 8, 9… mais vous vous lasseriez bien vite.
N’est-il pas possible d’écrire un seul algorithme, plus général, qui résolve tous ces problèmes d’un coup ?
= Un travail répétitif =
Les ordinateurs révèlent tout leur potentiel dans leur capacité à répéter inlassablement les mêmes tâches. Vous avez pu appréhender les boucles lors de votre initiation sur le site code.org. Voyons comment utiliser à bon escient des boucles dans nos codes.
Attention ! D’expérience, nous savons que ce chapitre est difficile à appréhender. Beaucoup d’entre vous perdent pied ici. Accrochez-vous, faites bien tous les exercices proposés, montrez vos solutions à votre professeur et demandez de l’aide dès que vous vous sentez perdu !
La notion de travail répétitif.
Si on veut faire effectuer un travail répétitif, il faut indiquer deux choses :
Examinons quelques exemples pour fixer notre propos.
Exemple 1..
Pour traiter des dossiers, on dira quelque chose comme « tant qu’il reste un dossier à traiter, le traiter » ou encore « traiter un dossier puis passer au suivant jusqu’à ce qu’il n’en reste plus à traiter ».
Exemple 2..
Pour calculer la cote finale de tous les étudiants, on aura quelque chose du genre « Pour tout étudiant, calculer sa cote ».
Exemple 3..
Pour afficher tous les nombres de 1 à 100, on aura « Pour tous les nombres de 1 à 100, afficher ce nombre ».
Une même instruction, des effets différents.
Comprenez bien que c’est toujours la même tâche qui est exécutée mais pas avec le même effet à chaque fois. Ainsi, on traite un dossier mais à chaque fois un différent ; on affiche un nombre mais à chaque fois un différent.
Par exemple, la tâche à répéter pour afficher des nombres ne peut pas être ni ni… Par contre, on pourra utiliser l’instruction si on s’arrange pour que la variable s’adapte à chaque passage dans la boucle.
De façon générale, pour obtenir un travail répétitif, il faut trouver une formulation de la tâche qui va produire un effet différent à chaque fois. 
Exemple - Afficher les nombres de 1 à 5.
Si on veut un algorithme qui affiche les nombres de 1 à 5 sans utiliser de boucle, on pourrait écrire :
Ces cinq instructions sont proches mais pas tout-à-fait identiques. En l’état, on ne peut pas encore en faire une boucle  ; il va falloir ruser. On peut obtenir le même résultat avec l’algorithme suivant :
4cm
nb 1 nb 2 nb 3 nb 4 nb 5
ou encore
4cm
[1] nb 1 nb nb + 1 nb nb + 1 nb nb + 1 nb nb + 1 nb nb + 1
Il est plus compliqué, mais cette fois les lignes 2 et 3 se répètent exactement. D’ailleurs, la dernière ligne ne sert à rien d’autre qu’à obtenir cinq copies identiques. Le travail à répéter est donc :
nb nb + 1
Cette tâche doit être effectuée cinq fois dans notre exemple. Il existe plusieurs structures répétitives qui vont se distinguer par la façon dont on va contrôler le nombre de répétitions. Voyons-les une à une .
« tant que ».
r6cm
[>=triangle 60, node distance = 1.5cm, auto] (Test) condition vraie ?; (Instr) instructions à exécuter; (End) ; (Test) – (Instr) node[near start] Oui; (Test.east) to[in=0,out=0] node[near start] Non (End.east); (Instr.west) to[bend left] (Test.west);
Le « tant que » est une structure qui demande à l’exécutant de répéter une tâche (une ou plusieurs instructions) tant qu’une condition donnée est vraie.
séquence d’instructions à exécuter
Comme pour la structure , la est une expression à valeur booléenne. Dans ce type de structure, il faut qu’il y ait dans la séquence d’instructions comprise entre et au moins une instruction qui modifie une des composantes de la condition de telle manière qu’elle puisse devenir fausse à un moment donné. Dans le cas contraire, la condition reste indéfiniment vraie et la boucle va tourner sans fin, c’est ce qu’on appelle une boucle infinie. L’ordinogramme ci-dessus décrit le déroulement de cette structure. On remarquera que si la condition est fausse dès le début, la tâche n’est jamais exécutée.
Exemple - Afficher les nombres de 1 à 5.
Reprenons notre exemple d’affichage des nombres de 1 à 5. Pour rappel, la tâche à répéter est :
nb nb + 1
La condition va se baser sur la valeur de . On continue tant que le nombre n’a pas dépassé 5. Ce qui donne (en n’oubliant pas l’initialisation de ) :
5cm
[1] nb 1 nb nb + 1
8cm
Exemple - Généralisation à n nombres.
On peut généraliser l’exemple précédent en affichant tous les nombres de 1 à n où n est une donnée de l’algorithme.
nb 1 nb nb + 1
Exercices.
Compréhension d’algorithmes Quels sont les affichages réalisés lors de l’exécution des algorithmes suivants ?
[t]40mm
x 0 x x + 2 x
[t]45mm
x : entier ok vrai x 5 x x + 7 ok x MOD 11 formula_64 0 x
[t]50mm
cpt, x : entiers x 10 cpt 0 ok vrai x x + 1 ok x < 20 x x + 3 cpt cpt + 1 x
Afficher des nombres En utilisant un , écrire un algorithme qui reçoit un entier formula_68 positif et affiche
« pour ».
r7cm
[>=triangle 60, node distance = 1.5cm, auto] (Init) variable début; (Test) variable formula_223 fin ?; (Instr) instructions à exécuter; (Incr) variable variable + pas; (End) ; (Init) – (Test); (Test) – (Instr) node[near start] Vrai; (Test.east) to[in=-30,out=0] node[near start] Faux (End.south); (Instr) – (Incr); (Incr.west) to[bend left] (Test.west);
Ici, on va plutôt indiquer combien de fois la tâche doit être répétée. Cela se fait au travers d’une variable de contrôle dont la valeur va évoluer à partir d’une valeur de départ jusqu’à une valeur finale.
séquence d’instructions à exécuter
Dans ce type de structure, , et peuvent être des constantes, des variables ou des expressions entières.
Le est facultatif, et généralement omis (dans ce cas, sa valeur par défaut est 1).
La boucle s’arrête lorsque la variable dépasse la valeur de .
La variable de contrôle ne servant que pour la boucle et étant forcement entière, on va considérer qu’il n’est pas nécessaire de la déclarer et qu’elle n’est pas utilisable en dehors de la boucle .
Exemples.
Reprenons notre exemple d’affichage des nombres de 1 à 5. Voici la solution avec un et le traçage correspondant.
55mm
[1] par défaut le pas est de 1 nb “nb n’existe plus”
75mm
Si on veut généraliser l’affichage à n nombres, on a :
nb
Un pas négatif.
r6cm
[>=triangle 60, node distance = 1.5cm, auto] (Init) variable début; (Test) variable formula_229 fin ?; (Instr) instructions à exécuter; (Incr) variable variable + pas; (End) ; (Init) – (Test); (Test) – (Instr) node[near start] Vrai; (Test.east) to[in=-30,out=0] node[near start] Faux (End.south); (Instr) – (Incr); (Incr.west) to[bend left] (Test.west);
Le pas est parfois négatif, dans le cas d’un compte à rebours, par exemple. Dans ce cas, la boucle s’arrête lorsque la variable prend une valeur plus petite que la valeur de (cf. le test dans l’organigramme ci-contre).
Exemple : Compte à rebours à partir de n.
nb “Partez !”
Cohérence.
Il faut veiller à la cohérence de l’écriture de cette structure. On considérera qu’au cas (à éviter) où est strictement supérieur à et le est positif, la séquence d’instructions n’est jamais exécutée (mais ce n’est pas le cas dans tous les langages de programmation !). Idem si est strictement inférieur à mais avec un négatif.
Exemples :
i 2 0 La boucle n’est pas exécutée. i 1 10 -1 La boucle n’est pas exécutée. i 1 1 5 La boucle est exécutée 1 fois.
Modification des variables de contrôle.
Il est important de ne pas modifier dans la séquence d’instructions une des variables de contrôle , ou  ! Il est aussi fortement déconseillé de modifier « manuellement » la de contrôle au sein de la boucle . Il ne faut pas l’initialiser en début de boucle, et ne pas s’occuper de sa modification, l’instruction étant automatique et implicite à chaque étape de la boucle.
Exemple – Afficher uniquement les nombres pairs.
Cette fois-ci on affiche uniquement les nombres pairs jusqu’à la limite formula_68.
Exemple : Les nombres pairs de formula_67 à formula_232 sont : formula_233, formula_58, formula_3, formula_236, formula_232.
Notez que formula_68 peut être impair. Si formula_68 vaut formula_240, l’affichage est le même que pour formula_232. On peut utiliser un pour. Une solution possible est :
nb
La section sur les suites proposera d’autres solutions pour ce problème.
Exercices.
Compréhension d’algorithmes Quels sont les affichages réalisés lors de l’exécution des algorithmes suivants ?
[t]6cm
x 3 ok vrai x x + i ok ok ET (x MOD 2 = 0) x 2 * x
[t]6cm
fin 6 * i - 11 10 * i + j
Afficher des nombres Reprenons un exercice déjà donné avec le . En utilisant un , écrire un algorithme qui reçoit un entier formula_68 positif et affiche
« faire – tant que ».
r4cm
[>=triangle 60, node distance = 2cm, auto] (Instr) instructions à exécuter; (Test) Condition vraie ?; (End) ; (Instr) – (Test); (Test) – (End) node[near start] Non; (Test.east) to[in=0,out=0] node[near start] Oui (Instr.east);
Cette structure est très proche du «faire - tant que » à ceci près que le test est fait à la fin et pas au début . La tâche est donc toujours exécutée au moins une fois.
séquence d’instructions à exécuter
Comme avec le tant-que, il faut que la séquence d’instructions comprise entre et contienne au moins une instruction qui modifie la condition de telle manière qu’elle puisse devenir vraie à un moment donné pour arrêter l’itération. Le schéma ci-contre décrit le déroulement de cette boucle.
Exemple.
Reprenons notre exemple d’affichage des nombres de 1 à 5. Voici la solution et le traçage correspondant.
5cm
[1] nb 1 nb nb + 1
8cm
Exercices.
Compréhension d’algorithmes Quels sont les affichages réalisés lors de l’exécution des algorithmes suivants ?
x 1 p 1 p 2 * p x x + p pair x MOD 2 = 0 grand x > 15 x
Afficher des nombres Reprenons un exercice déjà fait avec le et le en utilisant cette fois un . Écrire un algorithme qui reçoit un entier formula_68 positif et affiche
Quel type de boucle choisir ?
En pratique, il est possible d’utiliser systématiquement la boucle qui peut s’adapter à toutes les situations. Cependant, il est plus clair d’utiliser la boucle dans les cas où le nombre d’itérations est fixé et connu à l’avance (par là, on veut dire que le nombre d’itérations est déterminé au moment où on arrive à la boucle). La boucle convient quant à elle dans les cas où le contenu de la boucle doit être parcouru au moins une fois, alors que dans , le nombre de parcours peut être nul si la condition initiale est fausse. La schéma ci-dessous propose un récapitulatif.
 [fig:boucle-choix]
Acquisition de données multiples.
Il existe des problèmes où l’algorithme doit demander une série de valeurs à l’utilisateur pour pouvoir les traiter. Par exemple, les sommer, en faire la moyenne, calculer la plus grande…
Dans ce genre de problème, on va devoir stocker chaque valeur donnée par l’utilisateur dans une seule et même variable et la traiter avant de passer à la suivante. Prenons un exemple concret pour mieux comprendre.
On veut pouvoir calculer (et retourner) la somme d’une série de nombres donnés par l’utilisateur.
Il faut d’abord se demander comment l’utilisateur va pouvoir indiquer combien de nombres il faut additionner ou quand est-ce que le dernier nombre à additionner a été entré. Voyons quelques possibilités.
Variante 1 : nombre de valeurs connu.
L’utilisateur indique le nombre de termes au départ. Ce problème est proche de ce qui a déjà été fait.
Lit des valeurs entières et retourne la somme des valeurs lues. Variante 1 nb de valeurs à additionner un des termes de l’addition la somme somme 0 la somme se construit petit à petit. 0 au départ nbValeurs valeur somme somme + valeur somme
Afficher les nombres impairs Écrire un algorithme qui demande une série de valeurs entières à l’utilisateur et qui affiche celles qui sont impaires. L’algorithme commence par demander à l’utilisateur le nombre de valeurs qu’il désire donner.
Variante 2 : stop ou encore.
Après chaque nombre, on demande à l’utilisateur s’il y a encore un nombre à additionner.
Ici, il faut chercher une solution différente car on ne connait pas au départ le nombre de valeurs à additionner et donc le nombre d’exécution de la boucle. On va devoir passer à un « tant que » ou un «faire - tant que». On peut envisager de demander en fin de boucle s’il reste encore un nombre à additionner. Ce qui donne :
Lit des valeurs entières et retourne la somme des valeurs lues. Variante 2a est-ce qu’il reste encore une valeur à additionner ? un des termes de l’addition la somme somme 0 valeur somme somme + valeur encore somme
Avec cette solution, on additionne au moins une valeur. Si on veut pouvoir tenir compte du cas très particulier où l’utilisateur ne veut additionner aucune valeur, il faut utiliser un « tant que » et donc poser la question avant d’entrer dans la boucle.
Lit des valeurs entières et retourne la somme des valeurs lues. Variante 2b est-ce qu’il reste encore une valeur à additionner ? un des termes de l’addition la somme somme 0 encore valeur somme somme + valeur encore somme
Compter les nombres impairs Écrire un algorithme qui demande une série de valeurs entières à l’utilisateur et qui lui affiche le nombre de valeurs impaires qu’il a donné. Après chaque valeur entrée, l’algorithme demande à l’utilisateur s’il y en a encore d’autres.
Variante 3 : valeur sentinelle.
L’utilisateur entre une valeur spéciale pour indiquer la fin. On parle de valeur sentinelle. Ceci n’est possible que si cette valeur sentinelle ne peut pas être un terme valide de l’addition. Par exemple, si on veut additionner des nombres positifs uniquement, la valeur -1 peut servir de valeur sentinelle. Mais sans limite sur les nombres à additionner (positifs, négatifs ou nuls), il n’est pas possible de choisir une sentinelle.
Ici, on se base sur la valeur entrée pour décider si on continue ou pas. Il faut donc toujours effectuer un test après une lecture de valeur. C’est pour cela qu’il faut effectuer une lecture avant la boucle et une autre à la fin de la boucle.
Lit des valeurs entières positives et retourne la somme des valeurs lues. La valeur sentinelle est -1. Variante 3 un des termes de l’addition la somme somme 0 valeur somme somme + valeur valeur remarquer l’endroit où on lit une valeur. somme
Choix de la valeur sentinelle Quelle valeur sentinelle prendrait-on pour additionner une série de cotes d’interrogations ? Une série de températures ?
Afficher les nombres impairs Écrire un algorithme qui demande une série de valeurs entières non nulles à l’utilisateur et qui affiche celles qui sont impaires. La fin des données sera signalée par la valeur sentinelle 0.
Compter le nombre de réussites Écrire un algorithme qui demande une série de cotes (entières, sur 20) à l’utilisateur et qui affiche le pourcentage de réussites. La fin des données sera signalée par une valeur sentinelle que vous pouvez choisir.
Les suites.
Nous avons vu quelques exemples d’algorithmes qui affichent une suite de nombres (par exemple, afficher les nombres pairs). Nous avons pu les résoudre facilement avec un en choisissant judicieusement les valeurs de début et de fin ainsi que le pas.
Ce n’est pas toujours aussi simple. Nous allons voir deux exemples plus complexes et les solutions qui vont avec. Elles pourront se généraliser à beaucoup d’autres exemples.
Exemple - Afficher les carrés.
On veut afficher les formula_68 premiers nombres carrés parfaits : formula_67, formula_58, formula_262, formula_263, formula_264…
Si on vous demande : “Quel est le 7 nombre à afficher ?”. Vous répondrez : “Facile ! C’est formula_265, soit formula_266”. Plus généralement, le nombre à afficher lors du formula_267 passage dans la boucle est formula_268.
l|*8>m8mm étape & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8valeur à afficher & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64
L’algorithme qui en découle est :
formula_268
Dans cette solution, la variable de contrôle compte simplement le nombre d’itérations. On calcule le nombre à afficher en fonction cette variable de contrôle (ici le carré convient). Par une vieille habitude des programmeurs , une variable de contrôle qui se contente de compter les passages dans la boucle est souvent nommée formula_267. On l’appelle aussi « itérateur ».
Cette solution peut être utilisée chaque fois qu’on peut calculer le nombre à afficher en fonction de formula_267.
Exemple - Une suite un peu plus complexe.
Écrire un algorithme qui affiche les formula_68 premiers nombres de la suite : 1, 2, 4, 7, 11, 16…
Comme on peut le constater, à chaque étape on ajoute un peu plus au nombre précédent. formula_273
Ici, difficile de partir de la solution de l’exemple précédent car il est n’est pas facile de trouver la fonction formula_274 qui permet de calculer le nombre à afficher en fonction de i.
Par contre, il est assez simple de calculer ce nombre en fonction du précédent. formula_275 Sauf pour le premier, qui ne peut pas être calculé en fonction du précédent. Une solution élégante et facilement adaptable à d’autres situations est :
val "1 valeur à afficher" val val "la valeur suivante calculée à partir de la valeur courante"
qui, dans notre exemple précis, devient :
affiche la suite 1 2 4 7 11 16 ... val 1 val val val + i
Suites Écrire les algorithmes qui affichent les formula_68 premiers termes des suites suivantes. À vous de voir quel est le canevas de solution le plus adapté.
Exercices récapitulatifs.
Pour tous ces exercices, nous vous donnons peu d’indications sur la solution à mettre en œuvre. À vous de jouer…
Lire un nombre Écrire un algorithme qui demande à l’utilisateur un nombre entre 1 et formula_68 et le retourne. Si la valeur donnée n’est pas dans l’intervalle souhaité, l’utilisateur est invité à rentrer une nouvelle valeur jusqu’à ce qu’elle soit correcte.
Solution..
Si la valeur donnée par l’utilisateur était toujours correcte, il suffirait d’écrire :
val
Pour tenir compte des entrées invalides, il faut ajouter une boucle qui prévient que la valeur est mauvaise et la redemande. Et ceci, tant que c’est incorrect. Ce qui donne :
“valeur incorrecte” val
La solution qu’on obtient est proche d’une lecture répétée avec valeur sentinelle. Dans ce cas, la valeur sentinelle est toute valeur correcte.
Lancé de dés Écrire un algorithme qui lance formula_68 fois un dé et compte le nombre de fois qu’une certaine valeur est obtenue.
Factorielle Écrire un algorithme qui retourne la factorielle de formula_68 (entier positif ou nul). Rappel : la factorielle de formula_68, notée formula_68!, est le produit des formula_68 premiers entiers strictement positifs.
Par convention, 0! = 1.
Produit de 2 nombres Écrire un algorithme qui retourne le produit de deux entiers quelconques sans utiliser l’opérateur de multiplication, mais en minimisant le nombre d’opérations.
Table de multiplication
[t]10cm Écrire un algorithme qui affiche la table de multiplication des nombres de 1 à 10 (cf. l’exemple ci-contre).
Attention ! Nous somme en algorithmique, ne vous préoccupez pas de la mise en page de ce qui est affiché. Ce sera une question importante quand vous traduirez l’algorithme dans un langage de programmation mais pas ici.
[t]4cm
Double 6 Écrire un algorithme qui lance de façon répétée deux dés. Il s’arrête lorsqu’il obtient un double 6 et retourne le nombre de lancés effectués.
Nombre premier Écrire un algorithme qui vérifie si un entier positif est un nombre premier.
Rappel : un nombre est premier s’il n’est divisible que par 1 et par lui-même. Le premier nombre premier est 2.
Nombres premiers Écrire un algorithme qui affiche les nombres premiers inférieurs ou égaux à un entier positif donné. Le module de cet algorithme fera appel de manière répétée mais économique à celui de l’exercice précédent.
Somme de chiffres Écrire un algorithme qui calcule la somme des chiffres qui forment un nombre naturel formula_68. Attention, on donne au départ le nombre et pas ses chiffres. Exemple : 133045 doit donner comme résultat 16, car 1 + 3 + 3 + 0 + 4 + 5 = 16.
Nombre parfait Écrire un algorithme qui vérifie si un entier positif est un nombre parfait, c’est-à-dire un nombre égal à la somme de ses diviseurs (sauf lui-même).
Par exemple, 6 est parfait car 6 = 1 + 2 + 3. De même, 28 est parfait car 28 = 1 + 2 + 4 + 7 + 14.
Décomposition en facteurs premiers Écrire un algorithme qui affiche la décomposition d’un entier en facteurs premiers. Par exemple, formula_284 donnerait comme décomposition formula_285.
Nombre miroir Le miroir d’un nombre est le nombre obtenu en lisant les chiffres de droite à gauche. Ainsi le nombre miroir de formula_286 est formula_287. Écrire un algorithme qui calcule le miroir d’un nombre entier positif donné.
Palindrome Écrire un algorithme qui vérifie si un entier donné forme un palindrome ou non. Un nombre palindrome est un nombre qui lu dans un sens (de gauche à droite) est identique au nombre lu dans l’autre sens (de droite à gauche). Par exemple, formula_288 est un nombre palindrome.
Jeu de la fourchette Écrire un algorithme qui simule le jeu de la fourchette. Ce jeu consiste à essayer de découvrir un nombre quelconque compris entre 1 et 100 inclus, tiré au sort par l’ordinateur (la primitive retourne un entier entre 1 et formula_68). L’utilisateur a droit à huit essais maximum. À chaque essai, l’algorithme devra afficher un message indicatif « nombre donné trop petit » ou « nombre donné trop grand ». En conclusion, soit « bravo, vous avez trouvé en [nombre] essai(s) » soit « désolé, le nombre était [valeur] ».
= Les tableaux =
Dans ce chapitre nous étudions les tableaux, une structure qui peut contenir plusieurs exemplaires de données similaires.
Utilité des tableaux.
Nous allons introduire la notion de tableau à partir d’un exemple dans lequel l’utilité de cette structure de données apparaitra de façon naturelle.
Exemple. Statistiques de ventes.
Un gérant d’une entreprise commerciale souhaite connaitre l’impact d’une journée de promotion publicitaire sur la vente de dix de ses produits. Pour ce faire, les numéros de ces produits (numérotés de 0 à 9 pour simplifier) ainsi que les quantités vendues pendant cette journée de promotion sont encodés au fur et à mesure de leurs ventes. En fin de journée, le vendeur entrera la valeur -1 pour signaler la fin de l’introduction des données. Ensuite, les statistiques des ventes seront affichées.
La démarche générale se décompose en trois parties :
Vous trouverez sur la page suivante une version possible de cet algorithme.
Calcule et affiche la quantité vendue de 10 produits. cpt0 0 cpt1 0 cpt2 0 cpt3 0 cpt4 0 cpt5 0 cpt6 0 cpt7 0 cpt8 0 cpt9 0 “Introduisez le numéro du produit :” numéroProduit “Introduisez la quantité vendue :” quantité 0 : cpt0 cpt0 + quantité 1 : cpt1 cpt1 + quantité 2 : cpt2 cpt2 + quantité 3 : cpt3 cpt3 + quantité 4 : cpt4 cpt4 + quantité 5 : cpt5 cpt5 + quantité 6 : cpt6 cpt6 + quantité 7 : cpt7 cpt7 + quantité 8 : cpt8 cpt8 + quantité 9 : cpt9 cpt9 + quantité “Introduisez le numéro du produit :” numéroProduit “quantité vendue de produit 0 :”, cpt0 “quantité vendue de produit 1 :”, cpt1 “quantité vendue de produit 2 :”, cpt2 “quantité vendue de produit 3 :”, cpt3 “quantité vendue de produit 4 :”, cpt4 “quantité vendue de produit 5 :”, cpt5 “quantité vendue de produit 6 :”, cpt6 “quantité vendue de produit 7 :”, cpt7 “quantité vendue de produit 8 :”, cpt8 “quantité vendue de produit 9 :”, cpt9
Il est clair, à la lecture de cet algorithme, qu’une simplification d’écriture s’impose ! Et que ce passerait-il si le nombre de produits à traiter était de 20 ou 100 ? Le but de l’informatique étant de dispenser l’humain des tâches répétitives, le programmeur peut en espérer autant de la part d’un langage de programmation ! La solution est apportée par un nouveau type de variables : les variables indicées ou tableaux.
Au lieu d’avoir à manier dix compteurs distincts (, , etc.), nous allons envisager une seule « grande » variable compartimentée en dix « cases » ou « sous-variables » (qu’on appelle aussi les « éléments » du tableau). Elles se distingueront les unes des autres par un numéro (on dit un « indice ») : deviendrait ainsi , deviendrait , et ainsi de suite jusqu’à qui deviendrait .
Un des intérêts de cette notation est la possibilité de faire apparaitre une variable entre les crochets, par exemple , ce qui permet une grande économie de lignes de code.
Voici la version avec tableau.
[tableau:tab1DStock10Articles]
[tableau:tab1DStock10Articles] Calcule et affiche la quantité vendue de 10 produits. cpt[i] 0 “Introduisez le numéro du produit :” numéroProduit “Introduisez la quantité vendue :” quantité cpt[numéroProduit] cpt[numéroProduit] + quantité “Introduisez le numéro du produit :” numéroProduit “quantité vendue de produit ”, i, “: ”, cpt[i]
Définitions.
Un tableau est une suite d’éléments de même type portant tous le même nom mais se distinguant les uns des autres par un indice.
L’indice est un entier donnant la position d’un élément dans la suite. Cet indice varie entre la position du premier élément et la position du dernier élément, ces positions correspondant aux bornes de l’indice. Notons qu’il n’y a pas de « trou » : tous les éléments existent entre le premier et le dernier indice.
La taille d’un tableau est le nombre de ses éléments. Attention ! la taille d’un tableau ne peut pas être modifiée pendant son utilisation.
Déclaration.
Pour déclarer un tableau, on écrit :
où est le nombre d’éléments et est le type des éléments que l’on trouvera dans le tableau. Tous les types sont permis mais tous les éléments sont du même type.
Utilisation.
Un élément (une case) du tableau peut être accédé via la notation
tab[i]
La première case du tableau porte l’indice , la dernière l’indice . C’est considéré comme une erreur d’indiquer un indice qui ne correspond pas à une case du tableau (trop petit ou trop grand). Par exemple, si on déclare : il est interdit d’utiliser ou .
Déclarer et initialiser Écrire un algorithme qui déclare un tableau de 100 chaines et met votre nom dans la 3 case du tableau.
Initialiser un tableau à son indice Écrire un algorithme qui déclare un tableau de 100 entiers et initialise chaque élément à la valeur de son indice. Ainsi, la case numéro formula_267 contiendra la valeur formula_267.
Initialiser un tableau aux valeurs de 1 à 100 Écrire un algorithme qui déclare un tableau de 100 entiers et y met les nombres de 1 à 100.
Compréhension Expliquez la différence entre et .
Initialisation compacte.
Chaque élément d’un tableau doit être manié avec la même précaution qu’une variable simple, c’est-à-dire qu’on ne peut utiliser un élément du tableau qui n’aurait pas été préalablement affecté ou initialisé. L’initialisation d’un tableau peut se faire via une série d’assignations, case par case mais on va aussi se permettre une notation compacte  :
Tableau et paramètres.
Le type "tableau" étant un type à part entière, il est tout-à-fait éligible comme type pour les paramètres et la valeur de retour d’un algorithme. Voyons cela en détail.
Passer un tableau en paramètre.
Les trois sortes de passages de paramètres sont possibles. Elles servent à spécifier ce qui sera fait avec les cases du tableau. Plus précisément :
Retourner un tableau.
Comme pour n’importe quel autre type, un algorithme peut retourner un tableau. Ce sera à lui de le déclarer et de lui donner des valeurs.
Exemple :
tab[i] i tab monTab créer()
Paramétrer la taille.
Un tableau peut être passé en paramètre à un algorithme mais qu’en est-il de sa taille ? Plus haut, nous avons écrit un algorithme qui affiche un tableau de 10 entiers. Il serait utile de pouvoir appeler le même algorithme avec des tableaux de tailles différentes. Pour permettre cela, la taille du tableau reçu en paramètre peut être déclarée avec un nom (habituellement "n") qui peut être considéré comme un paramètre entrant et peut être utilisé dans l’algorithme. Idem pour un tableau en retour.
Exemple :
“Tableau de ”, n, “ éléments”. tab[i] Crée un tableau d’entiers de taille n, l’initialise à 0 et le retourne. tab[i] 0 tab entiers créer(20) afficher(entiers)
La fiche récapitule tout ça.
Trouver les entêtes Écrire les entêtes (et uniquement les entêtes) des algorithmes qui résolvent les problèmes suivants :
Parcours d’un tableau.
Dans la plupart des problèmes que vous rencontrerez vous serez amené à parcourir un tableau. Il est important de maitriser ce parcours. Examinons les situations courantes et voyons quelles solutions conviennent.
Parcours complet.
Vous avez déjà vu dans les exemples comment parcourir tous les éléments d’un tableau. On s’en sort facilement avec une boucle . La fiche décrit comment afficher tous les éléments d’un tableau. On pourrait faire autre chose avec ces éléments : les sommer, les comparer…
Inverser le signe des éléments Écrire un algorithme qui inverse le signe de tous les éléments négatifs dans un tableau d’entiers.
Somme Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 entiers et qui retourne la somme de ses éléments.
Nombre d’éléments d’un tableau Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 réels et qui retourne le nombre d’éléments du tableau.
Compter les éléments négatifs Écrire un algorithme qui donne le nombre d’éléments négatifs dans un tableau d’entiers.
Parcours partiel.
Parfois, on ne doit pas forcément parcourir le tableau jusqu’au bout mais on pourra s’arrêter prématurément si une certaine condition est remplie. Par exemple :
Pour résoudre ce problème, on peut partir du parcours complet et :
La fiche détaille un parcours partiel.
Tester la présence de négatifs Écrire un algorithme qui détermine si un tableau d’entiers contient au moins un nombre négatif.
Y a-t-il un pilote dans l’avion ? Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 chaines et qui retourne un booléen indiquant s’il contient au moins un élément de valeur “pilote”.
Taille logique et taille physique.
Parfois, on ne sait pas exactement quelle taille doit avoir un tableau. Imaginons, par exemple, qu’il s’agisse de demander des valeurs à l’utilisateur et de les stocker dans un tableau pour un traitement ultérieur. Supposons que l’utilisateur va indiquer la fin des données par une valeur sentinelle. Impossible de savoir, à priori, combien de valeurs il va entrer et, par conséquent, la taille à donner au tableau.
Une solution est de créer un tableau suffisamment grand pour tous les cas quitte à n’en n’utiliser qu’une partie. Mais comment savoir quelle est la partie du tableau qui est effectivement utilisée ? Comprenez bien qu’il n’y a pas de concept de case vide. Rien ne différencie une case utilisée d’une case non utilisée. On s’en sort en stockant les valeurs dans la partie basse du tableau (à gauche) et en retenant, dans une variable, le nombre de cases effectivement utilisées.
La taille physique d’un tableau est le nombre de cases qu’il contient. Sa taille logique est le nombre de cases actuellement utilisées.
Exemple..
Voici un tableau qui ne contient pour l’instant que quatre nombres.
Les cases indiquées par “?” ne sont pas vides ; elles peuvent être non initialisées (et on ne peut pas tester si une case est non initialisée) ou bien contenir une valeur qui n’est pas pertinente.
Exemple..
L’algorithme suivant demande des valeurs positives à l’utilisateur et les stocke dans un tableau (maximum 1000). Toute valeur négative ou nulle est une valeur sentinelle.
nbÉléments 0 valeur tab[nbÉléments] valeur nbÉléments nbÉléments + 1 valeur “La limite physique a été atteinte”
Modifier l’exemple Tel quel, l’exemple ci-dessus n’est pas très intéressant. Ce serait mieux s’il retournait le tableau ce qui permettrait effectivement un traitement ultérieur des valeurs. Modifiez-le en ce sens.
Des tableaux qui ne commencent pas à 0.
Les tableaux que nous avons vus jusqu’à présent "commencent à 0" ce qui signifie que la première case est d’indice 0. Il peut être intéressant d’utiliser des tableaux qui commencent à un autre indice.
Exemple..
Imaginons l’algorithme qui permet de convertir un numéro de jour en son intitulé : 1 donne “lundi”, 2 donne “mardi”, … Une solution possible, sans tableau, serait :
“lundi” “mardi” “mercredi” “jeudi” “vendredi” “samedi” “dimanche”
Mais une solution plus élégante passe par l’utilisation d’un tableau. Appelons-le et stockons-y les noms des jours comme illustré ci-dessous.
Pour obtenir le nom d’un jour, il suffit d’écrire : .
On voit dans cet exemple qu’il est plus naturel que le tableau commence à 1. Pour déclarer un tel tableau, nous utiliserons la notation suivante :
L’algorithme devient :
nomsJours {“lundi”, “mardi”, “mercredi”, “jeudi”, “vendredi”, “samedi”, “dimanche”} nomsJours[numéroJour]
Comment traduire ça dans un langage de programmation ?
Certains langages comme Pascal permettent de choisir l’indice de début d’un tableau. D’autres l’imposent, parfois à 1 comme Cobol mais le plus souvent à 0 comme Java. Que faire dans ce cas ? Il existe deux stratégies.
Cette seconde approche est à préférer car elle modifie le moins l’algorithme de départ et entrainera moins d’erreurs de conversion (au prix d’un faible gaspillage de la mémoire). Mais elle n’est pas toujours possible. Par exemple, imaginons qu’on veuille prendre des relevés de températures (arrondies à l’entier) à Bruxelles et retenir le nombre de fois que chaque température a été relevée. Le plus évident serait d’utiliser un tableau allant de -30 à 40 où la case formula_267 donne le nombre de fois que la température formula_267 a été relevée. Pour cet exemple, impossible d’utiliser la seconde approche mais la première est toujours possible en stockant le nombre de relevés de la température formula_267 dans la case formula_303.
Lancers de dé Écrire un algorithme qui lance formula_68 fois un dé et compte le nombre de fois que chaque valeur apparait.
Nombre de jours dans un mois Écrire un algorithme qui reçoit un numéro de mois (de 1 à 12) ainsi qu’une année et donne le nombre de jours dans ce mois (en tenant compte des années bissextiles). N’hésitez pas à réutiliser des algorithmes déjà écrits.
= Gérer les données dans un tableau =
Une utilisation courante des tableaux est le stockage des données changeantes. Lors de l’évolution de l’algorithme des données sont ajoutées, recherchées, supprimées, modifiées.
Par exemple, imaginons que l’école organise un événement libre et gratuit pour les étudiants. Mais pour y assister, ils doivent s’inscrire. On veut fournir ce qu’il faut pour :
Pour ce faire, on pourra stocker les numéros des étudiants inscrits dans un tableau . Comme le tableau ne sera généralement pas rempli, on va gérer sa taille logique. On a donc deux variables :
On va envisager deux cas :
Données non triées.
Dans cette approche, les valeurs sont stockées dans le tableau dans un ordre quelconque. Par exemple, on pourrait avoir la situation suivante :
indiquant qu’il y a pour le moment quatre étudiants inscrits dont les numéros sont ceux repris dans les quatre premières cases du tableau.
Inscription.
Commençons par l’inscription. Pour inscrire un étudiant, il suffit de l’ajouter à la suite dans le tableau. Par exemple, en partant de la situation décrite ci-dessus, l’inscription de l’étudiant numéro 42123 aboutit à la situation suivante :
L’algorithme est assez simple :
inscrits[nbInscrits] numéro nbInscrits nbInscrits + 1
Vérifier une inscription.
Pour vérifier si un étudiant est déjà inscrit, il faut le rechercher dans la partie utilisée du tableau. Cette recherche se fait via un parcours avec sortie prématurée. On pourrait se contenter de retourner un booléen indiquant si oui ou non on l’a trouvé mais retournons plutôt un entier indiquant l’indice où il est (-1 si on ne l’a pas trouvé), ce sera plus utile.
i 0 i i + 1 i -1
La fiche reprend cet algorithme dans un cadre plus général.
Désinscription.
Pour désinscrire un étudiant, il faut le trouver dans le tableau et l’enlever. Attention, il ne peut pas y avoir de trou dans un tableau (il n’y a pas de case vide). Le plus simple est d’y déplacer le dernier élément. Par exemple, reprenons la situation après inscription de l’étudiant numéro 42123. La désinscription de l’étudiant numéro 41390 donnerait 
L’algorithme est assez simple à écrire si on utilise la recherche écrite juste avant :
pos vérifier(inscrits, nbInscrits, numéro) inscrits[pos] inscrits[nbInscrits-1] nbInscrits nbInscrits - 1
Exercices.
Éviter la double inscription Comment modifier l’algorithme d’inscription pour s’assurer qu’un étudiant ne s’inscrive pas deux fois ?
Limite au nombre d’inscriptions Comment modifier l’algorithme d’inscription pour refuser une inscription si le nombre maximal de participant est atteint en supposant que ce maximum est égal à la taille physique du tableau ?
Vérifier la désinscription Que se passerait-il avec l’algorithme de désinscription tel qu’il est si on demande à désinscrire un étudiant non inscrit ? Que suggérez-vous comme changement ?
Optimiser la désinscription Dans l’algorithme de désinscription tel qu’il est, voyez-vous un cas où on effectue une opération inutile ? Avez-vous une proposition pour l’éviter ?
Données triées.
Imaginons à présent que nous maintenons un ordre dans les données du tableau.
Si on reprend l’exemple utilisé pour les données non triées, on a :
Qu’est-ce que ça change au niveau des algorithmes ? Beaucoup ! Par exemple, plus question de placer un nouvel inscrit à la suite des autres; il faut trouver sa place.
Rechercher la position d’une inscription.
Tous les algorithmes que nous allons voir dans le cadre de données triées ont une partie en commun : la recherche de la position du numéro, s’il est présent ou de la position où il aurait dû être s’il est absent. Commençons par ça.
L’algorithme est assez proche de celui de la vérification d’une inscription vu précédemment si ce n’est qu’on peut s’arrêter dès qu’on trouve un numéro plus grand. On va aussi ajouter un booléen indiquant si la valeur a été trouvée.
pos 0 pos pos + 1 trouvé pos < nbInscrits ET inscrits[pos] = numéro
Comprenez-vous pourquoi :
Inscrire un étudiant.
L’inscription d’un étudiant se fait en trois étapes :
Ce qui nous donne :
rechercher( inscrits, nbInscrits, numéro, trouvé, pos ) décalerDroite( inscrits, pos, nbInscrits) inscrits[pos] numéro nbInscrits nbInscrits + 1 tab[i+1] tab[i]
Vérifier une inscription.
Cette opération est triviale.
rechercher( inscrits, nbInscrits, numéro, trouvé, pos ) pos -1
Désinscription.
Ici, il va falloir décaler vers la gauche les éléments qui suivent celui à supprimer.
rechercher( inscrits, nbInscrits, numéro, trouvé, pos ) décalerGauche( inscrits, pos+1, nbInscrits) nbInscrits nbInscrits - 1 tab[i-1] tab[i]
La fiche reprend cet algorithme dans un cadre plus général.
Exercices.
Éviter la double inscription Comment modifier l’algorithme d’inscription pour s’assurer qu’un étudiant ne s’inscrive pas deux fois ?
Limite au nombre d’inscriptions Comment modifier l’algorithme d’inscription pour refuser une inscription si le nombre maximal de participants est atteint en supposant que ce maximum est égal à la taille physique du tableau ?
Vérifier la désinscription Que se passerait-il avec l’algorithme de désinscription tel qu’il est si on demande à désinscrire un étudiant non inscrit ? Que suggérez-vous comme changement ?
Intérêt de trier les valeurs ?
Est-ce que trier les valeurs est vraiment intéressant ? On voit que la recherche est un peu plus rapide (en moyenne 2x plus rapide si l’élément ne s’y trouve pas). Par contre, l’ajout et la suppression d’un élément sont plus lents. En plus, les algorithmes sont plus complexes à écrire et à comprendre. Le gain ne parait pas évident et en effet, en l’état, il ne l’est pas.
Mais c’est sans compter un autre algorithme de recherche, beaucoup plus rapide, la recherche dichotomique, que nous allons voir maintenant.
La recherche dichotomique.
La recherche dichotomique est un algorithme de recherche d’une valeur dans un tableau trié. Il a pour essence de réduire à chaque étape la taille de l’ensemble de recherche de moitié, jusqu’à ce qu’il ne reste qu’un seul élément dont la valeur devrait être celle recherchée, sauf bien entendu en cas d’inexistence de cette valeur dans l’ensemble de départ.
Pour l’expliquer, on va prendre un tableau d’entiers complètement rempli. Il sera facile d’adapter la solution à un tableau partiellement rempli (avec une taille logique) ou un tableau contenant tout autre type de valeurs qui peut s’ordonner.
Description de l’algorithme
Soit la valeur recherchée dans une zone délimitée par les indices et . On commence par déterminer l’élément médian, c’est-à-dire celui qui se trouve « au milieu » de la zone de recherche  ; son indice sera déterminé par la formule
On compare alors avec la valeur de cet élément médian ; il est possible qu’on ait trouvé la valeur cherchée; sinon, on partage la zone de recherche en deux parties : une qui ne contient certainement pas la valeur cherchée et une qui pourrait la contenir. C’est cette deuxième partie qui devient la nouvelle zone de recherche. On adapte ou en conséquence. On réitère le processus jusqu’à ce que la valeur cherchée soit trouvée ou que la zone de recherche soit réduite à sa plus simple expression, c’est-à-dire un seul élément.
Exemple de recherche fructueuse
Supposons que l’on recherche la valeur 23 dans un tableau de 20 entiers. La zone ombrée représente à chaque fois la partie de recherche, qui est au départ le tableau trié dans son entièreté. Au départ, vaut 0 et vaut 19.
"Première étape" : , c’est-à-dire 9. Comme la valeur en position 9 est 15, la valeur cherchée doit se trouver à sa droite, et on prend comme nouvelle zone de recherche celle délimitée par qui vaut 10 et qui vaut 19.
"Deuxième étape" : , c’est-à-dire 14. Comme on y trouve la valeur 25, on garde les éléments situés à la gauche de celui-ci ; la nouvelle zone de recherche est [10, 13].
"Troisième étape" : , c’est-à-dire 11 où se trouve l’élément 20. La zone de recherche devient vaut 12 et vaut 13.
"Quatrième étape :" , c’est-à-dire 12 où se trouve la valeur cherchée ; la recherche est terminée.
Exemple de recherche infructueuse
Recherchons à présent la valeur 8. Les étapes de la recherche vont donner successivement
Arrivé à ce stade, la zone de recherche s’est réduite à un seul élément. Ce n’est pas celui qu’on recherche mais c’est à cet endroit qu’il se serait trouvé ; c’est donc là qu’on pourra éventuellement l’insérer. Le paramètre de sortie prend la valeur 5.
Algorithme
indiceGauche 0 indiceDroit n-1 trouvé faux indiceMédian (indiceGauche + indiceDroit) DIV 2 candidat tab[indiceMédian] trouvé vrai indiceGauche indiceMédian + 1 on garde la partie droite indiceDroit indiceMédian – 1 on garde la partie gauche pos indiceMédian pos indiceGauche dans le cas où la valeur n’est pas trouvée, on vérifiera que indiceGauche donne la valeur où elle pourrait être insérée. trouvé
Introduction à la complexité.
L’algorithme de recherche dichotomique est beaucoup plus rapide que l’algorithme de recherche linéaire. Mais qu’est-ce que cela veut dire exactement ? En est-on sûr ? Comment le mesure-t-on ? Quels critères utilise-t-on ? De façon générale, comment comparer la vitesse de deux algorithmes différents qui résolvent le même problème.
Une approche pratique : la simulation numérique.
On pourrait se dire que pour comparer deux algorithmes, il suffit de les traduire tous les deux dans un langage de programmation, de les exécuter et de comparer leur temps d’exécution. Cette technique pose toutefois quelques problèmes :
En fait, un chiffre précis ne nous intéresse pas. Ce qui est vraiment intéressant, c’est de savoir comment l’algorithme va se comporter avec de grandes données. C’est ce qu’apporte l’approche suivante.
Une approche théorique : la complexité.
Avec cette approche, on va déduire de l’algorithme le nombre d’opérations de base à effectuer en fonction de la taille du problème à résoudre et en déduire comment il va se comporter sur de « gros » problèmes ?
Dans le cas de la recherche dans un tableau, la taille du problème est la taille du tableau dans lequel on recherche un élément. On peut considérer que l’opération de base est la comparaison avec un élément du tableau. La question est alors la suivante : pour un tableau de taille formula_68, à combien de comparaisons faut-il procéder pour trouver l’élément (ou se rendre compte de son absence) ?
Pour la recherche linéaire
Cela dépend évidemment de la position de la valeur à trouver. Dans le meilleur des cas c’est 1, dans le pire c’est formula_68 mais on peut dire, qu’en moyenne, cela entraine « formula_308 » comparaisons (que ce soit pour la trouver ou se rendre compte de son absence).
Pour la recherche dichotomique
Ici, la zone de recherche est divisée par 2, à chaque étape. Imaginons une liste de 64 éléments : après 6 étapes, on arrive à un élément isolé. Pour une liste de taille formula_68, on peut en déduire que le nombre de comparaisons est au maximum l’exposant qu’il faut donner à 2 pour obtenir formula_68, soit « formula_311 ».
Comparaisons
Voici un tableau comparatif du nombre de comparaisons en fonction de la taille formula_68
 |>m4.4300003cm |>m0.507cm |>m0.71900004cm |>m0.93100005cm |>m1.2479999cm |>m1.4599999cm |>m1.671cm| formula_68 & 10 & 100 & 1000 & 10.000 & 100.000 & 1 millionrecherche linéaire & 5 & 50 & 500 & 5.000 & 50.000 & 500.000recherche dichotomique & 4 & 7 & 10 & 14 & 17 & 20
On voit que c’est surtout pour des grands problèmes que la recherche dichotomique montre toute son efficacité. On voit aussi que ce qui est important pour mesurer la complexité c’est l’ordre de grandeur du nombre de comparaisons.
On dira que la recherche simple est un algorithme de complexité linéaire (c’est-à-dire que le nombre d’opérations est de l’ordre de formula_68 ou proportionnel à formula_68 ou encore que si on double la taille du problème, le temps va aussi être doublé) ce qu’on note en langage plus mathématique formula_316 (prononcé « grand formula_317 de formula_68 »).
Pour la recherche dichotomique, la complexité est logarithmique, et on le note formula_319 ce qui veut dire que si on double la taille du problème, on a juste une itération en plus dans la boucle.
Comparons les complexités les plus courantes.
 |>m2cm |>m0.8cm |>m0.8cm |>m1.0cm |>m1.3cm |>m1.287cm |>m1.425cm |>m1.714cm| formula_68 & 10 & 100 & 1000 & formula_321 & formula_322 & formula_323 & formula_324formula_325 & 1 & 1 & 1 & 1 & 1 & 1 & 1formula_319 & 4 & 7 & 10 & 14 & 17 & 20 & 30formula_316 & 10 & 100 & 1000 & formula_321 & formula_322 & formula_323 & formula_324formula_332 & 100 & formula_321 & formula_323 & formula_335 & formula_336 & formula_337 & formula_338formula_339 & 1000 & formula_323 & formula_324 & formula_337 & formula_343 & formula_338 & formula_345formula_346 & 1024 & formula_347 & formula_348 & formula_349 & formula_350 & formula_351 & formula_352
On voit ainsi que si on trouve un algorithme correct pour résoudre un problème mais que cet algorithme est de complexité exponentielle alors cet algorithme ne sert à rien en pratique. Par exemple un algorithme de recherche de complexité exponentielle, exécuté sur une machine pouvant effectuer un milliard de comparaisons par secondes, prendrait plus de dix mille milliards d’années pour trouver une valeur dans un tableau de 100 éléments.
Calcul de complexités Quelle est la complexité d’un algorithme qui :
Gestion des données Comparer les algorithmes d’ajout, de recherche et de suppression de valeurs dans le cas d’un tableau trié et d’un tableau non trié.
Réflexion L’algorithme de recherche dichotomique est-il toujours à préférer à l’algorithme de recherche linéaire ?
= Le tri =
Dans ce chapitre nous voyons quelques algorithmes simples pour trier un ensemble d’informations : recherche des maxima, tri par insertion et tri bulle dans un tableau. Des algorithmes plus efficaces seront vus en deuxième année.
Motivation.
Dans le chapitre précédent, nous avons vu que la recherche d’information est beaucoup plus rapide dans un tableau trié grâce à l’algorithme de recherche dichotomique. Nous avons vu comment garder un ensemble trié en insérant toute nouvelle valeur au "bon" endroit.
Dans certaines situations, on est amené à devoir trier tout un tableau.
Le dernier cas illustre un classement sur une clé complexe (ou composée) impliquant la comparaison de plusieurs champs d’une même structure : le premier classement se fait sur le numéro de groupe, et à numéro de groupe égal, l’ordre se départage sur le nom de l’étudiant. On dira de cet ensemble qu’il est classé en majeur sur le numéro de groupe et en mineur sur le nom d’étudiant.
Notons que certains tris sont dits stables parce qu’en cas de tri sur une nouvelle clé, l’ordre de la clé précédente est préservé pour des valeurs identiques de la nouvelle clé, ce qui évite de faire des comparaisons sur les deux champs à la fois. Les méthodes nommées tri par insertion, tri bulle et tri par recherche de minima successifs (que nous allons aborder dans ce chapitre) sont stables.
Certains tris sont évidemment plus performants que d’autres. Le choix d’un tri particulier dépend de la taille de l’ensemble à trier et de la manière dont il se présente, c’est-à-dire déjà plus ou moins ordonné. La performance quant à elle se juge sur deux critères : le nombre de tests effectués (comparaisons de valeurs) et le nombre de transferts de valeurs réalisés.
Les algorithmes classiques de tri présentés dans ce chapitre le sont surtout à titre pédagogique. Ils ont tous une « complexité en formula_355 », ce qui veut dire que si formula_68 est le nombre d’éléments à trier, le nombre d’opérations élémentaires (tests et transferts de valeurs) est proportionnel à formula_355. Ils conviennent donc pour des ensembles de taille « raisonnable », mais peuvent devenir extrêmement lents à l’exécution pour le tri de grands ensembles, comme par exemple les données de l’annuaire téléphonique. Plusieurs solutions existent, comme la méthode de tri Quicksort. Cet algorithme très efficace faisant appel à la récursivité et qui sera étudié en deuxième année a une complexité en formula_358.
Dans ce chapitre, les algorithmes traiteront du tri dans un tableau d’entiers à une dimension. Toute autre situation peut bien entendu se ramener à celle-ci moyennant la définition de la relation d’ordre propre au type de données utilisé. Ce sera par exemple l’ordre alphabétique pour les chaines de caractères, l’ordre chronologique pour des objets ou (que nous verrons plus tard), etc. De plus, le seul ordre envisagé sera l’ordre croissant des données. Plus loin, nous envisagerons le tri d’autres structures de données.
Enfin, dans toutes les méthodes de tri abordées, nous supposerons la taille physique du tableau à trier (notée formula_68) égale à sa taille logique, celle-ci n’étant pas modifiée par l’action de tri.
Tri par insertion.
Cette méthode de tri repose sur le principe d’insertion de valeurs dans un tableau ordonné.
Description de l’algorithme..
Le tableau à trier sera à chaque étape subdivisé en deux sous-tableaux : le premier cadré à gauche contiendra des éléments déjà ordonnés, et le second, cadré à droite, ceux qu’il reste à insérer dans le sous-tableau trié. Celui-ci verra sa taille s’accroitre au fur et à mesure des insertions, tandis que celle du sous-tableau des éléments non triés diminuera progressivement.
Au départ de l’algorithme, le sous-tableau trié est le premier élément du tableau. Comme il ne possède qu’un seul élément, ce sous-tableau est donc bien ordonné ! Chaque étape consiste ensuite à prendre le premier élément du sous-tableau non trié et à l’insérer à la bonne place dans le sous-tableau trié.
Prenons comme exemple un tableau de 20 entiers. Au départ, le sous-tableau trié est formé du premier élément, , qui vaut 20 :
L’étape suivante consiste à insérer , qui vaut 12, dans ce sous-tableau de taille 2 :
Ensuite, c’est au tour de , qui vaut 18, d’être inséré :
Et ainsi de suite jusqu’à insertion du dernier élément dans le sous-tableau trié.
Algorithme..
On combine la recherche de la position d’insertion et le décalage concomitant de valeurs.
Trie le tableau reçu en paramètre (via un tri par insertion). valÀInsérer tab[i] recherche de l’endroit où insérer valÀInsérer dans le sous-tableau trié et décalage simultané des éléments j i - 1 tab[j+1] tab[j] j j – 1 tab[j+1] valÀInsérer
Tri par sélection des minima successifs.
Dans ce tri, on recherche à chaque étape la plus petite valeur de l’ensemble non encore trié et on la place immédiatement à sa position définitive.
Description de l’algorithme..
Prenons par exemple un tableau de 20 entiers.
La première étape consiste à rechercher la valeur minimale du tableau. Il s’agit de l’élément d’indice 9 et de valeur 17.
Celui-ci devrait donc apparaitre en 1 position du tableau. Or cette position est occupée par la valeur 20. Comment procéder dès lors pour ne perdre aucune valeur et sans faire appel à un second tableau ? La solution est simple, il suffit d’échanger le contenu des deux éléments d’indices 0 et 9 :
Le tableau se subdivise à présent en deux sous-tableaux, un sous-tableau déjà trié (pour le moment réduit au seul élément formula_360) et le sous-tableau des autres valeurs non encore triées (de l’indice 1 à 19). On recommence ce processus dans ce second sous-tableau : le minimum est à présent l’élément d’indice 16 et de valeur 19. Celui-ci viendra donc en 2 position, échangeant sa place avec la valeur 52 qui s’y trouvait :
Le sous-tableau trié est maintenant formé des deux premiers éléments, et le sous-tableau non trié par les 18 éléments suivants.
Et ainsi de suite, jusqu’à obtenir un sous-tableau trié comprenant tout le tableau. En pratique l’arrêt se fait une étape avant car lorsque le sous-tableau non trié n’est plus que de taille 1, il contient nécessairement le maximum de l’ensemble.
Algorithme..
Trie le tableau reçu en paramètre (via un tri par sélection des minima successifs). i correspond à l’étape de l’algorithme indiceMin positionMin( tab, i, n-1 ) swap( tab[i], tab[indiceMin] )
Retourne l’indice du minimum entre les indices début et fin du tableau reçu. indiceMin début indiceMin i indiceMin
aux a a b b aux
Tri à bulles.
Il s’agit d’un tri par permutations ayant pour but d’amener à chaque étape à la « surface » du sous-tableau non trié (on entend par là l’élément d’indice minimum) la valeur la plus petite, appelée la bulle. La caractéristique de cette méthode est que les comparaisons ne se font qu’entre éléments consécutifs du tableau.
Description de l’algorithme.
Prenons pour exemple un tableau de taille 14. En partant de la fin du tableau, on le parcourt vers la gauche en comparant chaque couple de valeurs consécutives. Quand deux valeurs sont dans le désordre, on les permute. Le premier parcours s’achève lorsqu’on arrive à l’élément d’indice 0 qui contient alors la « bulle », c’est-à-dire la plus petite valeur du tableau, soit 1 :
Ceci achève le premier parcours. On recommence à présent le même processus dans le sous-tableau débutant au deuxième élément, ce qui donnera le contenu suivant :
Et ainsi de suite. Au total, il y aura formula_361 étapes.
Algorithme..
Dans cet algorithme, la variable est à la fois le compteur d’étapes et aussi l’indice de l’élément récepteur de la bulle à la fin d’une étape donnée.
Trie le tableau reçu en paramètre (via un tri bulle). swap( tab[i], tab[i + 1] ) voir algorithme précédent
Cas particuliers.
Tri partiel
Parfois, on n’est pas intéressé par un tri complet de l’ensemble mais on veut uniquement les « formula_362 » plus petites (ou plus grandes) valeurs. Le tri par recherche des minima et le tri bulle sont particulièrement adaptés à cette situation ; il suffit de les arrêter plus tôt. Par contre, le tri par insertion est inefficace car il ne permet pas un arrêt anticipé.
Sélection des meilleurs
Une autre situation courante est la suivante : un ensemble de valeurs sont traitées (lues, calculées…) et il ne faut garder que les formula_362 plus petites (ou plus grandes). L’algorithme est plus simple à écrire si on utilise une position supplémentaire en fin de tableau. Notons aussi qu’il faut tenir compte du cas où il y a moins de valeurs que le nombre de valeurs voulues ; c’est pourquoi on ajoute une variable indiquant le nombre exact de valeurs dans le tableau.
Exemple : on lit un ensemble de valeurs strictement positives (un 0 indique la fin de la lecture) et on ne garde que les formula_362 plus petites valeurs.
nbValeurs 0 val insérer( val, plusPetits, nbValeurs ) val
i nbValeurs - 1 plusPetits[i + 1] plusPetits[i] i i - 1 plusPetits[i + 1] val nbValeurs nbValeurs + 1
Références.
= Exercices sur les tableaux =
Voici quelques exercices qui reprennent les différentes notions vues sur les tableaux. Pour chacun d’entre-eux :
Renverser un tableau Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 caractères, et qui « renverse » ce tableau, c’est-à-dire qui permute le premier élément avec le dernier, le deuxième élément avec l’avant-dernier et ainsi de suite.
Tableau symétrique ? Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 chaines et qui vérifie si ce tableau est symétrique, c’est-à-dire si le premier élément est identique au dernier, le deuxième à l’avant-dernier et ainsi de suite.
Maximum/minimum Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 entiers et qui retourne la plus grande valeur de ce tableau. Idem pour le minimum.
Indice du maximum/minimum [ex:indiceminmax] Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 entiers et qui retourne l’indice de l’élément contenant la plus grande valeur de ce tableau. En cas d’ex-æquo, c’est l’indice le plus petit qui sera renvoyé.
Que faut-il changer pour renvoyer l’indice le plus grand ? Et pour retourner l’indice du minimum ? Réécrire l’algorithme de l’exercice précédent en utilisant celui-ci.
Tableau ordonné ? Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 entiers et qui vérifie si ce tableau est ordonné (strictement) croissant sur les valeurs. L’algorithme retournera si le tableau est ordonné, sinon.
Remplir un tableau On souhaite remplir un tableau de 20 éléments avec les entiers de 1 à 5, chaque nombre étant répété quatre fois. On voudrait deux variantes :
Remarque : Il existe de nombreuses façons de résoudre ce problème. On peut par exemple utiliser deux boucles imbriquées. On peut aussi adapter un algorithme de génération de suites.
Positions du minimum Écrire un algorithme qui reçoit en paramètre le tableau de formula_68 entiers et qui affiche le ou les indice(s) des éléments contenant la valeur minimale du tableau.
Lancers de deux dés Écrire un algorithme qui lance formula_68 fois deux dés et compte le nombre de fois que chaque somme apparait.
Occurrence des chiffres Écrire un algorithme qui reçoit un nombre entier positif ou nul en paramètre et qui retourne un tableau de 10 entiers indiquant, pour chacun de ses chiffres, le nombre de fois qu’il apparait dans ce nombre. Ainsi, pour le nombre 10502851125, on retournera le tableau {2,3,2,0,0,3,0,0,1,0}.
Les doublons Écrire un algorithme qui vérifie si un tableau de chaines contient au moins 2 éléments égaux.
Le crible d’Ératosthène
Le crible d’Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. L’algorithme procède par élimination : il s’agit de supprimer d’une table des entiers de 2 à N tous les multiples d’un entier. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d’aucun entier, et qui sont donc les nombres premiers. On commence par rayer les multiples de 2, puis à chaque fois on raye les multiples du plus petit entier restant. On peut s’arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment. (source : Wikipédia)
Le tableau dont il est question peut être un simple tableau de booléens; le booléen en position “i” indiquant si le nombre “i” est premier ou pas.
Écrire un algorithme qui reçoit un entier formula_68 et affiche tous les entiers premiers de formula_67 à formula_68.
Mastermind Dans le jeu du Mastermind, un joueur A doit trouver une combinaison de formula_68 pions de couleur, choisie et tenue secrète par un autre joueur B. Cette combinaison peut contenir éventuellement des pions de même couleur. À chaque proposition du joueur A, le joueur B indique le nombre de pions de la proposition qui sont corrects et bien placés et le nombre de pions corrects mais mal placés.
Les propositions du joueur A, ainsi que la combinaison secrète du joueur B sont contenues dans des tableaux de formula_68 composantes de type chaine.
Écrire l’algorithme suivant qui renvoie dans les variables et respectivement le nombre de pions bien placés et mal placés dans la « proposition » du joueur A en la comparant à la « solution » cachée du joueur B.
= Les chaines =
Dans ce chapitre, nous allons apprendre à manipuler du texte en étudiant les différentes fonctions associées aux variables de type chaine. Ce sera aussi l’occasion de revoir quelques techniques algorithmiques déjà acquises pour les nombres (alternatives, boucles) afin de les consolider dans un contexte plus littéraire .
Introduction.
Très tôt dans ce cours, nous avons introduit le type mais nous n’en avons encore fait que des usages basiques, essentiellement des affichages. Il est temps d’aller plus loin et de les "manipuler", c’est-à-dire d’examiner et de manipuler le contenu de chaines. Mais procédons par étapes.
Longueur.
La longueur d’une chaine est le nombre de caractères qu’elle contient. Pour la connaitre on utilisera la notation . Par exemple :
Chaine et caractère.
Certains langages, comme Java, distinguent clairement le type chaine et le type caractère. Ainsi, en Java, le littéral représente un caractère qui est différent du littéral qui représente une chaine (composée d’un seul caractère). Cette distinction est essentiellement dictée par des détails d’implémentation; un caractère pouvant se représenter de façon plus économe qu’une chaine.
D’autres langages, comme Python, n’ont pas de type caractère spécifique. D’autres encore, comme C, ont un type caractère mais pas de type chaine à proprement parler; ils sont vus comme des tableaux de caractères.
Ici, nous introduirons un type mais sans le distinguer clairement d’une chaine. Ainsi, un caractère pourra être utilisé comme une chaine et une chaine d’un seul caractère pourra être considéré comme un caractère. En somme, n’est qu’un raccourci pour dire : "une chaine de longueur 1".
Le contenu d’une chaine.
Pour pouvoir manipuler une chaine, il faut pouvoir accéder aux caractères qui la composent. Comme il s’agit d’une opération de base souvent utilisée, nous allons introduire une écriture compacte, empruntée aux tableaux : désigne le i caractère de la chaine nomChaine (en commençant à 1). Par exemple :
texte “Hello” texte[5] Affiche “o” texte[2] “a” texte vaut “Hallo”; un caractère doit être remplacé par un seul caractère.
Exemple..
Écrivons un algorithme qui vérifie si un mot donné contient une lettre donnée.
i 1 i i + 1 iformula_377long(mot)
La concaténation.
Il est fréquent de devoir rassembler plusieurs chaines pour former une seule chaine plus grande, il s’agit de l’opération de concaténation. Introduisons également une notation compacte, le . Par exemple :
texte “al” + “go” + “rithmique” assigne la chaine “algorihmique” à la variable texte.
Exemple..
Écrivons un algorithme qui inverse toutes les lettres d’un mot. Ainsi, “algo” deviendra “ogla”.
miroir “” miroir mot[i] + miroir miroir
Manipuler les caractères.
Les algorithmes qui suivent pourraient être écrits avec ce que nous avons déjà introduit mais ce serait long et fastidieux. Nous allons supposer qu’ils existent et on pourra les utiliser si nécessaire.
L’alphabet.
Il peut aussi être pratique de connaitre la position d’une lettre dans l’alphabet. Ceci se fera à l’aide de la fonction :
Il peut être utile d’avoir un outil qui fait l’opération inverse, à savoir associer la lettre de l’alphabet correspondant à une position donnée. Pour cela, nous aurons :
Chaine et nombre.
Si une chaine contient un nombre, on doit pouvoir le convertir, et inversement.
Extraction de sous-chaines.
Il faudra aussi être très vigilant pour une utilisation correcte: doit être compris entre 1 et la taille de la chaine, et la valeur de doit être telle qu’on ne déborde pas de la chaine !
Par exemple, donne “rit”.
Cette fonction est très utile pour sélectionner des portions d’une chaine contenant des informations codées sous un certain format. Prenons par exemple une date stockée dans une chaine "ch" de format “JJ/MM/AAAA” (de longueur 10). Pour extraire le jour de cette date, on écrira  ; le mois s’obtiendra avec et l’année avec . Attention, les 3 résultats obtenus sont des chaines de chiffres et non des nombres mais il est possible de les convertir via la fonction  !
Recherche de sous-chaine.
La valeur de l’entier renvoyé est la position où commence la sous-chaine recherchée. Par exemple, retournera 9. Si la sous-chaine ne s’y trouve pas, la fonction retourne 0. On peut admettre ici d’écrire un caractère à la place de la sous-chaine. Par exemple, retournera également 9.
Exercices.
Calcul de fraction Écrire un algorithme qui reçoit une fraction sous forme de chaine, et retourne la valeur numérique de celle-ci. Par exemple, si la fraction donnée est “5/8”, l’algorithme renverra 0,625. On peut considérer que la fraction donnée est correcte, elle est composée de 2 entiers séparés par le caractère de division ’/’.
Solution..
Voici une solution possible.
posFraction position(fraction,“/”) numérateur nombre(souschaine(fraction,1,posFraction-1)) dénominateur nombre(souschaine(fraction,posFraction+1,long(fraction)-posFraction)) numérateur / dénominateur
Conversion de nom Écrire un algorithme qui reçoit le nom complet d’une personne dans une chaine sous la forme “nom, prénom” et la renvoie au format “prénom nom” (sans virgule séparatrice). Exemple : “De Groote, Jan” deviendra “Jan De Groote”.
Gauche et droite Écrire un algorithme et un qui retourne la chaine formée respectivement des n premiers et des n derniers caractères d’une chaine donnée.
Grammaire Écrire un algorithme qui met un mot en « ou » au pluriel. Pour rappel, un mot en « ou » prend un « s » à l’exception des 7 mots bijou, caillou, chou, genou, hibou, joujou et pou qui prennent un « x » au pluriel. Exemple : un clou, des clous, un hibou, des hiboux. Si le mot soumis à l’algorithme n’est pas un mot en « ou », un message adéquat sera affiché.
Normaliser une chaine Écrire un module qui reçoit une chaine et retourne une autre chaine, version normalisée de la première. Par normalisée, on entend : enlever tout ce qui n’est pas une lettre et tout mettre en majuscule.Exemple : “Le <COBOL>, c’est la santé !” devient “LECOBOLCESTLASANTE”.
Les palindromes Cet exercice a déjà été réalisé pour des entiers, en voici 2 versions « chaine » !
Le chiffre de César [ex:cesar] Depuis l’antiquité, les hommes politiques, les militaires, les hommes d’affaires cherchent à garder secret les messages importants qu’ils doivent envoyer. L’empereur César utilisait une technique (on dit un "chiffrement") qui porte à présent son nom : remplacer chaque lettre du message par la lettre qui se situe formula_362 positions plus loin dans l’alphabet (cycliquement).
Exemple : si formula_362 vaut formula_233, alors le texte clair “CESAR” devient “EGUCT” lorsqu’il est chiffré et le texte “ZUT” devient “BWV”.
Bien sûr, il faut que l’expéditeur du message et le récepteur se soient mis d’accord sur la valeur de formula_362.
On vous demande d’écrire un algorithme qui reçoit une chaine ne contenant que des lettres majuscules ainsi que la valeur de formula_362 et qui retourne la version chiffrée du message.
On vous demande également d’écrire l’algorithme de déchiffrement. Cet algorithme reçoit un message chiffré et la valeur de formula_362 qui a été utilisée pour le chiffrer et retourne le message en clair. Attention ! Ce second algorithme est très simple.
Remplacement de sous-chaines Écrire un algorithme qui remplace dans une chaine donnée toutes les sous-chaines ch1 par la sous-chaine ch2. Attention, cet exercice est plus coriace qu’il n’y parait à première vue…  Assurez-vous que votre code n’engendre pas de boucle infinie.
= Les variables structurées =
Le type structuré.
Comme un tableau, une structure permet de stocker plusieurs valeurs. Mais, à l’inverse des tableaux, chaque valeur peut être de type différent et est désignée par un nom et pas par un numéro.
Cela permet de créer un nouveau type permettant de représenter des données qui ne peuvent s’inscrire dans les types simples déjà vus. Par exemple :
Pour stocker et manipuler de tels ensembles de données, nous utiliserons des types structurés ou structures. Une structure est donc un ensemble fini d’éléments pouvant être de types distincts. Chaque élément de cet ensemble, appelé champ de la structure, possède un nom unique.
Notez qu’un champ d’une structure peut lui-même être une structure. Par exemple, une carte d’identité inclut parmi ses informations une date de naissance, l’adresse de son propriétaire (cachée dans la puce électronique !)…
Définition d’une structure.
La définition d’un type structuré adoptera le modèle suivant :
, …, sont les noms des différents champs de la structure, et , …, les types de ces champs. Tous les types peuvent être envisagés : les types « simples » (entier, réel, booléen, chaine), les tableaux et même d’autres types structurés dont la structure aura été préalablement définie.
Pour exemple, nous définissons ci-dessous trois types structurés que nous utiliserons souvent par la suite :
4.5cm
4.5cm
4.5cm
Déclaration d’une variable de type structuré.
Une fois un type structuré défini, la déclaration de variables de ce type est identique à celle des variables simples. Par exemple :
Utilisation des variables de type structuré.
En général, pour manipuler une variable structurée ou en modifier le contenu, il faut agir au niveau de ses champs en utilisant les opérations permises selon leur type. Pour accéder à l’un des champs d’une variable structurée, il faut mentionner le nom de ce champ ainsi que celui de la variable dont il fait partie. Nous utiliserons la notation « pointée » :
nomVariable.nomChamp
Exemples d’instructions utilisant les variables déclarées au paragraphe précédent :
anniversaire.jour 15 anniversaire.mois 10 anniversaire.année 2014 arrivée.heure départ.heure + 2 centreGravité.x (a.x + b.x) / 2
On peut cependant, dans certains cas, utiliser une variable structurée de manière globale (c’est-à-dire d’une façon qui agit simultanément sur chacun de ses champs). Le cas le plus courant est l’affectation interne entre deux variables structurées de même type, par exemple :
arrivée départ
qui résume les trois instructions suivantes :
arrivée.heure départ.heure arrivée.minute départ.minute arrivée.seconde départ.seconde
Par facilité d’écriture, on peut assigner tous les champs en une fois via des « {} ». Exemple :
Une variable structurée peut aussi être le paramètre ou la valeur de retour d’un algorithme. Par exemple, l’entête d’un algorithme renvoyant le nombre de secondes écoulées entre une heure de départ et d’arrivée serait :
On pourra aussi lire ou afficher une variable structurée .
unMoment unMoment
Par contre, il n’est pas autorisé d’utiliser les opérateurs de comparaison (<, >) pour comparer des variables structurées (même de même type), car une relation d’ordre n’accompagne pas toujours les structures utilisées. En effet, s’il est naturel de vouloir comparer des dates ou des moments, comment définir une relation d’ordre avec les points du plan ou avec des cartes d’identités ?
Si le besoin de comparer des variables structurées se fait sentir, il faudra dans ce cas écrire des modules de comparaison adaptés aux structures utilisées.
Exemple d’algorithme.
Le module ci-dessous reçoit en paramètre deux dates ; la valeur renvoyée est négative si la première date est antérieure à la deuxième, 0 si les deux dates sont identiques ou positive si la première date est postérieure à la deuxième.
Reçoit 2 dates en paramètres et retourne une valeur négative si la première date est antérieure à la deuxième nulle si les deux dates sont identiques positive si la première date est postérieure à la deuxième. date1.année - date2.année date1.mois - date2.mois date1.jour - date2.jour
Exercices sur les structures.
Conversion moment-secondes Écrire un module qui reçoit en paramètre un moment d’une journée et qui retourne le nombre de secondes écoulées depuis minuit jusqu’à ce moment.
Conversion secondes-moment Écrire un module qui reçoit en paramètre un nombre de secondes écoulées dans une journée à partir de minuit et qui retourne le moment correspondant de la journée.
Temps écoulé entre 2 moments Écrire un module qui reçoit en paramètres deux moments d’une journée et qui retourne le nombre de secondes séparant ces deux moments.
Milieu de 2 points Écrire un module recevant les coordonnées de deux points distincts du plan et qui retourne les coordonnées du point situé au milieu des deux.
Distance entre 2 points Écrire un module recevant les coordonnées de deux points distincts du plan et qui retourne la distance entre ces deux points.
Un cercle Définir un type Cercle pouvant décrire de façon commode un cercle quelconque dans un espace à deux dimensions. Écrire ensuite
Un rectangle Définir un type Rectangle pouvant décrire de façon commode un rectangle dans un espace à deux dimensions et dont les côtés sont parallèles aux axes des coordonnées. Écrire ensuite
Validation de date Écrire un algorithme qui valide une date reçue en paramètre sous forme d’une structure.
= Exercices récapitulatifs =
La plupart des exercices qui suivent sont inspirés d’anciens examens. Ils sont assez conséquents et reprennent la plupart des notions vues dans ce cours.
AEBBCLRS.
Le Scrabble est un jeu de lettres, où le but est de former des mots ayant le score le plus élevé possible. Pour calculer le score d’un mot, une valeur est associée à chaque lettre de l’alphabet. Par exemple la lettre codice_40 vaut 1, codice_41 vaut 4, codice_42 vaut 8,… Le score d’un mot est la somme de la valeur de ses lettres .
Par exemple le score du mot codice_43 est formula_385.
Les joueurs tirent chacun 7 lettres qu’ils placent sur un "chevalet". Le but du jeu est de former des mots à partir des lettres du chevalet et de les placer sur le plateau de jeu.
Valeur des lettres.
Écrire un algorithme, codice_44, qui reçoit un caractère et retourne sa valeur. Les valeurs des lettres sont les suivantes:
L’algorithme lance une erreur avec un message adéquat si le caractère passé en paramètre n’est pas une lettre majuscule.
Score d’un mot.
Écrire un algorithme, codice_45, qui reçoit une chaine de caractères, codice_46, et retourne la valeur de ce mot, c’est-à-dire la somme de la valeur de chacune de ses lettres.
Mot possible.
Écrire un algorithme, codice_48, qui reçoit un tableau de caractères, codice_49, et une chaine de caractères, codice_46, et retourne vrai si les lettres du chevalet permettent d’obtenir le mot donné, et retourne faux dans le cas contraire.
 : Une solution possible est de faire une copie du chevalet et pour chaque lettre du mot de vérifier que la lettre s’y trouve, si elle s’y trouve de la remplacer par un symbole (par exemple un ’-’). Pour cela on définit un algorithme codice_55 permettant de copier un chevalet et un algorithme codice_56 permettant de connaitre l’indice d’une lettre dans un chevalet (cet algorithme retourne -1 si la lettre ne s’y trouve pas).
Meilleur mot.
Écrire un algorithme, codice_57, qui reçoit :
L’algorithme retourne le mot du dictionnaire que l’on peut obtenir avec les lettres du chevalet et qui a le score le plus élevé. Si aucun mot n’est possible avec le chevalet, l’algorithme retourne un mot vide codice_60.
Serpents et échelles.
Serpents et échelles est un jeu de société populaire, se jouant à plusieurs, consistant à déplacer les jetons sur un tableau de cases avec un dé en essayant de monter les échelles et en évitant de trébucher sur les serpents.
Pour l’histoire, le jeu peut être perçu comme une représentation d’un chemin spirituel que les humains prennent pour atteindre le ciel. Avec des bons gestes, le chemin est raccourci (ce que symbolisent les échelles), tandis qu’avec de mauvais gestes, le chemin est allongé (d’où vient le symbolisme des serpents).
Extrait de Wikipedia.
Représentation du chemin.
Nous représenterons le chemin par un tableau d’entiers. Chaque case du tableau contiendra une valeur :
Règles du jeu.
Pour jouer, le joueur qui a la main lance le dé et avance de la valeur indiquée par le dé. À partir de cette nouvelle position, il vérifie la valeur de la case sur laquelle il se trouve pour continuer à avancer ou au contraire reculer. Si la valeur est positive, il avance et si elle est négative, il recule de la valeur contenue dans la case.
Si la case est déjà occupée, le joueur se placera sur la case suivante.
Le joueur passe la main au joueur suivant.
Exemple. Le joueur se trouvant à la position 3 lance le dé. Il obtient la valeur 4. Il avance de 4 cases et se retrouve sur la case en position 7 qui contient la valeur 2. Il avance encore de 2 cases … et termine donc son tour en position 9. Il passe alors la main au joueur suivant.
Le premier joueur à atteindre ou dépasser la dernière case a gagné. Nous supposerons que cette dernière case est en position 42. Nous supposons également que la première et la dernière case n’ont ni échelle ni serpent (valeur nulle).
Positions des joueurs.
Les positions des joueurs seront mémorisées dans un tableau d’entiers. Toutes les cases de ce tableau sont initialisées à 0.
Le plateau de jeu, un tableau d’entiers s’appellera chemin.
Le tableau d’entiers contenant la position courante des joueurs s’appellera positionsJoueurs.
S’il y a 4 joueurs, le tableau "positionsJoueurs" contient [2,5,1,7] alors :
Le premier jour, initialiser le chemin.
Écrivez un algorithme
Cet algorithme "créerChemin" créera un tableau d’entiers dont les valeurs seront des valeurs aléatoires comprises strictement entre -10 et 10 (inclus).
Nous supposons que l’entier formula_68 est un naturel strictement supérieur à 0. Vous ne devez pas le vérifier.
Qui est en tête ?
Écrivez un algorithme
Cet algorithme retourne le numéro du joueur en tête de la course. Il recherche donc le maximum dans le tableau passé en argument et retourne l’indice de ce maximum.
Jouer un tour de jeu.
Cet algorithme permettra de jouer un tour de jeu pour un joueur donné. Jouer un tour de jeu consiste à le faire avancer ou reculer (c’est-à-dire changer sa position) du bon nombre de cases.
Cet algorithme fait changer de position le joueur d’indice "joueurCourant" de la valeur donnée par le dé ("valeurDé") en respectant les règles du jeu.
Cet algorithme met donc à jour le tableau "positionsJoueurs".
Comme le joueur ne peut se placer sur une case déjà occupée, il peut être utile d’écrire un module codice_61 précisant si la case est libre ou occupée.
Les algorithmes en maternelle.
En maternelle, déjà, les enfants font des algorithmes mais il s’agit d’une chose un peu différente. On leur propose un collier dessiné sur une feuille de papier et ils doivent le colorier en répétant un "motif" donné, une séquence précise de couleurs.
Par exemple, on donne ce collier  ---------  qui est pré-colorié avec deux perles rouges et une perle verte, c’est le motif.Le résultat attendu est : ---------.
Comme on peut le constater sur cet exemple, un motif peut comporter plusieurs perles de la même couleur et, en fin de collier, il est possible qu’on ne puisse appliquer qu’une partie du motif.
Nous allons représenter chaque perle par un caractère indiquant sa couleur et un collier comme un tableau de caractères. Une perle non coloriée sera indiquée par un point (codice_62).
Par exemple, le collier ci-dessus serait représenté ainsi :
Créer un collier.
Écrivez un algorithme créerCollier qui reçoit une taille et crée un collier de cette taille où toutes les perles sont non coloriées (rappel : une perle non coloriée est représentée par un point).
On suppose que la taille reçue est bien un entier non négatif.
Créer un motif.
Écrivez un algorithme créerMotif qui reçoit un collier dont aucune perle n’est coloriée et qui colorie les premières en fonction des indications de l’utilisateur.
Concrètement, l’utilisateur entre les couleurs des perles en spécifiant à chaque fois, après, s’il y a encore une perle à colorier. Dans notre exemple de la première page, l’utilisateur entrerait successivement : ’R’, vrai, ’R’, vrai, ’V’, faux.
L’algorithme doit vérifier que l’utilisateur ne demande pas à colorier plus de perles qu’il n’y en a dans le collier.
Taille du motif.
Écrivez un algorithme tailleMotif qui reçoit un collier dont seulement les premières perles sont coloriées (c’est le motif qu’il faudra suivre) et qui donne la taille de ce motif. Dans l’exemple de la première page, il faudra retourner la valeur 3. Votre algorithme doit générer une erreur si il n’y a pas de motif à suivre.
Suivre un motif.
Écrivez un algorithme colorier qui reçoit un collier dont seulement les premières perles sont coloriées (c’est le motif qu’il faut suivre) et qui colorie le reste du collier en suivant ce motif.
Vérifier un collier.
Écrivez un algorithme vérifier qui reçoit un collier complètement colorié et la taille du motif de départ et qui vérifie si le collier respecte ce motif.
Trouver le motif.
Écrivez un algorithme trouverMotif qui reçoit un collier complètement colorié et qui détermine la taille du motif. C’est la plus petite séquence qui se répète. Comme cas extrème, ce pourrait être le collier tout entier.
Aide : vous avez déjà tout pour que cet exercice soit facile.
= Les fiches =
Vous trouverez ici toutes les fiches des algorithmes analysés dans ce cours.
Un calcul simple [fiche:calcul-simple]
Calculer la surface d’un rectangle à partir de sa longueur et sa largeur.
Données (toutes réelles et non négatives) :
Résultat : un réel représentant la surface du rectangle.
La surface d’un rectangle est obtenue en multipliant la largeur par la longueur. formula_14 Ce qui donne :
longueur * largeur
Ce type de solution peut être utilisé à chaque fois que la réponse s’obtient par un calcul simple sur les données. Si le calcul est plus complexe, il peut être utile de le décomposer pour accroitre la lisibilité (cf. fiche )
Un calcul complexe [fiche:calcul-complexe]
Calculer la vitesse moyenne (en km/h) d’un véhicule dont on donne la distance parcourue (en mètres) et la durée du parcours (en secondes).
Données (toutes réelles et non négatives) :
Résultat : la vitesse moyenne du véhicule (en km/h).
La vitesse moyenne est liée à la distance et à la durée par la formule : formula_392
pour autant que les unités soient cohérentes. Ainsi pour obtenir une vitesse en km/h, il faut convertir la distance en kilomètres et la durée en heures. Ce qui donne :
Ce type de solution peut être utilisé à chaque fois que la réponse s’obtient par un calcul complexe sur les données qu’il est bon de décomposer pour aider à sa lecture. Si le calcul est plutôt simple, on peut le garder en une seule expression (cf. fiche ).
Un nombre pair [fiche:calcul-pair]
Un nombre reçu en paramètre est-il pair ?
Données : le nombre entier dont on veut savoir si il est pair.
Résultat : un booléen à "vrai" si le "nombre" est pair et "faux" sinon.
Un nombre est pair si il est multiple de 2. C’est-à-dire si le reste de sa division par 2 vaut 0.
nombre MOD 2 = 0
Attention à éviter les mauvaises écritures expliquées à l’annexe  : pas de .
À chaque fois qu’un résultat booléen dépend d’un calcul simple. Si le calcul est plus compliqué, on peut le décomposer comme indiqué dans la fiche .
On peut également s’inspirer de cette solution quand il faut donner sa valeur à une variable booléenne.
Maximum de deux nombres [fiche:max2nb]
Quel est le maximum de deux nombres ?
Voilà un classique de l’algorithmique. Attention ! On ne veut pas savoir "lequel" est le plus grand mais juste la valeur. Il n’y a donc pas d’ambigüité si les deux nombres sont égaux.
Données : deux nombres réels.
Résultat : un réel contenant la plus grande des deux valeurs données.
3
max nb1 max nb2 max
Attention à éviter les mauvaises écritures expliquées à l’annexe .
Cet algorithme peut bien sûr être facilement adapté à la recherche du minimum.
Passage d’un tableau en paramètre [fiche:tab-passage-param]
Le type "tableau" étant un type à part entière, il est tout-à-fait éligible comme type pour les paramètres et la valeur de retour d’un algorithme.
Comme pour n’importe quel autre type, un algorithme peut retourner un tableau. Ce sera à lui de le déclarer et de lui donner des valeurs.
Exemple :
Crée un tableau d’entiers de taille n, l’initialise à 0 et le retourne. tab[i] 0 tab entiers créerTableau(20) afficher(entiers)
Parcours complet d’un tableau [fiche:tab-parcours-complet]
Afficher tous les éléments d’un tableau d’entiers.
Données : le tableau à afficher
Résultat : aucun. Se contente d’afficher les éléments.
Puisqu’on parcourt tout le tableau, on peut utiliser une boucle "pour".
tab[i]
Ce type de solution peut être utilisé à chaque fois qu’on doit examiner tous les éléments d’un tableau, quel que soit le traitement qu’on en fait : les afficher, les sommer, les comparer…
Parcours partiel d’un tableau [fiche:tab-parcours-partiel]
Recherche d’un zéro dans un tableau.
Données : le tableau à tester
Résultat : un booléen à vrai si il existe une valeur nulle dans le tableau.
Contrairement au parcours complet (cf. fiche ) on va utiliser un "tant que" car on peut s’arrêter dès qu’on trouve ce qu’on cherche.
Il existe essentiellement deux solutions, avec ou sans variable booléenne. En général, la solution [A] sera plus claire si le test est court.
[A] Sans variable booléenne.
i 0 i i + 1 i < n Si i<n -> arrêt prématuré -> on a trouvé un 0.
Il faut être attentif à ne pas inverser les deux parties du test. Il faut absolument vérifier que l’indice est bon avant de tester la valeur à cet indice. Revoyez la notion de court-circuit ( ).
[B] Avec variable booléenne.
zéroPrésent faux i 0 zéroPrésent tab[i] = 0 i i + 1 zéroPrésent
Au sortir de la boucle, l’indice ne désigne pas l’élément qui nous a permis d’arrêter mais le suivant. Si nécessaire, on peut remplacer l’intérieur de la boucle par :
zéroPrésent vrai i i + 1
Dans notre exemple, on cherche un élément particulier (un 0). Dans le cas où on vérifie si tous les éléments possèdent une certaine propriété (être positifs par exemple), on veillera à adapter le nom du booléen et son utilisation (par exemple un booléen appelé , initialisé à vrai avec un dans le test.
Dans tous les cas, faites attention à ne pas utiliser si vous n’êtes pas sûr du . C’est particulièrement vrai après la boucle.
Attention aussi à éviter les mauvaises pratiques expliquées à l’annexe .
Ce type de solution peut être utilisé à chaque fois qu’on parcourt un tableau mais qu’un arrêt avant la fin est possible.
Maximum dans un tableau [fiche:tab-max]
Trouver la valeur maximale dans un tableau d’entiers.
Données : le tableau à analyser
Résultat : la valeur du maximum
Il faut veiller à initialiser le maximum avec la première valeur du tableau pour parcourir le reste du tableau à la recherche d’une valeur plus grande.
max tab[0] max tab[i] max
On peut être intéressé par la position où se trouve le (en tout cas un) maximum.
posMax 0 posMax i posMax
Tableau non trié [fiche:tab-recherche-non-triee]
Rechercher, ajouter, supprimer des données non triées dans un tableau d’entiers non triés.
Retourner l’indice d’une donnée trouvée dans un tableau non trié ou -1 si elle n’est pas trouvée
Données : le tableau à analyser, le nombre d’éléments dans ce tableau (taille logique), la valeur à rechercher
Résultat : la position de l’élément si il est dans le tableau et -1 sinon
i 0 i i + 1 i -1
Ajouter une donnée non encore présente dans le tableau de données non triées
Données : le tableau à modifier, le nombre d’éléments dans ce tableau, la valeur à ajouter
Résultat : le tableau reçu est modifié en lui ajoutant la valeur si elle n’y était pas déjà
tab[nbElem] nbAjouter nbElem nbElem + 1
Supprimer une donnée d’un tableau de données non triées
Données : le tableau à modifier, le nombre d’éléments dans ce tableau, la valeur à supprimer
Résultat : le tableau reçu est modifié en lui supprimant la valeur
pos vérifier(tab, nbElem, nbSupprimer) tab[pos] tab[nbElem-1] nbElem nbElem - 1
Tableau trié [fiche:tab-recherche-triee]
Rechercher, ajouter, supprimer des données triées dans un tableau d’entiers triés.
Rechercher la position où a été trouvé l’élément ou la position où il aurait dû être
Données : le tableau à analyser, le nombre d’éléments dans ce tableau, la valeur à rechercher
Résultat : la position où a été trouvé la valeur ou la position où elle aurait dû être
pos 0 pos pos + 1 trouvé pos < nbElem ET tab[pos] = nbRecherché
Rechercher l’indice d’une donnée trouvée dans un tableau trié ou -1 si elle n’est pas trouvée
Données : le tableau à analyser, le nombre d’éléments dans ce tableau, la valeur à rechercher
Résultat : la position de l’élément si il est dans le tableau et -1 sinon
Cette opération est triviale.
rechercher( tab, nbElem, nbRecherché, trouvé, pos ) pos -1
Ajouter une donnée non encore présente dans le tableau de données non triées
Données : le tableau à modifier, le nombre d’éléments dans ce tableau, la valeur à ajouter
Résultat : le tableau reçu est modifié en lui ajoutant la valeur si elle n’y était pas déjà
rechercher( tab, nbElem, nbAjouter, trouvé, pos ) décalerDroite( tab, pos, nbElem) tab[pos] nbAjouter nbElem nbElem + 1 tab[i+1] tab[i]
Supprimer une donnée d’un tableau de données non triées
Données : le tableau à modifier, le nombre d’éléments dans ce tableau, la valeur à supprimer
Résultat : le tableau reçu est modifié en lui supprimant la valeur
rechercher( tab, nbElem, nbSupprimer, trouvé, pos ) décalerGauche( tab, pos+1, nbElem) nbElem nbElem - 1 tab[i-1] tab[i]
Recherche dichotomique [fiche:dicho]
Trouver rapidement la position d’une valeur donnée dans un tableau trié d’entiers. Si la valeur n’est pas présente, on donnera la position où elle aurait du se trouver.
Données :
Résultat :
L’algorithme rapide que nous avons vu est la recherche dichotomique.
indiceGauche 0 indiceDroit n-1 trouvé faux indiceMédian (indiceGauche + indiceDroit) DIV 2 candidat tab[indiceMédian] trouvé vrai indiceGauche indiceMédian + 1 on garde la partie droite indiceDroit indiceMédian – 1 on garde la partie gauche pos indiceMédian pos indiceGauche dans le cas où la valeur n’est pas trouvée, on vérifiera que indiceGauche donne la valeur où elle pourrait être insérée. trouvé
Tri d’un tableau [fiche:tri]
Trier un tableau d’entiers par ordre croissant.
Données : le tableau non trié, à trier.
Résultat : ce même tableau trié.
Nous avons vu trois algorithmes
Le tri par insertion.
Trie le tableau reçu en paramètre (via un tri par insertion). valÀInsérer tab[i] recherche de l’endroit où insérer valÀInsérer dans le sous-tableau trié et décalage simultané des éléments j i - 1 tab[j+1] tab[j] j j – 1 tab[j+1] valÀInsérer
Le tri par sélection des minima successifs.
Trie le tableau reçu en paramètre (via un tri par sélection des minima successifs). i correspond à l’étape de l’algorithme indiceMin positionMin( tab, i, n-1 ) swap( tab[i], tab[indiceMin] )
Retourne l’indice du minimum entre les indices début et fin du tableau reçu. indiceMin début indiceMin i indiceMin
aux a a b b aux
Le tri bulle.
Trie le tableau reçu en paramètre (via un tri bulle). swap( tab[i], tab[i + 1] ) voir algorithme précédent
= Bonnes (et mauvaises) pratiques =
Au fil des années, nous voyons souvent les étudiants écrire les mêmes bouts de code qui sont discutables, voire à proscrire. Discutons ici des plus courants.
Tester un booléen.
Lorsqu’il s’agit de comparer deux nombres dans la condition d’un , vous écrivez tous assez naturellement :Il ne vous viendrait pas à l’idée d’écrire :
9cm Avec un booléen, les choses sont moins simples. Par exemple, si on doit faire quelque chose si la variable est vraie, vous êtes nombreux à écrire le bout de code ci-contre, en tout cas en début d’année.
4cm
-5mm 
9cm Cette écriture est correcte mais inutilement lourde. La variable étant déjà un booléen qui vaut vrai ou faux, il suffit d’écrire :
4cm
-5mm 
9cm De même, si le test doit être vrai quand la variable booléenne est fausse, il suffit d’écrire :
4cm
-5mm 
On comprend que la première écriture vous vienne d’abord et on la tolérera les premières séances mais vous devrez vite vous en débarrasser ; elle ne sera pas tolérée lors des évaluations.
Assigner un booléen.
Lorsqu’il s’agit de donner une valeur à un booléen, on vous voit souvent écrire un si-sinon. Ce n’est pas la bonne idée.
9cm Par exemple, si la variable booléenne doit valoir si un nombre est égal à 0 et sinon, vous êtes nombreux à écrire le bout de code ci-contre.
4cm
nul vrai nul faux
-5mm 
9cm C’est correct mais inutilement compliqué. Puisque on assigne si la condition est vraie et si la condition est fausse, il suffit d’assigner la condition. Ce qui donne :
4cm
nul nb = 0
-5mm 
À nouveau, on tolérera le si-sinon les premières séances mais on attend de vous que vous passiez rapidement à une simple assignation. Ce sera sanctionné lors des évaluations.
Assigner une valeur en fonction d’une condition.
9cm Examinons l’exemple ci-contre qui assigne un qui doit être différent en fonction du droit ou non à un tarif réduit.
4cm
prix 8 prix 12
-5mm 
9cm Nous voyons régulièrement des étudiants écrire plutôt fièrement la version ci-contre en arguant qu’elle est plus courte, donc mieux.
Elle comporte effectivement (un peu) moins de lignes mais ce critère n’a que très peu d’importance. Cette version n’est pas plus rapide (elle est même plus lente en cas de tarif réduit) et elle est moins lisible car le lecteur croit d’abord que le tarif est toujours de 12 avant de constater qu’il peut être différent.
4cm
prix 12 prix 8
-5mm 
On vous demande de vous en tenir à la première version. La seconde sera sanctionnée.
Interrompre une boucle pour.
On voit trop souvent des étudiants écrire une boucle pour et l’interrompre anticipativement en modifiant l’indice ; c’est une très mauvaise idée.
Dans l’exemple ci-contre, si une certain condition est vraie, on donne une grande valeur à l’indice pour sortir de la boucle.
[t]7cm -8mm
… i n+1 …
-5mm 
Il est totalement interdit de modifier explicitement l’indice d’une boucle, quelle qu’en soit la raison. Ce n’est pas une bonne idée en terme de lisibilité et dans certains langages c’est interdit ou cela ne fait pas ce qui est attendu.
6cm Nous tenons absolument à ce que vous passiez par une boucle tant-que et l’utilisation d’un booléen pour contrôler la fin. Par exemple :
[t]7cm -8mm
i 1 fini faux … fini vrai …i i+1
-5mm 
6cm Si le test est la première instruction de la boucle et que la condition est courte, on peut aussi se passer de la variable booléenne.
[t]7cm -8mm
i 1 …i i+1
-5mm 
Plusieurs retourner.
Dans le cours, nous vous avons donné comme règle : Un seul par algorithme.
Cette règle n’est pas partagée par tous les programmeurs. Il existe un courant qui tolère plusieurs dans certains cas précis.
7cm Un cas concret est pour interrompre anticipativement une boucle. Certains écrivent :
6cm
quelquechose autrechose
-5mm 
7cm Une autre situation est lorsque la valeur à retourner dépend d’un test. On voit alors des bouts de code qui ressemblent à :
6cm
quelquechose autrechose
-5mm 
Ces écritures seront tolérées dans ce cours (et donc non sanctionnées) mais nous ne les encourageons pas par crainte d’abus : elles ne peuvent se justifier que pour des algorithmes très courts.
= Le LDA =
Dans cette annexe nous définissons le LDA ("le Langage de Description d’Algorithmes") que nous allons utiliser. Nous ne nous attarderons pas sur les concepts ni sur certaines bonnes pratiques; tout cela est vu dans les chapitres associés.
Nous utilisons un pseudo-code pour nous libérer des contraintes des langages de programmation.
Dans vos réflexions, brouillons, premiers jets, nous vous encourageons à utiliser des notations qui vous sont propres et qui vous permettent de poser votre réflexion sur un papier et d’avancer vers une solution.
La version finale, toutefois, doit être lue par d’autres personnes. Il est essentiel qu’il n’y ait aucune ambigüité sur le sens de votre écrit. C’est pourquoi, nous devons définir une notation à la fois souple et précise.
Cette notation doit aussi être adaptée à des étudiants de première année. Ce qui nous amène à ne pas introduire des nuances qui leur échappent encore et, parfois, à imposer des contraintes qui seront relâchées plus tard mais qui permettent de cadrer l’apprentissage d’un débutant.
Remarque : Ce guide n’est pas universel. En dehors de l’école, d’autres notations sont utilisées, parfois proches, parfois plus lointaines. Votre professeur pourra également introduire quelques notations qui ne sont pas reprises ici ou relâcher quelques contraintes définies ici. Lorsque vous changerez de professeur, soyez conscient que ces ajouts ne seront peut-être plus valables.
L’important est que le groupe qui doit communiquer au moyen d’algorithmes se soit préalablement mis d’accord sur des notations.
Un algorithme.
6cm
Instructions expression
6cm
Instructions
On permet l’utilisation du raccourci .
Types, variables et constantes.
Les types permis sont : , , et .
Les instructions de base.
var expression var1, var2…expression1, expression2…“raison” Provoque l’arrêt de l’algorithme.
Les instructions de choix.
[t]4.5cm
Instructions
[t]4.5cm
Instructions Instructions
[t]4.5cm
Instructions Instructions …Instructions
Instructions Instructions … Instructions Instructions
où l’expression peut être de type ou (pas de ) et les valeurs sont des constantes.
Les instructions de répétition.
[t]4cm
Instructions
[t]6.0cm
Instructions
[t]3.2cm
Instructions
Les tableaux.
Le type tableau se note . Ainsi une déclaration ressemble à :
Les éléments se notent à . On remarque que nous avons choisi de faire commencer les tableaux à 0 par défaut mais on peut choisir un autre début en écrivant :
On peut assigner toutes les valeurs d’un tableau via une notation compacte.
Les structures.
Une structure se définit ainsi :
On peut alors déclarer naturellement une variable structurée.
Un champ s’accède grâce à la notation pointée : .
Pour assigner une valeur à tous les champs d’une variable structurée, on peut assigner chaque champ séparément avec la notation pointée ou utiliser une notation compacte.
= Aide mémoire =
Cet aide-mémoire peut vous accompagner lors d’une interrogation ou d’un examen. Il vous est permis d’utiliser ces méthodes sans les développer. Par contre, si vous sentez le besoin d’utiliser une méthode qui n’apparait pas ici, il faudra en écrire explicitement le contenu.
Manipuler les chaines.
Remarque : lorsqu’on indique , on signifie une chaine de longueur 1.