Algorithmes et programmation en Pascal

1 AlgorithmesetprogrammationenPascalFacult e desSciencesde LuminyEdouardThielCoursDeug1 MassMAModulede 75 heures1997 a 20042 Algorithmeset programmationenPascalEdouardThielTablede smati eresILesvariablesenPascal61 .. 'unevariableenti ere.. tableaudesortie.. 'unevaleur..72 Identi cateur73 Types pr ed e entier:integer.. r eel:real.. caract ere:char.. bool een:boolean.. 104 D .. a ectation.. 115 .. desexpressionsbienform ees.. eglesd' evaluation.. 136 intervalle.. enum er e .. eclareruntype.. enregistrement .. 17 IIProc edures181 Proc eduresansparam .. ee desvariables.. etdebord.. 202 Proc edureparam etr etres.. etrage.. ca marche.. e exes.. 23 IIIL esinstructionsenPascal24 CoursDeug1 MassMA,1997 a 200431 Instructioncompos ee242 eenif.. electiondecasaveccase.. 263 .. boucle.. 31 IVFonctions321 Fonctionsansparam.

2 322 Fonctionavec param edurevs fonction.. enregistrement .. 343 Fonctionavec plusieursr esultats344 Gestiond'erreurs36 VTableaux381 .. ^oledesbornes.. 402 Super a plusieursdimensions.. 413 .. erateurssurlesstrings.. 43 VIFichierss equentiels441 Leclavieret l' chageavecwrite.. 452 en erales.. texte.. ' elements.. 504 Algorithmeset programmationenPascalEdouardThielVII Algorithmesavec desvecteurs521 Recherches equentielled'un el e .. e.. 532 .. 553 Tri d' parremplacement .. parpermutation.. a bulles.. parcomptage.. 594 Mise a jourd' e .. e .. e .. e .. 615 Tri parinsertion61 CoursDeug1 MassMA,1997 a 200456 Algorithmeset 'instructions,certaines etant desmotscl chela cha^ nedecaract eres<Bonjour> a l' ecran:PROGRAM bonjour;BEGIN writeln('Bonjour'); (analyse)unprogrammeet le traduitencodemachine,directement ex ecutableparle processeurdel' {commentaire}dansunprogrammeau-dessusou a cot e d' 'estpasprisencompte a la sert a rendreleprogrammeplusclair a la lecture, a noterdesremarques,etc:{ EdouardThiel- 21/01/2003}PROGRAM bonjour;BEGIN{ AfficheBonjour a l' ecran}writeln('Bonjour'); 'unevariableenti ereUnevariableestunezonedansla m emoirevive de l'ordinateur,dot ee d'unnometd'untype.

3 Lenomde la variablepermetd'acc ederaucontenu de la zonem emoire;le type sp eci ela naturedece quipeut^etrestock e dansla zonem emoire(entier,r eel,caract ere,etc).Ona coutumede repr esenterunevariableparunebo^ te ; dessousonmetle nom,audessusle type, et dansla bo^ tele unevariablede nomaet detype entier:PROGRAMvar_entiere;VARa : integer;{ D eclaration}BEGINa := 5;{ Affectation}writeln('valeurde a = ', a);{ Affichage: a = 5 } MassMA,1997 a 20047 Lastructuredece programmeesten3 parties: le nomduprogramme,la partied eclarations,et le corpsduprogramme,quiestunesuited' eclarationcr ee lesvariables(lesbo^ tes); leurcontenu estind etermin e(onmetun' ?' danschaquebo^ te).Latailledela zonem emoirede chaquevariableestadapt ee autype (parexemple1 octetpouruncaract ere,4 octetspourunentier,etc). tableaudesortieLatrace d'unprogrammeestobtenueenpla cant deswritelnpourquele pro-grammea che lesvaleursdesvariables a l'ex sortied'unprogrammeestuntableauavecuneco lonneparva-riable,o u l'on ecritl' evolutiondesvariablespendant le d eroulement e enTDet 'unevaleurPROGRAMlit_ecrit;VARa : integer;BEGIN write('Entrezun entier: ');{ pas de retourchariot}readln(a);{ Lecture}writeln('valeurde a = ', a); cateurSert a donnerunnom a erede'a'.

