Algorithmique

Un livre de Wikilivres.
Aller à : navigation, rechercher
Algorithmique

un livre appartenant à l'étagère Informatique de Wikilivres.

Livre à fractionner

Il a été suggéré de fractionner ce livre en plusieurs sous-pages afin d'améliorer sa lisibilité.

Sections

Cours d'algorithmique pour débutants[modifier | modifier le wikicode]

Ce cours algorithmique pour débutants est très largement inspiré du cours proposé 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 | modifier le wikicode]

  1. Introduction aux algorithmes
  2. Les bases de l'algorithmique
  3. Les tableaux
  4. Compléments : chaines et structures
  5. Exercices et solutions
  6. Annexes

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 à esi-dev1-list@heb.be.

Résoudre des problèmes[modifier | modifier le wikicode]

« L’algorithmique est le permis de conduire de l’informatique. Sans elle, il n’est pas concevable d’exploiter sans risque un ordinateur. » [1]

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[modifier | modifier le wikicode]

Préliminaires : utilité de l’ordinateur[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 :

  • toutes ont un nom
  • elles s’expriment dans un langage (français, anglais, dessins…)
  • l’ensemble de la procédure consiste en une série chronologique d’instructions ou de phrases (parfois numérotées)
  • une instruction se caractérise par un ordre, une action à accomplir, une opération à exécuter sur les données du problème
  • certaines phrases justifient ou expliquent ce qui se passe :  ce sont des commentaires.

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 ! [2]

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 ambigüe, on vous propose l’expérience suivante.

Expérience.[modifier | modifier le wikicode]

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 ».

  1. Chaque personne prend une feuille de papier et y dessine quelque chose en quelques traits précis. Le dessin ne doit pas être trop compliqué ; on ne teste pas ici vos talents de dessinateur ! (ça peut être une maison, une voiture…)
  2. Sur une autre feuille de papier, chacun rédige des instructions permettant de reproduire fidèlement son propre dessin. Attention ! Il est important de ne jamais faire référence à la signification du dessin. Ainsi, on peut écrire : « dessine un rond » mais certainement pas : « dessine une roue ».
  3. Chacun cache à présent son propre dessin et échange sa feuille d’instructions avec celle de quelqu’un d’autre.
  4. Chacun s’efforce ensuite de reproduire le dessin d’un autre en suivant scrupuleusement les instructions indiquées sur la feuille reçue en échange, sans tenter d’initiative (par exemple en croyant avoir compris ce qu’il faut dessiner).
  5. Nous examinerons enfin les différences entre l’original et la reproduction et nous tenterons de comprendre pourquoi elles se sont produites (par imprécision des instructions ou par mauvaise interprétation de celles-ci par le dessinateur…)

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Pour prolonger votre réflexion sur le concept d’algorithme nous vous proposons quelques ressources en ligne :

Une approche ludique : Code Studio[modifier | modifier le wikicode]

l14mm -4mm image -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 :

  • L’heure de code : http://studio.code.org/hoc/1.

    Un survol des notions fondamentales en une heure au travers de vidéos explicatives et d’exercices interactifs.

  • Cours d’introduction : http://studio.code.org/s/20-hour.

    Un cours de 20 heures destiné aux adolescents. Il reprend et approfondi les éléments effleurés dans  L’heure de code

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Décrivons la différence entre un algorithme et un programme et comment un ordinateur peut exécuter un programme.

Algorithme[modifier | modifier le wikicode]

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 ambigüité, 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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 :

  • l’organe de contrôle :  c’est le cerveau de l’ordinateur. Il est l’organisateur, le contrôleur suprême de l’ensemble. Il assume l’enchainement des opérations élémentaires. Il s’occupe également d’organiser l’exécution effective de ces opérations élémentaires reprises dans les programmes.
  • l’organe de calcul :  c’est le calculateur où ont lieu les opérations arithmétiques ou logiques. Avec l’organe de contrôle, il constitue le processeur ou unité centrale.
  • la mémoire centrale :  dispositif permettant de mémoriser, pendant le temps nécessaire à l’exécution, les programmes et certaines données pour ces programmes.
  • les unités d’échange avec l’extérieur : dispositifs permettant à l’ordinateur de recevoir des informations de l’extérieur (unités de lecture telles que clavier, souris, écran tactile…) ou de communiquer des informations vers l’extérieur (unités d’écriture telles que écran, imprimantes, signaux sonores…).
  • les unités de conservation à long terme :  ce sont les mémoires auxiliaires (disques durs, CD ou DVD de données, clés USB…) sur lesquelles sont conservées les procédures (programmes) ou les informations résidentes dont le volume ou la fréquence d’utilisation ne justifient pas la conservation permanente en mémoire centrale.

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[modifier | modifier le wikicode]

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

image

& Comment fonctionne le processeur ?

De façon très simplifiée, on passe par les étapes suivantes :

  1. Le processeur lit l’instruction courante.
  2. Il exécute cette instruction. Cela peut amener à manipuler les données.
  3. L’instruction suivante devient l’instruction courante.
  4. On revient au point 1.


On voit qu’il s’agit d’un travail automatique ne laissant aucune place à l’initiative !

Les phases d’élaboration d’un programme[modifier | modifier le wikicode]

Voyons pour résumer un schéma simplifié des phases par lesquelles il faut passer quand on développe un programme.

m0.20m0.75

(P1) to (P2); (P2) to (P3); (P3) to (P4); (P4) to (P5);

&

  • Lors de l’analyse, le problème doit être compris et clairement précisé. Vous aborderez cette phase dans le cours d’analyse.
  • Une fois le problème analysé, et avant de passer à la phase de programmation, il faut réfléchir à l’algorithme qui va permettre de résoudre le problème. C’est à cette phase précise que s’attache ce cours.
  • On peut alors programmer cet algorithme dans le langage de programmation choisi. Vos cours de langage (Java, Cobol, Assembleur, …) sont dédiés à cette phase.
  • Vient ensuite la phase de tests qui ne manquera pas de montrer qu’il subsiste des problèmes qu’il faut encore corriger. (Vous aurez maintes fois l’occasion de vous en rendre compte lors des séances de laboratoire)
  • Le produit sans bug (connu) peut être mis en application ou livré à la personne qui vous en a passé la commande.


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.

  • Passer par une phase « algorithmique » permet de séparer deux difficultés :  quelle est la marche à suivre ? Et comment l’exprimer dans le langage de programmation choisi ? Le langage que nous allons utiliser en algorithmique est plus souple et plus général que le langage Java par exemple (où il faut être précis au « ; » près).
  • De plus, un algorithme écrit facilite le dialogue dans une équipe de développement. « J’ai écrit un algorithme pour résoudre le problème qui nous occupe. Qu’en pensez-vous ? Pensez-vous qu’il est correct ? Avez-vous une meilleure idée ? ». L’algorithme est plus adapté à la communication car plus lisible.
  • Enfin, si l’algorithme est écrit, il pourra facilement être traduit dans n’importe quel langage de programmation. La traduction d’un langage de programmation à un autre est un peu moins facile à cause des particularités propres à chaque langage.

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 paraitra difficile en début d’année vous paraitra (enfin, il faut l’espérer !) une évidence en fin d’année.

Conclusion[modifier | modifier le wikicode]

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 :

  • essayer de définir une bonne démarche d’élaboration d’algorithmes (apprentissage de la logique de programmation) ;
  • comprendre et apprendre les algorithmes classiques qui ont fait leurs preuves. Pouvoir les utiliser en les adaptant pour résoudre nos problèmes concrets.

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) :

  • la représentation des algorithmes
  • la programmation structurée
  • la programmation procédurale : les modules et le passage de paramètres
  • les algorithmes de traitement des tableaux
  • la résolution de problèmes récursifs
  • les algorithmes liés au traitement des structures de données particulières telles que listes, files d’attente, piles, arbres, graphes, tables de hachage, etc.

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[modifier | modifier le wikicode]

