ALGORITHMIQUEETPROGRAMMATION POURNONMATHEUX

COURSCOMPLETavecexercices,corrigsetcitationsphilosophiques

Christophe DarmangeatUniversit Paris 7 http://www.pise.info/algo/index.htm -2008-

L'ALGORITHMEPrambule : le Codage Pourquoi les ordinateurs sont-ils binaires ? La base dcimale La base binaire Le codage hexadcimal Introduction l'algorithmique Qu'est-ce que l'algomachin ? Faut-il tre matheux ?... L'ADN, les Shadoks et les ordinateurs Algorithmique et programmation Avec quelles conventions crit-on ? 1. Les Variables 1.1. A quoi servent les variables ? 1.2. Dclaration des variables 1.2.1 Types numriques classiques 1.2.2 Autres types numriques 1.2.3 Type alphanumrique 1.2.4 Type boolen 1.3. L'instruction d'affectation 1.3.1 Syntaxe et signification 1.3.2 Ordre des instructions Exercices Corrigs 8 8 10 12 15 18 18 19 20 21 22 23 23 24 24 26 26 27 28 28 30 32 35

2

1.4. Expressions et oprateurs 1.4.1 Oprateurs numriques : 1.4.2 Oprateur alphanumrique : & 1.4.3 Oprateurs logiques (ou boolens) : Exercices Corrigs 1.5. Deux remarques pour terminer 2. Lecture et Ecriture 2.1 De quoi parle-t-on ? 2.2 Les instructions de lecture-criture Exercices Corrigs 3. Les Tests 3.1 De quoi s'agit-il ? 3.2 Structure d'un test 3.3 Qu'est-ce qu'une condition ? Exercices Corrigs 3.4 Conditions composes Exercices Corrigs 3.5 Test imbriqus Exercices Corrigs 3.6 De l'aiguillage la gare de tri 3.7Variables boolennes 3

38 39 39 40 41 42 43 44 44 45 46 47 49 49 50 51 53 54 55 58 59 60 62 63 65 67

4. Encore de la Logique 4.1 Faut-il mettre un Et ? un OU ? Exercices Corrigs 4.2 Au del de la logique : le style Exercices Corrigs 5. Les Boucles 5.1 A quoi cela sert-il donc ? Exercices Corrigs 5.2 Boucler en comptant... 5.3 Des boucles dans des boucles 5.4 Et encore une btise ne pas faire ! Exercices Corrigs 6. Les Tableaux 6.1 Utilit des tableaux 6.2 Notation et utilisation algorithmique Exercices Corrigs 6.3 Tableaux dynamiques Exercices Corrigs

68 68 71 73 76 78 80 89 89 94 95 97 99 101 102 105 111 111 112 115 118 121 122 124

4

7. Techniques Ruses 7.1 Le tri par slection 7.2 Un exemple de flag 7.3 Le tri bulles 7.4 La recherche dichotomique Exercices Corrigs 8. Tableaux Multidimensionnels 8.1 Pourquoi plusieurs dimensions ? 8.2 Tableaux 2 dimensions Exercices Corrigs 8.3 Tableaux n dimensions 9. Fonctions Prdfinies 9.1 Structure gnrale des fonctions Exercices Corrigs 9.2 Les fonctions de texte Exercices Corrigs 9.3 Trois fonctions numriques classiques Exercices Corrigs 9.4 Les fonctions de conversion

129 129 131 135 137 139 141 146 146 147 149 152 159 160 160 162 163 164 166 168 172 174 177 181

5

10. Fichiers 10.1 Organisation des fichiers 10.2 Structure des enregistrements 10.3 Types d'accs 10.4 Instructions Exercices Corrigs 10.5 Stratgies de traitement 10.6 Donnes structures 10.6.1 Donnes structures simples 10.6.2 Tableaux de donnes structures 10.7 Rcapitulatif gnral Exercices Corrigs 11. Procdures et Fonctions 11.1 Fonctions personnalises 11.1.1 De quoi s'agit-il ? 11.1.2 Passage d'arguments 11.1.3 Deux mots sur l'analyse fonctionnelle Exercices Corrigs 11.2 Sous-procdures 11.2.1 Gnralits 11.2.2 Le problme des arguments 11.2.3 Comment a marche tout a ? 11.3 Variables publiques et prives 6

182 182 184 185 187 191 192 194 195 195 197 198 200 202 212 212 212 215 216 218 219 221 221 222 223 227

11.4 Peut-on tout faire ? 11.5 Algorithmes fonctionnels Corrigs 12. Notions Complmentaires 12.1 Programmation structure 12.2 Interprtation et compilation 12.3 La programmation rcursive Liens

228 229 236 242 242 244 245 248

7

Prambule : Le Codage Linformation nest pas le savoir. Le savoir nest pas la sagesse. La sagesse nest pas la beaut. La beaut nest pas lamour. Lamour nest pas la musique, et la musique, cest ce quil y a de mieux. - Frank Zappa Les ordinateurs sont comme les dieux de lAncien Testament : avec beaucoup de rgles, et sans piti. - Joseph Campbell Compter en octal, cest comme compter en dcimal, si on nutilise pas ses pouces - Tom Lehrer Il y a 10 sortes de gens au monde : ceux qui connaissent le binaire et les autres - Anonyme

Cest bien connu, les ordinateurs sont comme le gros rock qui tche : ils sont binaires. Mais ce qui est moins connu, cest ce que ce qualificatif de binaire recouvre exactement, et ce quil implique. Aussi, avant de nous plonger dans les arcanes de lalgorithmique proprement dite, ferons-nous un dtour par la notion de codage binaire. Contrairement aux apparences, nous ne sommes pas loigns de notre sujet principal. Tout au contraire, ce que nous allons voir prsent constitue un ensemble de notions indispensables lcriture de programmes. Car pour parler une machine, mieux vaut connatre son vocabulaire 1. Pourquoi les ordinateurs sont-ils binaires ? De nos jours, les ordinateurs sont ces machines merveilleuses capables de traiter du texte, dafficher des tableaux de matre, de jouer de la musique ou de projeter des vidos. On nen est pas encore tout fait HAL, lordinateur de 2001 Odysse de

lEspace, lintelligence si dveloppe quil a peur de mourir pardon, dtredbranch. Mais lordinateur parat tre une machine capable de tout faire. Pourtant, les ordinateurs ont beau sembler repousser toujours plus loin les limites de leur champ daction, il ne faut pas oublier quen ralit, ces fiers--bras ne sont toujours capables que dune seule chose : faire des calculs, et uniquement cela. Eh oui, ces gros malins dordinateurs sont rests au fond ce quils ont t depuis leur invention : de vulgaires calculatrices amliores !

8

Lorsquun ordinateur traite du texte, du son, de limage, de la vido, il traite en ralit des nombres. En fait, dire cela, cest dj lui faire trop dhonneur. Car mme le simple nombre 3 reste hors de porte de lintelligence dun ordinateur, ce qui le situe largement en dessous de lattachant chimpanz Bonobo, qui sait, entre autres choses, faire des blagues ses congnres et jouer au Pac-Man. Un ordinateur manipule exclusivement des informations binaires, dont on ne peut mme pas dire sans tre tendancieux quil sagit de nombres. Mais quest-ce quune information binaire ? Cest une information qui ne peut avoir que deux tats : par exemple, ouvert - ferm, libre occup, militaire civil, assis couch, blanc noir, vrai faux, etc. Si lon pense des dispositifs physiques permettant de stocker ce genre dinformation, on pourrait citer : charg non charg, haut bas, trou non trou. Je ne donne pas ces derniers exemples au hasard : ce sont prcisment ceux dont se sert un ordinateur pour stocker lensemble des informations quil va devoir manipuler. En deux mots, la mmoire vive (la RAM ) est forme de millions de composants lectroniques qui peuvent retenir ou relcher une charge lectrique. La surface dun disque dur, dune bande ou dune disquette est recouverte de particules mtalliques qui peuvent, grce un aimant, tre orientes dans un sens ou dans lautre. Et sur un CDROM, on trouve un long sillon troit irrgulirement perc de trous. Toutefois, la coutume veut quon symbolise une information binaire, quel que soit son support physique, sous la forme de 1 et de 0. Il faut bien comprendre que ce nest l quune reprsentation, une image commode, que lon utilise pour parler de toute information binaire. Dans la ralit physique, il ny a pas plus de 1 et de 0 qui se promnent dans les ordinateurs quil ny a crit, en lettres gantes, Ocan Atlantique sur la mer quelque part entre la Bretagne et les Antilles. Le 1 et le 0 dont parlent les informaticiens sont des signes, ni plus, ni moins, pour dsigner une information, indpendamment de son support physique. Les informaticiens seraient-ils des gens tordus, possdant un got immodr pour labstraction, ou pour les jeux intellectuels alambiqus ? Non, pas davantage en tout cas que le reste de leurs contemporains non-informaticiens. En fait, chacun dentre nous pratique ce genre dabstraction tous les jours, sans pour autant trouver cela bizarre ou difficile. Simplement, nous le faisons dans la vie quotidienne sans y penser. Et force de ne pas y penser, nous ne remarquons mme plus quel mcanisme subtil dabstraction est ncessaire pour pratiquer ce sport.

9

Lorsque nous disons que 4+3=7 (ce qui reste, normalement, dans le domaine de comptence mathmatique de tous ceux qui lisent ce cours !), nous manions de pures abstractions, reprsentes par de non moins purs symboles ! Un tre humain dil y a quelques millnaires se serait demand longtemps quest-ce que cest que quatre ou trois , sans savoir quatre ou trois quoi ? . Mine de rien, le fait mme de concevoir des nombres, cest--dire de pouvoir considrer, dans un ensemble, la quantit indpendamment de tout le reste, cest dj une abstraction trs hardie, qui a mis trs longtemps avant de simposer tous comme une vidence. Et le fait de faire des additions sans devoir prciser des additions de quoi ? , est un pas supplmentaire qui a t encore plus difficile franchir. Le concept de nombre, de quantit pure, a donc constitu un immense progrs (que les ordinateurs nont quant eux, je le rpte, toujours pas accompli). Mais si concevoir les nombres, cest bien, possder un systme de notation performant de ces nombres, cest encore mieux. Et l aussi, lhumanit a mis un certain temps (et essay un certain nombre de pistes qui se sont rvles tre des impasses) avant de parvenir au systme actuel, le plus rationnel. Ceux qui ne sont pas convaincus des progrs raliss en ce domaine peuvent toujours essayer de rsoudre une multiplication comme 587 x 644 en chiffres romains, on leur souhaite bon courage ! 2. La numrotation de position en base dcimale Lhumanit actuelle, pour reprsenter nimporte quel nombre, utilise un systme de numrotation de position, base dcimale. Quest-ce qui se cache derrire cet obscur jargon ? Commenons par la numrotation de position. Pour reprsenter un nombre, aussi grand soit-il, nous disposons dun alphabet spcialis : une srie de 10 signes qui sappellent les chiffres. Et lorsque nous crivons un nombre en mettant certains de ces chiffres les uns derrire les autres, lordre dans lequel nous mettons les chiffres est capital. Ainsi, par exemple, 2 569 nest pas du tout le mme nombre que 9 562. Et pourquoi ? Quel opration, quel dcodage mental effectuons-nous lorsque nous lisons une suite de chiffres reprsentant un nombre ? Le problme, cest que nous sommes tellement habitus faire ce dcodage de faon instinctive que gnralement nous nen connaissons plus les rgles. Mais ce nest pas trs compliqu de les reconstituer Et cest l que nous mettons le doigt en plein dans la deuxime caractristique de notre systme de notation numrique : son caractre dcimal.

10