4 'z'ou'A'..'Z'ou'_'.Onappelledigituncarac t erede'0'..'9'.Unidenti cateurPascalestunesuitede lettresoude digitaccol es,commen ,y1,jour,mois,annee,NbCouleurs, n'ya pasdedi erenceentreminusculeset 'apasle droitdemettred'accents,ni decaract cateurdoit^etredi erent desmotscl es(begin,write,real, ..)Onse sertdesidenti cateurspour: le nomduprogramme,lesnomsde variables,lesnomsdeconstantes, programmationenPascalEdouardThiel3 Types pr ed e nisUntyped ecritunensembledevaleurset unensembled'op entier:integerEntiersign e encompl ement a deuxsur16ou32bits,selonmachineet compila-teur: 16 pourTurbo Pascal ,32 bits, a valeurdans 32 768: : :+ 32 767( 215: : :+ 215 1).Sur32 bits, a valeurdans 2 147483648: : :+ 2 147483647( 231: : :+ 231 1). Op erateurssurlesentiers:abs(x) (x)x (x)x+ (x)truesixestimpair, (x)le carr e dex.+ xidentit xsigneoppos + - * / ydivision,fournissant unr esultatdetype r divydividendedela divisionenti modyrestedela divisionenti ere, ,lesop erateurs/,divetmod, produisent uneerreur a l'ex 'unevaleur(ouunr esultatinterm ediaire)d epasselesbornesaucoursdel'ex ecution,ona uneerreurappel eed ebordementarithm r eel:realLeurdomaineded e nitiond ependdela machineet ducompilateurutilis eelavecunecertainepr ecision,et lesop erationsfournissent unevaleurapproch eedur esultatdit<juste>.

5 Il fautdoncse m e er:SousDelphi,writeln( );a Cen'estpasunbug; simple-ment, 'estpasrepr esentableenbase2. Ene et,enbase2 il s' ecrit0;01001:base100;30;61;20;40;81;6 base20;01001 CoursDeug1 MassMA,1997 a ; (= 21;4 103= 21400); (=1;234 10 2) Op erateurssurunargumentxr eel:abs(x),sqr(x),+x,-x. Si l'unaumoinsdes2 arguments estr eel,le r esultatestr eelpour:x - y,x + y,x * y. R esultatr eelquel'argument soitentierour eel:x / y(ydoit^etrenonnul);fonctionssin(x),cos( x),exp(x),ln(x),sqrt(x)(square root, racinecarr ee). Fonctionsprenant unargument r eelet fournissant unr esultatentier:trunc(x)(partieenti ere),round(x)(entierle plusproche).Si le r esultatn'estpasrepr esen-tablesuruninteger, il y a d caract ere:charLe jeuxdescaract erescomportant leslettres,lesdigits,l'espace,lesponctua tions,etc,estcod e surunoctetnonsign l'ordredes256caract erespossibled ependdela machineet ,onutilisele codeASCII, o u'A'estcod e par65,'B'par66,'a'par97,' 'par32,'{'par123, e commesuit: de0 a 31, sont cod es lescaract eresdecontr^ole(7 pourle signalsonore,13pourle sautdeligne,etc).}

