Home

jacques courtin, irene kowarski, initiation a l`algorithmique et

1. Solution proc dure d placer n G M D d placer un disque de G vers D en utilisant l axe M Base 1 d placer un disque de G vers D r currence d placer n 1 G D M d placer un disque de G vers D d placer n 1 M G D R cursivit applications ressens G auche Milieu D roite k 3 bonne chance R currence Hypoth se on connait la solution le probl me pour k disques Trouver la solution pour disques R cursivit applications Program hanoi inout output var n integer nombre de disques proc dure deplacer n integer G char M char D char begin if n 1 then begin write d placer un disque de writeln G vers D end else begin d placer n 1 G D M write d placer un disque de writeln G vers D d placer n 1 M G D end begin write Nb disques readin n deplacer n 2 m d end R cursivit pile d ex cution exemple L D D L Recursivite Program PP 3 var nb 37 sc integer procedure P n entier var s entier Conclusion var c integer 9 Re begin La r cursivit est un principe puissant nous SANE S c EE En iai ud d FJ n permettant de else begin c n mod 10 7 a d finir des structures de donn es complexes P n d 10 s P 37 de
2. y readin R end until i gt Max Les fichiers Qu est ce qu un fichier Un fichier est une collection de fiches Trouver une fiche a parcourir le fichier fiche apr s fiche a utiliser une cl d acc s si le fichier est tri selon cette cl ordre alphab tique ordre de cotation des livres Exemple un fichier dans une biblioth que une administration etc Les fichiers Motivation Toutes les structures de donn es que nous avons vues ont un point commun R sident dans la m moire principale de l ordinateur existence limit e la dur e d ex cution du programme Besoin de conserver des donn es pour une utilisation future apr s l ex cution du programme exemple carnet d adresses a notion de fichier Les fichiers En informatique Un fichier est une s quence de donn es du m me type enregistr es sur un support informatique de mani re permanente Un fichier est a conserv s en m moire secondaire disques et bandes magn tiques disquettes a d sign par un nom et poss de des attributs tels que date de cr ation taille Fichiers organisation et acc s D finition L organisation d un fichier est la mani re dont sont rang s physiquement les enregistrements du fichier Le but est d arranger les enregistrement de mani re y acc der le plus rapidement possible L organisation est choi
3. I if IOResult 0 then writeln Fichier non trouve else begin writeln la taille du fichier est filesize FICH write Entrez un num ro d enregistrement readin N SEEK FICH N read FICH ARTICLE writeln Nom du produit ARTICLE NOM Prix ARTICLE PRIX close FICH end Gestion d un carnet d adresses Proposer les structure de donn es permettant de a Stocker les informations concernant une personne de stocker durablement toutes les informations relatives toutes les personnes D claration des types TYPE Enregistrement adresse record nom prenom adresse cp ville tel mail string end Fichier d enregistrements carnetAdresse file of adresse Gestion d un carnet d adresses BUT proposer une solution de gestion d un ensemble d informations concernant des personnes nom pr nom adresse code postal ville t l phone e mail On d sire pouvoir cr er consulter Supprimer et modifier Pour information il faut savoir que la constitution et l exploitation d un fichier informatique contenant des informations sur des individus doit tre soumis l accord de la CNIL Commission Nationale Informatique et Libert Dans le cas contraire de graves sanctions p nales sont encourues Gestion d un carnet d adresses crire un programme principal avec menu permettant les op rations suivantes a cr er recr e
4. Probl me Calculer p permutation de 1 2 telle que Cl e 1 Cl e lt Cl ey Stabilit p est stable chaque fois que Cl Cl i lt k quivalent p i lt p k le tri n change pas les l ments de m me cl Tri par s lection t t 117 1 27 7 4 4 4 12 2 516 6 6 4 4 MIN 7 1 7 reste classer 8 8 8 913 9 i3 10 10 11 11 5 11 15 12 4 12 4 Recherche du minimum par balayage s quentiel Tri par s lection Constante n Type table tableau 1 n de type element proc dure triSelection r t table var temp type element min i j entier d but pour i variant de 1 n 1 faire min lt i pour j lt i 1 n faire si t j t min alors min j fsi fpour echanger t i t min fpour lt indMin t i n fin Tri par insertion alla ES proc dure trilnsertion r t table d but pour lt 2 n faire lt 1 temp t i tant que k 0 et temp lt t k faire t k dT t k k 1 ftant que 1 lt temp rechercher la position d insertion fpour de mani re dichotomique et effectuer 1 insertion faire fin Tri par insertion t 11 1 2 1 1 329 2 class 4 3 3 7 3 6 8 7 7 9 8 8 3r 9 9 4 4 10 7 7
5. 11 1 1 12 5 5 Point d insertion recherche s quentielle recherche dichotomique Tri bulles Un balayage 2 2 2 2 3 3 3 1 J 5 5 1 3 1 5 5 4 4 4 4 Suite des balayages 2 1 1 1 2 2 2 5 3 3 3 1 5 4 4 4 4 5 5 peuvent tre limin s class RO OO N AA Q O N gt Tri bulles Tris a bulles proc dure triBulles r t table var i entier proc dure triBulles r t table changement bool en var i k dernierEchange entier d but d but jet r p ter tant que ixn 1 faire changement lt faux dernierEchange lt n pour i variant de 1 n 1 faire si t i gt t i 1 alors pour k variant de n i 1 pas 1 faire si t k 1 gt t k alors imb e echanger t k 1 t k Change ent ecu dernierEchange k E od fsi ef jusqu non changement E id ernierEchange ftant que fin Tri fusion Tri fusion ali ii 1 PARTAGE FUSION Si liste assez longue proc dure triFusion r t table d f entier 3171912171115 13 var m entier d but PARTAGE si d f 3171912 7111513 alors m lt d f 2 TRI TRI triFusion t d m 21317 19 113 5I 7 triFusion t m 1 f Rn fusion t d m f 1121313157179 fsi fusionner les sous suites tri es
6. begin seek f i read f r write temp r end Suppression suite for i pos 1 to filesize f 1 do begin seek f i read f r write temp r end close f close temp erase f rename temp carnet fic assign f carnet fic writeln writeln Ok end Recherche nom suite if trouve then afficherAdresse output r else writeln Personne n est pas dans le fichier end Recherche nom var nc pc string r adresse trouve boolean begin write Nom a chercher write Prenom a chercher readin pc trouve false reset f while not eof f and not trouve do begin read f r trouve r nomznc and r prenom pc end close f Recherche Ville procedure recherche ville var f carnetAdresse var v string r adresse c integer begin write Ville readln v reset f c 0 while not eof f do begin read f r if r villezv then begin writeln filepos f r nom r prenom 1 end close f if c 0 then writeln Personne dans cette ville end procedure recherche nom var f carnetAdresse Tri procedure tri var f carnetAdresse var r rMin aux adresse indMin i j integer begin reset f for i 0 to filesize f 2 do begin seek f i read f rMin inMin i for j i 1 to filesize f 1 do begin seek f j read f r i rMin nom rMin prenom gt r nom r prenom th
7. const NB MULT 50 var a b repEnfant integer fin ok boolean nbEssaisOk integer begin randomize nbEssaisOk 0 repeat a random 8 2 a random 9 1 QI b randon 8 F2 Q2 b random 9 1 ok false repeat clrscr write a x b 2 readln repEnfant ok repEnfant a b if ok then writeln Bravo else writeln C est Faux r essayer readkey until ok nbEssaisOk nbEssaisOk 1 until nbEssaisOk NB MULT end Correction du Ds exercice 3 Q3 program tablesMult iput output repeat clrscr uses crt write a x b const NB MULT 50 readin repEnfant var ok repEnfant a b a b x y nbErreurs integer if ok then writeln Bravo else begin nbErreursMax repEnfant integer nbErreurs nbErreurs 1 fin ok boolean writeln Faux nbEssaisOk integer PN begin until ok nbEssaisOk 0 if nbErreurs gt nbErreursMax E then begin randomize nbErreursMax nbErreurs nbErreursMax 0 x a y b end repeat nbEssaisOk nbEssaisOk 1 a random 8 2 until nbEssaisOk NB MULT writeln x x y x y est l op Ln ame ier la plus difficile pour vous nbErreurs 0 writeln Notez bien le r sultat end ok false Correction du Ds exercice 3 Q4 Correction du Ds exercice 3 Q4 Q4 program tablesMult iput output On veut disposer maintenant d un moyen de sauvegarder le uses crt const NB MULT 50 nombre d erreurs effectu e
8. des algorithmes Encore plus fort a Avez vous indiqu un chemin un touriste gar a Avez vous fait chercher un objet quelqu un par t l phone a Si oui Vous avez d j fabriqu et fait ex cuter des algorithmes D finition Un algorithme est une suite d instructions qui une fois ex cut e correctement conduit un r sultat donn e R f rences bibliographique Livres 1 Jacques Courtin Ir ne Kowarski Initiation l algorithmique et aux structures de donn es volume 1 et 2 Dunod 2 Guy Chaty Jean Vicard lt Programmation cours et exercices Ellipses amp Utiliser internet et la biblioth que d Poser des questions Introduction Exemple 1 Un algorithme de r solution de l quation ax b 0 donn es a et b entiers Algorithme crire r solution de I quation ax b 0 lire a lire b Si a est non nul alors on obtient la solution x b a sinon si b est non nul alors l quation est insoluble sinon tout r el est solution R sultat la solution de I quation ax b 0 si elle existe Introduction Programme a Remarque l algorithme de calcul du ne peut tre ex cut par une machine qui ne comprend que des 0 et des 1 Besoin d un langage de programmation ici le langage Pascal Un programme est la traduction d un algorithme dans un langage informatique particulier et parfaitement pr cis program equation input
9. ou gauche Une proc dure P de niveau n voit sur le niveau afficher voit n les proc dures fr res qui la pr c dent ici Pere E win tri effectif et saisir R gle de fils gauche d un anc tre une proc P de niveau n voit sur les niveaux n q permuter voit saisir les procs fr res gauches du qe me anc tre le qieme anc tre est sur le niveau n q Visibilit localit et globalit des objets Visibilit localit et globalit des objets Bal A D finitions R gle de visibilit des objets Dans une proc P de niveau n les objets utilisables sont les objets On appelle objet une constante une variable ou un param tre globaux et les objets locaux P formel a Dans le cas o un objet local une proc et un objet global une Lp roc P portent le m me nom objet qui sera consid r est objet On appelle objet local une proc dure un objet d fini dans cette GE po 9 objet qu pense J proc dure a Plus g n ralement dans le cas o deux objet globaux la proc P on appelle objet global une proc dure P un objet d fini dans les portent le m me nom objet qui sera consid r est objet le plus proc dures anc tres de P sur le chemin menant de P la racine proche de P celui d fini dans anc tre de P le plus proche Remarque les r gles et d finitions pr c dentes sont galement valables dans le cas des fonctions a on appel
10. projetTp controleTp 2 sinon ajourn e note 3 4 moyEcrit 1 4 moyTp coefficients est ce suffisant r p ter lire Ex jusqu 0 lt lt 20 Calcul du Sup Introduction Exemple calcul de la note finale Note Ex Ds 3 x Su 1 ip 1 Ex xT 2 Introduction calcul de program notes input output p a Kosa cados mas D claration des constantes et des variables const COEF ECRIT 3 COEF TP 1 B INF 0 B SUP 20 var ex ds moyEcrit real projetTp controleTp moyTp real note real begin Saisie des donn es repeat write Exam readln ex until ex gt B_INF and ex lt B_ SUP repeat write Ds readIn ds until ds gt B INF and ds lt B SUP repeat write Projet de Tp readIn projetTp until projetTp gt B_INF and projetTp lt sup repeat write contr le de Tp readln controleTp la note finale suite 1 Calcul de la moyenne moyEcrit Ex Ds 2 if moyEcrit lt Ex then moyEcrit Ex moyTp projetTp controleTp 2 note COEF ECRIT moyEcrit CoEF TP moyTp COEF ECRIT COEF TP Affichage du r sultat writeln Note note if note gt 10 then writeln Admis else writeln Ajourn e end until controle Tp gt and controle Tp lt B SUP Rappel C Rappel Un programme manipul
11. trouver un caract re chiffre 2 lire la partie enti re du nombre r p ter 2 1 convertir le caract re chiffre en sa valeur enti re 2 2 rajouter cette valeur nombre d j calcul 10 2 3 lire le caract re suivant Jusqu ce que le caract re lu ne soit plus un caract re chiffre Introduction Programme Pascal Program convertir repeat input output const POINT 10 var resultat real echelle integer car char begin repeat read car until 0 car and car lt 9 l I rechercher un chiffre resultat 0 repeat resultat BASE resultat ord car ord 0 2 lire la partie enti re read car until 0 car or car gt 9 Introduction if car POINT then begin echelle 0 read car while 0 lt and car 9 do begin resultat BASE resultat ord car 0 read car echelle echelle 1 end while while echelle gt 0 do 3 lire la partie d cimale begin resultat resultat BASE echelle echelle 1 end while end then writeln resultat end convertir Introduction 1 Saisie des donn es 2 Calcul de la moyenne 3 Affichage du r sultat lire Ex moyEcrit Ex Ds 2 lire Ds crire Note note si moyEcrit lt Ex si note gt 10 lire projetTp alors moyEcrit Ex alors crire Admis lire controleTp moyTp
12. 10 2 5 e 2 0 10 2 15 0 2 3 2 5 Correction du Ds exercice 2 var i j integer begin i 1 while i lt S1 nbElement and x gt Sl tab i do begin S2 tab i S1 tab i i i l end S2 tab i x for j i to Sl nbEelement do S2 tab j 1 S1 tab j S2 nbElement S1 nbElement 1 end procedure inserer x integer Sl tabEntiers var S2 tabEntiers Correction du Ds exercice 2 qui tant donn e une suite S1 quelconque calcule la suite ordonn e 52 des l ments de S1 procedure ordonner Sl tabEntiers var S2 tabEntiers var i integer begin S2 nbElement 0 for i 1 to S1 nbElement do inserer S1 tab i S2 S2 end qui tant donn e deux suite S1 et S2 teste retourne vrai si S1 et S2 contiennent exactement les m mes l ments et dans le m me ordre fonction identiques S1 S2 suiteEntiers bool en Correction du Ds exercice 2 qui tant donn e une suite S retourne vrai si S est ordonn e faux sinon en utilisant les questions pr c dentes LI sans utiliser les questions pr c dentes fonction est ordonn e S suiteEntiers bool en avec utilisation des proc fonct prec function estOrdonnee S1 tabEntiers boolean var S2 tabEntiers begin ordonner S1 S2 estOrdonne identiques 51 52 end Correction du Ds exercice 2 function identiques S1 S2 tabEntiers 1 var i integer ok boolean begin i 1 ok Sl nbElement S2 n
13. c nom c prenom then trouve true else if in cl nom in cl prenom gt c nom c prenom then max pos 1 else min pos 1 end close ind P if trouve then rechercherPos pos else rechercherPos 1 end Acc s procedure acces var f carnetAdresse var ind fichierIndex var pos integer r adresse c cle in begin saisieCle c ind if pos lt gt 1 then begin reset ind pos read ind in reset f seek f in position read f r afficherAdresse output r end else writeln non trouv close f end Suppression procedure suppression var f carnetAdresse var ind fichierIndex var posIndex i integer r adresse in index c cle tempAdr fichierAdresse tempInd fichierIndex begin saisieCle c posIndex zrechercherPosIndex c ind reset ind seek ind posIndex read ind in suppression dans le fichier d adresse assign tempAdr tempAdr fic rewrite tempAdr reset f for i 0 to in position 1 do begin seek f i read f r write temp r end Modif procedure modif var f carnetAdresse var ind fichierIndex var pos integer r adresse c cle begin saisieCle c pos rechercherPos c ind writeln Entrez la nouvelle adresse 1 saisieAdress input r reset f seek f pos write f r close f trierIndex ind end Suppression suite for i in position 1 to filesize f 1 do begin
14. contenant du code binaire Un fichier Pascal est une s quence de donn es de m me type repr sentant chaque l ment enregistrement Ces fichiers et de longueur ind finie ne doivent tre manipul s que par des programmes Points techniques Les fichiers textes appel s aussi imprimables contenant a La fin du fichier est rep r e par un marqueur de fin de fichiers d t t tibles d tre sdit E dox emploi de la fonction bool enne eof end of file ract res e i r i imprim s adu egen o Rc d bos i bag EE eof fichier vrai si fin de fichier atteinte eof fichier faux sinon Longueur du fichier nombre d l ments du fichier non d finie lors de la d claration du fichier a S il n y a pas d l ments fichier vide a i 5 05 I El ments attach s aux fichiers D claration a On appelle nom interne d un fichier le nom sous lequel un DIT mr Un fichier binaire se d clare fichier est identifi fichier logique On appelle nom externe d un fichier fichier physique le En pseudo nom sous lequel un fichier est identifi en m moire type fichierDeTypeElement fichier de type l ment secondaire Le nom externe est une cha ne de caract re compos e de 3 En Pascal partie type fichierDeTypeElement file of type l ment indentification du support le nom du fichier proprement dit un suffixe qui pr cise le genre donn e texte etc To
15. end Correction du Ds exercice 1 P variables i j k l m proc dures Q Q param tres r sultat j donn e i variables k proc dure R S R param tre param tres r sultat k r sultat 1 i variables j Correction du Ds exercice 2 Exercice 2 const MAX 10 type suiteEntiers record nbElements entier tab array 1 MAX of integer end crire les proc dure fonction suivantes a qui tant donn e un entier X et une suite d entiers ordonn e par ordre croissant S1 calcule la suite S2 obtenue partir de S1 en ins rant l l ment X la bonne place proc dure ins rer X entier S1 suiteEntiers r S2 suiteEntiers Correction du Ds exercice 1 Program P Vx i j 1 m integer procedure Q var j integer i integer var k integer procedure S var k integer begin i 3 k j 4 1 k 1 end procedure R var 1 i integer var j integer begin k 0 1 m i j 1 S i ti v9 writeln Kee sim end begin j 1 i k 2 j i k m R i 1 l amp 333 writeln i j k 1 m end 1 j 2 k 3 1 4 m 5 Q i D end 25 7 writeln i 3 t Uk TL writeln i 3 s PER CL i7 m s k j 10 R i L5 j k VAK 10 Q4 i a52 j ms 71 1 Aw Wy P j 2 i X0 On affiche 2 10 0 10 5 0 10
16. entier si n 0 ou 1 alors n sinon u u n 1 u n 2 fin si fin action R cursivit applications Exemple 2 suite solution it rative fonction u d n entier entier d but var x y Z entier si n 0 ou n 1 alors retourner n sinon 0 u 0 1 u 1 pour i allant de 2 n faire 2 1 2 X y 7 fin pour retourner z fin si fin R cursivit applications Exemple 2 suite Voyons l ex cution u 9 u 9 u 8 u 7 u 7 u 6 u 6 u 5 O 2 1 appels la fonction u pour 100 O 299 O 10 Une solution r cursive n est pas toujours viable R cursivit applications Les Tours de Hanoi TH n disques concentriques es G auche Milieu D roite But d placer tous les disques de G D R gles 1 seul disque peut tre d plac la fois a 1 disque ne peut jamais tre d pos sur un plus petit 1 disque ne peut tre d pos que sur G M ou D R cursivit applications TH id e de la solution r cursive exprimer le probl me des n disques I aide de la m me solution sur n 1 disques base savoir r soudre le probl me pour 1 disque quations de r currences G auche Milieu Droite k 1 R cursivit applications G auche Milieu 2 Droite
17. fin Sch ma pour TRI RAPIDE t d m et t m 1 f pour obtenir t d f tri e faire TRI par FUSION Tri rapide Partage avec pivot 3 Suite du tri Correction du DS 2002 2003 Exercice 1 D rouler la main le programme Pascal suivant Indiquez les valeurs affich s l cran chaque occurrence du symbole V dans la partie instruction de ce programme indiquez quel est l tat de la pile l ex cution Tri rapide pl proc dure triRapide r t table d f entier var m entier d but si d f alors m partitionner t d f triRapide t d m 1 triRapide t m 1 f fsi choisir un pivot et partionner t d f en deux t d m et t m 1 f tq t d m 1 lt t m 1 f faire en TD fin Correction du DS exercice 1 E Program P begin var i j k l m integer i 1 5 2 k 23 24 m 5 procedure Q var j integer i integer 1 var k integer Qi D yo procedure S var k integer writeln i j k L m begin end 1 3 k j 4 k j writeln i 5 A k L s m end procedure R var i integer var j integer begin k 0 1 m i j l SG k i j writeln i j k 1 m end begin j 1 i k 2 j ktm RG 1 k i tj writeln i j k L m
18. if inMin cl nom inMin cl prenom in cl nom in cl prenom en begin inMin in indMin j end end if posMin lt gt i then begin seek ind i read ind aux write ind inMin seek ind posMin write ind aux end en close ind writeln writeln Ok end
19. output var a b real Algorithme begin Ecrire r solution de l quation ax b 0 writeln R solution de quation lire a lire b axtb 07 Si a est non nul write a readin a alors on obtient la solution x b a up write b readin b Sinon si b est non nul if a lt gt alors I equation est insoluble hen writeln x b a sinon tout r el est solution else if b lt gt 0 r b then writeln insoluble else writeln tout r el est solution Choisir end Introduction program Calcul_ pgcd input output var a b reste integer begin write a readin a write b readin b while b lt gt 0 do begin reste a mod b a b gt b reste end writeln pgcd a end Introduction Exemple 2 a Calcul du PGCD de deux entiers positifs donn es a et b entiers positifs Algorithme Appliquer r cursivement les deux r gles suivantes R1 PGCD a 0 a R2 PGCD a b PGCD b a modulo b b 0 R sultat le pgcd entre a et b Ex cution PGCD 36 24 PGCD 36 24 R2 PGCD 24 12 R2 PGCD 12 0 R1 12 Introduction Stuctures de donn es D finition une structure de donn e est un moyen de coder et de structurer les donn es manipul es Exemple type suite tableau 1 N d entiers etudiant structure nom pr nom chaine de caract res ge entier positif sexe car
20. que celui d une proc dure Il y a cependant quelques diff rences a renvoi d une valeur unique la fonction est typ Type de la fonction scalaire r el intervalle string structure Exemple 1 F R 5R x gt ax b E proc dures Incorporation dans une expression if F x0 10 then Retour l exemple de t ches D changer le contenu des variables enti res A et B a Diviser entier A par l entier B pour obtenir le quotient Q et le reste R Trier la suite de N l ments contenu dans le tableau T lt leverA puissance B Proc dures et fonctions D claration En pseudo proc dure nomProc don 1 type don n type r r s 1 r s m type d but fin fonction nomFonct don 1 type don n type typeValeurRetourn e d but fin En pascal procedure nomProc don 1 type don n type Var r s 1 r s m type begin end function nomFonct don 1 type don n type typeValeurRetourn e begin nomFonct end Proc dures et fonctions exemples function puissance a b integer integer donn es a b entier r sultat a puissance b sp cifications lever A la puissance B 7 var p i integer begin p 1 for i 1 to b do p p a puissance p end Proc dures et fonctions exemples I E procedure echanger var a b integer donn es a b entier r sultats a b entier sp cifications changer le contenu des variables e
21. single 1 5 10 3 4 107 double 5 0 10224 1 7 10 extended 3 4 10 1 1 10292 Op rateurs classiques Autres fonctions pr d finies abs x sqr x sqrt x sin x In x trunc x round x Op rateurs de comparaisons gt gt lt lt gt Rappel Type Bool en Boolean un bool en admet deux valeurs false Faux et true Vrai Ordre false true succ false true pred true false Op rations and et or ou not non xor ou exclusif Rappel Type caract re char a Chiffres 0 9 a lettres A Z a z a caract res sp ciaux 2 les caract res sont ordonn es selon un code unique pour chaque caract re le plus courant est le code ASCII Les op rations possibles sur les caract res sont les comparaisons lt gt lt lt gt gt succ et pred ord c retourne le code ASCII de c chr n retourne le caract re dont le code ASCII est n upcase c retourne le caract re majuscule de c et c sinon Quelques soit le code utilis on a toujours A lt B lt lt 7 a lt b lt lt 7 eU cie cg Rappel Type num r un type num r permet de construire explicitement les valeurs de ce type Nous pouvons crire type jourSemaine lundi mardi mercredi jeudi vendredi samedi dimanche couleurs arc en ciel ro
22. 4 m 5 Qu end writeln 31 45 43 4 5 k 7 1 0 E 1 j 2 k 3 E24 m 5 j Se S sik j 10 R i Eee k v 20 9 i AS j m 5 A 50 8 0 2 P k 3 j 2 i XA 3 On affiche 3 2 10 10 5 10 10 20 5 5 5 3 20 2 5 z235 2 354 2 15 R cursivit Raisonnement par r currence z 1 Exemple Montrer que S n 2 T M Preuve Cas de base a n 0 S 0 gt i 0 0 Vrai a n l sQ Yi on V 1 R currence Hypoth se S n est vrai montrer que S n 1 est vrai R cursivit quations de r currences Base S 0 2 0 R currence S n 1 S n n 1 SZ La r cursivit est un m canisme de calcul puissant amp R soudre un probl me de taille n peut se ramener la r solution d un plusieurs sous probl mes de taille plus r duite 2 R cursivit hypoth se de r currence 7 SaD Sn D TU n DG St 2 Vrai R cursivit Action r cursive une action A est exprim e de facon r cursive si la d composition de A fait appel A gt Action calculer S n Appliquer les deux r gles suivantes 1 5 0 0 2 Sn S n 1 n n gt 0 gt S 3 S 2 3 S 1 2 3 5 0 1 2 3 0 1 2 3 6 R cursivit Objet r cursif La d finition d un objet est r cursive lorsqu elle se formule en utilisant l objet m me qu
23. Pr sentation Cours Algorithmique amp Programmation Responsable Lakhdar SA S Contact CRIL Bureau 307 sais cril fr Lakhdar SAIS http www cril fr sais Licence Maths Info 2 me ann e Cours Facult des sciences Jean Perrin Universit d Artois 2 s ances sem Lundi 10h45 12h15 Amphi S19 Vendredi 9h30 10h30 Amphi S23 E LA D L D Pr sentation Pr sentation MESES E DRE EM ID Les examens a Intervenants Contr les E CC la semaine du 29 octobre 4 Novembre 2007 s es din pu Examen la semaine 17 21 d cembre 2007 1 re session TP Seconde session semaine du 22 6 janvier 2008 TP 1 projet 1 contr le de TP a Intervenants a Lakhdar Sa s valuation Nathalie Chetcuti Ex Ds 3 Si Note gt 10 or d SE 1 Ex xT AP alors crire Admis Ce sinon crire Ajourn crire Une nouvelle chance en seconde session fin si I Plan Introduction Rappel Proc dures amp fonctions R cursivit Pointeurs Listes piles files Arbres Fichiers Langage Pascal ntroduction Algorithme a Vous avez d j ouvert un livre de recettes de cuisine Avez vous d j d chiffr un mode d emploi traduit du cor en pour faire fonctionner un magn toscope m Si oui Sans le savoir vous avez d j ex cut
24. a 2 tant que a lt gt S1 nbElement faire pour i allant de a S1 nbElement faire si S1 tab i lt min alors 2 S1 tab i S1 tab i min min z fsi a acri fpour S2 nbElement S1 nbElement fpour Un chantillon d erreurs function estOrdonn e S suiteEntiers boolean a i integer difference boolean begin i 1 difference false reapeat if S tab i lt S element i 1 then difference true inc i until difference false or i S nbElement estOrdonnee difference end Un chantillon d erreurs Procedure ordonner S1 suiteEntiers var S2 suitentiers variable i j entier begin j 0 pour i allant de 2 S1 nbElement faire si S1 element i lt S2 element i 1 alors d but j j 1 S2 element j S1 element i fin sinon d but j j 1 S2 element j S1 element i 1 fin fsi fpour fin Un chantillon d erreurs fonction identiques S1 S2 suiteEntiers bool en a vari integer id bool en d but si S1 nbElement lt gt S2 nbElement alors id faux sinon id vrai i 1 tant que id et i lt S1 nbElement faire si S1 tab i S2 tab i alors id vrai ftantque fsi identiques id Un chantillon d erreurs Program multiplication LU aaa Repeat X random N Y random N writeln x y readIn R R1 x y if R R1 then begin writeln Bbravo iE i 1 end else begin writeln faux writeln x
25. a partie instruction de ce D rouler la main le programme Pascal suivant Indiquez les valeurs affich s l cran programme indiquez quel est tat de la pile l x cution proc dures S et Q variables i j k l m 5 Q Param tre param tres r sultat k r sultat j donn e i variables k proc dure R R param tres r sultat l variables j Exemple Program P var i j k m integer procedure S var k integer begin begin i i 3 ki j 4 k j V writeln i tr j k S l i m Q i D end writeln i procedure Q var integer nd var k integer procedure R var i integer var j integer begin k 0 j 1 m i j lI S i k i j writeln i j k m end begin j l i k 2 j i k m R i I Litt V writeln i y k 1 m end Exemple Program P var i j k 1 m integer procedure S var k integer begin i s i 3 j 4 l k j E E RU r T v m end procedure Q var j integer i integer var k integer procedure R var 1 i integer var j integer begin k 2 0 1 m i j 1 S i k i e writeln i j k 7 1 m end begin 1 1 2 j Lekt am R i 1 lis ilt D writeln i j Erk tan t m end begin i 1 j 2 k 3 1
26. act re fin structure Programme Algorithme Structures de donn es Introduction Probl me Trouver le plus court chemin sida entre Lille et Marseille 220 km Donn es Graphe Algorithme recherche du plus court chemin entre deux villes R sultats Chemin V5 Graphe chemin gt Structure de donn es Introduction r solution de probl mes crire formellement la solution algorithme sur papier Utiliser un pseudo langage V rifier votre solution sur un exemple a preuve formelle de algorithme encore mieux Traduire dans un langage de programmation 4 Tester le programme sur diff rents jeux de tests le jeux de tests doit tre suffisant a ne pas oublier les cas particuliers Introduction r solution de probl mes Lire l nonc du probl me tre certain de bien le comprendre a Utiliser une loupe a ressortir les informations pertinentes a donn es r sultats ignorant l existence de l ordinateur d terminer les points principaux traiter R fl chir la r solution du probl me en exploiter l ensemble de vos connaissances a adapter ou r utiliser des recettes existantes a encore difficile D composer le probl me Analyse descendante Introduction Exemple conversion de nombre nonc crire un programme qui simule la conversion d un nombre d cimale en tant que cha n
27. bElement while i S1 nbElement and ok do begin ok S1 tab i S2 tablil i i 1 end identiques ok end Correction du Ds exercice 2 Ll sans utilisation des proc fonct prec function estOrdonnee S1 tabEntiers boolean var ok boolean i integer begin ok true i 1 while i Sl nbElement and ok do begin ok S1 tab li lt S1 tab i 1 1 estOrdonnee ok end Correction du Ds exercice 3 Exercice 3 se propose d crire un programme permettant l utilisateur enfant de r viser ses tables de multiplications Pour ce faire le programme doit g n rer al atoirement des op rations et les proposer l enfant A chaque r ponse de l enfant le programme le f licitera bonne r ponse ou lui demandera de r essayer mauvaise r ponse Le programme s arr tera apr s un certain nombre d op rations r ussies Ce nombre est fix l avance par le programme Q1 crire le programme Pascal correspondant Q2 Que faut il modifier pour viter les op rations a 1 et 1 a Correction du Ds exercice 3 Q3 Q3 On d sire ensuite disposer d un moyen de d tecter l op ration qui lui a pos le plus de probl mes nombre le plus lev d essais successifs avant de trouver la bonne r ponse a Modifier le programme pour afficher une telle op ration Correction du Ds exercice 3 Q1 et Q2 program tablesMult iput output uses crt
28. devinez ce que fait ce programme ai S Procedure LIT Var c char Begin Reset F fichierText read F c while not eof F do begin write c read F c end Close F End Begin Repeat Writeln 1 Ecriture Writeln 2 Lecture Writeln 0 Ein Write Votre choix gt Readin rep Case rep of 1 ECRIT 2 SEIT End Until rep 0 Exemple 1 devinez ce que fait ce programme Program MON TEXTE Var F Text rep char Procedure ECRIT Var c char Begin Assign F fichierText Rewrite F Writeln Tapez un texte et terminez par read c While c lt gt do begin write F c read c end Close F End Les fichiers Acc s Direct e Quelques instructions soit var f file of lt typElements gt FILEPOS f indique la position du pointeur courant t te de lecture donne un entier FILESIZE f retourne le nombre d enregistrements composants du fichier SEEK fji positionne le pointeur au composant n i Ox i lt filesize f IORESULT variable contenant 0 si l action sur un fichier s est bien d roul e un entier sup rieur 0 sinon Exemple Exemple Program LIRE PRODUITS DIRECT Type PRODUIT record NOM string 20 PRIX real end var ARTICLE produit FICH file of PRODUIT N integer begin end assign FICH inventaire I reset FICH
29. e de caract res en sa valeur r elle Exemples de nombres lire 12 45 3 0 9625 notation d cimale Analyse a les nombres ne sont pas des valeurs isol es a font partie d un texte Exemples a valeur de x est 1526 32 lt 12 5 01 x y gt V Le programme doit lire tous les caract res jusqu au premier caract re chiffre lire la partie enti re du nombre ets il trouve le point la partie d cimale Introduction Exemple le mot 15 67 sera traduit en la valeur enti re 1567 cette valeur sera ensuite divis par 102 2 tant le nombre de chiffres apr s la virgule Algorithme 1 rechercher un chiffre 2 lire la partie enti re du nombre 3 siil y a un point d cimal alors 3 1 lire les chiffres suivants ce point 3 2 remettre l chelle ce nombre fin si 4 crire le r sultat Introduction 3 lire la partie d cimale sile caract re lu pr c demment est un point alors 3 1 lire le caract re suivant tant que le caract re lu est un caract re chiffre faire 3 1 1 convertir le caract re chiffre en sa valeur enti re 3 1 2 rajouter cette valeur nombre d j calcul 10 3 1 3 comptabiliser le nombre de chiffre apr s le point 3 1 4 lire le caract re suivant fin tant que 3 2 diviser le nombre obtenu par 10 puissance le nombre de chiffres lus apr s la virgule fin si Introduction 1 rechercher un chiffre r p ter lire un caract re jusqu
30. e deux types de donn es Variable une variable est un objet bien identifi dont les valeurs Algorithme amp programme quelques briques fondamentales A S PSS peuvent tre alt r es au cours de l ex cution du programme l affectation de variables Constante une constante est un objet bien identifi dont la valeur est la ecture criture fix e une fois pour toute et ne peut tre modifi e au cour de l ex cution du programme les tests D claration const NOM CONST valeur les boucles V un algorithme prog se ram ne toujours une var nomVar type m d type de la variable combinaison de ces quatre petites briques Exemples const PI 3 14 integer real char ces briques op rent sur des donn es variables BB identificateu SS var rayon surface real constantes de diff rents types GH Aa nom de la variable eem identificateur a a VI 17 Rappel Rappel Type entier Type de donn es Exemple de type Does 2octets 9 div 5 1 T 9 mod 5 4 successeur Succ 5 6 pr d cesseur red 5 4 Integer Real Boolean Char type num r Structur Array Record Type ensemble Type fichier Pointeur Type Pointer Type de donn es standard m moire occup 1 Rappel Type r el Espace m moire occup 6octet
31. ecimale nbChiffre resultat partEntiere miseAEchelle partDecimale nbChiffre end writeln resultat end R gles de visibilit Objets locaux ou globaux A program tri suite const MAX 100 type suiteEntier record nbElement integer elements array 1 MAX of integer end Z proc dure saisir var s suiteEntier proc dure tri effectif vdr s suiteEntier j function indMinimum s suiteEntier pos integer integer procedure permuter var a b integer begin gt p gt e gt proc dure afficher s suiteEntier e e procedure afficherLigne s suiteEntier Ig integer end begin end Visibilit s variables locales et globales program blocs input output const max 10 var lettre char nb integer 18 begin blocs 19 end blocs R gles de visibilit Objets locaux ou globaux program tri suite Niveau 0 procedure saisir procedure tri effectif lt procedure afficher Niveau 1 ag procedure afficherLigne Niveau 2 Les arcs expriment la relation de visibilit on dira qu une proc dure A voit une proc dure B si A peut utiliser B dans ses instructions A ech B R gle de hi rarchie Exemples Une proc dure P de niveau n voit sur le niveau n 1 tri suite voit saisir iud d onu A tri effectif et afficher R gle de pr c dence
32. elle entend d finir gt Exemple d f r cursive d une chaine Une chaine de caract re est a Soit la chaine vide a Soit un caract re suivi d une chaine de caract re R cursivit Vs It ration It ration R cursivit proc dure It ration proc dure It ration Tantque condition faire Si condition alors Instructions Instructions fin tantque It ration fin si fonction S n entier fonction S n entier S 0 Si n 0 Tant que n gt 0 faire alus Sed S S n sinon S S n 1 n n n 1 fin si fin tant que retourner S R cursivit Exemple suite D apr s la d finition pr c dente gt lt a gt est une chaine un caract re a suivi d une chaine vide gt ab est une cha ne un caract re a suivi de la chaine b La r cursivit est un m canisme puissant de d finition d objets R cursivit applications Exemple 1 calcul de la factorielle quations de r currences a 0 1 base n n n 1 r currence fonction fact d n entier entier d but sin 0 alors fact 1 sinon fact n fact n 1 fin si fin 3 Que se passe t il si n 0 gt r cursivit infinie R cursivit applications Exemple 2 suite de fibonacci quations de r currences a u 0 0 u 1 1 Base u n u n 1 u n 2 gt 1 r currence fonction u d n entier
33. en begin inMin j rMin r end end if indMin i then begin seek f i read f aux seek f i write f rMin seek f indMin write f aux end end writeln writeln Ok end Recherche Dichotomique suite while min lt max and not trouve do begin pos min max div 2 seek f pos read f r it it 1 if r nom r prenom nc pc then trouve true else if r nom r prenom gt nc pc then max pos 1 else min pos 1 end close f Recherche Dichotomique procedure dicho var f carnetAdresse var nc pc string r adresse trouve boolean min max pos it integer begin write Nom a chercher write Prenom a chercher readln pc reset f trouve false it 0 min 0 max filesize f 1 Recherche Dichotomique suite Affichage r sultat if trouve then begin afficher output r write trouve en it iteration if it 1 then write s writeln end end else writeln Personne ne correspond ce nom et ce prenom end Carnet d adresse utilisation d un fichier d index EI Cr ation d un fichier d index TYPEEnregistrement Fichier d index cle record nom prenom string end index record cl cle position integer end fichierIndex file of index Fichier d adresse D claration des types adresse record cl cle adresse cp ville tel mail string end Fichier d enregist
34. eudo Exemple assign FichierBib C Livres bib Primitives de manipulations de fichiers s quentiels Ecriture dans un fichier Syntaxe write nom interne E Pascal Ecriture de l enregistrement E dans le fichier logique F Le type de E doit tre compatible avec le type d clar par le fichier La commande crit le contenu de E l endroit o pointe le la t te de lecture et la d place d une position Ecriture dans un fichier Exemple type fichierBiblioth que file of livreCote var fichierBib fichierBiblioth que nom interne nomFich string MAX CH pour le nom externe E livreCote begin write entrez le nom du fichier 1 readin nomFich assign fichierBib nomFich rewrite fichierBib read E write fichierBib E Lecture d un fichier exemple Program LIRE ADRESSES Type ADRESSE record NOM RUE VILLE string NUMERO integer end FICHIER file of ADRESSE Var CARNET fichier CLIENT adresse begin assign CARNET carnet adresses reset CARNET while not eof CARNET do begin Read CARNET CLIENT write NOM CLIENT NOM write NUMERO CLIENT NUMERO write RUE CLIENT RUE write VILLE CLIENT VILLE end close CARNET end Ouverture d un fichier existant en lecture Syntaxe reset nom interne Pascal ouvrirLecture nom interne Pseudo L effet de reset F Ouverture en lecture et posit
35. f choix 1 then assigncrt res else begin assign res carnet txt writeln Resultat dans le fichier carnet txt end Ajout procedure ajout var f carnetAdresse var nouveau adresse choix integer begin reset f seek f filesize f repeat saisieAdresse input nouveau write f nouveau write Saisir un nouveau correspondant 1 Fin 0 readin choix until choix 0 close f end Liste suite reset f while not eof f do begin read f r afficherAdresse res r end close f end Acc s saisie de la position d acc s function saisiepos var f carnetAdresse integer var pos integer begin reset f repeat write Position dans le fichier write O filesize f 1 readin pos until pos gt 0 and pos lt filesize f 1 close f saisiepos pos end Modif procedure modif var f carnetAdresse var pos integer r adresse begin pos saisiepos f saisieAdresse input r reset f seek f pos write f r close f end Acc s procedure acces var f carnetAdresse var pos integer r adresse begin pos saisiepos f reset f seek f pos read f r afficherAdresse output r close f end Suppression procedure suppression var f carnetAdresse var pos i integer r adresse temp fichierAdresse begin pos saisiepos f assign temp temp fic rewrite temp reset f for i 0 to pos 1 do
36. har boolean begin estUnChiffre 0 lt car and car 9 end function car2Chiffre car char integer begin car2Chiffre ord car ord 0 end procedure repererUnNombre var car char begin repeat read car until estUnChiffre car end Proc dures et fonctions utilisation Utilisation d une fonction program appels foncts var x y integer function puissance a b integer integer donn es a b entier r sultat a puissance b sp cifications lever la puissance B 7 var p i integer begin ETY On peut crire for i 1 to b do p p a puissance p end z 2 puissance x y 10 begin writeln calcul de x puissance y write x readin x write y readin y writeln puissance x y puissance x y end Proc dures et fonctions exemple uus extraireNombre var car char var nb nbChiffre integer egin nb 0 nbChiffre Z0 repeat nbChiffre nbChiffre 1 nb BASE nb car2chiffre car read car until not estUnChiffre car end fonction miseAEchelle partDecimale nbChiffre integer real var nb real begin nb partDecimale while nbChiffre gt 0 do begin nb nb BASE nbChiffre nbChiffre 1 end miseAEchelle nb end Proc dures et fonctions exemple begin repererUnNombre car extraireNombre car partEntiere nbChiffre if car POINT then begin read car extraireNombre car partD
37. ionnement de la t te de lecture en face du premier enregistrement Lecture du premier enregistrement Sile fichier contient au moins un article eof F devient faux Lecture d un fichier Read F E a trois effets Lecture de l enregistrement point par le fichier a Affectation de son contenu dans E D placement vers l enregistrement suivant du fichier Ecriture dans un fichier exemple Program ADRESSES Type ADRESSE record NOM RUE VILLE string NUMERO integer end FICHIER file of ADRESSE Var CARNET fichier CLIENT adresse C char begin assign CARNET C IPersolcarnet adresses rewrite CARNET C 0 while C lt gt N do begin write NOM readln CLIENT NOM write NUMERO readin CLIENT NUMERO write RUE readln CLIENT RUE write VILLE readln CLIENT VILLE write CARNET CLIENT writeln autre adresse readin end close CARNET end Les fichiers de Texte Dans le cas de fichiers de texte on utilise les d clarations suivantes qui sont toutes quivalentes mais varient selon les compilateurs Pascal Type Fichier File of char Text Type Fichier Comme pour la saisie de donn es au clavier et pour l affichage d informations l cran il est possible d utiliser les instructions READLN et WRITELN au lieu de READ et WRITE La fonction EOLN End Of LiNe est galement disponible Exemple 1
38. le not eof ind do var r adresse in index begin res text read ind in seek f in position read f r writeln res Numero in position choix integer ger afficherAdresse res repeat close f close res close ind write Sortie a 1 end write ou dans un fichier texte 2 rocedure afficherAdresse f text r adresse readin choix egin until choix 1 or choix 2 GE if choix 1 then assigncrt res egan write f Nom cl nom else begin write f Pr nom cl prenon d write f Adresse adresse assign res carnet txt write f Code postal cp writeln Resultat dans le fichier carnet txt fr KEES f 5 end write f E mall mail i end ene Acc s rechercher position Acc s saisie de la cl d acc s d acc s Function rechercherPosIndex c cle var ind fichierIndex integer p integer var in cle trouye boolean procedure saisieCle var c cle min max pos it integer var pos integer begin ind begin reset ind a s trouve false it 0 min 0 max filesize ind 1 writeln entrez la cl d while mi Tas and ot trouve do write Nom readin c nom begin write Pr nom readin c prenom div 2 seek ind pos read ind in it it 1 if in cl nom in cl prenom
39. le objet global un programme un objet d fini au niveau 0 Visibilit localit et globalit des objets Visibilit localit et globalit des objets Local ou global e x Il vaut toujours mieux privil gier les variables locales aux Pricipe de la boite noire Une proc dure peut tre assimil une boite noire variables globales c est dire un module dont on peut ne conna tre que les Inconv nients d une utilisation syst matique de variables globales interactions possibles avec le monde ext rieur manque de lisibilit risque d effets de bord si la proc dure modifie les variables globales N entr es Proc dure fonction y gt N sorties Avantages d une utilisation de variables locales P meilleure structuration Les r gles de visibilit s au niveau des objets permettent d utiliser des diminution des erreurs de programmation objets globaux il s agit alors de la programmation par effet de bords les variables locales servent de variables interm diaires tampon et sont Ceci parfois un int r t mais oubli es effac es de la m moire la sortie de la proc dure C est totalement d conseill au programmeur d butant Une proc dure doit effectuer la t che qui lui a t confi e viter pour le programmeur exp riment en ne modifiant que l tat de ses variables locales Exemple chaque occurrence du symbole V dans l
40. nbErreurstl fsi writeln C est Faux r essayer s end fsi readkey fpour until ok Un chantillon d erreurs fori 1 to S1 nbElement do if X S1 tab i then begin pos zS1 tab i S2 tab i S1 tab i S2 tab i 1 X end else S2 tab i S1 tab i a i 1 S2 nbElement S1 nbElement 1 repeat S2 tabl i S1 tablil i i 1 until S1 tab i gt X S2 tab i X repeat S2 tab i 1 S1 tab i i i 1 until i gt S1 nbElement Un chantillon d erreurs a i 1 repeat if X gt S1 i then S2 i S1 i else if X lt S1 i then begin S2 i X for j i to max do S2 j S1 j end i i 1 if X gt S1 max then S2 max 1 X until izMax or X S1 Max Un chantillon d erreurs Var p i integer begin for i 1 to p 1 do S2 tab i S1 tab i a i 1 S2 nbElement S1 nbElement 1 repeat S2 tab i S1 tablil i i 1 until S1 tab i gt X S2 tab i zX repeat S2 tab i 1 S1 tablil i i 1 until i gt S1 nbElement Un chantillon d erreurs Procedure ordonner S1 suiteEntiers var S2 suitentiers a variable min i entier min i pour i allant de 2 S1 nbelement faire si S1 tab i lt S1 tab min alors min i echanger S1 tab i S1 tab min fsi fpour pour i allant de 1 S1 nbElement faire S2 tab i S1 tab i fpour Un chantillon d erreurs Procedure ordonner S1 suiteEntiers var S2 suitentiers Variable min a z entier min S1 tab 1
41. nti res A et B 7 var aux integer begin aux a a b b aux end procedure division a b integer var q r integer donn es a b entier r sultats q r entier sp cifications Diviser entier A par l entier B pour obtenir le quotient Q et le reste F begin r a q 0 while r gt b do begin r r b q q 1 end end Proc dures et fonctions passage de param tres connexion direcie retour pas de recopie Passage par valeur Passage par adresse par r f rence Proc dures et fonctions utilisation Utilisation d une proc dure et passage de param tres program appels procs var x y quotient reste integer procedure division a b integer var q r integer donn es a b entier r sultats q r entier sp cifications Diviser entier A par l entier B pour obtenir le quotient Q et le reste R7 begin r a q 0 while r gt b do begin r r b q q 1 end end begin writeln division enti re de x par y write readin x write y readin y division x y quotient reste writeln le quotient de la division de vest quotient le reste est reste end Proc dures et fonctions exemple Programme Pascal Program convertir repeat input output const POINT BASE 10 var resultat real partEntiere partDecimale nbChiffre integer car char function estUnChiffre car c
42. orer sa lisibilit Les proc dures et les fonctions sont la base de la programmation structur s Proc dures et fonctions Quand r aliser une proc dure On doit r aliser une proc dure chaque fois que l analyse d un probl me conduit identifier une t che a Sp cifier une proc dure c est identifier 1 l action r alis par cette proc dure 2 les param tres formels c est dire a l ensemble des donn es n cessaires ainsi que leur type b ensemble des r sultats produits ainsi que leurs types Si vous avez un gros programme mettre au point et que certaines parties utiliser une proc dure sous programme si un m me traitement est Proc dures et fonctions Besoin de proc dure et fonctions L analyse d un probl me d marche descendante consiste d couper un probl me complexes en t ches sous probl me que l on est capable de d finir Notion de tache une tache est une action bien d finie plus ou moins complexe qui s exerce un instant donn e sur un ou plusieurs objets Exemple changer le contenu des variables enti res A et B Diviser entier A par l entier B pour obtenir le quotient Q et le reste R lever A la puissance B et mettre le r sultat dans C Trier la suite de N l ments contenu dans le tableau T Proc dures et fonctions Quand r aliser une fonction En g n ral le r le d une fonction est le m me
43. r 2 readin choix until choix 1 or choix 2 if choix 1 then begin rewrite f close f writeln Ok end end Programme principal program fichiers iput output var f carnetAdresse begin assign f carnet fic repeat choix menu case choix of 1 creation f 2 ajout f 3 liste f 4 acces f 5 modif f 6 suppression f 7 recherche nom f 8 recherche ville f 9 tri f 10 dicho f end until choix 0 end Saisie d une adresse procedure lireAdresse var f text var adr adresse begin reset f with adr do begin write Nom 5 readln f nom write Prenom readin f prenom write Adresse readin f adresse write Code postal readin f cp write Ville readln f ville write Telephone readln f tel write E mail readln f mail end close f end Afficher une adresse procedure afficherAdresse f text adr adresse begin rewrite f with adr do begin write f Nom nom write f Prenom prenom write f Adresse adresse write f Code postal cp write f Ville ville write f Telephone tel write f E mail mail end close f end liste procedure liste var f carnetAdresse var r adresse res text choix integer begin repeat write Sortie a l ecran 1 write ou dans un fichier texte 2 readin choix until choix 1 or choix 2 i
44. r le fichier contenant les donn es a ajouter un ou plusieurs enregistrements a Obtenir la liste des enregistrements l cran ou dans un fichier texte afficher les renseignements concernant une personne a modifier les donn es concernant une personne sachant sa position dans le fichier a Supprimer une personne du fichier a rechercher les renseignements concernant une personne partir de son nom et de son pr nom a rechercher toutes les personnes habitant une ville donn e trier le fichier par ordre alphab tique des noms et des pr noms des personnes Menu 7 Function menu integer var choix integer begin writeln 1 Creer recreer le fichier de donnees writeln 2 Ajouter des enregistrements writeln 3 Liste des enregistrements writeln 4 Affichage d un enregistrement a partir de sa position writeln 5 Modification d un enregistrement a partir de sa position writeln 6 Suppression d un enregistrement a partir de sa position writeln 7 Recherche a partir du nom et du prenom writeln 8 Recherche des personnes habitant une ville writeln 9 Tri par ordre alphab tique writeln 101 Recherche rapide sur fichier trie writeln writeln O Fin writeln writeln write Votre choix readIn choix menu choix end Cr ation procedure creation var f carnetAdresse var choix integer begin repeat write Detruire le fichier existant 1 ou annule
45. rements carnetAdresse file of adresse Cr ation I procedure creation var f carnetAdresse var ind fichierIndex var choix integer begin repeat write Detruire le carnet existant et son index 1 ou annuler 2 readin choix until choix 1 or choix 2 if choix 1 then begin rewrite f rewrite ind close f close ind writeln Ok end end Programme principal program fichiers iput output var f carnetAdresse ind fichierIndex tri e par ordre croissant des noms et pr noms begin assign f carnet fic assign ind carnet index repeat choix menu case choix of creation f ind ajout f ind liste f ind acces f ind modif f ind suppression f ind recherche nom f ind recherche ville f ind D zl OU B Q N F end until choix 0 end Ajout procedure ajout var f carnetAdresse var ind fichierIndex var nouveau adresse in index choix integer begin reset f reset ind seek f filesize f seek ind filesize ind repeat saisieAdresse input nouveau write f nouveau in position filepos ind in position filepos f 1 in cl nouveau cl write ind in write Saisir un nouveau correspondant 1 Fin 0 readin choix until choix 0 close f close ind trier ind end liste Liste suite reset f reset ind procedure liste var f carnetAdresse var ind fichierIndex whi
46. s sur chaque op ration type tableMultiplications array 1 9 1 9 of integer Proposer une nouvelle version du programme permettant de sauvegarder dans la structure de donn e le nombre d erreurs pour var a b x y i j nbErreurs repEnfant integer chaque op ration pos s pour une op ration pos plusieurs fin ok boolean reprises par le programme le nombre d erreurs est le cumul des nbEssaisOk integer table tableMultiplications erreurs Correction du Ds exercice 3 Q4 Un chantillon d erreurs VE 7 sau DES table a b table a b nbErreurs Procedure inserer X integer S1 suiteEntiers S2 suitentiers E nbEssaisOk nbEssaisOk 1 i 1 f tep op until nbEssaisOk NB MULT s Hen table i j 70 T while X S1 tab i do randomize nbEssaisOk 0 writeln Les erreurs effectuees Pouride1 S1 nbElement faire repeat si X S1 tab i M A E on a Sad D D alors S2 nbElement S1 nbElement nbErreurs 0 ok false writeln S2 tab i S1 tab i repeat for i 1 to 9 do i i begin sinon S2 nbElement S2 nbElement 1 write a x b write 1 4 tant que X S1 tab i faire readln repEnfant for yu to 9 in S2 tab i S1 tab i ok repEnfant a b write table i j 4 ftant que if ok writeln and si X S1 tab i faire then writeln Bravo id S2 tab i X else begin S2 tab i 1 S1 tabli nbErreurs
47. seek f i read f r write tempAdr r end close f close tempAdr erase f rename tempAdr carnet fic assign f carnet fic suppression dans le fichier index Suppression suite en assign tempInd tempInd fic rewrite tempInd reset ind for i 0 to posIndex 1 do begin seek ind i read ind in write tempInd in end for i posind 1 to filesize ind 1 do begin seek ind i read ind in write tempInd in end close ind close tempInd erase ind rename tempInd carnet index assign ind carnet index EE Se Recherche Ville procedure recherche ville var f carnetAdresse var v string r adresse c integer begin D finir un autre fichier d index avec comme cl d acc s le nom de la ville end Recherche nom procedure recherche nom var f carnetAdresse var ind fichierIndex var r adresse c cle in index trouve boolean begin saisieCle c posIndex zrechercherPosIndex c ind if posIndex 1 then begin reset ind seek ind posIndex read ind in close ind reset f seek f in position read f r close f afficherAdresse output r end else writeln non trouve end Tri procedure trierIndex var ind fichierIndex var inMin in aux index posMin i j integer begin reset ind for i 0 to filesize ind 2 do begin ek ind i read ind inMin posMin i for j i 1 to filesize ind 1 do begin seek ind j read ind in di
48. sie la cr ation du fichier m Le choix d une organisation correspond un compromis entre rapidit d acc s et espace de stockage disponible Fichiers organisation relative acc s direct Chaque enregistrement poss de un num ro On acc de la fiche recherch e en sp cifiant ce num ro d enregistrement L indication d un num ro permet donc un acc s direct l information ainsi r f renc e Fichiers organisation s quentielle Elle ne permet qu un seul acc s le s quentiel Toutes les informations sont enregistr es de facon s quentielle lin aire les unes la suite des autres Pour acc der une information particuli re il faut n cessairement parcourir le fichier partir du d but et ce jusqu au moment o cette information est retrouv e Fichiers organisation index e Notion d index Soitun fichier F dont les enregistrements E poss dent une cl C e g nom Un index permet d associer chaque cl C le rang R de l enregistrement E de cl C dans F L index est alors une table des mati res du fichiers Oncr e des fichiers suppl mentaire d index On parcourt un index pour rechercher une clef On obtient ainsi l adresse exacte de l information recherch e Les types de fichiers Fichiers s quentiels Tt Les fichiers s quentiels en Pascal On distingue deux cat gories D finition w Les jfichiers jibinaires
49. simplifier les algorithmes op rants sur ces structures de 5 5 c s 2 end nbl 37 donn es end PP d 0 B 10 begin Pile d ex cution P nb sc writeln somme des chiffres nb est sc end Tris Tris internes Liste El mentaires L 7 3 1 4 8 3 classement tri S lection L 1 4 7 1 3 3 4 7 8 Insertion Liste class e en ordre croissant Tri interne Bulles l ments en table tableau liste cha n e en m moire centrale Tri externe Dichotomiques l ments en fichiers en m moire secondaire Tri rapide Op rations l mentaires comparaison de deux l ments Fusion change s lection de places Cl s P 1 2 M gt Guy 2 4 T gt Anne 3 us Lou 4 1 gt Luc 1m75 1m70 1m75 1m72 Probl me quivalent trier 1 2 n suivant certaines c s CLE POIDS TAILLE GLES Guy 1m75 60k Anne 1m70 55k Lou 1m 5 57k Luc 1m72 61k CLE TAIEEE Anne 1m70 55k Anne Luc 1m72 61k Lou Guy 1m75 60k Guy Lou 1m75 57k Luc CLE TAILLE POIDS Anne 1m70 55k Luc 1m72 61k Lou 1m75 57k Guy 1m75 60k Exemple EU ET MUR QE RR NU T m 1 Guy 1m75 60 k 2 Anne 1m70 55k 3 Lou 1m75 57k 4 Luc 1m72 61k 1m70 1m75 1m75 1m72 60k 55k 57k 61k 55k 57k 60k 61k Classement par rapport la cl TAILLE POIDS Tri en TABLE L 64 65 en table acc s direct e Cl L Ensemble muni de l ordre
50. te vn a writeln v1 v2 vn quivaut write v1 write v2 write vn writeln Exemple var rayon real rayon d un cercle write Veuillez donner le rayon du cercle readin rayon Rappel Entr es Sorties Lecture reen pseudo read suite de variables resp readin suite de variables permet de saisir des donn es au clavier le curseur reste sur la m me ligne resp saute une ligne Exemple read V1 v2 vn quivaut read v1 read v2 read vn readin v1 v2 vn quivaut read v1 read v2 read vn readin R gle pratique Pour viter toute surprise chaque fois qu une donn e tap e par l utilisateur se termine par une marque de fin de ligne cette marque doit tre saut e limin e par l utilisation de readln Rappel Affectation En pseudo variable expression En pascal variable expression Exemple moyTp projetTp controleTp 2 Remarque le type de la variable et de la valeur de l expression doivent tre identique d pend du langage Rappel Tests En pseudo si condition alors instruction 1 sinon instruction 2 fin si En pascal if condition then instruction 1 else instruction 2 condition est une expression bool enne Exemple if nb mod 2 1 then begin write Le nombre nb writeln est impair end else writeln Le nombre nb est pair Rappel Bo
51. ucles En pseudo tantque condition faire instructions fin tanque En pascal while condition do instructions condition est une expression bool enne Exemple var a b reste integer begin a 36 zs E b 24 Conditions initiales while b 9 do reste a mod b Condition d arr t a b bitreste Corps de la boucle end writeln Le pgcd 2 b a Rappel Tests Questions peut on remplacer l instruction conditionnel par affectation var pair boolean nb integer begin var pair boolean nb integer begin p df nbmod2 0 99 i nb mod 2 0 then pair true Eom else pair 5 end end Proc dures et fonctions Quelques citations Pour comprendre un programme d un seul tenant un tre humain met normalement un temps qui augmente exponentiellement avec la taille du programme Djikstra Pour ma triser la complexit du probl me r soudre diviser chacune des difficult s que j examinerais en autant de parcelles qu il pourrait et qu il serait requis pour mieux le r soudre Descartes strat gie diviser pour r gner Proc dures et fonctions sont semblables ou d autres tr s complexes alors il faut le structurer et chercher utiliser au maximum l existant effectu plusieurs reprises dans le programme V permet d all ger le programme de faciliter sa maintenance de le structurer et d am li
52. uge orange jaune vert bleu indigo violet Les valeurs d un type num r ordonn es selon leur ordre de d claration Pour le type jourSemaine nous avons lundi mardi mercredi jeudi vendredi samedi dimanche Remarques A chaque valeur num r e correspond un num ro d ordre nombre entier Dans notre exemple lundi porte le num ro 0 mardi porte le num ro 1 Les op rations possibles lt gt lt lt gt gt succ pred ord Rappel Type intervalle Un intervalle permet de restreindre le groupe des valeurs d un type appel type de base et choisi parmi integer boolean char ou un type num r Exemples a O 9 est l intervalle des valeurs enti res 0 9 le type de base est integer lundi vendredi est l intervalle des valeurs num r es lundi vendredi le type de base est jourSemaine A Z est l intervalle des lettres majuscules le type de base est char type chiffre 0 9 joursDeTravail lundi vendredi majuscule A Z Les op rations possibles sont celles du type de base Rappel Entr es sorties Ecriture crire en pseudo write expression resp writeln expression permet d afficher des donn es au clavier le curseur reste sur la m me ligne resp passe la ligne suivante expression peut tre un texte le contenu d une variable r sultat d un calcul a Write Vv1 v2 vn quivaut write v1 write v2 wri
53. us les types sont autoris s pour les l ments sauf le type C TP donn e dat fichier On appelle une fen tre d un fichier une lt zone gt de la m moire principale pouvant contenir un enregistrement du fichier Les types de fichiers Exemples const LG MAX NOM 30 LG MAX TITRE 40 type auteurLivre string LG MAX NOM titreLivre string LG MAX TITRE livreCote record nomAuteur auteurLivre titre titreLivre cote integer end fichierBiblioth que file of livreCote var FichierBib fichierBiblioth que Primitives de manipulations de fichiers s quentiels gt Cr ation d un fichier rewrite nom interne Pascal ouvrirEcriture nom interne Pseudo Cette instruction permet d ouvrir un fichier en criture c est dire de cr er le fichier et d autoriser des op rations d criture dans ce dernier Diff rentes possibilit s se pr sentent lors de l appel de Rewrite F a Le fichier F n existe pas cr ation du fichier a Si le fichier F existe effacement de toutes les donn es inscrites dans l ancien fichier F eof F devient vrai Positionnement du pointeur de fichier ou fen tre au d but du fichier vide F Primitives de manipulations de fichiers s quentiels Etablir un lien entre le nom interne et le nom externe du fichier Assign nom interne nom externe en Pascal Assigner nom interne nom externe en Ps

jacques courtin, irene kowarski, initiation a l`algorithmique et

Contents

Download Pdf Manuals

Related Search

Related Contents