Lorsque jcris 9562, de quel nombre est-ce que je parle ? Dcomposons la lecture chiffre par chiffre, de gauche droite : 9562, cest 9000 + 500 + 60 + 2. Allons plus loin, mme si cela parat un peu bbte : 9000, cest 9 x 1000, parce que le 9 est le quatrime chiffre en partant de la droite 500, cest 5 x 100, parce que le 5 est le troisime chiffre en partant de la droite 60, cest 6 x 10, parce que le 6 est le deuxime chiffre en partant de la droite 2, cest 2 x 1, parce que le 2 est le premier chiffre en partant de la droite On peut encore crire ce mme nombre dune manire lgrement diffrente. Au lieu de : 9 562 = 9 x 1 000 + 5 x 100 + 6 x 10 + 2, On crit que : 9 562 = (9 x 10 x 10 x 10) + (5 x 10 x 10) + (6 x 10) + (2) Arrivs ce stade de la comptition, je prie les allergiques de mexcuser, mais il nous faut employer un petit peu de jargon mathmatique. Ce nest pas grand-chose, et on touche au but. Alors, courage ! En fait, ce jargon se rsume au fait que les matheux notent la ligne ci-dessus laide du symbole de puissance . Cela donne : 9 562 = 9 x 103 + 5 x 102 + 6 x 101 + 2 x 100 Et voil, nous y sommes. Nous avons dgag le mcanisme gnral de la reprsentation par numrotation de position en base dcimale. Alors, nous en savons assez pour conclure sur les consquences du choix de la base dcimale. Il y en a deux, qui nen forment en fin de compte quune seule : parce que nous sommes en base dcimale, nous utilisons un alphabet numrique de dix symboles. Nous nous servons de dix chiffres, pas un de plus, pas un de moins. toujours parce nous sommes en base dcimale, la position dun de ces dix chiffres dans un nombre dsigne la puissance de dix par laquelle ce chiffre doit tre multipli pour reconstituer le nombre. Si je trouve un 7 en cinquime position partir de la droite, ce 7 ne reprsente pas 7 mais 7 fois 104, soit 70 000.

11

Un dernier mot concernant le choix de la base dix. Pourquoi celle-l et pas une autre ? Aprs tout, la base dix ntait pas le seul choix possible. Les babyloniens, qui furent de brillants mathmaticiens, avaient en leur temps adopt la base 60 (dite sexagsimale). Cette base 60 impliquait certes dutiliser un assez lourd alphabet numrique de 60 chiffres. Mais ctait somme toute un inconvnient mineur, et en retour, elle possdait certains avantages non ngligeables. 60 tant un nombre divisible par beaucoup dautres (cest pour cette raison quil avait t choisi), on pouvait, rien quen regardant le dernier chiffre, savoir si un nombre tait divisible par 2, 3, 4, 5, 6, 10, 12, 15, 20 et 30. Alors quen base 10, nous ne pouvons immdiatement rpondre la mme question que pour les diviseurs 2 et 5. La base sexagsimale a certes disparu en tant que systme de notation des nombres. Mais Babylone nous a laiss en hritage sa base sexagsimale dans la division du cercle en soixante parties (pour compter le temps en minutes et secondes), et celle en 6 x 60 parties (pour les degrs de la gomtrie et de lastronomie). Alors, pourquoi avons-nous adopt la base dcimale, moins pratique bien des gards ? Nul doute que cela tienne au dispositif matriel grce auquel tout tre humain normalement constitu stocke spontanment une information numrique : ses doigts ! Profitons-en pour remarquer que le professeur Shadoko avait invent exactement le mme systme, la seule diffrence tant qu'il avait choisi la base 4 (normal, les shadoks n'avaient que 4 mots). Regardez donc cette video - ou comment faire rigoler les gens en ne disant (presque) que des choses vraies : http://www.youtube.com/watch?v=X9l8u4SjRcI&eurl=http://aigespc57.cicrp.jussieu.fr/ algo/codage.htm&feature=player_embedded J'ajoute que c'est l'ensemble des videos des shadoks, et en particulier celles traitant de la logique et des mathmatiques, qui vaut son pesant de cacahutes interstellaires. Mais hlas cela nous loignerait un peu trop de notre propos (c'est pas grave, on y reviendra la prochaine pause). 3. La numrotation de position en base binaire Les ordinateurs, eux, comme on la vu, ont un dispositif physique fait pour stocker (de multiples faons) des informations binaires. Alors, lorsquon reprsente une information stocke par un ordinateur, le plus simple est dutiliser un systme de reprsentation deux chiffres : les fameux 0 et 1. Mais une fois de plus, je me permets dinsister, le choix du 0 et du 1 est une pure convention, et on aurait pu choisir nimporte quelle autre paire de symboles leur place.

12

Dans un ordinateur, le dispositif qui permet de stocker de linformation est donc rudimentaire, bien plus rudimentaire que les mains humaines. Avec des mains humaines, on peut coder dix choses diffrentes (en fait bien plus, si lon fait des acrobaties avec ses doigts, mais cartons ce cas). Avec un emplacement dinformation dordinateur, on est limit deux choses diffrentes seulement. Avec une telle information binaire, on ne va pas loin. Voil pourquoi, ds leur invention, les ordinateurs ont t conus pour manier ces informations par paquets de 0 et de 1. Et la taille de ces paquets a t fixe 8 informations binaires.

Une information binaire (symbolise couramment par 0 ou 1) sappelle un bit (en anglais... bit). Un groupe de huit bits sappelle un octet (en anglais, byte) Donc, mfiance avec le byte (en abrg, B majuscule), qui vaut un octet, c'est--dire huit bits (en abrg, b minuscule).Dans combien dtats diffrents un octet peut-il se trouver ? Le calcul est assez facile (mais il faut nanmoins savoir le refaire). Chaque bit de loctet peut occuper deux tats. Il y a donc dans un octet : 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 28 = 256 possibilits Cela signifie quun octet peut servir coder 256 nombres diffrents : ce peut tre la srie des nombres entiers de 1 256, ou de 0 255, ou de 127 +128. Cest une pure affaire de convention, de choix de codage. Mais ce qui nest pas affaire de choix, cest le nombre de possibilits : elles sont 256, pas une de plus, pas une de moins, cause de ce quest, par dfinition, un octet. Si lon veut coder des nombres plus grands que 256, ou des nombres ngatifs, ou des nombres dcimaux, on va donc tre contraint de mobiliser plus dun octet. Ce nest pas un problme, et cest trs souvent que les ordinateurs procdent ainsi. En effet, avec deux octets, on a 256 x 256 = 65 536 possibilits. En utilisant trois octets, on passe 256 x 256 x 256 = 16 777 216 possibilits. Et ainsi de suite, je ne mattarderai pas davantage sur les diffrentes manires de coder les nombres avec des octets. On abordera de nouveau brivement le sujet un peu plus loin. Cela implique galement quun octet peut servir coder autre chose quun nombre : loctet est trs souvent employ pour coder du texte. Il y a 26 lettres dans lalphabet. Mme en comptant diffremment les minuscules et les majuscules, et mme en y 13

ajoutant les chiffres et les signes de ponctuation, on arrive un total infrieur 256. Cela veut dire que pour coder convenablement un texte, le choix dun caractre par octet est un choix pertinent. Se pose alors le problme de savoir quel caractre doit tre reprsent par quel tat de loctet. Si ce choix tait librement laiss chaque informaticien, ou chaque fabricant dordinateur, la communication entre deux ordinateurs serait un vritable casse-tte. Loctet 10001001 serait par exemple traduit par une machine comme un T majuscule, et par une autre comme une parenthse fermante ! Aussi, il existe un standard international de codage des caractres et des signes de ponctuation. Ce standard stipule quel tat de loctet correspond quel signe du clavier. Il sappelle lASCII (pour

American Standard Code for Information Interchange). Et fort heureusement, lASCIIest un standard universellement reconnu et appliqu par les fabricants dordinateurs et de logiciels. Bien sr, se pose le problme des signes propres telle ou telle langue (comme les lettres accentues en franais, par exemple). LASCII a par le problme en rservant certains codes doctets pour ces caractres spciaux chaque langue. En ce qui concerne les langues utilisant un alphabet non latin, un standard particulier de codage a t mis au point. Quant aux langues non alphabtiques (comme le chinois), elles payent un lourd tribut linformatique pour navoir pas su voluer vers le systme alphabtique Revenons-en au codage des nombres sur un octet. Nous avons vu quun octet pouvait coder 256 nombres diffrents, par exemple (cest le choix le plus spontan) la srie des entiers de 0 255. Comment faire pour, partir dun octet, reconstituer le nombre dans la base dcimale qui nous est plus familire ? Ce nest pas sorcier ; il suffit dappliquer, si on les a bien compris, les principes de la numrotation de position, en gardant lesprit que l, la base nest pas dcimale, mais binaire. Prenons un octet au hasard : 11010011 D'aprs les principes vus plus haut, ce nombre reprsente en base dix, en partant de la gauche : 1 x 27 + 1 x 26 + 0 x 25 + 1 x 24 + 0 x 23 + 0 x 22 + 1 x 21 + 1 x 20 = 1 x 128 + 1 x 64 + 1 x 16 + 1 x 2 + 1 x 1 = 128 + 64 + 16 + 2 + 1 = 211 Et voil ! Ce nest pas plus compliqu que cela !

14

Inversement, comment traduire un nombre dcimal en codage binaire ? Il suffit de rechercher dans notre nombre les puissances successives de deux. Prenons, par exemple, 186. Dans 186, on trouve 1 x 128, soit 1 x 27. Je retranche 128 de 186 et jobtiens 58. Dans 58, on trouve 0 x 64, soit 0 x 26. Je ne retranche donc rien. Dans 58, on trouve 1 x 32, soit 1 x 25. Je retranche 32 de 58 et jobtiens 26. Dans 26, on trouve 1 x 16, soit 1 x 24. Je retranche 16 de 26 et jobtiens 10. Dans 10, on trouve 1 x 8, soit 1 x 23. Je retranche 8 de 10 et jobtiens 2. Dans 2, on trouve 0 x 4, soit 0 x 22. Je ne retranche donc rien. Dans 2, on trouve 1 x 2, soit 1 x 21. Je retranche 2 de 2 et jobtiens 0. Dans 0, on trouve 0 x 1, soit 0 x 20. Je ne retranche donc rien. Il ne me reste plus qu reporter ces diffrents rsultats (dans lordre !) pour reconstituer loctet. Jcris alors quen binaire, 186 est reprsent par : 10111010 Cest bon ? Alors on passe la suite. 4. Le codage hexadcimal Pour en finir avec ce prambule (sinon, cela deviendrait de la gourmandise) , on va voquer un dernier type de codage, qui constitue une alternative pratique au codage binaire. Il sagit du codage hexadcimal, autrement dit en base seize. Pourquoi ce choix bizarre ? Tout dabord, parce que le codage binaire, ce nest tout de mme pas trs conomique, ni trs lisible. Pas trs conomique : pour reprsenter un nombre entre 1 et 256, il faut utiliser systmatiquement huit chiffres. Pas trs lisible : parce que dinterminables suites de 1 et de 0, on a dj vu plus folichon. Alors, une alternative toute naturelle, ctait de reprsenter loctet non comme huit bits (ce que nous avons fait jusque l), mais comme deux paquets de 4 bits (les quatre de gauche, et les quatre de droite). Voyons voir cela de plus prs. Avec 4 bits, nous pouvons coder 2 x 2 x 2 x 2 = 16 nombres diffrents. En base seize, 16 nombres diffrents se reprsentent avec un seul chiffre (de mme quen base 10, dix nombres se reprsentent avec un seul chiffre). Quels symboles choisir pour les chiffres ? Pour les dix premiers, on na pas t chercher bien loin : on a recycl les dix chiffres de la base dcimale. Les dix premiers nombres de 15