6 De32 a 127,sont cod es lescaract ereset ponctuationsstandardset nde128 a 255, sont cod es lescaract eresaccentu es propres a la langue,et descaract eressemi-graphiques. Lesop erateurssurlescharssont :ord(c)num erod'ordredansle codage; ici<code ascii>.chr(a)le r esultatestle caract eredont le code (c)caract eresuivantcdansl'ordreascii,chr(ord(c)+1 )prec(c)caract erepr ec edentcdansl' y a erreur a l'ex ecutionsi le caract eren' ;VARc, d : char;a: integer;BEGINc := 'F';a := ord(c);{ 70 }writeln('Lecodeasciide ', c, ' est ', a);a := 122;c := chr(a);{ 'z' }writeln('Lecaracterede codeascii', a, ' est ', c);c := 'j';d := succ(c);{ 'k' }writeln('Lecaracteresuivant', c, ' est ', d); programmationenPascalEdouardThielExercic eA cherlescaract eresdecodeasciide32a 255( !sur ecranet surimprimante,lesr esultatssont parfoisdi erents).Divers{ Onpeutremplacerchr(32)par#32, maispaschr(i)par#i.{ Lecaract ereapostrophese note''''.}}

7 Unesuitedecaract erestelleque'Ily a'estunecha^ nede caract eres; il s'agitd'unobjetde typestring, quel' bool een:booleanUtilis e :false(faux)ettrue(vrai). Op erateursbool eens:not(n egation),and(et),or(ou).Exemple{ Declaration}petit,moyen,grand: boolean;{ Instructions}petit:= false;moyen:= true;grand:= not (petitor moyen);Tabledev erit edecesop erateursxynotx x andy x or ytruetruefalsetruetruetruefalsefalsefals etruefalsetruetruefalsetruefalsefalsetru efalsefalse Op erateursdecomparaison(entre2 entiers,2 r eels,1 entieret 1 r eel,2 chars,2bool eens):<,>,<=,>=,=( egalit e, a nepasconfondreavec l'attribution:=),<>(di erent).Leresultatd'unecomparaisonestunbo ol bool eensentreeux,avec la relationd'ordrefalse< true. Enm emoire,lesbool eenssont cod es sur1 bit,avec0 pourfalseet 1 pourtrue. Del a lesrelationsd' erateursbool eensnot,and,ors'apparententapproximative ment a (1 x), , +.CoursDeug1 MassMA,1997 a 2004114D estd esign ee parunidenti cateuret unevaleur,quisont x es end ebutdeprogramme,entrelesmotscl ^etremodi ee,et nepeutpas^ valeur_constante;ouidentificateur: type= valeur_constante;Dansla premi ereforme,le type estsous-entendu(siil y a unpoint, c'estunr eel,sinonunentier; si il y a desquotes,c'estuncaract ere(unseul)ouunecha^ nedecaract eres(plusieurs).)

8 ExemplePROGRAM constantes;CONST faux= false;entier= 14;{ constantesNOMMEES}reel= ;carac= 'z';chaine= 'hop';pourcent: real= ;{ secondeformeavectype}VAR{ variables}BEGIN{ instructions} a ectationUnevariablerepr esente unobjetd'uncertaintype ; cetobjetestd esign e parunidenti ^etred eclar eesapr es : type ;Onpeutd eclarerplusieursvariablesde m^emetype en m^emetemps,en less eparantpardesvirgules(voirexempleci-dess ous). A la d eclaration,lesvariablesont unevaleurind etermin ee. Oninitialiselesvariablesjusteapr es leBEGIN(onnepeutpasle fairedansla d eclaration).Utiliserla valeurd'unevariablenoninitialis ee estuneerreurgrave !ExempleVARa, b, c : integer;BEGIN{ Partieinitialisation}12 Algorithmeset programmationenPascalEdouardThielb := 5;{ Partieprincipale}a := b + c; { ERREUR,c n'estpas affecte'} 'op erationidentificateur:= expression;estunea ectation. Onn'apasle droitd' ecrireid1:= id2:= expr, niexpr:= idniexpr1:= esigneunevaleur, exprim ee parcompositiond'op erateursappli-qu es a desop erandes, quisont : desvaleurs,desconstantes,desvariables,de sappels a Etant donn e unevariablex, uneconstantemaxet unefonctioncos(),chaquelignecontient uneexpression:5x + * cos(x)(x < max)or (cos(x-1)> 2 * (x+1)) erateursagissent sur2 op erandes:operande1operateur_binaireoperan de2et d'autresagissent sur1 op erande:operateur_unaireoperande Lesop erateursbinairessont :{ op erateursderelation= <> <= < > >={ op erateursadditifs+ - or{ op erateursmultiplicatifs* / divmodand Lesop erateursunairessont :{ op erateursdesigne+ -{ op erateurden egationnot Lesparenth esessont unop erateurprimaire,ellespeuvent encadrertoutop erande.}}}}}

9 Unefonctionestaussiunop erateurprimaire,elleagitsurl'op erandeplac e entreparenth eses a sa plusieursparam etres,s epar es MassMA,1997 a desexpressionsbienform eesUneexpressiondoit^etre<bienform ee>pourquel'onpuissetrouver exemple,3 * 'a'- truen'estpasbienform ee,et la compilationPascal partie3,Types pr ed e nis, ona d ej a ditquelsop erateurssont y a encored'autresr egles,dont le simplebon-sens!L'expressionbienform ee a untype, quid ependdesr eglesd' evaluationdel' eel,iunentier,euneconstante enti ere,cuncaract 'expression(round(r+1)> (i/e))or (c < 'a')estbienform ee,et sont type estbool eencommeonle montreici:bool eenz}|{(bool eenz}|{entierz}|{round(r eelz}|{r eelz}|{r +entierz}|{1 ) > (r eelz}|{entierz}|{i /entierz}|{e ) ) or (bool eenz}|{ }|{c < }|{'a' )RemarqueLefaitqu'uneexpressionestbienfo rm ee n'impliquepasqueson evaluationestsanserreur,ce quipeut^etrele eglesd' evaluationL'expressiona + b * cest evalu eea + (b * c)et nonpas(a + b) * c: ceciparcequele*estprioritaireparrapport a+.

10 Onclasselesdi erents op erateursparordre de priorit e, lesop erateursdeplusfortepriorit e etant r ealis esavantceuxdeplusfaiblepriorit erateurssont de priorit e egale,on evaluede gauche a + b - cest evalu e(a + b) - c, et nonpasa + (b - c).Voicila tabledespriorit es class eesparordred ecroissant, lesop erateurssurunem^emeligneayant unepriorit e egale.() fonction()primaire+ - notunaire* / divmodandmultiplicatif+ - oradditif= <> < <= >= >relation14 Algorithmeset programmationenPascalEdouardThielRemarqu eEst-cequel'expressiona < b or c <= destbienform ee ? Quelestsontype ?R eponse: non! Ecrireunetelleexpressionbool eennesansparenth etdansla tabledepriorit es,l'op erateurora unepriorit e plus elev ee quelesop erateurs<et<=, et doncl'expressionsera evalu eea < (b or c) <= d, 'expressionbienform ee estici(a < b) or (c <= d).6 NouveauxtypesOna vulestypes pr e-d eclar esboolean,integer, suitecomment cr consparlesplussimples,le type intervalleet le type enum er intervalleC'estunsous-ensembledevaleursc ons ecutivesd'untype h^ uNetMsont desconstantesdum^emetype, et sont lesbornesinf erieureset sup e-rieuresde l'intervalle, : 0.