Home

SOMMAIRE Algorithmie

1. 5 Tests imbriqu s Graphiquement on peut tr s facilement repr senter un SI comme un aiguillage de chemin de fer ou un aiguillage de train lectrique c est moins lourd porter Un SI ouvre donc deux voies correspondant deux traitements diff rents Mais il y a des tas de situations o deux voies ne suffisent pas Par exemple un programme devant donner l tat de l eau selon sa temp rature doit pouvoir choisir entre trois r ponses possibles solide liquide ou gazeuse Exemple Variable Temp en Entier D but Ecrire Entrez la temp rature de l eau Lire Temp Si Temp lt 0 Alors Ecrire C est de la glace Finsi Si Temp gt 0 Et Temp lt 100 Alors Ecrire C est du liquide Finsi Si Temp gt 100 Alors Ecrire C est de la vapeur Finsi Fin Vous constaterez que c est 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 m me chose la temp rature la valeur de la variable Temp Il serait ainsi bien plus rationnel d imbriquer les tests de cette mani re Exemple wwWw jeremyazoulay com 14 Variable Temp en Entier D but Ecrire Entrez la temp rature de l eau Lire Temp Si Temp lt 0 Alors Ecrire C est de la glace Sinon Si Temp lt 100 Alors Ecrire C est du liquide Sinon Ecrire C est de la vapeur Finsi Finsi Fin Nous avons fait des conomies
2. ce sujet On y reviendra Un autre type est le type bool en on y stocke uniquement les valeurs logiques VRAI et FAUX 3 L instruction d affectation 3 1 Syntaxe et signification Ouf apr s tout ce baratin pr liminaire on aborde enfin nos premi res v ritables manipulations d algo Pas trop t t wwWw jeremyazoulay com 6 La seule chose qu on puisse vraiment faire avec une variable c est de l affecter c est dire lui attribuer une valeur En algorithmique cette instruction se note avec le signe Ainsi Toto 24 Attribue la valeur 24 la variable Toto Ce qui soit dit en passant sous entend imp rativement que Toto est une variable de type num rique On peut attribuer une variable la valeur d une autre variable telle quelle ou modifi e Par exemple Tutu amp Toto Signifie que la valeur de Tutu est maintenant celle de Toto Notez que cette instruction n a modifi en rien la valeur de Toto une instruction d affectation ne modifie que ce qui est situ gauche de la fl che Tutu amp Toto 4 Si Toto contenait 12 Tutu vaut maintenant 16 De m me que pr c demment Toto vaut toujours 12 Tutu amp Tutu 1 Si Tutu valait 6 il vaut maintenant 7 La valeur de Tutu est modifi e puisque Tutu est la variable situ e gauche de la fl che 3 2 Ordre des instructions Il va de soi que l ordre dans lequel les instructions sont crites va jouer un r le essentiel dans le r sultat
3. carr ment de structures it ratives Ca calme hein Bon vous faites ce que vous voulez ici on est entre nous on parlera de boucles 1 quoi cela sert il donc Prenons le cas d une saisie au clavier une lecture par exemple on pose une question laquelle l utilisateur doit r pondre par O Oui ou N Non Mais l utilisateur fac tieux ou maladroit risque fort t t ou tard de taper autre chose que cela D s lors le programme peut soit planter par une erreur d ex cution parce que le type de r ponse ne correspond pas au type de la variable attendu soit se d rouler normalement jusqu au bout mais en produisant des r sultats fantaisistes Alors dans tout programme un tant soit peu s rieux on met en place ce qu on appelle un contr le de saisie pour v rifier que les donn es entr es au clavier correspondent bien celles attendues par l algorithme A vue de nez on pourrait essayer avec un SI Voyons voir ce que a donne Variable Rep en Caract re Ecrire Voulez vous un caf O N Lire Rep Si Rep lt gt O ET Rep lt gt N Alors Ecrire Saisie erronn e Recommencez Lire Rep FinsSi C est impeccable Du moins tant que l utilisateur a le bon go t de ne se tromper qu une seule fois et d entrer une valeur correcte la deuxi me demande Si l on veut galement b tonner en cas de deuxi me erreur il faudrait rajouter un SI Et ainsi de suite on peut rajouter des centaines de SI et
4. e une autre valeur Les valeurs peuvent tre a priori de n importe quel type num riques caract res Les op rateurs de comparaison sont lt gt lt gt lt gt L ensemble constitue donc si l on veut une affirmation qui a un moment donn est VRAIE ou FAUSSE A noter que ces op rateurs de comparaison s emploient tout fait avec des caract res Ceux ci sont cod s par la machine dans l ordre alphab tique les majuscules tant syst matiquement plac es avant les minuscules Ainsi on a d lt w VRAI Maman gt Papa FAUX maman gt Papa VRAI Attention certains raccourcis du langage courant qui peuvent mener des non sens informatiques Prenons par exemple la condition Toto est compris entre 5 et 8 On peut tre tent de la traduire par 5 lt Toto lt 8 Or une telle expression qui a du sens en math matiques ne veut rien dire en programmation On va voir tout de suite apr s comment traduire une telle condition 4 Conditions compos es Certains probl mes exigent parfois de formuler des conditions qui ne peuvent pas tre exprim es sous la forme simple expos e 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 sup rieur 5 et Toto est inf rieur 8 Il y a donc bien l deux conditions reli es par ce qu on appelle un op rateur logique le mot ET Comme on l a
5. en lecture Christine j crois qu c est clair Ouvrir Exemple txt sur 4 en Lecture Variables Truc Nom Pr nom Tel Mail en Caract res Lire 4 Truc Nom amp Mid Truc 1 20 Pr nom Mid Truc 21 15 Tel amp Mid Truc 36 10 Mail amp Mid Truc 46 20 L instruction Lire r cup re donc dans la variable sp cifi e l enregistrement suivant dans un fichier Suivant par rapport quoi Par rapport au dernier enregistrement lu C est en cela que le fichier est dit s quentiel Lire un fichier s quentiel de bout en bout suppose donc de programmer une boucle Comme on sait rarement combien d enregistrements comporte le fichier la combine consiste utiliser la fonction EOF acronyme pour End Of File Cette fonction est vraie si on a atteint la fin du fichier auquel cas une lecture suppl mentaire d clencherait une erreur L algorithme ultra classique en pareil cas est donc Variable Truc en Caract re Ouvrir Exemple txt sur 5 en Lecture Tantque Non EOF 5 Lire 5 Truc FinTantQue Pour une op ration d criture ou d ajout il faut d abord constituer une cha ne quivalente la nouvelle ligne du fichier Cette cha ne doit donc tre calibr e de la bonne mani re avec les diff rents champs qui tombent aux emplacements corrects Le moyen le plus simple pour s pargner de longs traitements est de proc der avec des cha nes correctement dimensionn es d s leur d claration la pl
6. venir l utilisateur de ce qu il doit frapper c est m me assez fortement recommand wwWw jeremyazoulay com 10 Ecrire Entrez votre nom Lire NomFamille Notez qu il y a une diff rence majeure entre afficher un libell et le contenu d une variable Exemple Variable Bonjour en Caract re Variable Bonjour en Caract re D but D but Bonjour Ave Cesar Bonjour Ave Cesar Ecrire Bonjour Ecrire Bonjour Fin Fin Le premier algorithme affiche le contenu de la variable Bonjour autrement dit Ave Cesar Le second affiche le libell Bonjour qui n a rien voir avec la variable du m me nom wwWw jeremyazoulay com 11 Ill Les tests Je vous avais dit que l algorithmique c est la combinaison de quatre structures l mentaires Nous en avons d j vu deux voici la troisi me Autrement dit on a quasiment fini le programme Mais non je rigole 1 De quoi s agit il Reprenons le cas de notre programmation algorithmique du touriste gar Normalement notre algorithme ressemblera quelque chose comme Allez tout droit jusqu au prochain carrefour puis prenez droite et ensuite la deuxi me gauche et vous y tes Mais en cas de doute l gitime de votre part cela pourrait devenir Allez tout droit jusqu au prochain carrefour et l regardez droite Si la rue est autoris e la circulation alors prenez la et ensuite c est la deuxi me gauche Mais si en revanche e
7. Truc Suivant Vous remarquerez que nous faisons ici g rer en double la variable Truc ces deux gestions tant contradictoires D une part la ligne Pour augmente la valeur de Truc de 1 chaque passage D autre part la ligne Truc amp Truc 2 double la valeur de Truc chaque passage Il va sans dire que de telles manipulations perturbent compl tement le d roulement normal de la boucle et sont sources d ex cutions erratiques Le gag de la journ e consiste donc manipuler au sein d une boucle Pour la variable qui sert de compteur cette boucle Cette technique est proscrire absolument sauf bien s r si vous cherchez un pr texte pour r galer tout le monde au bistrot Mais dans ce cas n ayez aucune inhibition proposez le directement pas besoin de pr texte wwWw jeremyazoulay com 19 V Les tableaux Bonne nouvelle on a vu toutes les structures logiques de la programmation Mauvaise nouvelle il vous reste tout de m me quelques petites choses apprendre 1 Utilit des tableaux Imaginons que dans un programme nous ayons besoin simultan ment de 12 valeurs par exemple des notes pour calculer une moyenne Evidemment la seule solution dont nous disposons l heure actuelle consiste d clarer quinze variables appel es par exemple Notea Noteb Notec etc Bien s r on peut opter pour une notation un peu simplifi e par exemple N1 N2 N3 etc Mais cela ne change pas fondamentalement
8. au niveau de la frappe du programme au lieu de devoir taper trois conditions dont une compos e nous n avons plus que deux conditions simples Mais aussi et surtout nous avons fait des conomies sur le temps d ex cution de l ordinateur Si la temp rature est inf rieure z ro celui ci crit dor navant C est de la glace et passe directement la fin sans tre ralenti par l examen d autres possibilit s qui sont forc ment fausses Cette deuxi me version n est donc pas seulement plus simple crire et plus lisible elle est galement plus performante l ex cution Les structures de tests imbriqu s sont donc un outil indispensable la simplification et l optimisation des algorithmes 6 Variables Bool ennes Jusqu ici nous avons utilis uniquement des conditions pour faire des choix Mais vous vous rappelez qu il existe un type de variables les bool ennes 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 l exemple de l eau On peut le r crire ainsi Exemple Variable Temp en Entier Variables A B en Bool en D but Ecrire Entrez la temp rature de l eau Lire Temp A amp Temp lt 0 B amp Temp lt 100 Si A Alors Ecrire C est de la glace Sinon B Alors Ecrire C est du liquide Sinon Ecrire C est de la vapeur Finsi Finsi Fin A prio
9. de fois plus rapides nanosecondes que les acc s aux m moires de masse millisecondes au mieux pour un disque dur e la facilit de programmation bien qu il faille crire en plus les instructions de recopie du fichier dans le tableau pour peu qu on doive tripoter ces informations dans tous les sens c est largement plus facile de faire cela avec un tableau qu avec des fichiers Pourquoi alors demanderez vous haletants ne fait on pas cela tous les coups Y a t il des cas o il vaut mieux en rester aux fichiers et ne pas passer par des tableaux e a recopie d un gros fichier en m moire vive consomme des ressources qui peuvent atteindre des dimensions consid rables Et au final le gain de rapidit d ex cution risque de ne pas tre vident e si le fichier contient des donn es de type non homog nes cha nes num riques etc cela risque d tre coton pour le stocker dans un tableau il va falloir d clarer plusieurs tableaux dont le maniement au final peut tre aussi lourd que celui des fichiers de d part Ou alors il faut utiliser une ruse qu offrent certains langages mais pas tous cr er des types de variables personnalis s compos s d un collage de plusieurs types existants 10 caract res puis un num rique puis 15 caract res etc Cette technique est un peu acrobatique Bien qu elle ne soit pas vraiment difficile elle exige tout de m me une certaine aisance Je rappelle qu a priori les fichie
10. e Cela implique deux choses e lorsqu on appelle la proc dure on doit lui pr ciser quel message elle doit afficher avant de lire la r ponse e a proc dure doit tre pr venue qu elle recevra un message et tre capable de le r cup rer pour l afficher En langage algorithmique on dira que le message est un param tre Comme le param tre le message est transmis de la proc dure principale vers la sous proc dure il s agit d un param tre en entr e Voil comment l affaire se pr sente La proc dure sera d clar e comme suit Proc dure R ponseOuiNon Msg en Caract re Il y a donc dor navant une variable Msg dont on pr cise le type et qui signale le proc dure qu un param tre peut lui tre envoy A pr sent le corps de la proc dure sera Proc dure R ponseOuiNon Msg en Caract re Ecrire Msg Rep LL LE TantQue Rep lt gt Oui et Rep lt gt Non Ecrire Tapez Oui ou Non Lire Rep FinTantQue Fin Proc dure La proc dure principale devient alors R ponseOuiNon Etes vous mari R ponseOuiNon Avez vous des enfants Et voil le travail L on a pass qu un seul param tre en entr e mais on peut en passer autant qu on veut mais ne soyons pas gourmands il suffit d en passer autant qu on en a besoin D un autre c t on ne s est gu re pr occup jusque l de r cup rer le r sultat de notre sous proc dure savoir la r ponse la
11. espace m moire contenant 3 x 5 x 4 x 4 240 valeurs Chaque valeur est rep r e par quatre coordonn es Le principal obstacle au maniement syst matique de ces tableaux plus de trois dimensions est que le programmeur quand il con oit son algorithme aime bien faire des petits gribouillis des dessins immondes imaginer les boucles dans sa t te etc Or autant il est facile d imaginer concr tement un tableau une dimension autant cela reste faisable pour deux dimensions autant cela devient l apanage d une minorit privil gi e pour les tableaux trois dimensions je n en fais malheureusement pas partie et hors de port e de tout mortel au del C est comme a l esprit humain a du mal se repr senter les choses dans l espace et crie gr ce d s qu on est dans l hyperespace oui c est comme a que a s appelle au del de trois dimensions Donc pour des raisons uniquement pratiques les tableaux plus de trois dimensions sont rarement utilis s par des programmeurs non matheux car les matheux de par leur formation ont une f cheuse propension manier des espaces n dimensions comme qui rigole mais ce sont bien les seuls et laissons les dans leur coin c est pas des gens comme nous wwWw jeremyazoulay com 24 VII Les fonctions pr d finies Certains traitements ne peuvent tre effectu s par un algorithme aussi savant soit il C est par exemple le cas du calcul du sinus d un angle pour en obtenir
12. fonctions n exigeant aucun argument les parenth ses restent obligatoires Le nombre d arguments n cessaire pour une fonction donn e ne s invente pas il est fix par le langage Par exemple la fonction sinus a besoin d un argument logique c est la valeur de l angle Si vous essayez de l ex cuter en lui donnant deux arguments ou aucun cela d clenchera une erreur l ex cution Notez galement que les arguments doivent tre d un certain type et qu il faut respecter ces types 2 Les fonctions de texte Une cat gorie privil gi e de fonctions est celle qui nous permet de manipuler des cha nes de caract res Nous avons d j vu qu on pouvait facilement coller deux cha nes l une l autre avec l op rateur de concat nation amp Mais ce que nous ne pouvions pas faire et qui va tre maintenant possible c est pratiquer des extractions de cha nes moins douloureuses il faut le noter que les extractions dentaires Tous les langages je dis bien tous proposent peu ou prou les fonctions suivantes m me si le nom et la syntaxe peuvent varier d un langage l autre Len cha ne renvoie le nombre de caract res d une cha ne Mid cha ne ni renvoie un extrait de la cha ne commen ant au caract re n1 et faisant n2 caract res de n2 long Left cha ne n renvoie les n caract res les plus gauche dans cha ne Right cha ne n renvoie les n caract res les plus droite dans cha ne Enf
13. n est pas un d r glement de votre t l viseur Nous contr lons tout nous savons tout et les ph nom nes paranormaux que vous constatez sont dus au fait que vous tes pass s dans la quatri me dimension musique angoissante tintintin Oui enfin bon avant d attaquer la quatri me on va d j se coltiner la deuxi me 1 Pourquoi plusieurs dimensions Une seule ne suffisait elle pas d j amplement notre bonheur me demanderez vous Certes r pondrai je mais vous allez voir qu avec deux et davantage encore c est carr ment le nirvana Prenons le cas de la mod lisation d un jeu de dames et du d placement des pions sur le damier Je rappelle qu un pion qui est sur une case blanche peut se d placer pour simplifier sur les quatre cases blanches adjacentes Avec les outils dont on dispose actuellement le plus simple serait videmment de mod liser le damier sous la forme d un tableau Chaque case est un emplacement du tableau qui contient par exemple 0 si elle est vide et 1 s il y a un pion On attribue comme indices aux cases les num ros 1 8 pour la premi re ligne 9 16 pour la deuxi me ligne et ainsi de suite jusqu 64 Un pion plac dans la case num ro i autrement dit la valeur 1 de Cases i peut bouger vers les cases contigu s en diagonale Cela va nous obliger de petites acrobaties intellectuelles la case situ e juste au dessus de la case num ro i ayant comme indice i 8 les
14. r dig es dans tel ou tel langage l ordinateur lui ne comprend qu un seul langage qui est un langage cod en binaire la rigueur en hexad cimal et qui s appelle le langage machine ou assembleur C est cela que sert un langage vous pargner la programmation en binaire une pure horreur vous vous en doutez et vous permettre de vous faire comprendre de l ordinateur d une mani re relativement lisible C est pourquoi tout langage partir d un programme crit doit obligatoirement proc der une traduction en langage machine pour que ce programme soit ex cutable Il existe deux strat gies de traduction ces deux strat gies tant parfois disponibles au sein du m me langage e le langage traduit les instructions au fur et mesure qu elles se pr sentent Cela s appelle la compilation la vol e ou l interpr tation e le langage commence par traduire l ensemble du programme en langage machine constituant ainsi un deuxi me programme un deuxi me fichier distinct physiquement et logiquement du premier Ensuite et ensuite seulement il ex cute ce second programme Cela s appelle la compilation Il va de soi qu un langage interpr t est plus maniable on peut ex cuter directement son code au fur et mesure qu on le tape sans passer chaque fois par l tape suppl mentaire de la compilation Mais il va aussi de soi qu un programme compil s ex cute beaucoup plus rapidement qu un programme interp
15. savoir vous avez d j ex cut des algorithmes Plus fort avez vous d j indiqu un chemin un touriste gar Avez vous fait chercher un objet quelqu un par t l phone Ecrit une lettre anonyme stipulant comment proc der une remise de ran on Si oui vous avez d j fabriqu et fait ex cuter des algorithmes Comme quoi l algorithmique n est pas un savoir sot rique r serv quelques rares initi s touch s par la gr ce divine mais une aptitude partag e par la totalit de l humanit Donc pas d excuses 2 D finissons l algorithmique Un algorithme c est une suite d instructions qui une fois ex cut e correctement conduit un r sultat donn Si l algorithme est juste le r sultat est le r sultat voulu et le touriste se retrouve l o il voulait aller Si l algorithme est faux le r sultat est disons al atoire et d cid ment cette saloperie de r pondeur ne marche pas Compl tons toutefois cette d finition Apr s tout en effet si l algorithme comme on vient de le dire n est qu une suite d instructions menant celui qui l ex cute r soudre un probl me pourquoi ne pas donner comme instruction unique r sous le probl me et laisser l interlocuteur se d brouiller avec a A ce tarif n importe qui serait champion d algorithmique sans faire aucun effort Pas de a Lisette ce serait trop facile Le malheur ou le bonheur tout d pend du point de vue e
16. types d acc s Le choix du type d acc s n est pas un choix qui concerne le fichier lui m me mais uniquement la mani re dont il va tre trait par la machine C est donc dans le programme et seulement dans le programme que l on choisit le type d acc s souhait Au premier abord il est clair que l acc s direct poss de tous les avantages et aucun inconv nient Sa programmation est immens ment plus simple et moins fastidieuse que celle de l acc s s quentiel Mais vous vous doutez bien qu il y a un mais Le gros probl me de l acc s direct c est qu il n est pas g r de la m me mani re selon le type de machine Car la gestion de l acc s direct suppose des l ments de langage annexes qui diff rent selon les ordinateurs et qui ne seront pas forc ment pr sents Pour r sumer disons que si vous crivez un programme C utilisant des acc s directs des fichiers vous n tes pas absolument certains que votre programme pourra tourner sur tous les ordinateurs En revanche l acc s s quentiel lui est enti rement pilot par le langage lui m me Il est donc laborieux programmer rustique tout ce que vous voulez mais il offre une s curit absolue de portabilit Voil pourquoi la plupart des programmeurs s astreignent encore utiliser ce type d acc s et voil pourquoi c est celui l que nous allons tudier Et de toute mani re qui peut le plus peut le moins et une fois que vous aurez m
17. un probl me donn ind pendamment des particularit s de tel ou tel langage Pour prendre une image si un programme tait une dissertation l algorithmique serait le plan une fois mis de c t la r daction et l orthographe Or vous savez qu il vaut mieux faire d abord le plan et r diger ensuite que l inverse 6 Avec quelles conventions crit on un algorithme Historiquement plusieurs types de notations ont repr sent des algorithmes Il y a eu notamment une repr sentation graphique avec des carr s des losanges etc qu on appelait des organigrammes Aujourd hui cette repr sentation est quasiment abandonn e pour deux raisons D abord parce que d s que l algorithme commence grossir un peu ce n est plus pratique du tout du tout Ensuite parce que cette repr sentation favorise le glissement vers un certain type de programmation dite non structur e nous d finirons ce terme plus tard que l on tente en g n ral d viter C est pourquoi on utilise g n ralement une s rie de conventions appel e pseudo code qui ressemble un langage authentique la plupart des probl mes de syntaxe tant mis de c t wwWw jeremyazoulay com 4 Les variables 1 D claration Dans un programme informatique on va avoir en permanence besoin de stocker provisoirement des valeurs Il peut s agir de donn es issues du disque dur fournies par l utilisateur frapp es au clavier ou que sais je encore Il peut au
18. une valeur approch e il faudrait appliquer une formule d une complexit vous glacer le sang Aussi que se passe t il sur les petites calculatrices que vous connaissez tous On vous fournit quelques touches sp ciales dites touches de fonctions qui vous permettent par exemple de conna tre imm diatement ce r sultat Sur votre calculatrice si vous voulez conna tre le sinus de 35 vous taperez 35 puis la touche SIN et vous aurez le r sultat Tout langage de programmation propose ainsi un certain nombre de fonctions certaines sont indispensables car elles permettent d effectuer des traitements qui seraient sans elles impossibles D autres servent soulager le programmeur en lui pargnant de longs algorithmes 1 Structure g n rale des fonctions Reprenons l exemple du sinus Les langages proposent g n ralement une fonction SIN Si nous voulons stocker le sinus de 35 dans la variable A nous crirons A amp Sin 35 Une fonction est donc constitu e de trois parties e le nom proprement dit de la fonction Ce nom ne s invente pas Il doit imp rativement correspondre une fonction propos e par le langage deux parenth ses une ouvrante une fermante une liste de valeurs indispensables la bonne ex cution de la fonction Ces valeurs s appellent des arguments ou des param tres Certaines fonctions exigent un seul argument d autres deux etc et d autres encore aucun noter que m me dans le cas de ces
19. voqu plus haut l informatique met notre disposition trois op rateurs logiques ET O et NON Le ET a le m me sens en informatique que dans le langage courant Pour que Conditioni ET Condition soit VRAI il faut imp rativement que Conditioni soit VRAIE et que Condition2 soit VRAIE wwWw jeremyazoulay com 13 Il faut se m fier un peu plus du O Pour que Condition1 OU Condition soit VRAI Il suffit que Condition soit VRAIE ou que Condition soit VRAIE Le point important est que si Conditioni est VRAIE et que Condition est VRAIE aussi Conditioni OU Condition est VRAIE Le O informatique ne veut donc pas dire ou bien sauf dans certaines formes rares d nomm es O exclusif et not es XOR On repr sente fr quemment tout ceci dans des tables de v rit Le gag de la journ e c est bien s r formuler une condition qui ne pourra jamais tre vraie Si c est pas fait expr s c est assez rigolo Si c est fait expr s c est encore plus dr le car une condition dont on sait d avance qu elle sera toujours fausse n est pas une condition Cela peut tre par exemple Si Toto lt 10 ET Toto gt 15 Alors Bon a c est un motif imm diat pour payer une tourn e g n rale et je sens qu on ne restera pas longtemps le gosier sec Quelques mots pour finir l dessus L op rateur NON lui inverse une condition Condition VRAI amp NON Condition FAUX NON X gt 15 revient crire X lt 15
20. Cet op rateur permet de concat ner autrement dit d agglom rer deux cha nes de caract res Exemple Variables A B C en Caract re D but A Gloubi B Boulga CEA amp B Fin wwWw jeremyazoulay com 8 La valeur de C la fin de l algorithme est GloubiBoulga Op rateurs logiques Il s agit du ET du O et du NON Nous les laisserons de c t provisoirement soyez en s rs 4 Deux remarques pour terminer J attire votre attention sur la trompeuse similitude de vocabulaire entre les math matiques et l informatique En math matiques une variable est g n ralement une inconnue Lorsque j cris que y 3 x 2 les variables x et y satisfaisant l quation existent en nombre infini graphiquement l ensemble des solutions cette quation dessine une droite Lorsque j cris ax bx c 0 la variable x d signe les solutions cette quation c est dire 0 une ou deux valeurs la fois En informatique une variable a toujours une valeur et une seule A la rigueur dans certains langages mais pas tous elle peut ne pas avoir de valeur du tout tant qu on ne l a pas affect e Dans les autres langages les variables non encore affect es sont consid r es comme valant z ro Et cette valeur justement ne varie pas proprement parler du moins ne varie t elle que lorsqu elle est l objet d une instruction d affectation La deuxi me remarque concerne le signe de l af
21. a tris la programmation de l acc s s quentiel celle d l acc s direct vous appara tra comme une ineffable poilade 3 Instructions Si l on veut travailler sur un fichier texte la premi re chose faire est de l ouvrir Cela se fait en attribuant au fichier un num ro de canal On ne peut ouvrir qu un seul fichier par canal mais on dispose toujours de plusieurs canaux dont pas de soucis L important est que lorsqu on ouvre un fichier on stipule ce qu on va en faire lire crire ou ajouter e Si on ouvre un fichier pour lecture on ne pourra que r cup rer les informations qu il contient sans les modifier en aucune mani re e Si on ouvre un fichier pour criture on pourra mettre dedans toutes les informations que l on veut Mais les informations pr c dentes si elles existent seront int gralement cras es e Si on ouvre un fichier pour ajout on ne peut ni lire ni modifier les infos existantes Mais on pourra comme vous commencez vous en douter ajouter de nouveaux enregistrements Au premier abord ces limitations peuvent sembler infernales Mais avec un peu d habitude on se rend compte qu en fait on peut faire tout ce qu on veut avec ces fichiers s quentiels Pour ouvrir un fichier texte on crira par exemple wWwWw jeremyazoulay com 28 Ouvrir Exemple txt sur 4 pour Lecture Ici Exemple txt est le nom du fichier sur le disque dur 4 est le num ro de canal et ce fichier a donc t ouvert
22. a proc dure principale et ces groupes d instructions auxquels on a recours s appellent des sous proc dures Reprenons cet exemple de question laquelle l utilisateur doit r pondre par oui ou par non Mauvaise Structure Ecrire Etes vous mari Rep LLL TantQue Rep lt gt Oui et Rep lt gt Non Ecrire Tapez Oui ou Non Lire Rep FinTantQue Ecrire Avez vous des enfants Rep mn TantQue Rep lt gt Oui et Rep lt gt Non Ecrire Tapez Oui ou Non Lire Rep FinTantQue Bonne Structure Ecrire Etes vous mari 7 R ponseOuiNon Ecrire Avez vous des enfants R ponseOuiNon Proc dure R ponseOuiNon Rep nn TantQue Rep lt gt Oui et Rep lt gt Non Ecrire Tapez Oui ou Non Lire Rep FinTantQue Fin Proc dure Dans ce cas on se contente donc d appeler des lignes de codes qui se r p tent l identique Mais on peut avoir des cas beaucoup plus rigolos 2 Passage de param tres wwWw jeremyazoulay com 31 Reprenons l exemple qui pr c de et analysons le Nous crivons un message puis appelons la proc dure pour poser une question puis plus tard on crit un autre message et on relance la proc dure pour poser la m me question etc C est une d marche acceptable mais qui peut encore tre am lior e puisqu avant chaque question on doit crire un message autant que cette criture du message figure directement dans la proc dure appel
23. absolue est qu ils peuvent comporter des lettres et des chiffres mais qu ils excluent la plupart des signes de ponctuation en particulier les espaces Un nom de variable correct commence imp rativement par une lettre Quant au nombre maximal de signes pour un nom de variable il d pend du langage utilis En pseudo code algorithmique on est bien s r libre du nombre de signes pour un nom de variable m me si pour des raisons purement pratiques et au grand d sespoir de St phane Bern on vite g n ralement les noms rallonge 2 Type des variables Il ne suffit pas de cr er une bo te r server un emplacement m moire encore doit on pr ciser ce que l on voudra mettre dedans car de cela d pendent la taille de la bo te de l emplacement m moire et le type de codage utilis 2 1 Types num riques classiques Commen ons par le cas le plus fr quent celui d une variable destin e recevoir des nombres Si l on r serve un octet pour coder un nombre on ne pourra coder que 28 256 valeurs diff rentes Cela peut signifier par exemple les nombres entiers de 1 256 ou de 0 255 ou de 127 128 c est une pure question de convention Mais ce qui n est pas une convention c est qu on est limit 256 valeurs possibles Si l on r serve deux octets on a droit 65 536 valeurs avec trois octets 16 777 216 etc Et l se pose un autre probl me ce codage doit il repr senter des nombres d cimaux d
24. ainsi Structure n 2 Fonfec Sophie 0142156487fonfec yahoo fr Z tofrais M lanie 0456912347z tofrais free fr Herbien Jean Philippe 0289765194vantard ree fr Herg bel Octave 0149875231rg aol fr La structure n 1 est dite d limit e Elle utilise un caract re de d limitation qui permet de rep rer quand commence un champ et quand commence le suivant Il va de soi que ce caract re de d limitation doit tre strictement interdit l int rieur de chaque champ faute de quoi la structure devient proprement illisible La structure n 2 elle est dite champs de largeur fixe I n y a pas de caract re de d limitation mais on sait que les x premiers caract res de chaque ligne stockent le nom les y suivants le pr nom etc Cela impose bien entendu de ne pas saisir un renseignement plus long que le champ pr vu pour l accueillir e L avantage de la structure n 1 est son faible encombrement en place m moire il n y a aucun espace perdu et un fichier texte cod de cette mani re occupe le minimum de place possible Mais elle poss de en revanche un inconv nient majeur qui est la lenteur de la lecture En effet chaque fois que l on r cup re une ligne dans le fichier il faut alors parcourir un par un tous les caract res pour rep rer chaque occurrence du caract res de s paration avant de pouvoir d couper cette ligne en diff rents champs e La structure n 2 l inverse gaspille de la place m moire puisque le fi
25. ais faux L ordinateur tourne alors dans la boucle comme un d rat et n en sort plus Seule solution quitter le programme avec un d monte pneu ou un b ton de dynamite Cette faute de programmation grossi re mais fr quente ne manquera pas d gayer l ambiance collective de cette formation et accessoirement d tancher la soif proverbiale de vos enseignants 3 Boucler en comptant ou compter en bouclant Dans le dernier algorithme vous avez remarqu qu une boucle tait fr quemment utilis e pour augmenter la valeur d une variable Il arrive galement tr s souvent qu on ait besoin d effectuer un nombre d termin de passages Or a priori notre structure TantQue ne sait pas l avance combien de tours de boucle elle va effectuer cela d pend d une condition C est pourquoi une autre structure de boucle est notre disposition Variable Truc en Entier Truc amp 0 TantQue Truc lt 15 Tes Truck I Ecrire Passage num ro Truc FinTantQue Equivaut Variable Truc en Entier Pour Truc 1 15 Ecrire Passage num ro Truc Truc Suivant Au sens strict on pourrait donc s en dispenser mais c est tellement agr able de faire moins d efforts 4 Des boucles dans des boucles On rigole on rigole De m me que les poup es russes contiennent d autres poup es russes de m me qu une structure SI ALORS peut contenir d autres structures SI ALORS une boucle peut cont
26. ation non structur e Dans ce cas les lignes ne sont pas d sign es par des num ros mais certaines peuvent tre rep r es par des noms dits tiquettes et on dispose d une instruction de branchement Une r gle d hygi ne absolue est de programmer syst matiquement de mani re structur e sauf imp ratif contraire fix par le langage wWwWw jeremyazoulay com 36 Autrement dit m me quand un langage vous offre une possibilit de faire des entorses la programmation structur e il ne faut s en saisir sous aucun pr texte 2 Interpr tation et compilation Avec ce paragraphe on sort un peu de l algorithmique proprement dite pour entrer dans le domaine plus technique de la r alisation pratique Ou si l on pr f re ces derni res lignes sont l apoth ose le bouquet final l extase ultime la cons cration grandiose de ce cours En toute modestie bien s r Jusqu ici nous avons travaill sur la premi re tape de la r alisation d un programme Si l algorithme est bien crit sans faute logique l tape suivante ne doit normalement poser aucun probl me conceptuel C est une simple traduction que vous devez effectuer A partir de l votre travail est virtuellement termin si l on excepte l in vitable phase de tests corrections etc Mais pour l ordinateur c est l que les ennuis commencent En effet aucun ordinateur n est en soi apte ex cuter les instructions telles qu elles sont
27. cases valables sont celles d indice i 7 et i 9 De m me la case situ e juste en dessous ayant comme indice i 8 les cases valables sont celles d indice i 7 et i 9 Bien s r on peut fabriquer tout un programme comme cela mais le moins qu on puisse dire est que cela ne facilite pas la clart de l algorithme Il serait videmment plus simple de mod liser un damier par un damier 2 Tableaux deux dimensions L informatique nous offre la possibilit de d clarer des tableaux dans lesquels les valeurs ne sont pas rep r es par une seule mais par deux coordonn es Un tel tableau se d clare ainsi Tableau Cases 8 8 en Entier Cela veut dire r serve moi un espace de m moire pour 8 x 8 entiers et quand j aurai besoin de l une de ces valeurs je les rep rerai par deux indices comme la bataille navale ou Excel la seule diff rence tant que pour les coordonn es on n utilise pas de lettres juste des chiffres Pour notre probl me de dames les choses vont s rieusement s claircir La case qui contient le pion est dor navant Cases i j Et les quatre cases disponibles sont Cases i 1 j 1 Cases i 1 j 1 Cases i 1 j 1 et Cases i 1 j 1 Une remarque il n y a aucune diff rence qualitative entre un tableau deux dimensions i j et un tableau une dimension i j De m me que le jeu de dames qu on vient d voquer tout probl me pouvant tre mod lis d une mani re peut aussi tre mod li
28. chier est un vrai gruy re plein de trous Mais d un autre c t la r cup ration des diff rents champs est tr s rapide Lorsqu on r cup re une ligne il suffit de la d couper en diff rentes cha nes de longueur pr d finie et le tour est jou wwWw jeremyazoulay com 27 A l poque o la place m moire co tait cher la structure d limit e tait privil gi e Mais depuis bien des ann es la quasi totalit des logiciels et des programmeurs optent pour la structure en champs de largeur fixe Aussi sauf mention contraire nous ne travaillerons qu avec des fichiers b tis sur cette structure 2 Types d acc s On vient de voir que l organisation des donn es au sein du fichier pouvait s effecteur selon deux grands choix strat giques Mais il existe une autre ligne de partage des fichiers le type d acc s autrement dit la mani re dont la machine va pouvoir aller rechercher les enregistrements On distingue e L acc s s quentiel on ne peut acc der qu l enregistrement suivant celui qu on vient de lire e L acc s direct ou al atoire on peut acc der directement l enregistrement de son choix en pr cisant le num ro de cet enregistrement A la diff rence de la pr c dente cette typologie ne se refl te pas dans la structure elle m me du fichier En fait tout fichier quelle que soit sa structure d limit ou en largeur fixe peut tre utilis avec l un ou l autre des deux grands
29. construite partir de quatre l ments invariables Ce n est que le nombre de ces l ments et l ordre dans lequel ils sont arrang s qui va d terminer si on obtient une puce ou un l phant Et tous autant que nous sommes splendides r ussites de la Nature avons t construits par un programme constitu uniquement de ces quatre briques ce qui devrait nous inciter la modestie Enfin les ordinateurs quels qu ils soient ne sont fondamentalement capables d ex cuter que quatre op rations logiques je n inclus pas ici les op rations de calcul Ces op rations sont l affectation de variables la lecture criture les tests les boucles Un algorithme informatique se ram ne 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 n irons pas jusque l cependant la taille d un algorithme ne conditionne pas en soi sa complexit de longs algorithmes peuvent tre finalement assez simples et de petits tr s compliqu s 5 Algorithmique et programmation Pourquoi apprendre l algorithmique pour apprendre programmer En quoi a t on besoin d un langage sp cial distinct des langages de programmation compr hensibles par les ordinateurs Parce que l algorithmique exprime les instructions r solvant
30. crire un algorithme aussi lourd qu une blague des Grosses T tes on n en sortira pas il y aura toujours moyen qu un acharn flanque le programme par terre C est donc une impasse 2 Une premi re structure de boucle La seule issue est donc cette structure de boucle qui se pr sente ainsi TantQue bool en Instructions FinTantQue Le principe est simple le programme arrive sur la ligne du TantQue Il examine alors la valeur du bool en qui je le rappelle peut tre une variable bool enne ou plus fr quemment une condition Si cette valeur est VRAI le programme ex cute les instructions qui suivent jusqu ce qu il rencontre la ligne FinTantQue Il retourne ensuite sur la ligne du TantQue proc de au m me examen et ainsi de suite Le man ge enchant ne s arr te que lorsque le bool en prend la valeur FAUX Illustration avec notre probl me de contr le de saisie Variable Rep en Caract re Ecrire Voulez vous un caf O N TantQue Rep lt gt O ET Rep lt gt N Lire Rep wWwWw jeremyazoulay com 17 Si Rep lt gt O ET Rep lt gt N Alors Ecrire Saisie erronn e Recommencez FinsSi FinTantQue On remarquera que la pr sence du bloc Si est uniquement l pour l affichage ventuel du libell de saisie erron e En lui m me le bloc tant que est d une simplicit biblique Le gag de la journ e c est d crire une structure TantQue dans laquelle le bool en ne devient jam
31. e fonctions est un puissant outil de programmation qui ne poss de que des avantages on conomise des lignes de programmation on rend le d boguage plus facile et on ne gaspille aucune ressource de la machine Pensez y donc s rieusement chaque fois que vous devez cr er une application un peu joufflue un projet par exemple 4 Une logique vicelarde la programmation r cursive wwWw jeremyazoulay com 33 Vous savez comment sont les informaticiens on ne peut pas leur donner quoi que ce soit sans qu ils essayent de jouer avec et le pire c est qu ils y r ussissent Cette technique des fonctions personnalis es a donn lieu la floraison d une logique un peu particuli re destin e en particulier traiter certains probl mes math matiques ou de jeux la programmation r cursive Pour vous expliquer de quoi il retourne nous allons reprendre un exemple cher vos c urs le calcul d une factorielle l je sentais que j allais encore me faire des copains Rappelez vous la formule de calcul de la factorielle d un nombre n s crit NI TXEeXS3Xx 3eN Nous avions programm cela aussi sec avec une boucle Pour et roule Raoul Mais une autre mani re de voir les choses ni plus juste ni moins juste serait de dire que N n x n 1 En bon fran ais la factorielle d un nombre c est ce nombre multipli par la factorielle du nombre pr c dent Encore une fois c est une mani re ni plus juste ni moins ju
32. e rentrer des valeurs au clavier pour qu elles soient utilis es par le programme Cette op ration est la lecture Dans l autre sens cela permet au programme de communiquer des valeurs l utilisateur en les affichant l cran Cette op ration est l criture 2 Une remarque essentielle A premi re vue on peut avoir l impression que les informaticiens taient bourr s comme des vaches lorsqu ils ont baptis s ces op rations lorsque l utilisateur doit crire au clavier on appelle a la lecture et lorsqu il doit lire sur l cran on appelle l criture Mais avant d insulter cette digne corporation il faut r fl chir un peu plus Un algorithme cela programme la machine pas l utilisateur Donc quand on dit la machine de lire une valeur cela implique que l utilisateur va devoir l crire Et quand on demande la machine d crire cette valeur c est pour que l utilisateur puisse la lire Et toc 3 Les instructions de lecture et d criture Tout b tement pour que l utilisateur entre la nouvelle valeur de Titi on mettra Lire Titi D s que le programme tombe sur cette instruction l ex cution s arr te l ordinateur attend sagement que l utilisateur ait frapp quelque chose au clavier et d s que la touche Enter a t frapp e l ex cution reprend Pour crire quelque chose l cran c est aussi simple que Ecrire Toto On peut galement choisir d crire des libell s l cran afin de pr
33. enir d autres boucles Variables Truc Trac en Entier Pour Truc amp 1 15 Ecrire Il est pass par ici Pour Trac amp 1 6 Ecrire Il repassera par l Trac Suivant Truc Suivant Dans cet exemple le programme crira une fois il est pass par ici puis six fois de suite il repassera par l et ceci quinze fois en tout A la fin il y aura donc eu 15 x 6 90 passages dans la deuxi me boucle celle du milieu wwWw jeremyazoulay com 18 Notez la diff rence marquante avec cette structure Variables Truc Trac en Entier Pour Truc amp 1 15 Ecrire Il est pass par ici Truc Suivant Pour Trac amp 1 6 Ecrire Il repassera par l Trac Suivant Ici il y aura quinze critures cons cutives de il est pass par ici puis six critures cons cutives de il repassera par l et ce sera tout Si des boucles peuvent tre imbriqu es cas n 1 ou successives cas n 2 elles ne peuvent jamais au grand jamais tre crois es Cela n aurait aucun sens logique et de plus bien peu de langages vous autoriseraient ne serait ce qu crire cette structure aberrante Variables Truc Trac en Entier Pour Truc instructions Pour Trac amp instructions Truc Suivant instructions Trac Suivant 5 Et encore une tourn e g n rale Examinons l algorithme suivant Variable Truc en Entier Pour Truc amp 1 15 Teuck REEUC Re Ecrire Passage num ro Truc
34. es nombres n gatifs Bref le type de codage autrement dit le type de variable choisi pour un nombre va d terminer e les valeurs maximales et minimales des nombres pouvant tre stock s dans la variable e la pr cision de ces nombres dans le cas de nombres d cimaux Tous les langages quels qu ils soient offrent un bouquet de types num riques dont le d tail est susceptible de varier l g rement d un langage l autre Grosso modo on retrouve cependant les types suivants Type Plage Num rique wWwWw jeremyazoulay com 5 Byte octet 0 255 Entier simple 32 768 32 767 Entier long 2 147 483 648 2 147 483 647 R el simple 3 40E38 1 40E 45 pour les valeurs n gatives 1 40E 45 3 40E38 pour les valeurs positives R el double 1 79E308 4 94E 324 pour les valeurs n gatives 4 94 324 1 79E308 pour les valeurs positives Pourquoi ne pas d clarer toutes les variables num riques en r el double histoire de b tonner et d tre certain qu il ny aura pas de probl me En vertu du principe de l conomie 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 l abus de variables surdimensionn es peut entra ner des ralentissements notables l ex cution voire un plantage pur et simple Alors autant prendre de bonnes habitudes d hygi ne Une d claration algorithmique de
35. et dont le r sultat final est obligatoirement du m me type que la variable situ e gauche Si l un de ces points n est pas respect la machine sera incapable d ex cuter l affectation et d clenchera une erreur est il besoin de dire que si aucun de ces points n est respect il y aura aussi erreur Revenons maintenant sur ce terme d op rateurs Un op rateur est un signe qui peut relier deux valeurs pour produire un r sultat Les op rateurs possibles d pendent du type des valeurs qui sont en jeu Allons y faisons le tour c est un peu fastidieux mais comme dit le sage quand c est fait c est plus faire Op rateurs num riques Ce sont les quatre op rations arithm tiques tout ce qu il y a de classique addition z soustraction multiplication division Mentionnons galement le qui signifie puissance 45 au carr s crira donc 45 2 Enfin on a le droit d utiliser les parenth ses avec les m mes r gles qu en math matiques La multiplication et la division ont naturellement priorit sur l addition Les parenth ses ne sont ainsi utiles que pour modifier cette priorit naturelle Cela signifie qu en informatique 12 3 5 et 12 3 5 valent strictement la m me chose savoir 41 Pourquoi d s lors se fatiguer mettre des parenth ses inutiles En revanche 12 3 5 vaut 12 8 soit 96 Rien de difficile l dedans que du normal Op rateur alphanum rique amp
36. fectation En algorithmique comme on l a vu c est le amp Mais en pratique la quasi totalit des langages emploient le signe gal Et l pour les d butants la confusion est facile avec les maths En maths B et B A sont deux propositions strictement quivalentes En informatique absolument pas puisque cela revient crire A amp Bet B A deux choses bien diff rentes Donc attention Vi wwWw jeremyazoulay com 9 Il Lecture criture 1 De quoi parle t on Trifouiller des variables en m moire vive par un chouette programme c est vrai que c est tr s rigolo et on a tous bien ri Cela dit la fin de la foire on peut tout de m me se demander quoi a sert En effet Imaginons que nous ayons fait un programme pour calculer le carr d un nombre mettons 12 Si on a fait au plus simple on a crit un truc du genre Exemple Variable en Num rique D but A lt 1212 Fin Ce gentil programme nous donne le carr de 12 Mais si l on veut le carr d un autre nombre que 12 il faut r crire le programme Bof D autre part le r sultat est tr s certainement calcul par la machine Mais elle le garde soigneusement pour elle et le pauvre utilisateur qui fait ex cuter ce programme lui ne saura jamais quel est le carr de 12 Re bof C est pourquoi un certain nombre d instructions permettent la machine de dialoguer avec l utilisateur Dans un sens cela permet l utilisateur d
37. final Consid rons les deux algorithmes suivant notez que ce sont les premiers algorithmes complets que nous examinerons comme quoi on avance Variable A en Entier Variable A en Entier D but D but Ag34A lt amp 12 A amp 12A lt 34 Fin Fin Il est clair que dans le premier cas la valeur finale de A est 12 dans l autre elle est 34 Il est tout aussi clair que ceci ne doit pas nous tonner Lorsqu on indique le chemin quelqu un dire prenez tout droit sur 1km puis droite n envoie pas les gens au m me endroit que si l on dit prenez droite puis tout droit pendant 1 km Enfin il est galement clair que si l on met de c t leur vertu p dagogique les deux algorithmes ci dessus sont parfaitement idiots tout le moins ils contiennent une incoh rence Il n y a aucun int r t affecter une variable pour l affecter diff remment juste apr s En l occurrence on aurait tout aussi bien atteint le m me r sultat en crivant simplement Variable A en Entier Variable A en Entier D but D but wwWw jeremyazoulay com 7 A amp 12A 34 Fin Fin Eh bien maintenant vous de jouer 3 3 Expressions et op rateurs Si on fait le point on s aper oit que dans une instruction d affectation on trouve gauche de la fl che un nom de variable et uniquement cela droite de la fl che ce qu on appelle une expression C est dire un ensemble de valeurs li es par des op rateurs
38. il ouvrir la fen tre de la salle Uniquement si les conditions l imposent savoir Si il fait trop chaud ET il ne pleut pas Alors Ouvrir la fen tre Sinon Fermer la fen tre Finsi Cette petite r gle pourrait tout autant tre formul e comme suit Si il ne fait pas trop chaud OU il pleut Alors Fermer la fen tre Sinon Ouvrir la fen tre Finsi Ces deux formulations sont strictement quivalentes Ce qui nous am ne la conclusion suivante toute structure de test requ rant une condition compos e faisant intervenir l op rateur ET peut tre exprim e de mani re quivalente avec un op rateur OU et r ciproquement Ceci est moins surprenant qu il n y para t au premier abord Jetez pour vous en convaincre un il sur les tables de v rit et vous noterez la sym trie entre celle du ET et celle du OU Bien s r on ne peut pas se contenter de remplacer purement et simplement les ET par des OU ce serait un peu facile La r gle d quivalence est la suivante on peut la v rifier sur l exemple de la fen tre Si ET B Alors Si NON A OU NON B Alors IrSbouctions ins teuctAons2 Sinon Sinon Taser ucte tons 2 MSC LLONS l Finsi Finsi wwWw jeremyazoulay com 16 IV Les boucles Et a y est on y est on est arriv s la voil c est Broadway la quatri me et derni re structure a est les boucles Si vous voulez pater vos amis vous pouvez galement parler de structures r p titives voire
39. in souvent on dispose galement de Trouve cha nel renvoie un nombre correspondant la position de cha ne2 dans cha ne1 Si cha ne n est cha ne2 pas comprise dans cha nel la fonction renvoie z ro wWwWw jeremyazoulay com 25 Exemples Len Bonjour a va vaut 16 Len vaut 0 Mid Zorro is back 4 6 vaut o esta Mid Zorro is back 12 1 vaut r Left Et pourtant 8 vaut Et pourt Right Et pourtant 4 vaut ta Trouve Un pur bonheur pur vaut 3 Trouve Un pur bonheur techno vaut 0 Il existe aussi dans tous les langages une fonction qui renvoie le caract re correspondant un code Ascii donn fonction Asc et Lyc e de Versailles fonction Chr Asc N vaut 78 Chr 63 vaut Avec tout on va faire des miracles 3 Deux fonctions classiques Une fonction extr mement r pandue est celle qui permet de r cup rer la partie enti re d un nombre Apr s A amp Ent 3 228 A vaut 3 Cette fonction est notamment indispensable pour effectuer le c l brissime test de parit voir exercice dans pas longtemps Une autre fonction classique car tr s utile est celle qui g n re un nombre choisi au hasard Tous les programmes de jeu ou presque ont besoin de ce type d outils qu il s agisse de simuler un lancer de d s ou le d placement chaotique du vaisseau spatial de l enfer de la mort pilot par l inf me Zorglub qui veut faire main basse sur l Univers heu
40. instruction qui envoie directement le programme la ligne sp cifi e Inversement ce type de langage ne comporte pas d instructions comme FinTantQue ou FinSi qui ferment un bloc Prenons l exemple d une structure Si Alors Sinon Programmation Structur e Si condition Alors instructions 1 Sinon instructions 2 FinSi Programmation non structur e 1000 Si condition Alors Aller En 1100 Sinon Aller En 1200 1100 instruction 1 1110 etc 1120 etc 1190 Aller en 1400 1200 instruction 2 1210 etc 1220 etc 1350 Aller en 1400 1400 suite de l algorithme Vous voyez le topo un programme crit dans ce type de langages se pr sente comme une suite de branchements emm l s les uns des les autres D une part on ne peut pas dire que cela favorise la lisibilit du programme D autre part c est une source importante d erreurs car t t ou tard on oublie un aller ou on un met un de trop etc A fortiori lorsqu on complique un algorithme existant cela peut devenir un jungle inextricable A l inverse la programmation structur e surtout si l on prend soin de rationaliser la pr sentation en mettant des lignes de commentaires et en pratiquant l indentation vite des erreurs et se r v le sa structure logique de mani re tr s claire Le danger est que si la plupart des langages de programmation utilis s sont structur s ils offrent tout de m me la plupart du temps la possibilit de pratiquer la programm
41. la premi re ligne Si Alors la machine examine la valeur du bool en Si ce bool en a pour valeur VRAI elle ex cute la s rie d instructions 1 Cette s rie d instructions peut tre tr s br ve comme tr s longue cela n a aucune importance A la fin de cette s rie d instructions au moment o elle arrive au mot Sinon la machine sautera directement la premi re instruction situ e apr s le Finsi De m me au cas o le bool en avait comme valeur Faux la machine saute directement la premi re ligne situ e apr s le Sinon et ex cute l ensemble des instructions 2 La forme simplifi e correspond au cas o l une des deux branches du Si est vide D s lors plut t qu crire sinon ne rien faire du tout il est plus simple de ne rien crire Exprim sous forme de pseudo code la programmation de notre touriste de tout l heure donnerait donc quelque chose du genre wwWw jeremyazoulay com 12 Exemple Allez tout droit jusqu au prochain carrefour Si la rue droite est autoris e la circulation Alors Tournez droite Avancez Prenez la deuxi me gauche Sinon Continuez jusqu la prochaine rue droite Prenez cette rue Prenez la premi re droite Fin si 3 Qu est ce qu une condition Une condition est une comparaison Cette d finition est essentielle C est dire qu elle est compos e de trois l ments e une valeur e un op rateur de comparaison
42. leaux contenant des variables de tous types tableaux de num riques bien s r mais aussi tableaux de caract res de bool ens de tout ce qui existe dans un langage donn comme type de variables Par contre hormis dans quelques rares langages on ne peut pas faire un mixage de types diff rents de valeurs au sein d un m me tableau L norme avantage des tableaux c est qu on va pouvoir les traiter en faisant des boucles Par exemple pour effectuer notre calcul de moyenne cela donnera Tableau Note 12 en Entier Variables i Som en Entier Variable Moy en R el Som amp 0 Pour i 1 12 Som Som Note 1 i Suivant Moy Som 12 wwWw jeremyazoulay com 20 NB Cet exemple ne peut tre qu un extrait dans la mesure o on n a pas programm comment s effectue le remplissage des valeurs du tableau L indice qui sert rep rer les l ments du tableau peut tre exprim directement comme un nombre en clair mais il peut tre aussi une variable ou une expression calcul e La valeur d un indice doit toujours e tre gale au moins 0 ou 1 dans certains langages le premier l ment d un tableau porte l indice z ro dans d autres l indice 1 tre un nombre entier Quel que soit le langage l l ment Truc 3 1416 n existe jamais tre inf rieure ou gale au nombre d l ments du tableau Si le tableau Bidule a t d clar comme ayant 25 l ments la pr sence dans une ligne
43. lle est en sens interdit alors continuez jusqu la prochaine droite prenez celle l et ensuite la premi re droite Ce deuxi me algorithme a ceci de sup rieur au premier qu il pr voit en fonction d une situation pouvant se pr senter de deux fa ons diff rentes deux fa ons alternatives d agir Cela suppose que l interlocuteur le touriste sache analyser la condition que nous avons fix e son comportement la rue est elle en sens interdit pour effectuer la s rie d actions correspondante Eh bien croyez le ou non mais les ordinateurs poss dent cette aptitude sans laquelle d ailleurs nous aurions bien du mal les programmer Nous allons donc pouvoir parler notre ordinateur comme notre touriste et lui donner des s ries d instructions effectuer selon que la situation se pr sente d une mani re ou d une autre 2 Structure d un test Il ny a que deux formes possibles pour un test la forme de gauche est la forme compl te celle de droite la forme simple Si bool en Alors Si bool en Alors MsSbrueLtions l Imat verrons Sinon Finsi Instructions 2 Finsi Un bool en est une expression dont la valeur est VRAI ou FAUX Cela peut donc tre il ny a que deux possibilit s e une variable de type bool en e une condition Nous reviendrons dans quelques instants sur ce qu est une condition en informatique Toujours est il que la structure d un test est relativement claire Arriv
44. n au del des ouvertures et fermetures de proc dures La mani re dont ces d clarations doivent tre faites est videmment fonction de chaque langage de programmation En pseudo code algorithmique vous pourrez utiliser le mot cl Public pour d clarer une variable publique Public Toto en Entier Comment choisir entre d clarer une variable en Public ou en Priv C est tr s simple les variables globales consomment norm ment de ressources en m moire En cons quence le principe qui doit pr sider au choix entre variables publiques et priv es doit tre celui de l conomie de moyens on ne d clare comme publiques que les variables qui doivent absolument l tre Et chaque fois que possible lorsqu on cr e une sous proc dure on utilise le passage de param tres par valeur plut t que des variables publiques 6 Algorithmes fonctionnels Pour clore ce chapitre quelques mots propos de la structure g n rale d une application Celle ci va couramment tre form e d une proc dure principale et de sous proc dures qui vont au besoin elles m mes en appeler d autres etc L exemple typique est celui d un menu ou d un sommaire qui branche sur diff rents traitements donc diff rentes sous proc dures L algorithme fonctionnel de l application est la repr sentation graphique de cette structure g n rale ayant comme objectif de faire comprendre d un seul coup d il quelle proc dure fait quoi et quelle
45. notre probl me car arriv au calcul cela donnera obligatoirement une atrocit du genre Moy N1 N2 N3 N4 N5 N6 N7 N8 N9 N10 N11 N12 12 Ouf C est tout de m me bigrement laborieux Et pour un peu que nous soyons dans un programme de gestion avec quelques centaines ou quelques milliers de valeurs traiter alors l c est direct le suicide Cerise sur le g teau pour peu que l on ne puisse savoir d avance combien il y aura de valeurs traiter l on est carr ment cuits C est pourquoi la programmation nous permet de rassembler toutes ces variables en une seule au sein de laquelle chaque valeur sera d sign e par un num ro En bon fran ais cela donnerait donc quelque chose du genre la note num ro 1 la note num ro 2 la note num ro 8 C est largement plus pratique vous vous en doutez Un ensemble de valeurs portant ainsi le m me nom de variable et rep r es par un nombre s appelle un tableau ou encore une variable indic e Et le nombre qui sert rep rer chaque valeur s appelle surprise un indice 2 Notation et utilisation algorithmique Dans notre exemple nous cr erons donc un tableau appel Note ou N si on veut aller plus vite Et chaque note individuelle sera d sign e Note 1 Note 2 etc Un tableau doit tre d clar comme tel en pr cisant le nombre et le type de valeurs qu il contiendra Tableau Note 12 en Entier On peut cr er des tab
46. proc dure appelle quelle autre L algorithme fonctionnel est donc en quelque sorte la repr sentation du squelette de l application II se situe un niveau plus g n ral plus abstrait que l algorithme normal qui lui d taille pas pas les traitements effectu s au sein de chaque proc dure Dans la construction et la compr hension d une application les deux documents sont indispensables et constituent deux tapes successives de l laboration d un projet wwWw jeremyazoulay com 35 X Notions compl mentaires Une fois n est pas coutume ce chapitre ne sera l objet d aucun exercice Cela ne veut pas dire pour autant que ce qui s y trouve n est pas int ressant Non mais des fois 1 Programmation structur e Petit retour sur une notion tr s rapidement survol e plus haut celle de programmation structur e En fait nous avons jusqu pr sent tels Monsieur Jourdain fait de la programmation structur e sans le savoir Aussi plut t qu expliquer longuement en quoi cela consiste je pr f re passer directement raconter en quoi cela ne consiste pas Dans certains langages historiquement ce sont g n ralement des langages anciens les lignes de programmation portent des num ros Les lignes sont ensuite ex cut es dans l ordre de leurs num ros Jusqu ici en soi pas de probl me Mais l astuce est que tous ces langages il existe une instruction de branchement not e aller en pseudo code
47. qu on crit une s rie d instructions qu on croit justes il faut se mettre la place de la machine qui va les ex cuter pour v rifier si le r sultat obtenu est bien celui que wWwWw jeremyazoulay com 3 l on voulait Mais cette op ration ne requiert pas la moindre once d intelligence uniquement d tre m thodique e il faut avoir une certaine intuition car aucune recette ne permet de savoir a priori quelles instructions permettront d obtenir le r sultat voulu C est l si l on y tient qu intervient la forme d intelligence requise pour l algorithmique Alors c est certain il y a des gens qui ont au d part davantage cette intuition que les autres Mais mais d une part les r flexes cela s acquiert et l exp rience finit par compenser largement bien des intuitions D autre part pour tre bon en algo il ne faut pas oublier le point num ro 1 4 L ADN les Shadoks et les ordinateurs Quel rapport me direz vous Eh bien le point commun est quatre mots de vocabulaire L univers lexical Shadok c est bien connu se limite aux termes Ga Bu Zo et Meu Ce qui leur a tout de m me permis de formuler quelques fortes maximes telles que Mieux vaut pomper et qu il ne se passe rien plut t qu arr ter de pomper et risquer qu il se passe quelque chose de pire L ADN qui est en quelque sorte le programme g n tique l algorithme la base de construction des tres vivants est une cha ne
48. question pos e Examinons maintenant ce probl me Une premi re solution serait la suivante juste apr s l appel de la proc dure on teste la variable Rep Si Rep Oui alors L inconv nient de cette technique c est que la variable Rep doit pouvoir conserver son contenu en voyageant d une proc dure l autre On en reparlera plus loin mais ce genre de variable est extr mement gourmand en m moire vive Donc si on appelle comme cela plusieurs proc dures avec plein de variables qu on veut r cup rer cela risque de coincer s rieusement l ex cution La solution la plus conomique en ressources consiste transmettre la valeur de la variable Rep de la sous proc dure vers la proc dure principale exactement comme on transmettait jusque l la valeur de la variable Msg de la proc dure principale vers la sous proc dure On introduit donc un second param tre mais qui est maintenant un param tre en sortie wwWw jeremyazoulay com 32 La d claration de la proc dure devient Proc dure R ponseOuiNon Msg en Caract re Rep en Bool en L appel devient quant lui R ponseOuiNon Etes vous mari toto si toto Oui alors R ponseOuiNon Avez vous des enfants tata si tata Oui alors L encore rien n emp che une sous proc dure de renvoyer plusieurs param tres en sortie vous avez toute libert 3 Fonctions personnalis es Si vous n avez qu un seul param tre renvoyer en
49. r t le gain est couramment d un facteur 10 voire 20 ou plus Toute application destin e un usage professionnel ou m me tout simplement s rieux est forc ment une application compil e
50. r l utilisateur Mais videmment cela ne suffit pas aux besoins r els Imaginons que l on veuille crire un programme g rant un carnet d adresses D une ex cution l autre l utilisateur doit pouvoir retrouver son carnet jour avec les modifications qu il y a apport es la derni re fois qu il a ex cut le programme Les donn es du carnet d adresse ne peuvent donc tre inclues dans l algorithme et encore moins tre entr es au clavier chaque nouvelle ex cution Les fichiers sont l pour combler ce manque lls servent stocker des informations de mani re permanente entre deux ex cutions d un programme Car si les variables qui sont je le rappelle des adresses de m moire vive disparaissent chaque fin d ex cution les fichiers eux sont stock s sur des p riph riques m moire de masse disquette disque dur CD Rom 1 Organisation des fichiers texte Il existe deux grandes variantes pour structurer les donn es au sein d un fichier texte la d limitation ou les champs de largeur fixe Reprenons le cas du carnet d adresse Nous nous limiterons aux renseignements suivants Nom pr nom t l phone e mail Les donn es sur le fichier texte peuvent tre organis es ainsi Structure n 1 Fonfec Sophie 0142156487 fonfec yahoo fr Z tofrais M lanie 0456912347 z tofrais free fr Herbien Jean Philippe 0289765194 vantard free fr Herg bel Octave 0149875231 rg aol fr ou
51. reusement vous tes l pour l en emp cher ouf Mais il ny a pas que les jeux qui ont besoin de g n rer des nombres al atoires La mod lisation physique g ographique conomique etc a parfois recours des mod les dits stochastiques chouette encore un nouveau mot savant Ce sont des mod les dans lesquels les variables se d duisent les unes des autres par des relations d terministes autrement dit des calculs mais o l on simule la part d incertitude par une fourchette de hasard Par exemple un mod le d mographique supposera qu une femme a en moyenne x enfants au cours de sa vie mettons 1 5 Mais il supposera aussi que sur une population donn e ce chiffre peut fluctuer entre 1 35 et 1 65 si on laisse une part d incertitude de 10 Chaque ann e c est dire chaque s rie de calcul des valeurs du mod le on aura ainsi besoin de faire choisir la machine un nombre au hasard compris entre 1 35 et 1 65 Dans tous les langages cette fonction existe et produit le r sultat suivant Apr s Toto Alea 0 lt Toto lt 1 Il est indispensable d apprendre manier cette fonction alors autant que ce soit fait wwWw jeremyazoulay com 26 VIII Les fichiers s quentiels Jusqu pr sent les informations utilis es dans nos programmes ne pouvaient provenir que de deux sources soit elles taient inclues dans l algorithme lui m me par le programmeur soit elles taient entr es en cours de route pa
52. ri cette technique ne pr sente gu re d int r t on a alourdi plut t qu all g l algorithme de d part en lui faisant recourir deux variables suppl mentaires Mais e une variable bool enne n a besoin que d un seul bit pour tre stock e L alourdissement de ce point de vue n est donc pas consid rable e dans certains cas notamment celui de conditions compos es tr s lourdes avec plein de ET et de OU tout partout cette technique peut faciliter le travail du programmeur Les variables bool ennes peuvent wwWw jeremyazoulay com 15 galement s av rer tr s utiles pour servir de flag technique dont on reparlera plus loin rassurez vous rien voir avec le flagrant d lit des policiers 7 Quelques jeux logiques Une remarque pour commencer dans le cas de conditions compos es les parenth ses jouent un r le important Variables A B C D E en Bool en Variable X en Entier D but A ET B OU C A ET B OU C Ecrire D E Fin A B Cax lt 6 D Si X 3 alors on remarque que D sera VRAI alors que E sera FAUX S il n y a que des ET ou que des OU en revanche les parenth ses ne changent strictement rien On en arrive une autre propri t des ET et des OU bien plus int ressante Spontan ment on pense souvent que ET et OU s excluent mutuellement et qu un probl me donn s exprime soit avec un ET soit avec un OU Pourtant ce n est pas si vident Quand faut
53. rs textes ne sont pas l pour servir de bases de donn es en tout cas dans des langages de programmation r cents Donc on aura peu de chances ou de risques de se trouver devant des immenses fichiers textes ne pouvant pas tre mis en tableau Mais ce n est pas une r gle il faut donc bien comprendre les tenants et les aboutissants de chaque strat gie Et pour cela quoi de mieux que la pratique wwWw jeremyazoulay com 30 IX Proc dures et fonctions 1 Sous proc dures Une application surtout si elle est longue a toutes les chances de devoir proc der aux m mes traitements ou des traitements similaires plusieurs endroits de son d roulement Par exemple la saisie et le contr le qu elle implique d une r ponse par oui ou par non peuvent tre r p t s dix fois des moments diff rents de la m me application La mani re la plus imm diate et la moins habile de r soudre la question est bien entendu de r p ter le code correspondant autant de fois que n cessaire Ainsi la structure peut para tre simple Mais elle est inutilement lourdingue et en r alit pour peu que le programme soit joufflu il peut devenir parfaitement illisible Il faut donc opter pour une autre strat gie qui consiste s parer ce traitement du corps du programme et appeler ces instructions qui ne figurent donc plus qu en un seul exemplaire chaque fois qu on en a besoin Le corps du programme s appelle alors l
54. s de l autre Simplement l une ou l autre de ces techniques correspond plus spontan ment tel ou tel probl me et facilite donc ou complique si on a choisi la mauvaise option l criture et la lisibilit de l algorithme Une autre remarque une question classique propos des tableaux deux dimensions est de savoir si le premier indice repr sente les lignes ou le deuxi me les colonnes ou l inverse Je ne r pondrai pas cette question non parce que j ai d cid de bouder mais parce qu elle n a aucun sens Lignes et Colonnes sont des wwWw jeremyazoulay com 23 concepts graphiques qui s appliquent des objets du monde r el les indices des tableaux ne sont que des coordonn es logiques pointant sur des adresses de m moire vive Si cela ne vous convainc pas pensez un jeu de bataille navale classique les lettres doivent elles d signer les lignes et les chiffres les colonnes Aucune importance Chaque joueur peut m me choisir une convention diff rente aucune importance L essentiel est qu une fois une convention choisie un joueur conserve la m me tout au long de la partie bien entendu 3 Tableaux n dimensions Si vous avez compris le principe des tableaux deux dimensions sur le fond il n y a aucun probl me passer au maniement de tableaux trois quatre ou pourquoi pas neuf dimensions C est exactement la m me chose Si je d clare un tableau Titi 3 5 4 4 il s agit d un
55. sortie alors vous pourrez opter pour une solution encore plus l g re cr er plut t qu une sous proc dure une fonction personnalis e Ce type de fonction comme une fonction normale renvoie une valeur Mais cette fois c est vous qui cr ez la fonction en indiquant le nombre et le type des param tres en entr e le mode de traitement et la valeur qui doit tre renvoy e en sortie Imaginons qu plusieurs reprises au cours d une application on ait besoin de calculer la moyenne d un tableau de notes le nombre de notes tant susceptible de varier d une fois sur l autre Plut t qu crire plusieurs boucles de calcul qui chaque fois risquent de se ressembler il sera pr f rable de cr er une fonction pour calculer cette moyenne Cette fonction admettra deux arguments qui lui sont indispensables pour effectuer ses calculs Le tableau lui m me Le nombre d l ments du tableau Cela donnera en pseudo code la chose suivante Fonction Moy Tab en tableau num rique n en entier Som 0 Pour i l n Som Som Tab i i suivant m som n Renvoyer m Fin Fonction On remarque au passage l apparition d un nouveau mot cl Renvoyer qui indique quelle valeur doit prendre la fonction Quant au programme principal quelques lignes pourraient en tre Tableau Notes en Num rique moyenne Moy notes nbnotes crire la moyenne est moyenne D une mani re g n rale la cr ation d
56. sous une forme ou sous une autre de Bidule 26 d clenchera automatiquement une erreur Le gag de la journ e consiste confondre dans sa t te et ou dans un algorithme l indice d un l ment d un tableau avec son contenu La troisi me maison de la rue n a pas forc ment trois habitants et la vingti me vingt habitants En notation algorithmique il n y a aucun rapport entre i et truc i 3 Tableaux dynamiques Il arrive fr quemment que l on ne connaisse pas l avance le nombre d l ments que devra comporter le tableau Bien s r une solution consisterait d clarer un tableau gigantesque 10 000 l ments pourquoi pas au diable les varices pour tre s r que a rentre Mais d une part on n en sera jamais parfaitement s r d autre part en raison de l immensit de la place m moire r serv e et la plupart du temps non utilis e c est un g chis pr judiciable la rapidit de notre algorithme Aussi pour parer ce genre de situation a t on la possibilit de d clarer le tableau sans pr ciser son nombre d l ments puis au cours du programme pr ciser ce nombre via l instruction Redim Notez que tant qu on n a pas pr cis le nombre d l ments d un tableau d une mani re ou d une autre ce tableau est inutilisable Exemple on veut faire saisir des notes pour un calcul de moyenne mais on ne sait pas combien il y aura de notes saisir Le d but de l algorithme sera q
57. ssi s agir de r sultats obtenus par le programme interm diaires ou d finitifs Ces donn es peuvent tre de plusieurs types on en reparlera elles peuvent tre des nombres du texte etc Toujours est il que d s que l on a besoin de stocker une information dans un programme on utilise une variable Pour employer une image une variable est une bo te rep r e par une tiquette Pour avoir acc s au contenu de la bo te il suffit de la d signer par son tiquette En r alit dans la m moire vive de l ordinateur il ny a ni bo te ni tiquette coll e dessus Il y a un emplacement de m moire d sign par une adresse binaire Le langage informatique se charge entre autres r les de vous pargner la gestion fastidieuse de ces emplacements m moire et de leurs adresses Il est beaucoup plus facile d employer les tiquettes de son choix que de devoir manier des adresses binaires La premi re chose faire avant de pouvoir utiliser une variable est de cr er la bo te et de lui coller une tiquette Ceci se fait tout au d but de l algorithme avant m me les instructions proprement dites C est ce qu on appelle la d claration des variables C est un genre de d claration certes moins romantique qu une d claration d amour mais d un autre c t moins d sagr able qu une d claration d imp ts Le nom de la variable l tiquette de la bo te ob it des imp ratifs changeant selon les langages Toutefois une r gle
58. st que justement si le touriste vous demande son chemin c est qu il ne le conna t pas Donc si on n est pas un goujat int gral il ne sert rien de lui dire de le trouver tout seul De m me les modes d emploi contiennent g n ralement mais pas toujours un peu plus d informations que d brouillez vous pour que a marche Pour fonctionner un algorithme doit donc contenir uniquement des instructions compr hensibles par celui qui devra l ex cuter C est d ailleurs l un des points d licats pour les r dacteurs de modes d emploi les r f rences culturelles ou lexicales des utilisateurs tant vari es un m me mode d emploi peut tre tr s clair pour certains et parfaitement abscons pour d autres En informatique heureusement il n y a pas ce probl me les choses auxquelles ont doit donner des instructions sont les ordinateurs et ceux ci ont le bon go t d tre tous strictement aussi idiots les uns que les autres 3 Faut il tre matheux pour tre bon en algorithmique Je consacre quelques lignes cette question car cette opinion aussi fortement affirm e que faiblement fond e sert r guli rement d excuse moi de toute fa on je suis mauvais e en algo j ai jamais rien pig aux maths Faut il tre bon en maths pour expliquer correctement son chemin quelqu un Je vous laisse juge La ma trise de l algorithmique requiert deux qualit s e il faut tre rigoureux Car chaque fois
59. ste de pr senter les choses c est simplement une mani re diff rente Si l on doit programmer cela on peut alors imaginer une fonction Fact charg e de calculer la factorielle Cette fonction effectue la multiplication du nombre pass en argument par la factorielle du nombre pr c dent Et cette factorielle du nombre pr c dent va bien entendu tre elle m me calcul e par la fonction Fact Autrement dit on va cr er une fonction qui pour fournir son r sultat va s appeler elle m me un certain nombre de fois C est cela la r cursivit Toutefois il nous manque une chose pour finir quand ces auto appels de la fonction Fact vont ils s arr ter Cela n aura t il donc jamais de fin Si bien s r rassure toi public la r cursivit ce n est pas Les Feux de L Amour On s arr te quand on arrive au nombre 1 pour lequel la factorielle est par d finition 1 Cela produit l criture suivante un peu d concertante certes mais parfois tr s pratique Fonction Fact N en Num rique Si N 1 alors Renvoyer 1 Sinon Renvoyer Fact N 1 Finsi Fin Fonction Vous remarquerez que le processus r cursif remplace en quelque sorte la boucle c est dire un processus it ratif Et en plus avec tous ces nouveaux mots qui riment vous allez pouvoir crire de tr s chouettes po mes Vous remarquerez aussi qu on traite le probl me l envers on part du nombre et on remonte rebours jusqu 1 pour pou
60. uelque chose du genre Tableau Notes en Entier Variable nb en Entier D but Ecrire Combien y a t il de notes saisir Lire nb Redim Notes nb 4 Tri d un tableau Ce qui suit est incontournable Combien de fois au cours d une carri re brillante de d veloppeur a t on besoin de ranger des valeurs dans un ordre donn C est incalculable Aussi plut t qu avoir r inventer chaque fois la roue le fusil tirer dans les coins le fil couper le roquefort et la poudre maquiller vaut il mieux avoir assimiler quelques techniques solidement prouv es m me si elles paraissent un peu ardues au d part Il existe plusieurs strat gies possibles pour trier les l ments d un tableau nous en verrons une le tri par s lection Admettons que le but de la man uvre soit de trier un tableau de 12 l ments dans l ordre croissant On commence par rechercher le plus petit l ment On l identifie en quatri me position et on l change alors avec l l ment num ro 1 wwWw jeremyazoulay com 21 On recommence rechercher le plus petit l ment mais cette fois partir du deuxi me l ment On le trouve en 8e position on change donc le deuxi me avec le troisi me Et cetera et cetera jusqu l avant dernier L algorithme permettant d effectuer cette t che est le suivant wwWw jeremyazoulay com 22 VI Tableaux multidimensionnels Ceci
61. upart des langages offrent cette possibilit Ouvrir Exemple txt sur 3 en Ajout Variable Truc en Caract re Variables Nom 20 Pr nom 15 Tel 10 Mail 15 en Caract re Nom amp Joker Pr nom amp Midnight Tel amp 0348946532 Mail amp allstars rockandroll com Truc amp Nom amp Pr nom amp Tel amp Mail Ecrire 3 Truc Et pour finir une fois qu on en a termin avec un fichier il ne faut pas oublier de fermer ce fichier On lib re ainsi le canal qu il occupait et accessoirement on pourra utiliser ce canal dans la suite du programme pour un autre fichier ou pour le m me 4 Strat gies de traitement Il existe globalement deux mani res de traiter les fichiers textes e l une consiste s en tenir au fichier proprement dit C est parfois un peu acrobatique lorsqu on veut supprimer un l ment d un fichier on programme alors une boucle avec un test qui recopie dans un deuxi me fichier tous les l ments du premier sauf un et il faut ensuite recopier int gralement le deuxi me dans le premier Ouf e l autre consiste passer par un ou plusieurs tableaux On recopie l int gralit du fichier de d part dans un tableau en m moire vive et on ne manipule ensuite que ce tableau qu on recopie la fin dans le fichier d origine wwWw jeremyazoulay com 20 Les avantages de la seconde technique sont nombreux e a rapidit les acc s en m moire vive sont des milliers
62. variables aura ainsi cette t te Variable g en Entier Long Variables PrixHT TauxTVA PrixTTC en R el Simple 2 2 Autres types num riques Certains langages autorisent d autres types num riques notamment e le type mon taire avec strictement deux chiffres apr s la virgule e le type date jour mois ann e Nous n emploierons pas ces types ici mais vous ne manquerez pas de les rencontrer en programmation proprement dite 2 3 Types non num riques Fort heureusement les bo tes que sont les variables peuvent contenir bien d autres informations que des nombres Sans cela on serait un peu emb t d s que l on devrait stocker un nom de famille par exemple On dispose donc galement du type alphanum rique galement appel type caract re dans une variable de ce type on stocke des caract res qu il s agisse de lettres de signes de ponctuation d espaces ou de chiffres Le nombre maximal de caract res pouvant tre stock s dans une seule variable d pend du langage utilis Une s rie de caract res stock e ou non dans une variable alphanum rique d ailleurs s appelle une cha ne de caract res Et une telle cha ne de caract res est toujours not e entre guillemets Pourquoi diable Parce que 423 peut repr senter le nombre 423 ou la suite de caract res 4 2 et 3 selon le type de codage le type de la variable qui a t utilis pour le stocker Les guillemets permettent d viter toute ambigu t
63. voir calculer la factorielle Cet effet de rebours est caract ristique de la programmation r cursive Pour conclure sur la r cursivit trois remarques fondamentales e la programmation r cursive pour traiter certains probl mes est tr s conomique pour le programmeur elle permet de faire les choses correctement en tr s peu de lignes de programmation e en revanche elle est tr s dispendieuse de ressources machine Car l ex cution la machine va tre oblig e de cr er autant de variable temporaires que de tours de fonction en attente e Last but not least et c est le gag final tout probl me formul en termes r cursifs peut galement tre formul en termes it ratifs Donc si la programmation r cursive peut faciliter la vie du programmeur elle n est pas indispensable Mais a me faisait tant plaisir de vous en parler que je n ai pas pu r sister 5 Variables publiques et priv es wwWw jeremyazoulay com 34 L existence de sous proc dures de param tres pose le probl me de la dur e de vie des variables ce qu on appelle leur port e Pour faire simple une variable peut tre d clar e e Comme priv e ou locale c est en g n ral l option par d faut Cela signifie qu une telle variable dispara t et sa valeur avec d s que prend fin la proc dure ou elle a t cr e e Comme publique ou globale Ce qui signifie qu une telle variable est conserv e intacte pour toute l applicatio
64. www jeremyazoulay com 1 SOMMAIRE Algorithmie INTRODUCTION nt nets eme sde ann tale ete ee P 2 3 CHAPITRE 1 Les variables msn mn Res P 4 8 CHAPITRE 2 Lecture Ecriture P 9 10 CHAPITRE SS LES tests sin dans dut om AS pen CAN te P11 15 CHAPITRE 4 Les boucles Sean ane Ent r ne n ee r t A Le Te P16 18 CHAPITRE 5 Les tableaux 4 P19 21 CHAPITRE 6 Les tableaux multidimensionnels P22 23 CHAPITRE 7 Les fonctions pr d finies P24 25 CHAPITRE 8 Les fichiers s quentiels P26 29 CHAPITRE 9 Proc dures et fonctions P30 34 CHAPITRE 10 Notions compl mentaires P35 36 wwWw jeremyazoulay com 2 INTRODUCTION Pr ambule L algorithmique est un terme d origine arabe comme alg bre amiral ou z nith Ainsi l algo n est pas rythmique la diff rence du bon rock n roll L algo n est pas non plus l agglo Alors ne confondez pas l algorithmique avec l agglo rythmique qui consiste poser des parpaings en cadence 1 Qu est ce que l algomachin Avez vous d j ouvert un livre de recettes de cuisine Avez vous d j d chiffr un mode d emploi traduit directement du cor en pour faire fonctionner un magn toscope ou un r pondeur t l phonique r ticent Si oui sans le

SOMMAIRE Algorithmie

Contents

Download Pdf Manuals

Related Search

Related Contents