la base seize scrivent donc tout btement 0, 1, 2, 3, 4, 5, 6, 7, 8, et 9. L, il nous manque encore 6 chiffres, pour reprsenter les nombres que nous crivons en dcimal 10, 11, 12, 13, 14, 15 et 16. Plutt quinventer de nouveaux symboles (ce quon aurait trs bien pu faire), on a recycl les premires lettres de lalphabet. Ainsi, par convention, A vaut 10, B vaut 11, etc. jusqu F qui vaut 15. Or, on saperoit que cette base hexadcimale permet une reprsentation trs simple des octets du binaire. Prenons un octet au hasard : 10011110 Pour convertir ce nombre en hexadcimal, il y a deux mthodes : lune consiste faire un grand dtour, en repassant par la base dcimale. Cest un peu plus long, mais on y arrive. Lautre mthode consiste faire le voyage direct du binaire vers lhexadcimal. Avec lhabitude, cest nettement plus rapide !

Premire mthode :On retombe sur un raisonnement dj abord. Cet octet reprsente en base dix : 1 x 27 + 0 x 26 + 0 x 25 + 1 x 24 + 1 x 23 + 1 x 22 + 1 x 21 + 0 x 20 = 1 x 128 + 1 x 16 + 1 x 8 + 1 x 4 + 1 x 2 + 0 x 1 = 128 + 16 + 8 + 4 + 2 = 158 De l, il faut repartir vers la base hexadcimale. Dans 158, on trouve 9 x 16, cest--dire 9 x 161. Je retranche 144 de 158 et jobtiens 14. Dans 14, on trouve 14 x 1, cest--dire 14 x 160. On y est. Le nombre scrit donc en hexadcimal : 9E

Deuxime mthode :Divisons 1 0 0 1 1 1 1 0 en 1 0 0 1 (partie gauche) et 1 1 1 0 (partie droite). 1 0 0 1, cest 8 + 1, donc 9 1 1 1 0, cest 8 + 4 + 2 donc 14 Le nombre scrit donc en hexadcimal : 9E. Cest la mme conclusion quavec la premire mthode. Encore heureux !

16

Le codage hexadcimal est trs souvent utilis quand on a besoin de reprsenter les octets individuellement, car dans ce codage, tout octet correspond seulement deux signes. Allez, assez bavard, on passe aux choses srieuses : les arcanes de lalgorithmique

17

Introduction a lAlgorithmique Un langage de programmation est une convention pour donner des ordres un ordinateur. Ce nest pas cens tre obscur, bizarre et plein de piges subtils. Ca, ce sont les caractristiques de la magie. - Dave Small C'est illogique, Capitaine - Mr Spock

Lalgorithmique est un terme dorigine arabe, comme algbre, amiral ou znith. Ce nest pas une excuse pour massacrer son orthographe, ou sa prononciation. Ainsi, lalgo nest pas rythmique , la diffrence du bon rockn roll. Lalgo nest pas non plus lagglo . Alors, ne confondez pas lalgorithmique avec lagglo rythmique, qui consiste poser des parpaings en cadence. 1. Quest-ce que lalgomachin ? Avez-vous dj ouvert un livre de recettes de cuisine ? Avez vous dj dchiffr un mode demploi traduit directement du coren pour faire fonctionner un magntoscope ou un rpondeur tlphonique rticent ? Si oui, sans le savoir, vous avez dj excut des algorithmes. Plus fort : avez-vous dj indiqu un chemin un touriste gar ? Avez vous fait chercher un objet quelquun par tlphone ? Ecrit une lettre anonyme stipulant comment procder une remise de ranon ? Si oui, vous avez dj fabriqu et fait excuter des algorithmes. Comme quoi, lalgorithmique nest pas un savoir sotrique rserv quelques rares initis touchs par la grce divine, mais une aptitude partage par la totalit de lhumanit. Donc, pas dexcuses

Un algorithme, cest une suite dinstructions, qui une fois excute correctement, conduit un rsultat donn. Si lalgorithme est juste, le rsultat est le rsultat voulu,et le touriste se retrouve l o il voulait aller. Si lalgorithme est faux, le rsultat est, disons, alatoire, et dcidment, cette saloperie de rpondeur ne veut rien savoir. Compltons toutefois cette dfinition. Aprs tout, en effet, si lalgorithme, comme on vient de le dire, nest quune suite dinstructions menant celui qui lexcute rsoudre un problme, pourquoi ne pas donner comme instruction unique : rsous le problme , et 18

laisser linterlocuteur se dbrouiller avec a ? A ce tarif, nimporte qui serait champion dalgorithmique sans faire aucun effort. Pas de a Lisette, ce serait trop facile. Le malheur (ou le bonheur, tout dpend du point de vue) est que justement, si le touriste vous demande son chemin, cest quil ne le connat pas. Donc, si on nest pas un goujat intgral, il ne sert rien de lui dire de le trouver tout seul. De mme les modes demploi contiennent gnralement (mais pas toujours) un peu plus dinformations que dbrouillez vous pour que a marche . Pour fonctionner, un algorithme doit donc contenir uniquement des instructions

comprhensibles par celui qui devra lexcuter. Cest dailleurs lun des points dlicatspour les rdacteurs de modes demploi : les rfrences culturelles, ou lexicales, des utilisateurs, tant variables, un mme mode demploi peut tre trs clair pour certains et parfaitement abscons pour dautres. En informatique, heureusement, il ny a pas ce problme : les choses auxquelles ont doit donner des instructions sont les ordinateurs, et ceux-ci ont le bon got dtre tous strictement aussi idiots les uns que les autres. 2. Faut-il tre matheux pour tre bon en algorithmique ? Je consacre quelques lignes cette question, car cette opinion aussi fortement affirme que faiblement fonde sert rgulirement dexcuse : moi, de toute faon, je suis mauvais(e) en algo, jai jamais rien pig aux maths . Faut-il tre bon en maths pour expliquer correctement son chemin quelquun ? Je vous laisse juge. La matrise de lalgorithmique requiert deux qualits, trs complmentaires dailleurs : il faut avoir une certaine intuition, car aucune recette ne permet de savoir a priori quelles instructions permettront dobtenir le rsultat voulu. Cest l, si lon y tient, quintervient la forme dintelligence requise pour lalgorithmique. Alors, cest certain, il y a des gens qui possdent au dpart davantage cette intuition que les autres. Cependant, et jinsiste sur ce point, les rflexes, cela sacquiert. Et ce quon appelle lintuition nest finalement que de lexprience tellement rpte que le raisonnement, au dpart laborieux, finit par devenir spontan .

19

il faut tre mthodique et rigoureux. En effet, chaque fois quon crit une srie dinstructions quon croit justes, il faut systmatiquement se mettre mentalement la place de la machine qui va les excuter, arm d'un papier et d'un crayon, afin de vrifier si le rsultat obtenu est bien celui que lon voulait. Cette opration ne requiert pas la moindre once dintelligence. Mais elle reste nanmoins indispensable, si lon ne veut pas crire laveuglette. Et petit petit, force de pratique, vous verrez que vous pourrez faire de plus en plus souvent lconomie de cette dernire tape : lexprience fera que vous verrez le rsultat produit par vos instructions, au fur et mesure que vous les crirez. Naturellement, cet apprentissage est long, et demande des heures de travail patient. Aussi, dans un premier temps, vitez de sauter les tapes : la vrification mthodique,

pas pas, de chacun de vos algorithmes reprsente plus de la moiti du travail accomplir... et le gage de vos progrs.3. LADN, les Shadoks, et les ordinateurs Quel rapport me direz-vous ? Eh bien le point commun est : quatre mots de vocabulaire. Lunivers lexical Shadok, cest bien connu, se limite aux termes Ga , Bu , Zo , et Meu . Ce qui leur a tout de mme permis de formuler quelques fortes maximes, telles que : Mieux vaut pomper et quil ne se passe rien, plutt quarrter de pomper et

risquer quil se passe quelque chose de pire (pour dautres fortes maximes Shadok,nhsitez pas visiter leur site Internet, il y en a toute une collection qui vaut le dtour). LADN, qui est en quelque sorte le programme gntique, lalgorithme la base de construction des tres vivants, est une chane construite partir de quatre lments invariables. Ce nest que le nombre de ces lments, ainsi que lordre dans lequel ils sont arrangs, qui vont dterminer si on obtient une puce ou un lphant. Et tous autant que nous sommes, splendides russites de la Nature, avons t construits par un programme constitu uniquement de ces quatre briques, ce qui devrait nous inciter la modestie.

20

Enfin, les ordinateurs, quels quils soient, ne sont fondamentalement capables de comprendre que quatre catgories d'ordres (en programmation, on n'emploiera pas le terme d'ordre, mais plutt celui d'instructions). Ces quatre familles d'instructions sont : laffectation de variables la lecture / criture les tests les boucles Un algorithme informatique se ramne donc toujours au bout du compte la combinaison de ces quatre petites briques de base. Il peut y en avoir quelques unes, quelques dizaines, et jusqu plusieurs centaines de milliers dans certains programmes de gestion. Rassurez-vous, dans le cadre de ce cours, nous nirons pas jusque l (cependant, la taille dun algorithme ne conditionne pas en soi sa complexit : de longs algorithmes peuvent tre finalement assez simples, et de petits trs compliqus). 4. Algorithmique et programmation Pourquoi apprendre lalgorithmique pour apprendre programmer ? En quoi a-t-on besoin dun langage spcial, distinct des langages de programmation comprhensibles par les ordinateurs ? Parce que lalgorithmique exprime les instructions rsolvant un problme donn

indpendamment des particularits de tel ou tel langage. Pour prendre une image, siun programme tait une dissertation, lalgorithmique serait le plan, une fois mis de ct la rdaction et lorthographe. Or, vous savez quil vaut mieux faire dabord le plan et rdiger ensuite que linverse Apprendre lalgorithmique, cest apprendre manier la structure logique dun programme informatique. Cette dimension est prsente quelle que soit le langage de programmation ; mais lorsquon programme dans un langage (en C, en Visual Basic, etc.) on doit en plus se colleter les problmes de syntaxe, ou de types dinstructions, propres ce langage. Apprendre lalgorithmique de manire spare, cest donc srier les difficults pour mieux les vaincre. A cela, il faut ajouter que des gnrations de programmeurs, souvent autodidactes (mais pas toujours, hlas !), ayant directement appris programmer dans tel ou tel langage, ne font pas mentalement clairement la diffrence entre ce qui relve de la structure logique gnrale de toute programmation (les rgles fondamentales de lalgorithmique) 21

et ce qui relve du langage particulier quils ont appris. Ces programmeurs, non seulement ont beaucoup plus de mal passer ensuite un langage diffrent, mais encore crivent bien souvent des programmes qui mme sils sont justes, restent laborieux. Car on nignore pas impunment les rgles fondamentales de lalgorithmique Alors, autant lapprendre en tant que telle ! Bon, maintenant que jai bien fait larticle pour vendre ma marchandise, on va presque pouvoir passer au vif du sujet 5. Avec quelles conventions crit-on un algorithme ? Historiquement, plusieurs types de notations ont reprsent des algorithmes. Il y a eu notamment une reprsentation graphique, avec des carrs, des losanges, etc. quon appelait des organigrammes. Aujourdhui, cette reprsentation est quasiment abandonne, pour deux raisons. Dabord, parce que ds que lalgorithme commence grossir un peu, ce nest plus pratique du tout du tout. Ensuite parce que cette reprsentation favorise le glissement vers un certain type de programmation, dite non structure (nous dfinirons ce terme plus tard), que lon tente au contraire dviter. Cest pourquoi on utilise gnralement une srie de conventions appele pseudocode , qui ressemble un langage de programmation authentique dont on aurait vacu la plupart des problmes de syntaxe. Ce pseudo-code est susceptible de varier lgrement dun livre (ou dun enseignant) un autre. Cest bien normal : le pseudo-code, encore une fois, est purement conventionnel ; aucune machine nest cense le reconnatre. Donc, chaque cuisinier peut faire sa sauce sa guise, avec ses petites pices bien lui, sans que cela prte consquence. Comme je nai pas moins de petites manies que la majorit de mes semblables, le pseudocode que vous dcouvrirez dans les pages qui suivent possde quelques spcificits mineures qui ne doivent qu mes nvroses personnelles. Rassurez-vous cependant, celles-ci restent dans les limites tout fait acceptables. En tout cas, personnellement, je les accepte trs bien.