Pour prolonger votre réflexion sur les notions vues dans ce chapitre, nous vous proposons quelques ressources en ligne :

Spécifier le problème[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 [3].

Exemple.[modifier | modifier le wikicode]

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 :

  • la longueur du rectangle ;
  • sa largeur.

Quel est le résultat attendu ? la surface du rectangle.

Les noms[modifier | modifier le wikicode]

Pour identifier clairement chaque donnée et pouvoir y faire référence dans le futur algorithme nous devons lui attribuer un nom [4]. 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.[modifier | modifier le wikicode]

Quel nom choisir pour la longueur d’un rectangle ?

On peut envisager les noms suivants :

  • est probablement le plus approprié.
  • peut se justifier pour éviter toute ambigüité avec une autre longueur.
  • peut être admis si le contexte permet de comprendre immédiatement l’abréviation.
  • et sont à proscrire car pas assez explicites.
  • est inutilement long.
  • ou ne sont pas de bons choix car ils n’ont aucun lien avec la donnée.

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 :

  • soit un verbe indiquant ce que fait l’algorithme ;
  • soit un nom indiquant le résultat fourni.
Exemple.[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 chaines de caractères, les textes (par exemple : , , , …)
& quand la valeur ne peut être que ou

Exemples.[modifier | modifier le wikicode]
  • Pour la longueur, la largeur et la surface d’un rectangle, on prendra un réel.
  • Pour le nom d’une personne, on choisira la chaine.
  • Pour l’âge d’une personne, un entier est indiqué.
  • Pour décrire si un étudiant est doubleur ou pas, un booléen est adapté.
  • Pour représenter un mois, on préférera souvent un entier donnant le numéro du mois (par ex: 3 pour le mois de mars) plutôt qu’une chaine (par ex: “mars”) car les manipulations, les calculs seront plus simples.

Il n’y a pas d’unité[modifier | modifier le wikicode]

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 mais certainement pas . Si cette unité a de l’importance, il faut la spécifier dans le nom de la donnée ou en commentaire.

Exemple.[modifier | modifier le wikicode]

Faut-il préciser les unités pour les dimensions d’un rectangle ?

Si la longueur d’un rectangle vaut , 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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]
  • Un âge est un entier qui ne peut pas être négatif.
  • Un mois est un entier compris entre 1 et 12.

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[modifier | modifier le wikicode]

Parfois, aucun des types disponibles ne permet de représenter la donnée. Il faut alors la décomposer.

Exemple.[modifier | modifier le wikicode]

Quel type choisir pour la date de naissance d’une personne ?

On pourrait la représenter dans une chaine (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 [5]. 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[modifier | modifier le wikicode]

Quel(s) type(s) de données utiliseriez-vous pour représenter

  • le prix d’un produit en grande surface ?
  • la taille de l’écran de votre ordinateur ?
  • votre nom ?
  • votre adresse ?
  • le pourcentage de remise proposé pour un produit ?
  • une date du calendrier ?
  • un moment dans la journée ?

Résumé graphique[modifier | modifier le wikicode]

Toutes les informations déjà collectées sur le problème peuvent être représentées graphiquement.

Exemple.[modifier | modifier le wikicode]

Pour le problème, de la surface du rectangle, on fera le schéma suivant :

Exemples numériques[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

Voici différentes façons de présenter des exemples numériques pour le problème de calcul de la surface d’un rectangle :

  • En français : si la longueur du rectangle vaut 3 et sa largeur vaut 2, alors sa surface vaut 6.
  • Via un schéma :
  • En notation compacte : donne/vaut .

Exercices[modifier | modifier le wikicode]

Pour les exercices suivants, nous vous demandons d’imiter la démarche décrite dans ce chapitre, à savoir :

  • Déterminer quelles sont les données ; leur donner un nom et un type.
  • Déterminer quel est le type du résultat.
  • Déterminer un nom pertinent pour l’algorithme.
  • Fournir un résumé graphique.
  • Donner des exemples.

Somme de 2 nombres Calculer la somme de deux nombres donnés.

Solution.[modifier | modifier le wikicode]

[6] 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 donne donne donne .

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, ). On voudrait calculer sa vitesse (en km/h) à partir de son allure. Par exemple, la vitesse d’un coureur ayant une allure de est de  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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Trouver l’algorithme[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

Calculer la surface d’un rectangle à partir de sa longueur et sa largeur.

Analyse.[modifier | modifier le wikicode]

Nous sommes arrivés à la spécification suivante :

Exemples.

2

  • donne  ;
  • donne .
Comment résoudre ce problème ?[modifier | modifier le wikicode]

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 : La surface s’obtient donc en multipliant la longueur par la largeur [7].

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 :

  • le nom de l’algorithme,
  • une déclaration des données, qu’on appellera ici les paramètres,
  • le type du résultat.

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 et la largeur est .

Vérifier l’algorithme[modifier | modifier le wikicode]

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 :

  • vérifier qu’il fonctionne également dans certains cas particuliers auxquels il est difficile de penser quand on débute ;
  • donner son avis sur la qualité de votre solution c-à-d essentiellement sur sa lisibilité. Nous y reviendrons.

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.[modifier | modifier le wikicode]

Vérifions notre solution pour le calcul de la surface du rectangle en reprenant les exemples choisis.

test longueur largeur réponse attendue réponse fournie
1 3 2 6 6
2 3.5 1 3.5 3.5

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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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.

test nombre1 nombre2 réponse attendue réponse fournie
1 3 2 5 5
2 -3 2 -1 -1
1 3 2.5 5.5 5.5
2 -2.5 2.5 0 0

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[modifier | modifier le wikicode]

Dans les exercices de la section précédente, vous avez écrit quelques longues formules [8]. 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[modifier | modifier le wikicode]

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.

  • On parle de variable car son contenu peut changer pendant le déroulement de l’algorithme.
  • On l’appelle locale car elle n’est connue et utilisable qu’au sein de l’algorithme où elle est déclarée [9].

Pour être utilisable, une variable doit être déclarée [10] 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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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

Remarques[modifier | modifier le wikicode]
  • Une assignation n’est pas une égalité, une définition.
    Ainsi, l’assignation ne veut pas dire que , ce qui est mathématiquement faux mais que la nouvelle valeur de doit être calculée en ajoutant 1 à sa valeur actuelle. Ce calcul doit être effectué au moment où on exécute cette instruction.
  • Seules les variables déclarées peuvent être affectées.
  • Toutes les variables apparaissant dans une expression doivent avoir été affectées préalablement. Le contraire provoquerait une erreur, un arrêt de l’algorithme.
  • La valeur affectée à une variable doit être compatible avec son type. Pas question de mettre une chaine dans une variable booléenne.

Tracer un algorithme[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

Traçons des bouts d’algorithmes.

4cm

[1] a 12 b 5 c a - b a a + c b a

7cm

| m1cm|*3 m2cm| # & a & b & c
1 & indéfini & indéfini & indéfini
2 & 12 & &
3 & & 5 &
4 & & & 7
5 & 19 & &
6 & & 19 &

4cm

[1] a 12 c a - b d c - 2

7cm

| m1cm|*3 m2cm| # & a & b & c
1 & indéfini & indéfini & indéfini
2 & 12 & &
3 & & & ???
4 & & & ???

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

| m1cm|*3 m2cm| # & a & b & c
1 & & &
2 & & &
3 & & &
4 & & &
5 & & &
6 & & &
7 & & &

4cm

[1] a 2 b a c b - a a a a / a

7cm

| m1cm|*3 m2cm| # & a & b & c
1 & & &
2 & & &
3 & & &
4 & & &
5 & & &
6 & & &

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 Échec d'analyse (erreur de syntaxe): {\displaystyle \frac{\textrm{distanceKM}}{\textrm{duréeH}}}

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.

| m1cm|*5 m2cm| # & & & & &
1 & & & & &
2 & & & & &
3 & & & & &
4 & & & & &
5 & & & & &

Si vous trouvez qu’il n’est pas correct, voyez ce qu’il faudrait changer pour le corriger.

Exercices de décomposition[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

L’analyse du problème aboutit à :

La formule qui lie les trois éléments est : pour autant que les unités soient compatibles. Dans notre cas, il faut d’abord convertir la distance en mètres, selon la formule : quelques exemples numériques :

2

L’algorithme s’écrit :

[1] distanceM 1000 * distanceKM distanceM / vitesseMS

Vérifions l’algorithme pour

| m1cm|*4 m2cm| # & vitesseMS & distanceKM & distanceM & résultat
1 & 1 & 1 & &
2 & & & indéfini &
3 & & & 1000 &
4 & & & & 1000

et pour

| m1cm|*4 m2cm| # & vitesseMS & distanceKM & distanceM & résultat
1 & 0.5 & 0.2 & &
2 & & & indéfini &
3 & & & 200 &
4 & & & & 400

Allure et vitesse L’allure d’un coureur est le temps qu’il met pour parcourir 1 km (par exemple, ). On voudrait calculer sa vitesse (en km/h) à partir de son allure. Par exemple, la vitesse d’un coureur ayant une allure de est de  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[modifier | modifier le wikicode]

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 :

  • assigner des valeurs booléennes en fonction de comparaisons ;
  • manipuler les opérateurs logiques ;
  • utiliser la division entière et le reste.

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[modifier | modifier le wikicode]

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.

expression
Une expression indique un calcul à effectuer (par exemple : (a + b) * c). Une fois le calcul effectué (on dit qu’on évalue l’expression), on obtient une valeur, d’un certain type. Une expression est composée d’opérandes et d’opérateurs.
opérateur
Un opérateur est ce qui désigne une opération. Exemple : + désigne l’addition.
opérande
Un opérande est ce sur quoi porte l’opération. Exemple : dans l’expression a+b, a et b sont les opérandes. Un opérande peut être une sous-expression. Exemple : dans l’expression (a+b) * c, (a+b) est l’opérande de gauche de l’opérateur *.
unaire, binaire, ternaire
Un opérateur qui agit sur deux opérandes (le plus fréquent) est qualifié de binaire. On rencontre aussi des opérateurs unaires (ex: le - dans l’expression -a). En Java, vous rencontrerez aussi un opérateur ternaire (3 opérandes) mais ils sont plus rares.
littéral
Un littéral est une valeur notée explicitement (comme 12, 34.4, "bonjour")
priorité
Les opérateurs sont classés par priorité. Cela permet de savoir dans quel ordre les exécuter. Par exemple, la multiplication est prioritaire par rapport à l’addition. C’est pourquoi l’expression a + b * c est équivalente à a + (b * c) et pas à (a + b) * c. Les parenthèses permettent de modifier ou de souligner la priorité.

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).

  • a+1
  • (a+b)*12-4*(-a-b)
  • a+(b*12)-4*-a

Les comparaisons et les assignations de variables booléennes[modifier | modifier le wikicode]

Si je vous dis que est un calcul dont le résultat est , un entier vous n’aurez aucun mal à me croire ; cela vous parait évident. Ce qui l’est peut-être moins c’est que 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 21 adulte est vrai si l’âge est 21 ou plus réussi cote 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.

  • La variable booléenne doit indiquer si le nombre est négatif.
  • Un groupe est complet s’il contient exactement 20 personnes.
  • Un algorithme est considéré comme long si le nombre de lignes dépasse 20.
  • Un étudiant a la plus grande distinction si sa cote est de 18/20 ou plus.

Les opérations logiques[modifier | modifier le wikicode]

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 :

a b a ET b a OU b
vrai vrai vrai vrai
vrai faux faux vrai
faux vrai faux vrai
faux faux faux faux
a NON a
vrai faux
faux vrai

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 [11].
Par exemple, ne pas écrire :

Loi de De Morgan.[modifier | modifier le wikicode]

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 :

Par exemple :
peut s’écrire aussi :
ce qui se simplifie en :

Priorités et parenthèses.[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

[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 b0 ET 1/b 0.1 donne la valeur à si (court-circuit). ok 1/b 0.1 ET b0 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.

  • J’irai au cinéma si le film me plait et que j’ai 20 en poche.
  • Je n’irai pas au cinéma si je n’ai pas 20 en poche.
  • Je brosserai le premier cours de la journée s’il commence à 8h et aussi si je n’ai pas dormi mes 8h.
  • Pour réussir GEN1, il faut au moins 10 dans chacune des AA qui le composent (math, anglais, compta).

La division entière et le reste[modifier | modifier le wikicode]

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

  • 7 DIV 2 vaut 3
  • 8 DIV 2 vaut 4
  • 6 DIV 6 vaut 1
  • 6 DIV 7 vaut 0

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

  • 7 MOD 2 vaut 1
  • 8 MOD 2 vaut 0
  • 6 MOD 6 vaut 0
  • 6 MOD 7 vaut 6

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

  • 11 DIV 3 = __ reste __
  • 3 DIV 11 = __ reste __
  • 11 DIV __ = 2 reste 3
  • __ DIV 3 = 3 reste 1

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)

test prixCentimes réponse correcte valeur retournée Correct ?
1 130 70
2 40 60
3 99 1
4 100 0

Tester la divisibilité[modifier | modifier le wikicode]

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.

On peut donc écrire : .

Extraire les chiffres d’un nombre[modifier | modifier le wikicode]

Faisons une petite expérience numérique.

calcul résultat
65536 MOD 10 6
65536 MOD 100 36
65536 MOD 1000 536
65536 MOD 10000 5536
calcul résultat
65536 DIV 10 6553
65536 DIV 100 655
65536 DIV 1000 65
65536 DIV 10000 6

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[modifier | modifier le wikicode]

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 [12]. À partir d’un nombre donné [13] (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 et 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[modifier | modifier le wikicode]

[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.[modifier | modifier le wikicode]

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

  • donne faux
  • donne vrai
  • donne vrai
  • donne vrai

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 :

test nombre réponse correcte valeur retournée Correct ?
1 4 faux faux
2 15 vrai vrai
3 0 vrai vrai
4 -10 vrai vrai

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 et sont bissextiles mais pas ni .

Des algorithmes de qualité[modifier | modifier le wikicode]

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é[modifier | modifier le wikicode]

L’efficacité désigne le fait que l’algorithme (le programme) résout [14] bien le problème donné. C’est un minimum !

La lisibilité[modifier | modifier le wikicode]

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 :

  • celles qui doivent se convaincre de sa validité avant de passer à la programmation ;
  • celles qui doivent trouver les causes d’une erreur lorsque celle-ci a été rencontrée [15] ;
  • celles qui doivent faire évoluer l’algorithme ou le programme suite à une modification du problème ;
  • et, accessoirement, celles qui doivent le coter ;)

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é[modifier | modifier le wikicode]

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.

  • Il est trompeur. On peut croire une version plus rapide alors qu’il n’en est rien. Par exemple, on peut se dire que décomposer un calcul ralentit un programme puisqu’il doit gérer des variables intermédiaires. Ce n’est pas forcément le cas. Les compilateurs modernes sont capables de nombreuses prouesses pour optimiser le code et fournir un résultat aussi rapide qu’avec un calcul non décomposé.
  • L’expérience montre que la recherche de rapidité mène souvent à des algorithmes moins lisibles. Or la lisibilité doit être privilégiée à la rapidité car sinon il sera impossible de corriger et/ou de faire évoluer l’algorithme.

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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é [16].

Améliorer la lisibilité d’un algorithme[modifier | modifier le wikicode]

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 ?

  1. Il y a d’abord la mise en page qui aide le lecteur à avoir une meilleure vue d’ensemble de l’algorithme, à en repérer rapidement la structure générale. Ainsi, dans ce syllabus :

    • Les mots imposés (on parle de mots-clés) sont mis en évidence (en gras [17]).

    • On écrit une seule instruction par ligne.

    • Les instructions à l’intérieur de l’algorithme sont indentées (décalées vers la droite). On indentera également les instructions à l’intérieur des choix et des boucles.

    • Des lignes verticales relient le début et la fin de quelque chose. Ici, un algorithme mais on pourra l’utiliser également pour les choix et les boucles.

    Exemples à ne pas suivre.

    distanceM 1000 * distanceKM distanceM / vitesseMS

    distanceM 1000 * distanceKM distanceM / vitesseMS

    Il faudra préférer

    distanceM 1000 * distanceKM distanceM / vitesseMS

  2. Il y a, ensuite, l’écriture des instructions elles-mêmes. Ainsi :

    • Il faut choisir soigneusement les noms (d’algorithmes, de paramètres, de variables…)

    • Il faut décomposer (ou au contraire fusionner) des calculs pour arriver au résultat qu’on jugera le plus lisible.

    • On peut introduire des commentaires et/ou des constantes. Deux concepts que nous allons développer maintenant.

Les commentaires[modifier | modifier le wikicode]

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 :

  • Ceux placés au-dessus de l’algorithme qui expliquent ce que fait l’algorithme et dans quelles conditions il fonctionne (les contraintes sur les paramètres). On parle aussi de documentation.
  • Ceux placés dans l’algorithme qui expliquent comment il le fait.

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.[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 [18] sous la forme suivante [19] :

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 :

  • Une meilleure lisibilité du code, pour autant que vous lui trouviez un nom explicite.
  • Une plus grande facilité pour modifier le code si la constante vient à changer (modification légale du seuil de réussite par exemple).

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[modifier | modifier le wikicode]

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 [20]. 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[modifier | modifier le wikicode]

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 [21].

Demander des valeurs[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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 [22] 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.

| m1cm |*2 m1cm| # & nb & test
& -3 &
1 & & vrai
2 & 3 &

| m1cm |*2 m1cm| # & nb & test
& 3 &
1 & & faux

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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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.

| m6mm |*4 m1cm| # & nb1 & nb2 & max & test
& 3 & 2 & indéfini &
1 & & & indéfini & vrai
2 & & & 3 &

| m6mm |*4 m1cm| # & nb1 & nb2 & max & test
& 4 & 42 & indéfini &
1 & & & indéfini & faux
4 & & & 42 &

Le cas où les deux nombres sont égaux est également géré.

| m1cm |*4 m1cm| # & nb1 & nb2 & max & test
& 4 & 4 & indéfini &
1 & & & indéfini & faux
4 & & & 4 &

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 quelconque, retourne le résultat de la fonction

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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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

|*2 m4mm *2 m9mm| # & nb & signe & test
& 2 & indéfini &
1 & & & vrai
2 & & “positif” &

|*2 m4mm *2 m9mm| # & nb & signe & test
& 0 & indéfini &
1 & & & faux
3 & & & vrai
4 & & “nul” &

|*2 m4mm *2 m9mm| # & nb & signe & test
& 0 & indéfini &
1 & & & faux
3 & & & faux
6 & & “négatif” &

Remarques.[modifier | modifier le wikicode]
  • Pour le dernier cas, on se contente d’un sans indiquer la condition ; ce serait inutile, elle serait toujours vraie.

  • Le et le peuvent être vus comme des cas particuliers du .

  • On pourrait écrire la même chose avec des imbriqués mais le est plus lisible.

    signe “positif” signe “nul” signe “négatif”

  • Lorsqu’une condition est testée, on sait que toutes celles au-dessus se sont avérées fausses. Cela permet parfois de simplifier la condition.

    Exemple. Supposons que le prix unitaire d’un produit () dépende de la quantité achetée (). En dessous de 10 unités, on le paie 10 l’unité. De 10 à 99 unités, on le paie 8 l’unité. À partir de 100 unités, on paie 6 l’unité.

    prixUnitaire 10 prixUnitaire 8 prixUnitaire 6

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 ces 3 coté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

  • moins de 50% n’a pas réussi ;
  • de 50% inclus à 60% exclu a réussi ;
  • de 60% inclus à 70% exclu a une satisfaction ;
  • de 70% inclus à 80% exclu a une distinction ;
  • de 80% inclus à 90% exclu a une grande distinction ;
  • de 90% inclus à 100% inclus a la plus grande distinction.

Le selon-que[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]
  • On peut spécifier plusieurs valeurs pour un cas donné.
  • On peut mettre un cas qui sera exécuté si la valeur n’est pas reprise par ailleurs.

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Motivation[modifier | modifier le wikicode]

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.

  • Cela permet de libérer l’esprit. L’esprit humain ne peut pas traiter trop d’informations à la fois (surcharge cognitive). Lorsqu’un sous-problème est résolu, on peut se libérer l’esprit et attaquer un autre sous-problème.
  • On peut réutiliser ce qui a été fait. Si un même sous-problème apparait plusieurs fois dans un problème ou à travers plusieurs problèmes, il est plus efficace de le résoudre une fois et de réutiliser la solution.
  • On accroit la lisibilité. Si, dans un algorithme, on appelle un autre algorithme pour résoudre un sous-problème, le lecteur verra un nom d’algorithme qui peut être plus parlant que les instructions qui se cachent derrière, même s’il y en a peu. Par exemple, est plus parlant que pour calculer les dizaines d’un nombre.

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[modifier | modifier le wikicode]

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 [23] 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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.

| m1cm | m16mm |*5 m16mm| & &
# & max & a & b & c & maxab & max
2 & indéfini & & & & &
3,7 & & 3 & 2 & 5 & &
8 & & & & & indéfini & indéfini
9 & & & & & 3 & indéfini
10 & & & & & & 5
11,3 & 5 & & & & &

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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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.

| m7mm |*3 m9mm | m10mm *3 m19mm | & &
# & heure & minute & seconde & totalSec & heuresEcoulées & minutesEcoulées & secondesEcoulées
9 & indéfini & indéfini & indéfini & & & &
10, 1 & & & & 65536 & indéfini & indéfini & indéfini
3 & & & & & 18 & &
4 & & & & & & 12 &
5 & & & & & & & 16
6, 10 & 18 & 12 & 16 & & & &

Le paramètre en entrée-sortie[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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.

| m1cm | m20mm |*2 m20mm| & &
# & température & nb & test
8 & indéfini & &
9 & -12.5 & &
10, 1 & & -12.5 &
2 & & & vrai
3 & & 12.5 &
5, 10 & 12.5 & &

La valeur de retour[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.

| m1cm |*5 m10mm |*5 m10mm| & &
# & & & & & & & & & &
3 & 0 & & & & & & & & &
4 & & 5 & & & & & & & &
5 & & & 3 & & & & & & &
6, 18 & & & & & & 0 & 5 & 3 & &
25 & & & & & & 1 & & & &
26 & & & & & & & & & & 1
27 & & & & & & & & & 2 &
32, 6 & 1 & & & 1 & 2 & & & & &
10 & & 7 & & & & & & & &
11 & & & 9 & & & & & & &
12, 18 & & & & & & 1 & 7 & 9 & &
25 & & & & & & 2 & & & &
26 & & & & & & & & & & 0
27 & & & & & & & & & 7 &
32, 6 & 2 & & & 0 & 7 & & & & &

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.

Fichier:Image/figure-parametres-entrants
caption Paramètre entrant

[fig:parin]

Fichier:Image/figure-parametres-sortants
caption Paramètre sortant

[fig:parout]

Fichier:Image/figure-parametres-entrant-sortants
caption Paramètre entrant-sortant

[fig:parinout]

Exercices[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Si on veut faire effectuer un travail répétitif, il faut indiquer deux choses :

  • le travail à répéter ;
  • une indication qui permet de savoir quand s’arrêter.

Examinons quelques exemples pour fixer notre propos.

Exemple 1.[modifier | modifier le wikicode]

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 ».

  • La tâche à répéter est : « traiter un dossier ».
  • On indique qu’on doit continuer s’il reste encore un dossier à traiter.
Exemple 2.[modifier | modifier le wikicode]

Pour calculer la cote finale de tous les étudiants, on aura quelque chose du genre « Pour tout étudiant, calculer sa cote ».

  • La tâche à répéter est : « calculer la cote d’un étudiant ».
  • On indique qu’on doit le faire pour tous les étudiants. On doit donc commencer par le premier, passer à chaque fois au suivant et s’arrêter quand on a fini le dernier.
Exemple 3.[modifier | modifier le wikicode]

Pour afficher tous les nombres de 1 à 100, on aura « Pour tous les nombres de 1 à 100, afficher ce nombre ».

  • La tâche à répéter est : « afficher un nombre ».
  • On indique qu’on doit le faire pour tous les nombres de 1 à 100. On doit donc commencer avec 1, passer à chaque fois au nombre suivant et s’arrêter après avoir affiché le nombre 100.

Une même instruction, des effets différents[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 [24] ; 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 [25].

« tant que »[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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

| m6mm |*3 m2cm| # & nb & condition & affichage
2 & indéfini & &
3 & 1 & &
4 & & vrai &
5 & & & 1
6 & 2 & &
4 & & vrai &
5 & & & 2
6 & 3 & &
4 & & vrai &
5 & & & 3
6 & 4 & &
4 & & vrai &
5 & & & 4
6 & 5 & &
4 & & vrai &
5 & & & 5
6 & 6 & &
4 & & faux &
8 & & & nb vaut 6

Exemple - Généralisation à n nombres[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 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 positif et affiche

  1. les nombres de 1 à  ;
  2. les nombres de 1 à en ordre décroissant ;
  3. les nombres impairs de 1 à  ;
  4. les nombres de -n à n ;
  5. les multiples de 5 de 1 à n ;
  6. les multiples de n de 1 à 100.

« pour »[modifier | modifier le wikicode]

r7cm

[ =triangle 60, node distance = 1.5cm, auto] (Init) variable début; (Test) variable 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 [26].

Exemples[modifier | modifier le wikicode]

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

| m6mm |*2 m12mm m25mm| # & nb & condition & affichage
3 & 1 & vrai &
4 & & & 1
3 & 2 & vrai &
4 & & & 2
3 & 3 & vrai &
4 & & & 3
3 & 4 & vrai &
4 & & & 4
3 & 5 & vrai &
4 & & & 5
3 & 6 & faux &
6 & # & # & nb n’existe plus

Si on veut généraliser l’affichage à n nombres, on a :

nb

Un pas négatif[modifier | modifier le wikicode]

r6cm

[ =triangle 60, node distance = 1.5cm, auto] (Init) variable début; (Test) variable 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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Cette fois-ci on affiche uniquement les nombres pairs jusqu’à la limite .

Exemple : Les nombres pairs de à sont : , , , , .

Notez que peut être impair. Si vaut , l’affichage est le même que pour . On peut utiliser un pour. Une solution possible est :

nb

La section sur les suites proposera d’autres solutions pour ce problème.

Exercices[modifier | modifier le wikicode]

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 positif et affiche

  1. les nombres de 1 à  ;
  2. les nombres de 1 à en ordre décroissant ;
  3. les nombres de -n à n ;
  4. les multiples de 5 de 1 à n ;
  5. les multiples de n de 1 à 100.

« faire – tant que »[modifier | modifier le wikicode]

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 [27]. 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[modifier | modifier le wikicode]

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

| m6mm |*3 m2cm| # & nb & condition & affichage
2 & indéfini & &
3 & 1 & &
5 & & & 1
6 & 2 & &
7 & & vrai &
5 & & & 2
6 & 3 & &
7 & & vrai &
5 & & & 3
6 & 4 & &
7 & & vrai &
5 & & & 4
6 & 5 & &
7 & & vrai &
5 & & & 5
6 & 6 & &
7 & & faux &
8 & & & nb vaut 6

Exercices[modifier | modifier le wikicode]

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 positif et affiche

  1. les nombres de 1 à  ;
  2. les nombres de 1 à en ordre décroissant ;
  3. les nombres de -n à n ;
  4. les multiples de 5 de 1 à n ;
  5. les multiples de n de 1 à 100.

Quel type de boucle choisir ?[modifier | modifier le wikicode]

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.

image [fig:boucle-choix]

Acquisition de données multiples[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

On veut afficher les premiers nombres carrés parfaits : , , , ,

Si on vous demande : “Quel est le 7 nombre à afficher ?”. Vous répondrez : “Facile ! C’est , soit ”. Plus généralement, le nombre à afficher lors du passage dans la boucle est .

l|*8 m8mm étape & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8
valeur à afficher & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64

L’algorithme qui en découle est :

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 [28], une variable de contrôle qui se contente de compter les passages dans la boucle est souvent nommée . On l’appelle aussi « itérateur ».

Cette solution peut être utilisée chaque fois qu’on peut calculer le nombre à afficher en fonction de .

Exemple - Une suite un peu plus complexe[modifier | modifier le wikicode]

Écrire un algorithme qui affiche les 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.

Ici, difficile de partir de la solution de l’exemple précédent car il est n’est pas facile de trouver la fonction 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. 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 premiers termes des suites suivantes. À vous de voir quel est le canevas de solution le plus adapté.

  1. -1, -2, -3, -4, -5, -6…
  2. 1, 3, 6, 10, 15, 21, 28…
  3. 1, 0, 1, 0, 1, 0, 1, 0…
  4. 1, 2, 0, 1, 2, 0, 1, 2…
  5. 1, 2, 3, 1, 2, 3, 1, 2…
  6. 1, 2, 3, 2, 1, 2, 3, 2…

Exercices récapitulatifs[modifier | modifier le wikicode]

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 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.[modifier | modifier le wikicode]

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 fois un dé et compte le nombre de fois qu’une certaine valeur est obtenue.

Factorielle Écrire un algorithme qui retourne la factorielle de (entier positif ou nul). Rappel : la factorielle de , notée !, est le produit des 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

                   1 x 1 = 1
                        1 x 2 = 2
                        ...
                        1 x 10 = 10
                        2 x 1 = 2
                        ...
                        10 x 9 = 90
                        10 x 10 = 100
                

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 . 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, donnerait comme décomposition .

Nombre miroir Le miroir d’un nombre est le nombre obtenu en lisant les chiffres de droite à gauche. Ainsi le nombre miroir de est . É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, 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 ). 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[modifier | modifier le wikicode]

Dans ce chapitre nous étudions les tableaux, une structure qui peut contenir plusieurs exemplaires de données similaires.

Utilité des tableaux[modifier | modifier le wikicode]

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 :

  • le traitement de début de journée, qui consiste essentiellement à mettre les compteurs des quantités vendues pour chaque produit à 0 ;
  • le traitement itératif durant toute la journée : au fur et à mesure des ventes, il convient de les enregistrer, c’est-à-dire d’ajouter au compteur des ventes d’un produit la quantité vendue de ce produit ; ce traitement itératif s’interrompra lorsque la valeur -1 sera introduite ;
  • le traitement final, consistant à communiquer les valeurs des compteurs pour chaque produit.

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 .

*11 m7mm & & & & & & & & & &
& & & & & & & & & &

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 [29], 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 contiendra la valeur .

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[modifier | modifier le wikicode]

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 [30] :

tab {2, 3, 5, 7} tab {0, …, 0} tab {0, 1, 2, …}

Tableau et paramètres[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 :

  • : indique que l’algorithme va consulter les valeurs du tableau reçu en paramètre. Les éléments doivent donc avoir été initialisés avant d’appeler l’algorithme. Exemple :

    tab[i]

    monTab {2,3,5,7,11,13,17,19,23,29} afficher(monTab)

    Rappelons qu’il s’agit du passage par défaut si aucune flèche n’est indiquée.

  • : indique que l’algorithme va consulter/modifier les valeurs du tableau reçu en paramètre. Exemple :

    tab[i] -tab[i]

    monTab {2,-3,5,-7,11,13,17,-19,23,29} inverserSigne(monTab)

  • : indique que l’algorithme va assigner des valeurs au tableau reçu en paramètre. Les éléments de ce tableau n’ont donc pas à être initialisés avant d’appeler cet algorithme. Exemple :

    tab[i] i initialiser(monTab)

Retourner un tableau[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 :

  1. Écrire un algorithme qui inverse le signe de tous les éléments négatifs dans un tableau d’entiers.
  2. Écrire un algorithme qui donne le nombre d’éléments négatifs dans un tableau d’entiers.
  3. Écrire un algorithme qui détermine si un tableau d’entiers contient au moins un nombre négatif.
  4. Écrire un algorithme qui détermine si un tableau de chaines contient une chaine donnée en paramètre.
  5. Écrire un algorithme qui détermine si un tableau de chaines contient au moins deux occurrences de la même chaine, quelle qu’elle soit.
  6. Écrire un algorithme qui retourne un tableau donnant les premiers nombres premiers, où est un paramètre de l’algorithme.
  7. Écrire un algorithme qui reçoit un tableau d’entiers et retourne un tableau de booléens de la même taille où la case indique si oui ou non le nombre reçu dans la case est strictement positif.

Parcours d’un tableau[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 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 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[modifier | modifier le wikicode]

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 :

  • on cherche la présence d’un élément et on vient de le trouver ;
  • on vérifie qu’il n’y a pas de et on vient d’en trouver un ;
  • on vérifie que tous les éléments sont positifs et on vient d’en trouver un qui est négatif ou nul.

Pour résoudre ce problème, on peut partir du parcours complet et :

  • Transformer le en .
  • Introduire un test d’arrêt.

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 chaines et qui retourne un booléen indiquant s’il contient au moins un élément de valeur “pilote”.

Taille logique et taille physique[modifier | modifier le wikicode]

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 [31] 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.[modifier | modifier le wikicode]

Voici un tableau qui ne contient pour l’instant que quatre nombres.

*10| m5mm| 10 & 4 & 3 & 7 & ? & ? & ? & ? & ? & ?


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.[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.[modifier | modifier le wikicode]

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.

*7 m15mm 1 & 2 & 3 & 4 & 5 & 6 & 7
& & & & & &

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 ?[modifier | modifier le wikicode]

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.

  1. La première passe par une conversion d’indice. On stocke les données dans le tableau comme nous l’impose le langage

    *7 m15mm 0 & 1 & 2 & 3 & 4 & 5 & 6
    & & & & & &

    et on accède à l’intitulé du jour dans la case . Ce qui donne

    nomsJours {“lundi”, “mardi”, “mercredi”, “jeudi”, “vendredi”, “samedi”, “dimanche”} nomsJours[numéroJour-1]

  2. La seconde approche crée un tableau avec une case en plus et n’utilise pas la première.

    m2mm*7 m15mm 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7
    & & & & & & &

    L’algorithme devient

    nomsJours {“”, “lundi”, “mardi”, “mercredi”, “jeudi”, “vendredi”, “samedi”, “dimanche”} nomsJours[numéroJour]

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 donne le nombre de fois que la température 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 dans la case .

Lancers de dé Écrire un algorithme qui lance 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[modifier | modifier le wikicode]

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 :

  • inscrire un étudiant ;
  • vérifier si un étudiant est inscrit ;
  • désinscrire un étudiant (s’il change d’avis par exemple) ;
  • afficher la liste des inscrits.

Pour ce faire, on pourra stocker les numéros des étudiants inscrits dans un tableau [32]. Comme le tableau ne sera généralement pas rempli, on va gérer sa taille logique. On a donc deux variables :

  •  : le tableau des numéros d’étudiants
  •  : le nombre d’étudiants actuellement inscrits (la taille logique du tableau)

On va envisager deux cas :

  1. Les numéros d’étudiants seront placés dans le tableau sans ordre imposé.
  2. Les numéros d’étudiants seront placés dans l’ordre.

Données non triées[modifier | modifier le wikicode]

Dans cette approche, les valeurs sont stockées dans le tableau dans un ordre quelconque. Par exemple, on pourrait avoir la situation suivante :

=

*10| m1cm| 42010 & 41390 & 43342 & 42424 & ? & ? & ? & ? & …

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[modifier | modifier le wikicode]

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 :

=

*10| m1cm| 42010 & 41390 & 43342 & 42424 & 42123 & ? & ? & ? & …

L’algorithme est assez simple :

inscrits[nbInscrits] numéro nbInscrits nbInscrits + 1

Vérifier une inscription[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 [33]

=

*10| m1cm| 42010 & 42123 & 43342 & 42424 & 42123 & ? & ? & ? & …

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[modifier | modifier le wikicode]

É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[modifier | modifier le wikicode]

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 :

=

*10| m1cm| 41390 & 42010 & 42424 & 43342 & ? & ? & ? & ? & …

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[modifier | modifier le wikicode]

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 :

  • on trouve un dans la condition du tant que et pas un  ?
  • l’expression assignée à est composée de deux parties et utilise un = ?

Inscrire un étudiant[modifier | modifier le wikicode]

L’inscription d’un étudiant se fait en trois étapes :

  1. On recherche l’étudiant via l’algorithme qu’on vient de voir, ce qui nous donne la place où le placer.
  2. On libère la place pour l’y mettre. Comprenez-bien que cette opération n’est pas triviale. Si vous tenez des cartes en main, il est tout aussi facile d’y insérer une nouvelle carte à n’importe quelle position. Avec un tableau, il en va tout autrement ; pour insérer un élément à un endroit donné, il faut décaler tous les suivants d’une position sur la droite.
  3. On peut placer l’élément à la position libérée.

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[modifier | modifier le wikicode]

Cette opération est triviale.

rechercher( inscrits, nbInscrits, numéro, trouvé, pos ) pos -1

Désinscription[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

É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 ?[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 [34] ; 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.

*20 'm2.5mm & & & & & & & & & & & & & & & & & & &

|*20 m2.5mm| & 3 & 5 & 7 & 7 & 9 & 9 & 10 & 10 & 15 & 16 & 20 & 23 & 23 & 25 & 28 & 28 & 28 & 29 & 29

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.

*20 'm2.5mm & & & & & & & & & & & & & & & & & & &

|*20 m2.5mm| & 3 & 5 & 7 & 7 & 9 & 9 & 10 & 10 & 15 & 16 & 20 & 23 & 23 & 25 & 28 & 28 & 28 & 29 & 29

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].

*20 'm2.5mm & & & & & & & & & & & & & & & & & & &

|*20 m2.5mm| & 3 & 5 & 7 & 7 & 9 & 9 & 10 & 10 & 15 & 16 & 20 & 23 & 23 & 25 & 28 & 28 & 28 & 29 & 29

Troisième étape : , c’est-à-dire 11 où se trouve l’élément 20. La zone de recherche devient vaut 12 et vaut 13.

*20 'm2.5mm & & & & & & & & & & & & & & & & & & &

|*20 m2.5mm| & 3 & 5 & 7 & 7 & 9 & 9 & 10 & 10 & 15 & 16 & 20 & 23 & 23 & 25 & 28 & 28 & 28 & 29 & 29

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

*20 'm2.5mm & & & & & & & & & & & & & & & & & & &

|*20 m2.5mm| & 3 & 5 & 7 & 7 & 9 & 9 & 10 & 10 & 15 & 16 & 20 & 23 & 23 & 25 & 28 & 28 & 28 & 29 & 29

|*20 m2.5mm| & 3 & 5 & 7 & 7 & 9 & 9 & 10 & 10 & 15 & 16 & 20 & 23 & 23 & 25 & 28 & 28 & 28 & 29 & 29

|*20 m2.5mm| & 3 & 5 & 7 & 7 & 9 & 9 & 10 & 10 & 15 & 16 & 20 & 23 & 23 & 25 & 28 & 28 & 28 & 29 & 29

|*20 m2.5mm| & 3 & 5 & 7 & 7 & 9 & 9 & 10 & 10 & 15 & 16 & 20 & 23 & 23 & 25 & 28 & 28 & 28 & 29 & 29

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é[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 :

  • Il faut que les programmes soient exécutés dans des environnements strictement identiques ce qui n’est pas toujours le cas ou facile à vérifier.
  • Certains environnements peuvent être favorables à un algorithme par rapport à l’autre ce qui ne serait pas le cas d’un autre environnement. Par exemple, certaines architectures sont plus rapides dans les calculs entiers mais moins dans les calculs flottants.
  • Le test ne porte que sur un (voir quelques uns) jeu(x) de tests. Comment en tirer un enseignement général ? Que se passerait-il avec des données plus importantes ? Avec des données différentes ?

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é[modifier | modifier le wikicode]

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 , à 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 mais on peut dire, qu’en moyenne, cela entraine «  » 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 , on peut en déduire que le nombre de comparaisons est au maximum l’exposant qu’il faut donner à 2 pour obtenir , soit «  ».

Comparaisons

Voici un tableau comparatif du nombre de comparaisons en fonction de la taille

| m4.4300003cm | m0.507cm | m0.71900004cm | m0.93100005cm | m1.2479999cm | m1.4599999cm | m1.671cm| & 10 & 100 & 1000 & 10.000 & 100.000 & 1 million
recherche linéaire & 5 & 50 & 500 & 5.000 & 50.000 & 500.000
recherche 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 ou proportionnel à 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 (prononcé « grand de  »).

Pour la recherche dichotomique, la complexité est logarithmique, et on le note 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| & 10 & 100 & 1000 & & & &
& 1 & 1 & 1 & 1 & 1 & 1 & 1
& 4 & 7 & 10 & 14 & 17 & 20 & 30
& 10 & 100 & 1000 & & & &
& 100 & & & & &