22

Partie 1 Les Variables Nattribuez Bonaparte A lorigine de toute erreur attribue lordinateur, vous trouverez au moins deux erreurs humaines. Dont celle consistant attribuer lerreur lordinateur. - Anonyme jamais la malveillance ce qui sexplique trs bien par lincomptence. - Napolon

1.1 A quoi servent les variables ?Dans un programme informatique, on va avoir en permanence besoin de stocker provisoirement des valeurs. Il peut sagir de donnes issues du disque dur, fournies par lutilisateur (frappes au clavier), ou que sais-je encore. Il peut aussi sagir de rsultats obtenus par le programme, intermdiaires ou dfinitifs. Ces donnes peuvent tre de plusieurs types (on en reparlera) : elles peuvent tre des nombres, du texte, etc. Toujours est-il que ds que lon a besoin de stocker une information au cours dun programme, on utilise une variable. Pour employer une image, une variable est une bote, que le programme (lordinateur) va reprer par une tiquette. Pour avoir accs au contenu de la bote, il suffit de la dsigner par son tiquette. En ralit, dans la mmoire vive de lordinateur, il ny a bien sr pas une vraie bote, et pas davantage de vraie tiquette colle dessus (javais bien prvenu que la bote et ltiquette, ctait une image). Dans lordinateur, physiquement, il y a un emplacement de mmoire, repr par une adresse binaire. Si on programmait dans un langage directement comprhensible par la machine, on devrait se fader de dsigner nos donnes par de superbes 10011001 et autres 01001001 (enchant !). Mauvaise nouvelle : de tels langages existent ! Ils portent le doux nom dassembleur. Bonne nouvelle : ce ne sont pas les seuls langages disponibles. Les langages informatiques plus volus (ce sont ceux que presque tout le monde emploie) se chargent prcisment, entre autres rles, dpargner au programmeur la gestion fastidieuse des emplacements mmoire et de leurs adresses. Et, comme vous commencez le comprendre, il est beaucoup plus facile demployer les tiquettes de son choix, que de devoir manier des adresses binaires. 23

1.2 Dclaration des variablesLa premire chose faire avant de pouvoir utiliser une variable est de crer la bote et

de lui coller une tiquette. Ceci se fait tout au dbut de lalgorithme, avant mme lesinstructions proprement dites. Cest ce quon appelle la dclaration des variables. Cest un genre de dclaration certes moins romantique quune dclaration damour, mais dun autre ct moins dsagrable quune dclaration dimpts. Le nom de la variable (ltiquette de la bote) obit des impratifs changeant selon les langages. Toutefois, une rgle absolue est quun nom de variable peut comporter des lettres et des chiffres, mais quil exclut la plupart des signes de ponctuation, en particulier les espaces. Un nom de variable correct commence galement imprativement par une lettre. Quant au nombre maximal de signes pour un nom de variable, il dpend du langage utilis. En pseudo-code algorithmique, on est bien sr libre du nombre de signes pour un nom de variable, mme si pour des raisons purement pratiques, et au grand dsespoir de Stphane Bern, on vite gnralement les noms rallonge. Lorsquon dclare une variable, il ne suffit pas de crer une bote (rserver un emplacement mmoire) ; encore doit-on prciser ce que lon voudra mettre dedans, car de cela dpendent la taille de la bote (de lemplacement mmoire) et le type de codage utilis.

1.2.1 Types numriques classiquesCommenons par le cas trs frquent, celui dune variable destine recevoir des nombres. Si lon rserve un octet pour coder un nombre, je rappelle pour ceux qui dormaient en lisant le chapitre prcdent quon ne pourra coder que 28 = 256 valeurs diffrentes. Cela peut signifier par exemple les nombres entiers de 1 256, ou de 0 255, ou de 127 +128 Si lon rserve deux octets, on a droit 65 536 valeurs ; avec trois octets, 16 777 216, etc. Et l se pose un autre problme : ce codage doit-il reprsenter des nombres dcimaux ? des nombres ngatifs ? Bref, le type de codage (autrement dit, le type de variable) choisi pour un nombre va dterminer : les valeurs maximales et minimales des nombres pouvant tre stocks dans la variable la prcision de ces nombres (dans le cas de nombres dcimaux).

24

Tous les langages, quels quils soient offrent un bouquet de types numriques, dont le dtail est susceptible de varier lgrement dun langage lautre. Grosso modo, on retrouve cependant les types suivants : Type Numrique Byte (octet) Entier simple Entier long Rel simple Plage 0 255 -32 768 32 767 -2 147 483 648 2 147 483 647 -3,40x1038 1,40x10-45

-1,40x104538

pour

les

valeurs

ngatives

3,40x10

pour les valeurs positives pour les valeurs ngatives

Rel double

1,79x10308

-4,94x10-324

4,94x10-324 1,79x10308 pour les valeurs positives

Pourquoi ne pas dclarer toutes les variables numriques en rel double, histoire de btonner et dtre certain quil ny aura pas de problme ? En vertu du principe de lconomie de moyens. Un bon algorithme ne se contente pas de marcher ; il marche en vitant de gaspiller les ressources de la machine. Sur certains programmes de grande taille, labus de variables surdimensionnes peut entraner des ralentissements notables lexcution, voire un plantage pur et simple de lordinateur. Alors, autant prendre ds le dbut de bonnes habitudes dhygine. En algorithmique, on ne se tracassera pas trop avec les sous-types de variables numriques (sachant qu'on aura toujours assez de soucis comme a, allez). On se contentera donc de prciser qu'il s'agit d'un nombre, en gardant en tte que dans un vrai langage, il faudra tre plus prcis.

En pseudo-code, une dclaration de variables aura ainsi cette tte :Variable g en Numrique ou encore Variables PrixHT, TauxTVA, PrixTTC en Numrique

25

1.2.2 Autres types numriquesCertains langages autorisent dautres types numriques, notamment : le type montaire (avec strictement deux chiffres aprs la virgule) le type date (jour/mois/anne). Nous nemploierons pas ces types dans ce cours ; mais je les signale, car vous ne manquerez pas de les rencontrer en programmation proprement dite.

1.2.3 Type alphanumriqueFort heureusement, les botes que sont les variables peuvent contenir bien dautres informations que des nombres. Sans cela, on serait un peu embt ds que lon devrait stocker un nom de famille, par exemple. On dispose donc galement du type alphanumrique (galement appel type caractre,

type chane ou en anglais, le type string mais ne fantasmez pas trop vite, les string,cest loin dtre aussi excitant que le nom le suggre. Une tudiante qui se reconnatra si elle lit ces lignes a d'ailleurs mis le doigt - si j'ose m'exprimer ainsi - sur le fait qu'il en va de mme en ce qui concerne les bytes). Dans une variable de ce type, on stocke des caractres, quil sagisse de lettres, de signes de ponctuation, despaces, ou mme de chiffres. Le nombre maximal de caractres pouvant tre stocks dans une seule variable string dpend du langage utilis. Un groupe de caractres (y compris un groupe de un, ou de zro caractres), quil soit ou non stock dans une variable, dailleurs, est donc souvent appel chane de caractres.

En pseudo-code, une chane de caractres est toujours note entre guillemetsPourquoi diable ? Pour viter deux sources principales de possibles confusions : la confusion entre des nombres et des suites de chiffres. Par exemple, 423 peut reprsenter le nombre 423 (quatre cent vingt-trois), ou la suite de caractres 4, 2, et 3. Et ce nest pas du tout la mme chose ! Avec le premier, on peut faire des calculs, avec le second, point du tout. Ds lors, les guillemets permettent dviter toute ambigut : sil ny en a pas, 423 est quatre cent vingt trois. Sil y en a, "423" reprsente la suite des chiffres 4, 2, 3.

26

Mais ce n'est pas le pire. L'autre confusion, bien plus grave - et bien plus frquente consiste se mlanger les pinceaux entre le nom d'une variable et son contenu. Pour parler simplement, cela consiste confondre l'tiquette d'une bote et ce qu'il y a l'intrieur On reviendra sur ce point crucial dans quelques instants.

1.2.4 Type boolenLe dernier type de variables est le type boolen : on y stocke uniquement les valeurs logiques VRAI et FAUX. On peut reprsenter ces notions abstraites de VRAI et de FAUX par tout ce qu'on veut : de l'anglais (TRUE et FALSE) ou des nombres (0 et 1). Peu importe. Ce qui compte, c'est de comprendre que le type boolen est trs conomique en termes de place mmoire occupe, puisque pour stocker une telle information binaire, un seul bit suffit. Le type boolen est trs souvent nglig par les

programmeurs, tort. Il est vrai qu'il n'est pas proprement parler indispensable, et qu'on pourrait crire peu prs nimporte quel programme en l'ignorant compltement. Pourtant, si le type boolen est mis disposition des programmeurs dans tous les langages, ce n'est pas pour rien. Le recours aux variables boolennes s'avre trs souvent un puissant instrument de lisibilit des algorithmes : il peut faciliter la vie de celui qui crit l'algorithme, comme de celui qui le relit pour le corriger. Alors, maintenant, c'est certain, en algorithmique, il y a une question de style : c'est exactement comme dans le langage courant, il y a plusieurs manires de s'exprimer pour dire sur le fond la mme chose. Nous verrons plus loin diffrents exemples de variations stylistiques autour d'une mme solution. En attendant, vous tes prvenus : l'auteur de ce cours est un adepte fervent (mais pas irraisonn) de l'utilisation des variables boolennes.

27

1.3 Linstruction daffectation1.3.1 Syntaxe et significationOuf, aprs tout ce baratin prliminaire, on aborde enfin nos premires vritables manipulations dalgorithmique. Pas trop tt, certes, mais pas moyen de faire autrement ! En fait, la variable (la bote) n'est pas un outil bien sorcier manipuler. A la diffrence du couteau suisse ou du superbe robot mnager vendu sur Tl Boutique Achat, on ne peut pas faire trente-six mille choses avec une variable, mais seulement une et une seule. Cette seule chose quon puisse faire avec une variable, cest laffecter, cest--dire lui attribuer une valeur. Pour poursuivre la superbe mtaphore file dj employe, on peut remplir la bote.

En pseudo-code, l'instruction d'affectation se note avec le signe Ainsi : Toto 24 Attribue la valeur 24 la variable Toto. Ceci, soit dit en passant, sous-entend imprativement que Toto soit une variable de type numrique. Si Toto a t dfini dans un autre type, il faut bien comprendre que cette instruction provoquera une erreur. Cest un peu comme si, en donnant un ordre quelquun, on accolait un verbe et un complment incompatibles, du genre Epluchez la casserole . Mme dote de la meilleure volont du monde, la mnagre lisant cette phrase ne pourrait quinterrompre dubitativement sa tche. Alors, un ordinateur, vous pensez bien On peut en revanche sans aucun problme attribuer une variable la valeur dune autre variable, telle quelle ou modifie. Par exemple : Tutu Toto Signifie que la valeur de Tutu est maintenant celle de Toto.

28

Notez bien que cette instruction na en rien modifi la valeur de Toto : une instruction daffectation ne modifie que ce qui est situ gauche de la flche. Tutu Toto + 4 Si Toto contenait 12, Tutu vaut maintenant 16. De mme que prcdemment, Toto vaut toujours 12. Tutu Tutu + 1 Si Tutu valait 6, il vaut maintenant 7. La valeur de Tutu est modifie, puisque Tutu est la variable situe gauche de la flche. Pour revenir prsent sur le rle des guillemets dans les chanes de caractres et sur la confusion numro 2 signale plus haut, comparons maintenant deux algorithmes suivants : Exemple n1 Dbut Riri "Loulou" Fifi "Riri" Fin Exemple n2 Dbut Riri "Loulou" Fifi Riri Fin La seule diffrence entre les deux algorithmes consiste dans la prsence ou dans labsence des guillemets lors de la seconde affectation. Et l'on voit que cela change tout ! Dans l'exemple n1, ce que l'on affecte la variable Fifi, c'est la suite de caractres R i r - i. Et la fin de lalgorithme, le contenu de la variable Fifi est donc Riri . Dans l'exemple n2, en revanche, Riri tant dpourvu de guillemets, n'est pas considr comme une suite de caractres, mais comme un nom de variable. Le sens de la ligne devient donc : affecte la variable Fifi le contenu de la variable Riri . A la fin de lalgorithme n2, la valeur de la variable Fifi est donc Loulou . Ici, loubli des guillemets conduit certes un rsultat, mais un rsultat diffrent. A noter, car cest un cas trs frquent, que gnralement, lorsquon oublie les guillemets lors dune affectation de chane, ce qui se trouve droite du signe daffectation ne 29

correspond aucune variable prcdemment dclare et affecte. Dans ce cas, loubli des guillemets se solde immdiatement par une erreur dexcution. Ceci est une simple illustration. Mais elle rsume lensemble des problmes qui surviennent lorsquon oublie la rgle des guillemets aux chanes de caractres.

1.3.2 Ordre des instructionsIl va de soi que lordre dans lequel les instructions sont crites va jouer un rle essentiel dans le rsultat final. Considrons les deux algorithmes suivants : Exemple 1 Variable A en Numrique Dbut A 34 A 12 Fin Exemple 2 Variable A en Numrique Dbut A 12 A 34 Fin Il est clair que dans le premier cas la valeur finale de A est 12, dans lautre elle est 34 . Il est tout aussi clair que ceci ne doit pas nous tonner. Lorsquon indique le chemin quelquun, dire prenez tout droit sur 1km, puis droite nenvoie pas les gens au mme endroit que si lon dit prenez droite puis tout droit pendant 1 km . Enfin, il est galement clair que si lon met de ct leur vertu pdagogique, les deux algorithmes ci-dessus sont parfaitement idiots ; tout le moins ils contiennent une incohrence. Il ny a aucun intrt affecter une variable pour laffecter diffremment juste aprs. En loccurrence, on aurait tout aussi bien atteint le mme rsultat en crivant simplement :

30

Exemple 1 Variable A en Numrique Dbut A 12 Fin Exemple 2 Variable A en Numrique Dbut A 34 Fin Tous les lments sont maintenant en votre possession pour que ce soit vous de jouer !

31

PARTIE 1nonc des Exercices Exercice 1.1Quelles seront les valeurs des variables A et B aprs excution des instructions suivantes ? Variables A, B en Entier Dbut A1 BA+3 A3 Fin

Exercice 1.2Quelles seront les valeurs des variables A, B et C aprs excution des instructions suivantes ? Variables A, B, C en Entier Dbut A5 B3 CA+B A2 CBA Fin

32

Exercice 1.3Quelles seront les valeurs des variables A et B aprs excution des instructions suivantes ? Variables A, B en Entier Dbut A5 BA+4 AA+1 BA4 Fin

Exercice 1.4Quelles seront les valeurs des variables A, B et C aprs excution des instructions suivantes ? Variables A, B, C en Entier Dbut A3 B 10 CA+B BA+B AC Fin

33

Exercice 1.5Quelles seront les valeurs des variables A et B aprs excution des instructions suivantes ? Variables A, B en Entier Dbut A5 B2 AB BA Fin Moralit : les deux dernires instructions permettent-elles dchanger les deux valeurs de B et A ? Si lon inverse les deux dernires instructions, cela change-t-il quelque chose ?

Exercice 1.6Plus difficile, mais cest un classique absolu, quil faut absolument matriser : crire un algorithme permettant dchanger les valeurs de deux variables A et B, et ce quel que soit leur contenu pralable.

Exercice 1.7Une variante du prcdent : on dispose de trois variables A, B et C. Ecrivez un algorithme transfrant B la valeur de A, C la valeur de B et A la valeur de C (toujours quels que soient les contenus pralables de ces variables).

34

PARTIE 1Corrigs des Exercices Exercice 1.1Aprs A1 BA+3 A3 La valeur des variables est : A=1 A=1 A = 3 B=? B=4 B = 4

Exercice 1.2Aprs A5 B3 CA+B A2 CBA La valeur des variables est : A=5 A=5 A=5 A=2 A = 2 B=? B=3 B=3 B=3 B = 3 C=? C=? C=8 C=8 C = 1

Exercice 1.3Aprs A5 BA+4 AA+1 BA4 La valeur des variables est : A=5 A=5 A=6 A = 6 B=? B=9 B=9 B = 2

35

Exercice 1.4Aprs A3 B 10 CA+B BA+B AC La valeur des variables est : A=3 A=3 A=3 A=3 A = 13 B=? B = 10 B = 10 B = 13 B = 13 C=? C=? C = 13 C = 13 C = 13

Exercice 1.5Aprs A5 B2 AB BA La valeur des variables est : A=5 A=5 A=2 A = 2 B=? B=2 B=2 B = 2

Les deux dernires instructions ne permettent donc pas dchanger les deux valeurs de B et A, puisque lune des deux valeurs (celle de A) est ici crase. Si lon inverse les deux dernires instructions, cela ne changera rien du tout, hormis le fait que cette fois cest la valeur de B qui sera crase.

Exercice 1.6Dbut CA AB BC Fin On est oblig de passer par une variable dite temporaire (la variable C).

36

Exercice 1.7Dbut DC CB BA AD Fin En fait, quel que soit le nombre de variables, une seule variable temporaire suffit

37

1.4 Expressions et oprateursSi on fait le point, on saperoit que dans une instruction daffectation, on trouve :

gauche de la flche, un nom de variable, et uniquement cela. En ce monde empli de doutes quest celui de lalgorithmique, cest une des rares rgles dor qui marche tous les coups : si on voit gauche dune flche daffectation autre chose quun nom de variable, on peut tre certain 100% quil sagit dune erreur.

droite de la flche, ce quon appelle une expression. Voil encore un mot qui est trompeur ; en effet, ce mot existe dans le langage courant, o il revt bien des significations. Mais en informatique, le terme dexpression ne dsigne quune seule chose, et qui plus est une chose trs prcise :

Une expression est un ensemble de valeurs, relies par des oprateurs, et quivalent une seule valeurCette dfinition vous parat peut-tre obscure. Mais rflchissez-y quelques minutes, et vous verrez quelle recouvre quelque chose dassez simple sur le fond. Par exemple, voyons quelques expressions de type numrique. Ainsi : 7 5+4 123-45+844 Toto-12+5-Riri sont toutes des expressions valides, pour peu que Toto et Riri soient bien des nombres. Car dans le cas contraire, la quatrime expression na pas de sens. En loccurrence, les oprateurs que jai employs sont laddition (+) et la soustraction (-). Revenons pour le moment sur laffectation. Une condition supplmentaire (en plus des deux prcdentes) de validit dune instruction daffectation est que :

lexpression situe droite de la flche soit du mme type que la variable situe gauche. Cest trs logique : on ne peut pas ranger convenablement des outils dans un sac provision, ni des lgumes dans une trousse outils sauf provoquer un rsultat catastrophique.

Si lun des trois points numrs ci-dessus nest pas respect, la machine sera incapable dexcuter laffectation, et dclenchera une erreur (est-il besoin de dire que si aucun de ces points nest respect, il y aura aussi erreur !) On va maintenant dtailler ce que lon entend par le terme d oprateur. 38

Un oprateur est un signe qui relie deux valeurs, pour produire un rsultat.Les oprateurs possibles dpendent du type des valeurs qui sont en jeu. Allons-y, faisons le tour, cest un peu fastidieux, mais comme dit le sage au petit scarabe, quand cest fait, cest plus faire.

1.4.1 Oprateurs numriques :Ce sont les quatre oprations arithmtiques tout ce quil y a de classique. + : addition - : soustraction * : multiplication / : division Mentionnons galement le ^ qui signifie puissance . 45 au carr scrira donc 45 ^ 2. Enfin, on a le droit dutiliser les parenthses, avec les mmes rgles quen mathmatiques. La multiplication et la division ont naturellement priorit sur laddition et la soustraction. Les parenthses ne sont ainsi utiles que pour modifier cette priorit naturelle. Cela signifie quen informatique, 12 * 3 + 5 et (12 * 3) + 5 valent strictement la mme chose, savoir 41. Pourquoi ds lors se fatiguer mettre des parenthses inutiles ? En revanche, 12 * (3 + 5) vaut 12 * 8 soit 96. Rien de difficile l-dedans, que du normal.

1.4.2 Oprateur alphanumrique : &Cet oprateur permet de concatner, autrement dit dagglomrer, deux chanes de caractres. Par exemple : Variables A, B, C en Caractre Dbut A "Gloubi" B "Boulga" CA&B Fin La valeur de C la fin de lalgorithme est "GloubiBoulga" 39

1.4.3 Oprateurs logiques (ou boolens) :Il sagit du ET, du OU, du NON et du mystrieux (mais rarissime XOR). Nous les laisserons de ct provisoirement, soyez-en srs.

40

PARTIE 1nonc des Exercices Exercice 1.8Que produit lalgorithme suivant ? Variables A, B, C en Caractres Dbut A "423" B "12" CA+B Fin

Exercice 1.9Que produit lalgorithme suivant ? Variables A, B, C en Caractres Dbut A "423" B "12" CA&B Fin

41

PARTIE 1Corrigs des Exercices Exercice 1.8Il ne peut produire quune erreur dexcution, puisquon ne peut pas additionner des caractres.

Exercice 1.9En revanche, on peut les concatner. A la fin de lalgorithme, C vaudra donc "42312".

42

1.5 Deux remarques pour terminerMaintenant que nous sommes familiers des variables et que nous les manipulons les yeux ferms (mais les neurones en veil, toutefois), jattire votre attention sur la trompeuse similitude de vocabulaire entre les mathmatiques et linformatique. En mathmatiques, une variable est gnralement une inconnue, qui recouvre un nombre non prcis de valeurs. Lorsque jcris : y=3x+2 les variables x et y satisfaisant lquation existent en nombre infini (graphiquement, lensemble des solutions cette quation dessine une droite). Lorsque jcris : ax + bx + c = 0 la variable x dsigne les solutions cette quation, cest--dire zro, une ou deux valeurs la fois

En informatique, une variable possde un moment donn une valeur et une seule.A la rigueur, elle peut ne pas avoir de valeur du tout (une fois quelle a t dclare, et tant quon ne la pas affecte. A signaler que dans certains langages, les variables non encore affectes sont considres comme valant automatiquement zro). Mais ce qui est important, cest que cette valeur justement, ne varie pas proprement parler. Du moins ne varie-t-elle que lorsquelle est lobjet dune instruction daffectation. La deuxime remarque concerne le signe de laffectation. En algorithmique, comme on la vu, cest le signe . Mais en pratique, la quasi totalit des langages emploient le signe gal. Et l, pour les dbutants, la confusion avec les maths est galement facile. En maths, A = B et B = A sont deux propositions strictement quivalentes. En informatique, absolument pas, puisque cela revient crire A B et B A, deux choses bien diffrentes. De mme, A = A + 1, qui en mathmatiques, constitue une quation sans solution, reprsente en programmation une action tout fait licite (et de surcrot extrmement courante). Donc, attention ! ! ! La meilleure des vaccinations contre cette confusion consiste bien employer le signe en pseudo-code, signe qui a le mrite de ne pas laisser place lambigut. Une fois acquis les bons rflexes avec ce signe, vous naurez plus aucune difficult passer au = des langages de programmation.

43

Partie 2 Lecture et Ecriture Un programme est un sort jet sur un ordinateur, qui transforme tout texte saisi au clavier en message derreur. - Anonyme Un clavier Azerty en vaut deux - Anonyme

2.1 De quoi parle-t-on ?Trifouiller des variables en mmoire vive par un chouette programme, cest vrai que cest trs marrant, et dailleurs on a tous bien rigol au chapitre prcdent. Cela dit, la fin de la foire, on peut tout de mme se demander quoi a sert. En effet. Imaginons que nous ayons fait un programme pour calculer le carr dun nombre, mettons 12. Si on a fait au plus simple, on a crit un truc du genre : Variable A en Numrique Dbut A 12^2 Fin Dune part, ce programme nous donne le carr de 12. Cest trs gentil lui. Mais si lon veut le carr dun autre nombre que 12, il faut rcrire le programme. Bof. Dautre part, le rsultat est indubitablement calcul par la machine. Mais elle le garde soigneusement pour elle, et le pauvre utilisateur qui fait excuter ce programme, lui, ne saura jamais quel est le carr de 12. Re-bof. Cest pourquoi, heureusement, il existe des dinstructions pour permettre la machine de dialoguer avec lutilisateur (et Lyce de Versailles, et ajout lestim Pierre Dac, qui en prcurseur mconnu de lalgorithmique, affirmait tout aussi profondment que rien

ne sert de penser, il faut rflchir avant ).Dans un sens, ces instructions permettent lutilisateur de rentrer des valeurs au clavier pour quelles soient utilises par le programme. Cette opration est la lecture. Dans lautre sens, dautres instructions permettent au programme de communiquer des valeurs lutilisateur en les affichant lcran. Cette opration est lcriture.

44

Remarque essentielle : A premire vue, on peut avoir limpression que les informaticienstaient beurrs comme des petits lus lorsquils ont baptis ces oprations ; puisque quand lutilisateur doit crire au clavier, on appelle a la lecture, et quand il doit lire sur lcran on appelle lcriture. Mais avant dagonir dinsultes une digne corporation, il faut rflchir un peu plus loin. Un algorithme, cest une suite dinstructions qui programme la machine, pas lutilisateur ! Donc quand on dit la machine de lire une valeur, cela implique que lutilisateur va devoir crire cette valeur. Et quand on demande la machine dcrire une valeur, cest pour que lutilisateur puisse la lire. Lecture et criture sont donc des termes qui comme toujours en programmation, doivent tre compris du point de vue de la machine qui sera charge de les excuter. Et l, tout devient parfaitement logique. Et toc.

2.2 Les instructions de lecture et dcritureTout btement, pour que lutilisateur entre la (nouvelle) valeur de Titi, on mettra : Lire Titi

Ds que le programme rencontre une instruction Lire, lexcution sinterrompt, attendant la frappe dune valeur au clavierDs lors, aussitt que la touche Entre (Enter) a t frappe, lexcution reprend. Dans le sens inverse, pour crire quelque chose lcran, cest aussi simple que : Ecrire Toto Avant de Lire une variable, il est trs fortement conseill dcrire des libells lcran, afin de prvenir lutilisateur de ce quil doit frapper (sinon, le pauvre utilisateur passe son temps se demander ce que lordinateur attend de lui et cest trs dsagrable !) : Ecrire "Entrez votre nom : " Lire NomFamille Lecture et Ecriture sont des instructions algorithmiques qui ne prsentent pas de difficults particulires, une fois quon a bien assimil ce problme du sens du dialogue (homme machine, ou machine homme). Et a y est, vous savez dores et dj sur cette question tout ce quil y a savoir

45

PARTIE 2nonc des Exercices Exercice 2.1Quel rsultat produit le programme suivant ? Variables val, double numriques Dbut Val 231 Double Val * 2 Ecrire Val Ecrire Double Fin

Exercice 2.2Ecrire un programme qui demande un nombre lutilisateur, puis qui calcule et affiche le carr de ce nombre.

Exercice 2.3Ecrire un programme qui lit le prix HT dun article, le nombre darticles et le taux de TVA, et qui fournit le prix total TTC correspondant. Faire en sorte que des libells apparaissent clairement.

Exercice 2.4Ecrire un algorithme utilisant des variables de type chane de caractres, et affichant quatre variantes possibles de la clbre belle marquise, vos beaux yeux me font mourir damour . On ne se soucie pas de la ponctuation, ni des majuscules.

46

PARTIE 2Corrigs des Exercices Exercice 2.1On verra apparatre lcran 231, puis 462 (qui vaut 231 * 2)

Exercice 2.2Variables nb, carr en Entier Dbut Ecrire "Entrez un nombre :" Lire nb carr nb * nb Ecrire "Son carr est : ", carr Fin En fait, on pourrait tout aussi bien conomiser la variable carr en remplaant les deux avant-dernires lignes par : Ecrire "Son carr est : ", nb*nb C'est une question de style ; dans un cas, on privilgie la lisibilit de l'algorithme, dans l'autre, on privilgie l'conomie d'une variable.

47

Exercice 2.3Variables nb, pht, ttva, pttc en Numrique Dbut Ecrire "Entrez le prix hors taxes :" Lire pht Ecrire "Entrez le nombre darticles :" Lire nb Ecrire "Entrez le taux de TVA :" Lire ttva pttc nb * pht * (1 + ttva) Ecrire "Le prix toutes taxes est : ", pttc Fin L aussi, on pourrait squeezer une variable et une ligne en crivant directement. : Ecrire "Le prix toutes taxes est : ", nb * pht * (1 + ttva) C'est plus rapide, plus lger en mmoire, mais un peu plus difficile relire (et crire !)

Exercice 2.4Variables t1, t2, t3, t4 en Caractre Dbut t1 "belle Marquise" t2 "vos beaux yeux" t3 "me font mourir" t4 "damour" Ecrire t1 & " " & t2 & " " & t3 & " " & t4 Ecrire t3 & " " & t2 & " " & t4 & " " & t1 Ecrire t2 & " " & t3 & " " & t1 & " " & t4 Ecrire t4 & " " & t1 & " " & t2 & " " & t3 Fin

48

Partie 3 Les Tests Il est assez difficile de trouver une erreur dans son code quand on la cherche. Cest encore bien plus dur quand on est convaincu que le code est juste. Steve McConnell Il nexiste pas, et il nexistera jamais, de langage dans lequel il soit un tant soit peu difficile dcrire de mauvais programmes . Anonyme Si le dboguage est lart denlever les bogues, alors la programmation doit tre lart de les crer. Anonyme

Je vous avais dit que lalgorithmique, cest la combinaison de quatre structures lmentaires. Nous en avons dj vu deux, voici la troisime. Autrement dit, on a quasiment fini le programme. Mais non, je rigole.

3.1 De quoi sagit-il ?Reprenons le cas de notre programmation algorithmique du touriste gar . Normalement, lalgorithme ressemblera quelque chose comme : Allez tout droit

jusquau prochain carrefour, puis prenez droite et ensuite la deuxime gauche, et vous y tes .Mais en cas de doute lgitime de votre part, cela pourrait devenir : Allez tout droit

jusquau prochain carrefour et l regardez droite. Si la rue est autorise la circulation, alors prenez la et ensuite cest la deuxime gauche. Mais si en revanche elle est en sens interdit, alors continuez jusqu la prochaine droite, prenez celle-l, et ensuite la premire droite .Ce deuxime algorithme a ceci de suprieur au premier quil prvoit, en fonction dune situation pouvant se prsenter de deux faons diffrentes, deux faons diffrentes dagir. Cela suppose que linterlocuteur (le touriste) sache analyser la condition que nous avons fixe son comportement ( la rue est-elle en sens interdit ? ) pour effectuer la srie dactions correspondante.

49

Eh bien, croyez le ou non, mais les ordinateurs possdent cette aptitude, sans laquelle dailleurs nous aurions bien du mal les programmer. Nous allons donc pouvoir parler notre ordinateur comme notre touriste, et lui donner des sries dinstructions effectuer selon que la situation se prsente dune manire ou dune autre. Cette structure logique rpond au doux nom de test. Toutefois, ceux qui tiennent absolument briller en socit parleront galement de structure alternative.

3.2 Structure dun testIl ny a que deux formes possibles pour un test ; la premire est la plus simple, la seconde la plus complexe. Si boolen Alors Instructions Finsi Si boolen Alors Instructions 1 Sinon Instructions 2 Finsi Ceci appelle quelques explications. Un boolen est une expression dont la valeur est VRAI ou FAUX. Cela peut donc tre (il ny a que deux possibilits) :

une variable (ou une expression) de type boolen une condition

Nous reviendrons dans quelques instants sur ce quest une condition en informatique. Toujours est-il que la structure dun test est relativement claire. Dans la forme la plus simple, arriv la premire ligne (Si Alors) la machine examine la valeur du boolen. Si ce boolen a pour valeur VRAI, elle excute la srie dinstructions. Cette srie dinstructions peut tre trs brve comme trs longue, cela na aucune importance. En revanche, dans le cas o le boolen est faux, l'ordinateur saute directement aux instructions situes aprs le FinSi. Dans le cas de la structure complte, c'est peine plus compliqu. Dans le cas o le boolen est VRAI, et aprs avoir excut la srie d'instructions 1, au moment o elle arrive au mot Sinon , la machine saute directement la premire instruction situe 50

aprs le Finsi . De mme, au cas o le boolen a comme valeur Faux , la machine saute directement la premire ligne situe aprs le Sinon et excute lensemble des instructions 2 . Dans tous les cas, les instructions situes juste aprs le FinSi seront excutes normalement. En fait, la forme simplifie correspond au cas o lune des deux branches du Si est vide. Ds lors, plutt qucrire sinon ne rien faire du tout , il est plus simple de ne rien crire. Et laisser un Si... complet, avec une des deux branches vides, est considr comme une trs grosse maladresse pour un programmeur, mme si cela ne constitue pas proprement parler une faute. Exprim sous forme de pseudo-code, la programmation de notre touriste de tout lheure donnerait donc quelque chose du genre : Allez tout droit jusquau prochain carrefour Si la rue droite est autorise la circulation Alors Tournez droite Avancez Prenez la deuxime gauche Sinon Continuez jusqu la prochaine rue droite Prenez cette rue Prenez la premire droite Finsi

3.3 Quest ce quune condition ?Une condition est une comparaisonCette dfinition est essentielle ! Elle signifie quune condition est compose de trois lments :

une valeur un oprateur de comparaison une autre valeur

Les valeurs peuvent tre a priori de nimporte quel type (numriques, caractres). Mais si lon veut que la comparaison ait un sens, il faut que les deux valeurs de la comparaison soient du mme type !

51

Les oprateurs de comparaison sont :

gal diffrent de strictement plus petit que strictement plus grand que plus petit ou gal plus grand ou gal

Lensemble des trois lments constituant la condition constitue donc, si lon veut, une affirmation, qui a un moment donn est VRAIE ou FAUSSE. A noter que ces oprateurs de comparaison peuvent tout fait semployer avec des caractres. Ceux-ci sont cods par la machine dans lordre alphabtique (rappelez vous le code ASCII vu dans le prambule), les majuscules tant systmatiquement places avant les minuscules. Ainsi on a : t < w Maman > Papa maman > Papa VRAI FAUX VRAI

Remarque trs importante En formulant une condition dans un algorithme, il faut se mfier comme de la peste de certains raccourcis du langage courant, ou de certaines notations valides en mathmatiques, mais qui mnent des non-sens informatiques. Prenons par exemple la phrase Toto est compris entre 5 et 8 . On peut tre tent de la traduire par : 5 < Toto < 8 Or, une telle expression, qui a du sens en franais, comme en mathmatiques, ne veut rien dire en programmation. En effet, elle comprend deux oprateurs de comparaison, soit un de trop, et trois valeurs, soit l aussi une de trop. On va voir dans un instant comment traduire convenablement une telle condition.

52

PARTIE 3nonc des Exercices Exercice 3.1Ecrire un algorithme qui demande un nombre lutilisateur, et linforme ensuite si ce nombre est positif ou ngatif (on laisse de ct le cas o le nombre vaut zro).

53

PARTIE 3Corrigs des Exercices Exercice 3.1Variable n en Entier Dbut Ecrire "Entrez un nombre : " Lire n Si n > 0 Alors Ecrire "Ce nombre est positif Sinon Ecrire "Ce nombre est ngatif" Finsi Fin

54

3.4 Conditions composesCertains problmes exigent parfois de formuler des conditions qui ne peuvent pas tre exprimes sous la forme simple expose ci-dessus. Reprenons le cas Toto est inclus entre 5 et 8 . En fait cette phrase cache non une, mais deux conditions. Car elle revient dire que Toto est suprieur 5 et Toto est infrieur 8 . Il y a donc bien l deux conditions, relies par ce quon appelle un oprateur logique, le mot ET. Comme on la voqu plus haut, linformatique met notre disposition quatre oprateurs logiques : ET, OU, NON, et XOR. Le ET a le mme sens en informatique que dans le langage courant. Pour que "Condition1 ET Condition2" soit VRAI, il faut imprativement que Condition1 soit VRAI et que Condition2 soit VRAI. Dans tous les autres cas, "Condition 1 et Condition2" sera faux. Il faut se mfier un peu plus du OU. Pour que "Condition1 OU Condition2" soit VRAI, il suffit que Condition1 soit VRAIE ou que Condition2 soit VRAIE. Le point important est que si Condition1 est VRAIE et que Condition2 est VRAIE aussi, Condition1 OU Condition2 reste VRAIE. Le OU informatique ne veut donc pas dire ou bien Le XOR (ou OU exclusif) fonctionne de la manire suivante. Pour que "Condition1 XOR Condition2" soit VRAI, il faut que soit Condition1 soit VRAI, soit que Condition2 soit VRAI. Si toutes les deux sont fausses, ou que toutes les deux sont VRAI, alors le rsultat global est considr comme FAUX. Le XOR est donc l'quivalent du "ou bien" du langage courant. Jinsiste toutefois sur le fait que le XOR est une raret, dont il nest pas strictement indispensable de sencombrer en programmation. Enfin, le NON inverse une condition : NON(Condition1)est VRAI si Condition1 est FAUX, et il sera FAUX si Condition1 est VRAI. C'est l'quivalent pour les boolens du signe "moins" que l'on place devant les nombres. Alors, vous vous demandez peut-tre quoi sert ce NON. Aprs tout, plutt qucrire NON(Prix > 20), il serait plus simple dcrire tout bonnement Prix= 15 Alors (il est trs difficile de trouver un nombre qui soit la fois infrieur 10 et suprieur 15 !) Bon, a, cest un motif immdiat pour payer une tourne gnrale, et je sens quon ne restera pas longtemps le gosier sec.

57

PARTIE 3nonc des Exercices Exercice 3.2Ecrire un algorithme qui demande deux nombres lutilisateur et linforme ensuite si leur produit est ngatif ou positif (on laisse de ct le cas o le produit est nul). Attention toutefois : on ne doit pas calculer le produit des deux nombres.

Exercice 3.3Ecrire un algorithme qui demande trois noms lutilisateur et linforme ensuite sils sont rangs ou non dans lordre alphabtique.

58

PARTIE 3Corrigs des Exercices Exercice 3.2Variables m, n en Entier Dbut Ecrire "Entrez deux nombres : " Lire m, n Si (m > 0 ET n > 0) OU (m < 0 ET n < 0) Alors Ecrire "Leur produit est positif" Sinon Ecrire "Leur produit est ngatif" Finsi Fin

Exercice 3.3Variables a, b, c en Caractre Dbut Ecrire "Entrez successivement trois noms : " Lire a, b, c Si a < b ET b < c Alors Ecrire "Ces noms sont classs alphabtiquement" Sinon Ecrire "Ces noms ne sont pas classs" Finsi Fin

59

3.5 Tests imbriqusGraphiquement, on peut trs facilement reprsenter un SI comme un aiguillage de chemin de fer (ou un aiguillage de train lectrique, cest moins lourd porter). Un SI ouvre donc deux voies, correspondant deux traitements diffrents. Mais il y a des tas de situations o deux voies ne suffisent pas. Par exemple, un programme devant donner ltat de leau selon sa temprature doit pouvoir choisir entre trois rponses possibles (solide, liquide ou gazeuse). Une premire solution serait la suivante : Variable Temp en Entier Dbut Ecrire "Entrez la temprature de leau :" Lire Temp Si Temp =< 0 Alors Ecrire "Cest de la glace" FinSi Si Temp > 0 Et Temp < 100 Alors Ecrire "Cest du liquide" Finsi Si Temp > 100 Alors Ecrire "Cest de la vapeur" Finsi Fin Vous constaterez que cest un peu laborieux. Les conditions se ressemblent plus ou moins, et surtout on oblige la machine examiner trois tests successifs alors que tous portent sur une mme chose, la temprature de l'eau (la valeur de la variable Temp).

60

Il serait ainsi bien plus rationnel dimbriquer les tests de cette manire : Variable Temp en Entier Dbut Ecrire "Entrez la temprature de leau :" Lire Temp Si Temp =< 0 Alors Ecrire "Cest de la glace" Sinon Si Temp < 100 Alors Ecrire "Cest du liquide" Sinon Ecrire "Cest de la vapeur" Finsi Finsi Fin Nous avons fait des conomies : au lieu de devoir taper trois conditions, dont une compose, nous navons plus que deux conditions simples. Mais aussi, et surtout, nous avons fait des conomies sur le temps dexcution de lordinateur. Si la temprature est infrieure zro, celui-ci crit dornavant Cest de la glace et passe directement la fin, sans tre ralenti par lexamen dautres possibilits (qui sont forcment fausses). Cette deuxime version nest donc pas seulement plus simple crire et plus lisible, elle est galement plus performante lexcution. Les structures de tests imbriqus sont donc un outil indispensable la simplification et loptimisation des algorithmes.

61

PARTIE 3nonc des Exercices Exercice 3.4Ecrire un algorithme qui demande un nombre lutilisateur, et linforme ensuite si ce nombre est positif ou ngatif (on inclut cette fois le traitement du cas o le nombre vaut zro).

Exercice 3.5Ecrire un algorithme qui demande deux nombres lutilisateur et linforme ensuite si le produit est ngatif ou positif (on inclut cette fois le traitement du cas o le produit peut tre nul). Attention toutefois, on ne doit pas calculer le produit !

Exercice 3.6Ecrire un algorithme qui demande lge dun enfant lutilisateur. Ensuite, il linforme de sa catgorie :

"Poussin" de 6 7 ans "Pupille" de 8 9 ans "Minime" de 10 11 ans "Cadet" aprs 12 ans

Peut-on concevoir plusieurs algorithmes quivalents menant ce rsultat ?

62

PARTIE 3Corrigs des Exercices Exercice 3.4Variable n en Entier Dbut Ecrire "Entrez un nombre : " Lire n Si n < 0 Alors Ecrire "Ce nombre est ngatif" SinonSi n = 0 Alors Ecrire "Ce nombre est nul" Sinon Ecrire "Ce nombre est positif" Finsi Fin

Exercice 3.5Variables m, n en Entier Dbut Ecrire "Entrez deux nombres : " Lire m, n Si m = 0 OU n = 0 Alors Ecrire "Le produit est nul" SinonSi (m < 0 ET n < 0) OU (m > 0 ET n > 0) Alors Ecrire "Le produit est positif" Sinon Ecrire "Le produit est ngatif" Finsi Fin Si on souhaite simplifier lcriture de la condition lourde du SinonSi, on peut toujours passer par des variables boolennes intermdiaires. Une astuce de sioux consiste galement employer un Xor (c'est l'un des rares cas dans lesquels il est pertinent)

63

Exercice 3.6Variable age en Entier Dbut Ecrire "Entrez lge de lenfant : " Lire age Si age >= 12 Alors Ecrire "Catgorie Cadet" SinonSi age >= 10 Alors Ecrire "Catgorie Minime" SinonSi age >= 8 Alors Ecrire "Catgorie Pupille" SinonSi age >= 6 Alors Ecrire "Catgorie Poussin" Finsi Fin On peut videmment crire cet algorithme de diffrentes faons, ne serait-ce quen commenant par la catgorie la plus jeune.

64

3.6 De laiguillage la gare de tri J'ai l'me ferroviaire : je regarde passer les vaches (Lo Ferr)Cette citation napporte peut-tre pas grand chose cet expos, mais je laime bien, alors ctait le moment ou jamais. En effet, dans un programme, une structure SI peut tre facilement compare un aiguillage de train. La voie principale se spare en deux, le train devant rouler ou sur lune, ou sur lautre, et les deux voies se rejoignant tt ou tard pour ne plus en former quune seule, lors du FinSi. On peut schmatiser cela ainsi :

Mais dans certains cas, ce ne sont pas deux voies quil nous faut, mais trois, ou mme plus. Dans le cas de ltat de leau, il nous faut trois voies pour notre train , puisque leau peut tre solide, liquide ou gazeuse. Alors, nous navons pas eu le choix : pour deux voies, il nous fallait un aiguillage, pour trois voies il nous en faut deux, imbriqus lun dans lautre. Cette structure (telle que nous lavons programme la page prcdente) devrait tre schmatise comme suit :

Soyons bien clairs : cette structure est la seule possible du point de vue logique (mme si on peut toujours mettre le bas en haut et le haut en bas). Mais du point de vue de lcriture, le pseudo-code algorithmique admet une simplification supplmentaire.

65

Ainsi, il est possible (mais non obligatoire, que lalgorithme initial : Variable Temp en Entier Dbut Ecrire "Entrez la temprature de leau :" Lire Temp Si Temp =< 0 Alors Ecrire "C'est de la glace" Sinon Si Temp < 100 Alors Ecrire "Cest du liquide" Sinon Ecrire "Cest de la vapeur" Finsi Finsi Fin devienne : Variable Temp en Entier Dbut Ecrire "Entrez la temprature de leau :" Lire Temp Si Temp =< 0 Alors Ecrire "Cest de la glace" SinonSi Temp < 100 Alors Ecrire "Cest du liquide" Sinon Ecrire "Cest de la vapeur" Finsi Fin

Dans le cas de tests imbriqus, le Sinon et le Si peuvent tre fusionns en un SinonSi. On considre alors quil sagit dun seul bloc de test, conclu par un seul FinSiLe SinonSi permet en quelque sorte de crer (en ralit, de simuler) des aiguillages plus de deux branches. On peut ainsi enchaner les SinonSi les uns derrire les autres pour simuler un aiguillage autant de branches que lon souhaite.

66

3.7 Variables BoolennesJusquici, pour crire nos des tests, nous avons utilis uniquement des conditions. Mais vous vous rappelez quil existe un type de variables (les boolennes) susceptibles de stocker les valeurs VRAI ou FAUX. En fait, on peut donc entrer des conditions dans ces variables, et tester ensuite la valeur de ces variables. Reprenons lexemple de leau. On pourrait le rcrire ainsi : Variable Temp en Entier Variables A, B en Boolen Dbut Ecrire "Entrez la temprature de leau :" Lire Temp A Temp =< 0 B Temp < 100 Si A Alors Ecrire "Cest de la glace" SinonSi B Alors Ecrire "Cest du liquide" Sinon Ecrire "Cest de la vapeur" Finsi Fin A priori, cette technique ne prsente gure dintrt : on a alourdi plutt quallg lalgorithme de dpart, en ayant recours deux variables supplmentaires.

Mais souvenons-nous : une variable boolenne na besoin que dun seul bit pour tre stocke. De ce point de vue, lalourdissement nest donc pas considrable.

dans certains cas, notamment celui de conditions composes trs lourdes (avec plein de ET et de OU tout partout) cette technique peut faciliter le travail du programmeur, en amliorant nettement la lisibilit de lalgorithme. Les variables boolennes peuvent galement savrer trs utiles pour servir de flag, technique dont on reparlera plus loin (rassurez-vous, rien voir avec le flagrant dlit des policiers).

67

Partie 4 Encore de la Logique La programmation peut tre un plaisir ; de mme que la cryptographie. Toutefois, il faut viter de combiner les deux. - Kreitzberg et Sneidermann

4.1 Faut-il mettre un ET ? Faut-il mettre un OU ?Une remarque pour commencer : dans le cas de conditions composes, les parenthses jouent un rle fondamental. Variables A, B, C, D, E en Boolen Variable X en Entier Dbut Lire X A X > 12 BX>2 CX 50 ou C > 50 ou D > 50 C3 A >= B et A >= C et A >= D C4 A >= 12,5 Si C1 Alors Ecrire Elu au premier tour" Sinonsi C2 ou Non(C4) Alors Ecrire Battu, limin, sorti !!! SinonSi C3 Alors Ecrire "Ballotage favorable" Sinon Ecrire "Ballotage dfavorable" FinSi Fin

80

Exercice 4.7L encore, on illustre l'utilit d'une bonne analyse. Je propose deux corrigs diffrents. Le premier suit l'nonc pas pas. C'est juste, mais c'est vraiment lourd. La deuxime version s'appuie sur une vraie comprhension d'une situation pas si embrouille qu'elle n'en a l'air. Dans les deux cas, un recours aux variables boolennes are srieusement l'criture. Donc, premier corrig, on suit le texte de l'nonc pas pas : Variables age, perm, acc, assur en Numrique Variables C1, C2, C3 en Boolen Variable situ en Caractre Dbut Ecrire "Entrez lge: " Lire age Ecrire "Entrez le nombre d'annes de permis: " Lire perm Ecrire "Entrez le nombre d'accidents: " Lire acc Ecrire "Entrez le nombre d'annes d'assurance: " Lire assur C1 age >= 25 C2 perm >= 2 C3 assur > 1 Si Non(C1) et Non(C2) Alors Si acc = 0 Alors situ "Rouge" Sinon situ "Refus" FinSi Sinonsi ((Non(C1) et C2) ou (C1 et Non(C2)) Alors Si acc = 0 Alors situ "Orange" SinonSi acc = 1 Alors situ "Rouge" Sinon situ "Refus" FinSi Sinon Si acc = 0 Alors 81

situ "Vert" SinonSi acc = 1 Alors situ "Orange" SinonSi acc = 2 Alors situ "Rouge" Sinon situ "Refus" FinSi FinSi Si C3 Alors Si situ = "Rouge" Alors situ "Orange" SinonSi situ = "Orange" Alors situ "Orange" SinonSi situ = "Vert" Alors situ "Bleu" FinSi FinSi Ecrire "Votre situation : ", situ Fin Vous trouvez cela compliqu ? Oh, certes oui, a l'est ! Et d'autant plus qu'en lisant entre les lignes, on pouvait s'apercevoir que ce galimatias de tarifs recouvre en fait une logique trs simple : un systme points. Et il suffit de comptabiliser les points pour que tout s'claire... Reprenons juste aprs l'affectation des trois variables boolennes C1, C2, et C3. On crit : P0 Si Non(C1) Alors PP+1 FinSi Si Non(C2) Alors PP+1 FinSi P P + acc Si P < 3 et C3 Alors PP1 FinSi Si P = -1 Alors situ "Bleu" SinonSi P = 0 Alors 82

situ "Vert" SinonSi P = 1 Alors situ "Orange" SinonSi P = 2 Alors situ "Rouge" Sinon situ "Refus" FinSi Ecrire "Votre situation : ", situ Fin Cool, non ?

83

Exercice 4.8En ce qui concerne le dbut de cet algorithme, il ny a aucune difficult. Cest de la saisie bte et mme pas mchante: Variables J, M, A, JMax en Numrique Variables VJ, VM, B en Booleen Dbut Ecrire "Entrez le numro du jour" Lire J Ecrire "Entrez le numro du mois" Lire M Ecrire "Entrez l'anne" Lire A C'est videmment ensuite que les ennuis commencent La premire manire d'aborder la chose consiste se dire que fondamentalement, la structure logique de ce problme est trs simple. Si nous crons deux variables boolennes VJ et VM, reprsentant respectivement la validit du jour et du mois entrs, la fin de l'algorithme sera d'une simplicit biblique (lanne est valide par dfinition, si on vacue le dbat byzantin concernant lexistence de lanne zro) : Si VJ et VM alors Ecrire "La date est valide" Sinon Ecrire "La date n'est pas valide" FinSi Toute la difficult consiste affecter correctement les variables VJ et VM, selon les valeurs des variables J, M et A. Dans l'absolu, VJ et VM pourraient tre les objets d'une affectation monstrueuse, avec des conditions atrocement composes. Mais franchement, crire ces conditions en une seule fois est un travail de bndictin sans grand intrt. Pour viter d'en arriver une telle extrmit, on peut srier la difficult en crant deux variables supplmentaires : B : variable boolenne qui indique s'il s'agit d'une anne bissextile

JMax : variable numrique qui indiquera le dernier jour valable pour le mois entr. Avec tout cela, on peut y aller et en ressortir vivant. On commence par initialiser nos variables boolennes, puis on traite les annes, puis les mois, puis les jours.

84

On note "dp" la condition "divisible par" : B A dp 400 ou (non(A dp 100) et A dp 4) Jmax 0 VM M >= 1 et M =< 12 Si VM Alors Si M = 2 et B Alors JMax 29 SinonSi M = 2 Alors JMax 28 SinonSi M = 4 ou M = 6 ou M = 9 ou M = 11 Alors JMax 30 Sinon JMax 31 FinSi VJ J >= 1 et J =< Jmax FinSi Cette solution a le mrite de ne pas trop compliquer la structure des tests, et notamment de ne pas rpter l'criture finale l'cran. Les variables boolennes intermdiaires nous pargnent des conditions composes trop lourdes, mais celles-ci restent nanmoins srieuses. Une approche diffrente consisterait limiter les conditions composes, quitte le payer par une structure beaucoup plus exigeante de tests imbriqus. L encore, on vite de jouer les extrmistes et l'on s'autorise quelques conditions composes lorsque cela nous simplifie l'existence. On pourrait aussi dire que la solution prcdente "part de la fin" du problme (la date est elle valide ou non ?), alors que celle qui suit "part du dbut" (quelles sont les donnes entres au clavier ?) : Si M < 1 ou M > 12 Alors Ecrire "Date Invalide" SinonSi M = 2 Alors Si A dp 400 Alors Si J < 1 ou J > 29 Alors Ecrire "Date Invalide" Sinon Ecrire "Date Valide" FinSi SinonSi A dp 100 Alors Si J < 1 ou J > 28 Alors Ecrire "Date Invalide" 85

Sinon Ecrire "Date Valide" FinSi SinonSi A dp 4 Alors Si J < 1 ou J > 28 Alors Ecrire "Date Invalide" Sinon Ecrire "Date Valide" FinSi Sinon Si J < 1 ou J > 28 Alors Ecrire "Date Invalide" Sinon Ecrire "Date Valide" FinSi FinSi SinonSi M = 4 ou M = 6 ou M = 9 ou M = 11 Alors Si J < 1 ou J > 30 Alors Ecrire "Date Invalide" Sinon Ecrire "Date Valide" FinSi Sinon Si J < 1 ou J > 31 Alors Ecrire "Date Invalide" Sinon Ecrire "Date Valide" FinSi FinSi On voit que dans ce cas, l'alternative finale (Date valide ou invalide) se trouve rpte un grand nombre de fois. Ce n'est en soi ni une bonne, ni une mauvaise chose. C'est simplement une question de choix stylistique. Personnellement, j'avoue prfrer assez nettement la premire solution, qui fait ressortir beaucoup plus clairement la structure logique du problme (il n'y a qu'une seule alternative, autant que cette alternative ne soit crite qu'une seule fois). Il convient enfin de citer une solution trs simple et lgante, un peu plus difficile peuttre imaginer du premier coup, mais qui avec le recul apparat comme trs immdiate. Sur le fond, cela consiste dire qu'il y a quatre cas pour qu'une date soit valide : celui d'un jour compris entre 1 et 31 dans un mois 31 jours, celui d'un jour compris entre 1 86

et 30 dans un mois 30 jours, celui d'un jour compris entre 1 et 29 en fvrier d'une anne bissextile, et celui d'un jour de fvrier compris entre 1 et 28. Ainsi : B (A dp 4 et Non(A dp 100)) ou A dp 400 K1 (m=1 ou m=3 ou m=5 ou m=7 ou m=8 ou m=10 ou m=12) et (J>=1 et J==1 et J==1 et J==1 et J= PG Alors PG N IPG i FinSi i Suivant Ecrire "Le nombre le plus grand tait : ", PG Ecrire "Il a t saisi en position numro ", IPG Fin

Exercice 5.8Variables N, i, PG, IPG en Entier Debut N1 i0 PG 0 TantQue N 0 Ecrire "Entrez un nombre : " Lire N ii+1 Si i = 1 ou N > PG Alors PG N IPG i FinSi FinTantQue Ecrire "Le nombre le plus grand tait : ", PG Ecrire "Il a t saisi en position numro ", IPG Fin

107

Exercice 5.9Variables FF, somdue, M, IPG, Reste, Nb10F, Nb5F En Entier Debut E1 somdue 0 TantQue E 0 Ecrire "Entrez le montant : " Lire E somdue somdue + E FinTantQue Ecrire "Vous devez :", E, " euros" Ecrire "Montant vers :" Lire M Reste M E Nb10E 0 TantQue Reste >= 10 Nb10E Nb10E + 1 Reste Reste 10 FinTantQue Nb5E 0 Si Reste >= 5 Nb5E 1 Reste Reste 5 FinSi Ecrire "Rendu de la monnaie :" Ecrire "Billets de 10 E : ", Nb10E Ecrire "Billets de 5 E : ", Nb5E Ecrire "Pices de 1 E : ", reste Fin

108

Exercice 5.10Spontanment, on est tent d'crire l'algorithme suivant : Variables N, P, i, Num, Dno1, Dno2 en Entier Debut Ecrire "Entrez le nombre de chevaux partants : " Lire N Ecrire "Entrez le nombre de chevaux jous : " Lire P Num 1 Pour i 2 N Num Num * i i Suivant Dno1 1 Pour i 2 N-P Dno1 Dno1 * i i Suivant Dno2 1 Pour i 2 P Dno2 Dno2 * i i Suivant Ecrire "Dans lordre, une chance sur ", Num / Dno1 Ecrire "Dans le dsordre, une sur ", Num / (Dno1 * Dno2) Fin Cette version, formellement juste, comporte tout de mme deux faiblesses. La premire, et la plus grave, concerne la manire dont elle calcule le rsultat final. Celui-ci est le quotient d'un nombre par un autre ; or, ces nombres auront rapidement tendance tre trs grands. En calculant, comme on le fait ici, d'abord le numrateur, puis ensuite le dnominateur, on prend le risque de demander la machine de stocker des nombres trop grands pour qu'elle soit capable de les coder (cf. le prambule). C'est d'autant plus bte que rien ne nous oblige procder ainsi : on n'est pas oblig de passer par la division de deux trs grands nombres pour obtenir le rsultat voulu. La deuxime remarque est qu'on a programm ici trois boucles successives. Or, en y regardant bien, on peut voir qu'aprs simplification de la formule, ces trois boucles comportent le mme nombre de tours ! (si vous ne me croyez pas, crivez un exemple de calcul et biffez les nombres i