Support de cours d Introduction à la programmation
Licence S.T.S - Semestre 1
Initiation la programmation
annØe universitaire 2013-2014
Licence Creative Commons cbea
2
Introduction
[ ] l’informatique est la discipline qui s’applique Øtudier et dØ nir des opØrations, et oø l’on op?re des transformations sur des combinaisons de symboles tr?s gØnØraux reprØsentant diverses informations en de nouvelles combinaisons de symboles, elles-mŒmes porteuses d’informations.
G. Ifrah, Histoire Universelle des Chi res, coll. Bouquins, t. II, p. 725.
Ce document est le support du cours d’initiation la programmation (InitProg) proposØ au semestre 1 de la premi?re annØe de licence Sciences et Technologies de l’universitØ de Lille 1, dans les parcours MASS, MIMP, PC, PEIP et SPI.
Les Øtudiants peuvent poursuivre l’Øtude de la programmation dans les deux cours Algorithmes et Programmation ImpØrative 1 (API1), proposØ au semestre 2 de premi?re annØe dans les pro ls MASS, MIMP, PEIP et SPI; et Algorithmes et Programmation ImpØrative 2 (API2), proposØ au semestre 3 en deuxi?me annØe de licence dans les mentions GØnie civil, GØnie mØca, Informatique, Maths, MØcanique et MASS.
La programmation
Un algorithme est la description d’un encha nement de calculs et de t ches ØlØmentaires en vue de la rØalisation d’un traitement automatique de donnØes. Ces donnØes doivent Œtre reprØsentØes par des structures appropriØes. L’algorithme peut ensuite Œtre codØ dans un langage de programmation pour donner un programme. La programmation regroupe ces activitØs : algorithmique, structuration de donnØes et codage, les deux premi?res Øtant certainement les plus importantes.
Contrairement ce que pourrait croire un novice, la t che principale de la conception d’un programme n’est pas l’Øcriture de celui-ci dans un langage informatique donnØ.
La rØalisation d’un programme se dØcompose en e et en plusieurs phases. De mani?re simpli Øe, on prØsente ainsi la gen?se d’un programme :
1. Øtablissement d’un cahier des charges : le probl?me posØ;
2. analyse du probl?me et dØcomposition de celui-ci en sous-probl?mes plus ou moins indØpendants et plus simples rØsoudre;
3. choix de structures de donnØes pour reprØsenter les objets du probl?me;
4. mise en uvre des di Ørents algorithmes utiliser pour rØsoudre les sous-probl?mes;
5. codage des algorithmes et crØation du programme dans un langage de programmation donnØ;
6. tests (et corrections) et validation aupr?s des utilisateurs.
Bien souvent, dans la pratique, ces Øtapes ne sont pas aussi nettement dØcoupØes. Les quatre premi?res sont certainement les plus importantes et on peut remarquer qu’elles sont indØpendantes du langage de programmation choisi, qui n’intervient normalement qu’ la cinqui?me
3
Øtape. La derni?re Øtape est, elle aussi, tr?s importante et ce serait une grave erreur de penser qu’elle ne fait pas partie du cycle de crØation d’un programme.
Pour un dØbutant en informatique, Øtudiant de surcro t, le cahier des charges consistera souvent en un ØnoncØ d’exercice ou de probl?me proposØ par un enseignant. Une premi?re t che, et elle est souvent plus di cile qu’on ne le croit, sera de comprendre cet ØnoncØ! Il faudra ensuite rØ Øchir la rØsolution de ce probl?me et, ensuite seulement, le coder dans un langage. On peut donc le constater, une bonne partie du travail doit se faire avec un crayon et un papier! Une erreur (mØthodologique) des dØbutants est souvent, une fois l’ØnoncØ lu (ou plus souvent simplement survolØ), de se ruer sur leur clavier et de commencer taper dessus (on ne sait d’ailleurs trop quoi) et seulement alors de commencer rØ Øchir la rØsolution du probl?me.
Objectif du cours
Il s’agit de poser les notions de base en programmation impØrative.
Expressions et instructions.
Constantes et variables, a ectation. Variables locales.
Types de donnØes simples : nombres entiers ou non entiers, boolØens, caract?res et cha nes de caract?res.
Expressions et instructions conditionnelles.
RØpØtition conditionnelle d’intructions (boucle tant que). RØpØtition non conditionnelle d’instructions (boucle pour).
Fonctions et procØdures. Param?tres formels, param?tres e ectifs.
Dans les deux cours qui suivent (API1 et API2) sont abordØes les notions tableaux; enregistrements; chiers;
rØcursivitØ;
structures de donnØes dynamiques; programmation modulaire; algorithmes de recherche et de tri; complexitØ des algorithmes.
Le choix du langage
Il existe de tr?s nombreux langages impØratifs : C, Pascal, Ada, Python, Caml
Pendant quelques annØes nous avons utilisØ le langage Pascal. Mais l’expØrience a montrØ que la lourdeur de la syntaxe de ce langage, ainsi que certaines de ses ambigu tØs, prØsentaient de rØelles di cultØs pour des Øtudiants dØbutant en programmation. Ce langage nØcessitant une phase d’Ødition, puis une phase de compilation avant toute exØcution, il devient tr?s vite fastidieux de tester la moindre idØe d’algorithme. Pour ces raisons nous avons dØcidØ de changer de langage.
Nous nous sommes alors tournØs vers Caml. MŒme si la base ce langage est avant tout un langage fonctionnel, il o re aussi la possibilitØ de programmer dans un style impØratif. Il dispose de plusieurs modes d’exØcution :
un mode interactif un mode compilØqui permet de produire des exØcutables autonomes. 5
Dans le cours d’InitProg, le mode interactif est le seul mode abordØ. La compilation pour produire des programmes exØcutables autonomes sera abordØe dans le cours d’API1.
Caml est un langage fonctionnel dans lequel les fonctions sont des valeurs du mŒme ordre que toute autre valeur. En particulier, une fonction peut produire une autre fonction. Par exemple, la fonction plus dØ nie ci-dessous est une fonction qui permet d’additionner deux nombres entiers.
# let plus a b = a + b ;; val plus : int -> int -> int = fun>
On peut le vØri er en appliquant la fonction plus aux deux entier 2 et 5.
# plus 2 5 ;;
- : int = 7
Mais on peut aussi appliquer cette fonction un seul entier, et la valeur produite par cette application donne une fonction qui, comme le montre le type indiquØ par l’interpr?te du langage est une fonction qui un entier associe un autre entier.
# let plus2 = plus 2 ;; val plus2 : int -> int = fun>
L’application de la fonction plus2 un entier donne cet entier augmentØ de 2.
# plus2 5 ;;
- : int = 7
MathØmatiquement parlant, la fonction plus est donc une fonction dont l’ensemble de dØpart est l’ensemble des entiers Z et celui d’arrivØe est l’ensemble des fonctions de Z dans Z.
plus : Z ?? (Z ? Z).
Une autre fa on de considØrer la fonction qui deux entiers associe la somme de ces deux entiers consiste la dØ nir comme une fonction dont l’ensemble de dØpart est l’ensemble des couples d’entiers Z × Z est celui d’arrivØe est Z.
add : Z × Z ?? Z.
Les deux fonctions plus et add sont d’une certaine mani?re deux facettes de la mŒme fonction :
on dit que la premi?re en est la version curry Øe et la seconde la version dØcurry Øe.
En Caml, on peut Øcrire tr?s simplement la forme dØcurry Øe.
# let add (a,b) = a + b ;; val add : int * int -> int = fun>
L’application de cette fonction deux entiers donne le rØsultat attendu.
# add (2,5) ;;
- : int = 7
Mais l’application un seul entier n’est plus possible
# add (2) ;;
This expression has type int but is here used with type int * int
puisque l’interpr?te du langage attend qu’un couple d’entiers soit fourni la fonction add.
En programmation, il est frØquent d’avoir dØ nir des fonctions ou procØdures deux (ou plus) param?tres. Dans la plupart des langages de programmation (C, Ada, Pascal ), lorsqu’une telle fonction a ØtØ dØ nie, il n’est pas possible de l’appliquer avec un nombre d’arguments infØrieur au nombre de param?tres prØcisØ dans sa dØ nition. Nous avons donc choisi, pour ce cours d’InitProg, de programmer toutes les fonctions ou procØdures plusieurs param?tres que nous rencontrerons sous leur forme dØcurry Øe. Cela a le double avantage d’Œtre syntaxiquement proche de ce qui se fait dans d’autres langages de programmation; de ne pas permettre l’application partielle d’une fonction qui fournirait des valeurs fonctionnelles qui pourrait dØsorienter le programmeur dØbutant.
Organisation du polycopiØ
Ce polycopiØ est dØcoupØ de mani?re assez classique en introduction (que vous lisez actuellement), chapitres, annexes, et diverses tables (des gures, des mati?res, ).
Les chapitres recouvrent les objectifs du programme d’InitProg. Ils sont tous suivis de quelques exercices. Durant les sØances hebdomadaires, les enseignants pourront complØter la liste de ces exercices par d’autres.
Une annexe importante est celle prØsentant les fonctions du module Cartes. Ce module dØ nit un environnement de travail qui permet de dØplacer des cartes situØes sur quatre tas d’un tas vers un autre. Cet environnement est utilisØ durant les premi?res semaines du cours pour introduire progressivement les di Ørentes structures de contr le en programmation impØrative, ainsi que les notions de fonctions et procØdures. Le report en annexe de la prØsentation de ce module est dØlibØrØ a n de distinguer les objectifs du cours (prØsentØs dans les divers chapitres) des moyens pour les atteindre.
Ce polycopiØ ne contient pas les sujets de TP qui seront proposØs au fur et mesure par l’intermØdiaire du semainier du portail des UE d’informatique (-lille1. ) ou du site du cours sur Moodle (fr/). Bien entendu, les TP font partie intØgrante du cours et sont indispensables une bonne comprØhension de ce cours.
Conventions utilisØes dans le polycopiØ
Les algorithmes de rØsolution de probl?me sont dØcrits en pseudo-code sous la forme
Sortie : n! f ? 1
pour i allant de 1 n faire f ? f × i
n pour
renvoyer f
La traduction d’un algorithme en Caml, ainsi que les programmes sont prØsentØs sous la forme
let fact (n) = let f = ref 1 |
7
in for i = 1 to n do f := !f * i done; !f |
En n, les dialogues avec l’interpr?te du langage sont dØcrits sous la forme
# let a = 5 ;; val a : int = 5 # fact (5) ;;
- : int = 120
Lorsqu’une nouvelle structure syntaxique du langage est prØsentØe pour la premi?re fois, elle l’est sous la forme
Syntaxe : DØclaration d’une variable |
let =
Le site du cours
Le site du cours se trouve l’adresse :
.
Vous pouvez y accØder l’aide de votre tØlØphone ØlØgant (smartphone pour les anglophones) gr ce au QR-code de la gure 1.
Figure 1 QR-code du site du cours
quipe pØdagogique 2013-2014
Pierre Allegraud, Fabrice Aubert, Alexandre Bilger, Julien Bosman, Fran ois Dervaux, Alexandre Feugas, Michel Fryziel, Sophie Jacquin, Laetitia Jourdan, CØline Kuttler, Jean-Luc Levaire, Didier Mailliet, Nour-Eddine Oussous, Yosra Rekik, Romain Rouvoy, Mikaºl Salson, Alexandre Sedoglavic, Bayrem Tounsi, Cristian Versari, Christophe Vroland, ric Wegrzynowski, LØopold Weinberg, Hassina Zeghlache.
Licence Creative Commons cbea
Ce polycopiØ est soumis la licence Creative Commons Attribution Pas d’Utilisation Commerciale Partage l’Identique 3.0 France ).
Chapitre 1
Expressions et instructions
1.1 Expressions
Une expression est une mani?re de reprØsenter un calcul. Par exemple, l’aire d’un disque de rayon r est donnØe par l’expression :
?r2
Cette expression est composØe de plusieurs sous-expressions. Certaines sous-expressions ne peuvent plus Œtre dØcomposØes, elles sont atomiques. Il s’agit soit de constantes, soit de variables, soit de fonctions ou d’opØrateurs.
*.
pi
r 2.
Dans les formules les grandeurs poss?dent ce que les physiciens appellent des dimensions, en informatique on parle plut t de types.
Lorsqu’on Øcrit de mani?re traditionnelle une expression, un certain nombre de conventions d’Øcriture nous permet d’omettre certains signes d’opØrations. Ici, par exemple, les signes de multiplications sont implicites. Lorsqu’on souhaite traduire cette expression de mani?re informatique, il faudra savoir que des rØgles strictes devront Œtre appliquØes, l’ensemble de ces r?gles forme la syntaxe du langage, et il faudra absolument les respecter pour espØrer obtenir un rØsultat.
1.2 Le logiciel Objective Caml
Le langage informatique que nous utiliserons pour ce cours est Caml. On peut utiliser ce langage dans di Ørents modes.
En mode interprØtØ : dans ce mode le programmeur dialogue (en Caml) avec un interpr?te du langage. Plus prØcisØment, il rØdige des phrases qu’il communique l’interpr?te, et celuici vØri e qu’elles sont bien rØdigØes et donne en retour une rØponse au programmeur. Le mode interprØtØ permet au programmeur d’Øvaluer immØdiatement et pas pas ses idØes.
9
En mode compilØ : dans ce mode, le programmeur rØdige (avec un Øditeur de textes) l’intØgralitØ de son programme, puis le soumet un compilateur du langage dont le r le est de produire un programme exØcutable. Si le programme est correctement rØdigØ (aucune erreur de syntaxe, cohØrence des types dans les expressions, ), il ne reste plus au programmeur qu’ lancer l’exØcution de son programme et vØri er la conformitØ de cette exØcution au cahier des charges initial.
Dans le cours d’InitProg, nous n’utiliserons que le mode interprØtØ. La compilation sera abordØe dans le cours API1 au semestre suivant.
Caml est un langage dØveloppØ par l’INRIA (Institut National de Recherche en Informatique et Automatique) que l’on peut tØlØcharger l’adresse . On en trouve di Ørentes implantations et celle que nous utiliserons est Objective Caml. Objective Caml est un logiciel libre qui peut Œtre tØlØchargØ depuis l’adresse prØcØdente ainsi que le manuel d’utilisation. Il en existe des versions pour les plateformes les plus courantes : Linux, Microsoft Windows, MacOS X. Dans ce polycopiØ, ainsi que dans les salles de TP, nous utiliserons une version pour Linux.
Pour dØbuter une session de dialogue avec l’interpr?te d’Objective Caml, on tape la commande ocaml dans un terminal.
> ocaml
Objective Caml version 3.10.2
#
Le symbole di?se (#) est l’invite de l’interpr?te : c’est le signe qu’il est prŒt vous Øcouter et exØcuter la commande que vous lui donnerez.
Avant de dØcouvrir les premi?res expressions et instructions du langage Caml, voyons celle qui permet de quitter l’interpr?te. C’est la directive#quit.
# #quit ;;
>
1.3 Premi?res expressions en Caml
1.3.1 Expressions numØriques
La syntaxe des expressions numØriques est tr?s proche de la notation mathØmatique usuelle. Ci-dessous, l’expression en Caml pour l’expression
, (1.1)
accompagnØe de la rØponse fournie par l’interpr?te.
# (4 * (-3 + 5)) / 2 ;;
- : int = 4
Analysons ce point de dialogue avec l’interpr?te.
1.3. PREMI¨RES EXPRESSIONS EN CAML
1. Tout d’abord l’expression (4 * (-3 + 5)) / 2. Elle est tr?s proche de la notation mathØmatique usuelle, les nombres sont notØs comme d’habitude, l’addition et la division aussi, la multiplication est notØe *, et on utilise des parenth?ses pour marquer ici la prioritØ de certaines opØrations sur d’autres.
2. L’expression est terminØe par un double point-virgule (;;). C’est une situation gØnØrale dans tout dialogue avec l’interpr?te, le double point-virgule marque la n d’une phrase que l’on souhaite communiquer l’Øvaluation. Ce marqueur mis, il ne reste plus qu’ le faire suivre d’un retour-chariot (touche Entrée du clavier) pour soumettre la phrase l’interpr?te.
3. Si l’expression ne contient aucune erreur de syntaxe, et est typable, alors l’interpr?te proc?de son Øvaluation et en donne le rØsultat. Dans le cas prØsent, l’expression est parfaitement bien formØe (aucune erreur de syntaxe), elle est correcte du point de vue des types mis en jeux, et l’interpr?te nous indique que cette expression a une valeur de type numØrique entier (int) et que sa valeur est l’entier 4.
PrØcisons tout de suite qu’une expression ne doit pas nØcessairement Œtre Øcrite sur une seule ligne. On peut Øcrire une expression sur autant de lignes que l’on veut. C’est le marqueur de n ;; qui indique l’interpr?te que la rØdaction de l’expression est achevØe. Voici la mŒme expression rØdigØe sur plusieurs lignes.
# ( 4 * ( -3 + 5 ) ) / 2 ;; - : int = 4 |
L’opØration de division sur les nombres entiers fournit le quotient dans la division euclidienne. Par exemple 7/3 vaut 2 et non pas environ 2.3333. Le reste de la divition est obtenu avec l’opØrateur mod.
# 7 / 3 ;;
- : int = 2
# 7 mod 3 ;;
- : int = 1
# 3 * 2 + 1 ;;
- : int = 7
Bien entendu, on peut calculer des nombres non entiers que nous nommerons nombres ottants ou simplement ottants. En Caml, ces nombres sont tous marquØs d’un sØparateur dØcimal, le point, qu’ils soient ou non dotØs de chi res apr?s la virgule.
# 2. ;; - : float = 2. # 2.333 ;; - : float = 2.333 |
Comme on peut le voir sur ces deux exemples, le type de ces nombres est float, pour nombre virgule ottante .
En Caml, il faut distinguer les opØrateurs arithmØtiques portant sur des nombres entiers, de ceux portant sur des nombres non entiers. Les opØrateurs pour les quatre opØrations usuelles (addition, soustraction, multiplication et division) portant sur les nombres de type float sont identiques ceux portant sur les nombres entiers, mais suivis d’un point. Voici l’expression arithmØtique (1.1) ci-dessus, ØvaluØe avec des nombres de type float.
# (4. *. (-. 3. +. 5.)) /. 2. ;; - : float = 4.
Caml refuse systØmatiquement toute expression numØrique oø sont mØlangØes des nombres de nature di Ørentes.
# 1 + 2. ;;
This expression has type float but is here used with type int # 1 +. 2. ;;
This expression has type int but is here used with type float
Les deux fonctions int_of_float et float_of_int assurent la conversion d’un nombre d’un type l’autre.
# int_of_float (-2.7) ;; - : int = -2 # int_of_float (2.7) ;; - : int = 2 # float_of_int (2);; - : float = 2. # 1 + int_of_float (2.) ;; - : int = 3 # 1. +. float_of_int (2) ;; - : float = 3. |
Il existe de tr?s nombreuses autres fonctions. En voici quelques unes :
1. sur les entiers : abs (valeur absolue d’un nombre entier).
2. sur les non entiers : abs_float (valeur absolue d’un ottant), sqrt (racine carrØe d’un ottant), exp (exponentielle de base e), log (logarithme nØpØrien), cos, sin, tan, et bien d’autres encore.
1.3.2 Expressions boolØennes
En programmation, les expressions boolØennes sont nØcessaires pour e ectuer des calculs ou exØcuter des instructions dØpendant de la rØalisation ou non de certaines conditions (cf chapitres 2 et 3).
Les boolØens forment un ensemble deux valeurs seulement, dØsignØes en Caml par true (vrai) et false (faux). Le type des boolØens est dØsignØ par bool.
Les expressions boolØennes sont les expressions qui ont pour valeur l’un des deux boolØens. Elles apparaissent naturellement dans les comparaisons.
1.3. PREMI¨RES EXPRESSIONS EN CAML
# true ;;
- : bool = true
# false ;;
- : bool = false
# 1 = 5-4 ;;
- : bool = true
# 1
- : bool = false
# 1 >= 5-4 ;;
- : bool = true
Les opØrateurs logiques usuels sont && (et), || (ou) et not (nØgation).
# (1 = 1) && (1 = 0) ;; - : bool = false
# (1 = 1) || (1 = 0) ;;
- : bool = true
# not (1 = 0) ;;
- : bool = true
Le chapitre 2 donne plus de prØcisions sur les opØrateurs logiques et les expressions boolØennes, ainsi que sur les expressions et instructions boolØennes.
1.3.3 Caract?res et cha nes de caract?res
Les caract?res forment un type nommØ char en Caml qui comprend 256 valeurs. Parmi ces valeurs on trouve toutes les lettres de l’alphabet latin dans leur version minuscule et majuscule, ainsi que les dix chi res, et des symboles de ponctuation.
Une expression littØrale de type char est obtenue en pla ant le caract?re voulu entre apostrophes.
# ’A’;;
- : char = ’A’
# ’a’;;
- : char = ’a’
# ’1’;;
- : char = ’1’
# ’?’;;
- : char = ’?’
Les cha nes de caract?res sont des suites nies de caract?res placØs les uns la suite des autres. Elles peuvent ne contenir aucun caract?re : cha ne vide, et elles peuvent en contenir jusqu’ 224?6, soit plus de 16 millions de caract?res. En Caml, elles sont mises entre guillemets et leur type est dØsignØ par string.
# "Aa1?" ;;
- : string = "Aa1?"
# "";;
- : string = ""
L’opØrateur de concatØnation qui construit une cha ne en mettant bout bout deux cha nes est dØsignØ par ^.
# "InitProg"^" c’est vachement bien !";;
- : string = "InitProg c’est vachement bien !"
Le chapitre 7 est consacrØ une prØsentation plus dØtaillØe des caract?res et cha nes de caract?res.
1.4 Instructions
En Caml, une instruction est une expression dont la valeur est de type unit. Ce type ne contient qu’une seule valeur notØe (). Par consØquent, cela signi e que toute instruction a pour valeur (), que cette valeur est connue avant mŒme que l’expression ne soit ØvaluØe, et donc que ce qui importe n’est pas tant la valeur de l’instruction, que l’e et de bord qu’elle produit. Et d’ailleurs, plut t que de parler d’Øvaluation de l’expression, on dit plut t exØcution de l’instruction.
Les e ets de bord produits par l’exØcution d’une instruction peuvent Œtre de plusieurs natures : modi cation de la valeur de l’environnement courant de travail, par exemple en modi ant la valeur d’une variable mutable (cf chapitre 4); communication du programme avec le monde extØrieur, par exemple par lecture ou Øcriture d’une valeur.
Voici la plus simple (et la plus inutile) des instructions.
# () ;;
- : unit = ()
L’exØcution de cette instruction ne provoque aucun e et de bord (ni modi cation de variable, ni lecture, ni Øcriture). Seule sa valeur est fournie par l’interpr?te.
1.4.1 Instructions d’impression
Plus intØressantes sont les instructions pour imprimer ou Øcrire des valeurs. Elles se distinguent selon le type des valeurs imprimer. En voici quatre illustrØes chacune par un exemple.
# print_int (8) ;;
8- : unit = ()
# print_float (8.) ;;
8.- : unit = ()
# print_string ("8") ;;
8- : unit = ()
# print_char (’8’) ;;
8- : unit = ()
Il faut bien comprendre la rØponse de l’interpr?te l’exØcution de ces instructions d’impression. Dans chacun des cas, on peut voir l’impression de la valeur donnØes ces instructions, immØdiatement suivie par la valeur de l’instruction qui est immuablement - : unit = ().
On pourrait prØfØrer qu’un saut de ligne distingue la valeur imprimØe de la valeur de l’instruction. La fonction print_endline e ectue un saut de ligne immØdiatement apr?s avoir imprimØ ce qu’on lui demande. Mais cette fonction ne permet l’impression que des cha nes de caract?res.
1.4. INSTRUCTIONS
# print_endline ("Timoleonapprend a programmer en Caml") ;; Timoleon apprend a programmer en Caml - : unit = () |
Une autre instruction provoque des sauts de ligne : l’instruction print_newline ().
# print_newline () ;;
- : unit = ()
Comme on peut le voir sur cet exemple, cette instruction ne prend aucun param?tre. Elle se contente d’imprimer un saut de ligne, et si rien auparavant n’a ØtØ imprimØ, comme c’est le cas ici, on obtient une ligne vide. Cette instruction suit en gØnØral d’autres instructions d’impression, et nØcessite d’exØcuter une sØquence d’instructions. Cette notion de sØquence d’instructions est prØsentØe dans la section 1.4.3.
1.4.2 Instructions du module Cartes
Le module Cartes est une extension du langage Caml qui permet de manipuler des tas de cartes jouer. Ce module est prØsentØ dans l’annexe A. Deux instructions y sont dØ nies :
1. l’instruction init_tas(n,s) qui initialise le tas numØro n avec une pile de cartes dØcrite par la cha ne de caract?res s;
2. et l’instruction deplacer_sommet(n,p) qui dØplace une carte du tas numØro n vers le tas numØro p.
Par exemple, en supposant qu’initialement aucun tas ne contienne de cartes, alors le dialoguequi suit donne le tas tel qu’on peut le voir sur la gure 1.1.
# init_tas (1,"TCP") ;;
- : unit = ()
Comme on peut le constater sur la gure 1.1, l’e et de bord provoquØ par cette instruction est une initialisation du tas numØro 1 avec trois cartes de couleurs successives ?, ? et ?.
En poursuivant le dialogue avec l’interpr?te, on dØplace la carte au sommet du tas numØro 1 vers le tas numØro 2 et la situation atteinte est celle montrØe sur la gure 1.2.
# deplacer_sommet (1,2) ;;
- : unit = ()
L’e et de bord de l’instruction deplacer_sommet (1,2) est la transformation de l’Øtat des cartes.
1.4.3 SØquence d’instructions
Supposons qu’initialement seul le premier tas de cartes n’est pas vide, et que ce tas contient trois cartes de couleur ?, ?, ? dans cet ordre de bas en haut (cf gure 1.1). Supposons que nous voulions vider le tas 1 en pla ant une carte sur chacun des trois autres tas (cf 1.3).
Cela peut se faire simplement en dØpla ant une une les cartes du tas 1 vers les autres tas comme le montre l’algorithme 1.1.
En Caml, cet algorithme se traduit simplement par trois instructions deplacer_sommet.
Si on utilise la boucle de dialogue avec l’interpr?te du langage, on atteint la situation voulue avec le dialogue :
Figure 1.1 Le tas 1 apr?s l’instruction init_tas (1,"TCP")
Algorithme 1.1 Mettre les trois cartes du tas 1 vers les tas 2, 3 et 4
1: deplacer le sommet du tas 1 vers le tas 2
2: deplacer le sommet du tas 1 vers le tas 3
3: deplacer le sommet du tas 1 vers le tas 4
# deplacer_sommet(1,2);;
- : unit = ()
# deplacer_sommet(1,3);;
- : unit = ()
# deplacer_sommet(1,4);;
- : unit = ()
Dans ce dialogue, chacune des trois instructions est donnØe exØcuter les unes apr?s les autres, et l’interpr?te donne le rØsultat de son travail apr?s chacune d’elles (la mention - : unit = ()).
On peut aussi regrouper ces trois instructions en une seule :
# deplacer_sommet(1,2); deplacer_sommet(1,3); deplacer_sommet(1,4);;
- : unit = ()
L’usage du simple point-virgule pour sØparer les instructions permet de les transmettre l’interpr?te en une seule fois, et celui-ci ne donne qu’une seule rØponse. En un seul ordre, nous avons commandØ l’exØcution de trois instructions.
Cette construction est tr?s frØquente en programmation impØrative, et on la nomme sØquence d’instructions. En Caml, une sØquence d’instructions s’obtient en sØparant les instructions par un simple point-virgule. Dans une sØquence d’instructions, le nombre d’instructions n’est pas
1.4. INSTRUCTIONS
Figure 1.2 Situation obtenue apr?s l’instruction deplacer_sommet (1,2)
limitØ.
fournie d’une sØquence est la valeur de la derni?re instruction, c’est- -dire () en gØnØral.
Voici un autre exemple d’utilisation de la sØquence d’instructions pour produire une a chage d’une ligne composØe de plusieurs ØlØments de types distincts.
# print_string ("(4 * (-3 + 5)) / 2 = "); print_int ((4 * (-3 + 5)) / 2) ; print_newline () ;; (4 * (-3 + 5)) / 2 = 4 - : unit = () |
On verra qu’il est parfois nØcessaire de parenthØserune sØquence d’instructions pour Øviter certaines ambiguitØs (cf page 28). En Caml cela peut se faire avec des parenth?ses ouvrante et fermante, ou bien avec les deux mots-clØs du langage begin et end. Dans la suite nous dØsignerons par bloc d’instructions toute sØquence placØe entre ces deux mots.
Figure 1.3 Situation nale souhaitØe
begin (* sequence d’instructions *) end |
Syntaxe : Bloc d’instructions
Ce parenthØsage n’a que pour seule vocation Øviter des ambiguitØs syntaxiques, et ne change rien l’exØcution de la sØquence qu’il contient.
# begin print_string ("(4 * (-3 + 5)) / 2 = "); print_int ((4 * (-3 + 5)) / 2) ; print_newline () end ;; (4 * (-3 + 5)) / 2 = 4 - : unit = () |
1.5. EXERCICES
1.5 Exercices
1.5.1 Expressions numØriques
Exercice 1-1 valuations d’expressions arithmØtiques
Pour chacune des expressions arithmØtiques qui suivent, Øvaluez-les avec Objective Caml en arithmØtique sur les entiers (int) et en arithmØtique sur les ottants (float).
1.
2.
3.
4..
5.
Pour la derni?re expression, expliquez la di Ørence sensible entre la valeur obtenue en arithmØtique enti?re, et celle en arithmØtique ottante.
1.5.2 Instructions
Exercice 1-2
Impressions de valeurs
Question 1 Utilisez l’une des instructions print_ pour imprimer la valeur des expressions de l’exercice
Question 2 crivez une instruction qui imprime une expression arithmØtique, puis le signe =, puis la valeur de l’expression arithmØtique et en n un passage la ligne. Voici un exemple, dans lequel l’instruction a ØtØ e acØe.
#(* instruction effacee *)
(3+4)*5 = 35
- : unit = ()
Trouvez une sØquence d’instructions qui rØalise cela, puis cherchez une seule instruction.
20 CHAPITRE 1. EXPRESSIONS ET INSTRUCTIONS
Chapitre 2
Conditions, expressions et instructions conditionnelles
2.1 Le probl?me
tat initial : Tas 1 un tr? e ou un pique les autres tas vides. tat nal : tas 1 et 4 vides et le tas 2 contient le tr? e ou rien , et le tas 3 contient le pique
ou rien.
2.1.1 Algorithme
La rØsolution du probl?me nØcessite une Øtude de cas :
Algorithme 2.1 Solution du probl?me
si la carte au sommet du tas 1 est un tr? e alors
mettre la carte sur le tas 2
sinon mettre la carte sur le tas 3 n si
2.2 Expressions boolØennes
2.2.1 BoolØens
On appelle boolØenl’une des deux valeurs de vØritØ vrai ou faux. On dØsigne en abrØgØ ces deux valeurs par les deux lettres V et F.
Une expression boolØenne est une expression qui prend une valeur boolØenne, autrement dit l’une ou l’autre des deux valeurs V ou F.
Les expressions boolØennes servent exprimer des conditions. Elles peuvent Œtre simples ou composØes
21
2.2.2 Expressions simples
Les expressions boolØennes simples
"la carte au sommet du tas 1 est un tr? e"
2.2.3 Expressions composØes
L’opØrateur ou
L’expression E ="la carte au sommet du tas 1 est un tr? e ou un carreau" peut se dØcomposer en deux expressions simples
1. E1 ="la carte au sommet du tas 1 est un tr? e",
2. E2 ="la carte au sommet du tas 1 est un carreau" le lien les unissant Øtant le connecteur ou opØrateur logique ou
E = E1ouE2
L’expression E est donc composØe.
L’expression E ne prend la valeur V que si au moins l’une des deux expressions E1, E2 est vraie.
On rØsume cette dØ nition de l’opØrateur ou par la table de vØritØ reprØsentØe par le tableau
2.1
E1 | E2 | E1ouE2 |
V | V | V |
V | F | V |
F | V | V |
F | F | F |
Table 2.1 Table de vØritØ de l’opØrateur ou
L’opØrateur et
L’expression E ="la carte au sommet du tas 1 est un tr? e et sa valeur est supØrieure celle de la carte situØe au sommet du tas 2" peut se dØcomposer en deux expressions simples
1. E1 ="la carte au sommet du tas 1 est un tr? e",
2. E2 ="la carte au sommet du tas 1 a une valeur supØrieure ou Øgale celle du tas 2" le lien les unissant Øtant le connecteur ou opØrateur logique et
E = E1etE2
L’expression E est donc composØe.
L’expression E ne prend la valeur V que si les deux expressions E1, E2 sont vraies.
On rØsume cette dØ nition de l’opØrateur et par la table de vØritØ reprØsentØe par le tableau
2.2.
2.2. EXPRESSIONS BOOL ENNES
E1 | E2 | E1etE2 |
V | V | V |
V | F | F |
F | V | F |
F | F | F |
Table 2.2 Table de vØritØ de l’opØrateur et
L’opØrateur non
L’expression E ="la carte au sommet du tas 1 n’est pas un tr? e" peut se dØcomposer en une expressions plus simple
1. E1 ="la carte au sommet du tas 1 est un tr? e", que l’on nie.
E = non(E1)
L’expression E est donc composØe.
La valeur de l’expression E est opposØe celle de E1.
On rØsume cette dØ nition de l’opØrateur non par la table de vØritØ reprØsentØe par le tableau
2.3.
E1 | non(E1) |
V | F |
F | V |
Table 2.3 Table de vØritØ de l’opØrateur non
2.2.4 PropriØtØs des opØrateurs
a, b et c sont trois expressions boolØennes.
Double nØgation | non(non(a)) = a |
lØment neutre du ou | aouF = a |
lØment neutre du et | aetV = a |
lØment absorbant du ou | aouV = V |
lØment absorbant du et | aetF = F |
Idempotence du ou | aoua = a |
Idempotence du et | aeta = a |
Tautologie | aou non(a) = V |
Contradiction | aet non(a) = F |
CommutativitØ du ou | aoub = boua |
CommutativitØ du et | aetb = beta |
AssociativitØ du ou | (aoub) ouc = aou (bouc) |
AssociativitØ du et | (aetb) etc = aet (betc) |
DistributivitØ du et par rapport au ou | a et (b ou c) = (a et b) ou (a et c) |
DistributivitØ du ou par rapport au et | a ou (b et c) = (a ou b) et (a ou c) |
Loi de Morgan (1) | non(aoub) = non(a) et non(b) |
Loi de Morgan (2) | non(aetb) = non(a) ou non(b) |
2.3 En Caml
2.3.1 BoolØens
En Caml, les deux valeurs boolØennes dØ nissent le type bool.
vrai | true |
faux | false |
Table 2.4 BoolØens en Caml
2.3.2 Expressions boolØennes
Les expressions boolØennes simples peuvent s’exprimer en Caml par des valeurs littØrales true ou false, une variable boolØenne (voir plus tard), une expression dØcrivant une relation, un appel une fonction valeurs boolØennes.
Figure 2.1 Un Øtat des tas de cartes
Exemple 1 :
Tous les exemples donnØs par la suite s’appuient sur une con guration des tas donnØe la gure
2.1.
2.3. EN CAML
# true ;; - : bool = true # false ;; - : bool = false # tas_vide(1);; - : bool = true # tas_non_vide(1);; - : bool = false # couleur_sommet(2) = PIQUE;; - : bool = false # couleur_sommet(2) = CARREAU;; - : bool = true # sommet_trefle(3);; - : bool = true |
Les expressions composØes se traduisent avec les opØrateurs logiques &&, || et not.
OpØrateur logique | et | ou | non |
En Caml | && | || | not |
Table 2.5 OpØrateurs logiques en Caml
Exemple 2 :
# true && true;; - : bool = true # true && false;; - : bool = false # true || false;; - : bool = true # false || false;; - : bool = false # not (true);; - : bool = false # not (false);; - : bool = true # sommet_carreau(2) && sommet_trefle(3) ;; - : bool = true # sommet_carreau(2) && not (sommet_coeur(3)) ;; - : bool = true # tas_non_vide(1) || sommet_coeur(4);; - : bool = true |
2.3.3 Attention!
Les opØrateurs && et || n’agissent que sur des boolØens!
On pourrait Œtre tentØ, pour exprimer que la carte au sommet du tas 1 est un tr? e ou un carreau, d’Øcrire
couleur_sommet(1) = TREFLE || CARREAU,
mais cela est incorrect car TREFLE et CARREAU ne sont pas des boolØens, mais des couleurs. Il faut donc Øcrire
couleur_sommet(1) = TREFLE || couleur_sommet(1) = CARREAU
mŒme si cela semble bien lourd.
2.3.4 Remarque sur les opØrateurs && et ||
En logique boolØenne, les opØrateurs et et ou sont commutatifs
aetb = beta aoub = boua
En Caml, ces opØrateurs ne sont pas commutatifs : les arguments sont ØvaluØs sØquentiellement de gauche droite.
Exemple 3 :
En Caml, les expressions
tas_non_vide(1) && sommet_trefle(1)
et sommet_trefle(1) && tas_non_vide(1) ne sont pas Øquivalentes :
l’Øvaluation de la premi?re expression ne dØclenche jamais d’exception, car si le tas 1 est vide, sommet_trefle(1) n’est pas ØvaluØ, puisque la valeur de l’expression compl?te est alors dØterminØe
# tas_non_vide(1) && sommet_trefle(1);;
- : bool = false
en revanche l’Øvaluation de la seconde expression dØclenche une exception si le tas 1 est vide
# sommet_trefle(1) && tas_non_vide(1) ;; Exception: LesExceptions.Tas_Vide 1.
2.4 Expressions conditionnelles
Les expressions conditionnelles sont des expressions qui dØterminent l’expression Øvaluer en fonction de la validitØ d’une condition.
ifthen 1>else 2> |
Syntaxe : Expression conditionnelle
Exemple 4 :
Dans le contexte indiquØ par la gure 2.1, on a
2.5. INSTRUCTIONS CONDITIONNELLES
# if sommet_carreau(2) then 0 else 1 ;; - : int = 0 # if sommet_trefle(2) then 0 else 1 ;; - : int = 1 |
2.5 Instructions conditionnelles
Les instructions conditionnelles sont des expressions conditionnelles dont la valeur est du type unit. On les utilise pour agir en fonction d’un contexte.
Instruction conditionnelle compl?te
L’instruction conditionnelle compl?te (ou alternative) permet de mener une action si une condition est satisfaite, et une autre dans le cas contraire.
ifthen (* bloc d’instructions *)else (* bloc d’instructions *) |
Syntaxe : Instruction conditionnelle compl?te
Exemple 5 :
Traduction en Caml de l’algorithme dØcrit la section 2.1.1.
if sommet_trefle(1) then begin deplacer_sommet(1,2) end else begin deplacer_sommet(1,3) end |
La condition est ici exprimØe par l’expression boolØenne (simple) sommet_trefle(1), le premier bloc d’instructions (celui qui suit le mot rØservØ then) est
begin deplacer_sommet(1,2)
end
et le second bloc (qui suit le mot rØservØ else)
begin deplacer_sommet(1,3) end
Notez qu’il n’y a pas de; apr?s le end qui prØc?de le else. En revanche, si cette instruction conditionnelle est suivie d’une autre, il faudra ajouter un; apr?s le end du second bloc (end {if};).
Instruction conditionnelle simple Il arrive qu’une action ait besoin d’Œtre menØe si une condition est satisfaite, mais qu’aucune ne soit nØcessaire sinon. C’est alors une instruction conditionnelle simple. En Caml, elle s’Øcrit sans la partie else.
ifthen (* bloc d’instructions *) |
Syntaxe : Instruction conditionnelle simple
Exemple 6 :
DØplacer la carte situØe au sommet du tas 1 si c’est un tr? e sinon ne rien faire.
if sommet_trefle(1) then begin
deplacer_sommet(1,2)
end
2.5.1 Remarque sur le parenthØsage
La syntaxe donnØe ci-dessus pour l’instruction conditionnelle mentionne quapr?s le then et le else doivent gurer des blocs d’instructions, c’est- -dire des sØquences parenthØsØes par begin et end.
En rØalitØ, il n’est pas nØcessaire de mettre le parenthØsage lorsque la sØquence ne comprend qu’une seule instruction (comme pour les expressions conditionnelles). Ainsi on peut Øcrire
if sommet_trefle(1) then
deplacer_sommet(1,2) else
deplacer_sommet(1,3)
En revanche, d?s que la sØquence comprend plusieurs instructions, le parenthØsage devient nØcessaire dans la partie else pour une instruction conditionnelle compl?te, et dans la partie then pour une instruction conditionnelle simple. En e et, l’instruction
if sommet_trefle(1) then begin
deplacer_sommet(1,2); deplacer_sommet(2,3)
end
ne peut pas Œtre remplacØe par
if sommet_trefle(1) then deplacer_sommet(1,2); deplacer_sommet(2,3)
qui est une sØquence de deux instructions :
1. une instruction conditionnelle simple,
2. suivie d’une instruction de dØplacement non soumise condition.
2.6. M THODOLOGIE
2.6 MØthodologie
Voici quelques principes mØthodologiques concernant la conception d’instructions conditionnelles.
1. tude des cas intervenant dans le probl?me commencer par distinguer les di Ørents cas,
vØri er que ces cas sont bien exhaustifs (on n’oublie aucune situation) vØri er que ces cas ne sont pas redondants (cas exclusifs)
donner un exemple de comportement attendu de l’instruction pour chacun des cas
2. Pour chacun des cas
Øtablir un test (expression boolØenne) permettant de distinguer le cas dØterminer la sØquence d’instructions exØcuter dans ce cas
3. Construire un jeu de tests qui permet de s’assurer de la validitØ du programme : ce jeu doit comprendre au moins un test pour chacun des cas envisagØs.
Exemple
ConsidØrons une situation initiale oø les tas numØrotØs de 1 3 contiennent un nombre quelconque non nul de cartes, et le tas 4 est vide.
init_tas(1,"(T+K+C+P)[T+K+C+P]"); init_tas(2,"(T+K+C+P)[T+K+C+P]"); init_tas(3,"(T+K+C+P)[T+K+C+P]"); init_tas(4,"");
L’objectif atteindre est de dØplacer la carte de plus grande valeur au sommet d’un des trois tas vers le tas 4.
RØsoudre ce probl?me revient repØrer quel tas poss?de en son sommet la carte de plus grande valeur.
tude des cas Il y a Øvidemment trois possibilitØs : c’est le tas 1 ou le tas 2 ou le tas 3. Comment les distinguer? c’est le tas 1, si la carte au sommet du tas 1 est supØrieure ou Øgale celle du tas 2, et est supØrieure ou Øgale celle du tas 3.
c’est le tas 2, si la carte au sommet du tas 2 est supØrieure ou Øgale celle du tas 1, et est supØrieure ou Øgale celle du tas 3.
c’est le tas 3, si la carte au sommet du tas 3 est supØrieure ou Øgale celle du tas 1, et est supØrieure ou Øgale celle du tas 2.
Autrement dit c’est le tas i si la condition superieur(i,j) && superieur(i,k) (dans laquelle j et k dØsignent les deux numØros de tas autres que i) est satisfaite. Les conditions distinguant les trois cas ne sont pas exclusives (penser aux cas d’ØgalitØ).
2.7 Exercices
Exercice 2-1
En utilisant les tables de vØritØ, prouvez quelques propriØtØs des opØrateurs logiques et, ou et non.
Exercice 2-2 Ou exclusif
Si a et b sont deux expressions boolØennes, le ou-exclusif de ces deux expressions, notØ a?b, est une nouvelle expression boolØenne qui est vraie si et seulement si une seule des deux expressions a ou b est vraie. La table de vØritØ du ou-exclusif est donnØe
a | b | a ? b |
V | V | F |
V | F | V |
F | V | V |
F | F | F |
Table 2.6 Table de vØritØ de l’opØrateur ou-exclusif
crivez l’expression a ? b l’aide des opØrateurs et, ou et non.
Exercice 2-3
Question 1 Exprimez le fait que [a,b] et [c,d] sont des intervalles disjoints, attention au cas des intervalles vides, par exemple si a = 15 et b = ?5.
Question 2 Exprimez le fait que [a,b] et [c,d] sont des intervalles qui se recouvrent partiellement de deux mani?res :
1. en utilisant la solution de la question prØcØdente (c’est tr?s simple).
2. directement (c’est compliquØ!).
Exercice 2-4 ØgalitØ et valeur boolØenne
Question 1 Soit a une expression boolØenne. RØaliser la table de vØritØ des expressions :
1. a = V
2. a = F
Exercice 2-5
Question 1 crivez l’instruction ci-dessous sans utiliser l’opØrateur non ni d’opØrateurs de comparaison. si non a alors instr1
sinon
instr2 n si
Question 2
crivez l’instruction ci dessous sans utiliser l’opØrateur et
2.7. EXERCICES
si aetb alors instr1
n si
Question 3
crivez l’instruction ci dessous sans utiliser l’opØrateur ou
si aoub alors instr1 n si
Exercice 2-6
Expliquez pourquoi le programme
if superieur(1,2) && superieur(1,3) then begin
deplacer_sommet(1,4)
end; if superieur(2,1) && superieur(2,3) then begin
deplacer_sommet(2,4)
end; if superieur(3,1) && superieur(3,2) then begin
deplacer_sommet(3,4)
end ;;
n’est pas correct pour le probl?me posØ dans la section 2.6
Exercice 2-7
Reprenez le probl?me de la section 2.6 en admettant qu’un ou plusieurs des trois premiers tas peut Œtre vide. Si les trois tas sont vides, on ne dØplace aucune carte.
32CHAPITRE 2. CONDITIONS, EXPRESSIONS ET INSTRUCTIONS CONDITIONNELLES
Chapitre 3
Instructions conditionnellement rØpØtØes
3.1 Un probl?me
tat initial : Tas 1 un nombre quelconque de cartes, les autres tas vides. tat nal : tas 1, 3 et 4 vides, le tas 2 contient toutes les cartes du tas 1 initial
3.2 Algorithme
La rØsolution du probl?me nØcessite de dØplacer (une une) toutes les cartes du tas 1 vers le tas 2. Ce qu’on peut dØcrire par
Algorithme 3.1 Solution du probl?me
tant que le tas 1 n’est pas vide faire
dØplacer la carte au sommet du tas 1 vers le tas 2 n tant que
3.3 Sortie d’une boucle tant que
Une boucle tant que se termine lorsque sa condition n’est plus satisfaite. Par consØquent la sortie de la boucle, on est assurØ que la condition est fausse
tant que condition faire actions
n tant que
{condition est fausse}
3.4 La boucle tant que en Caml
Comme bien des langages de programmation, Caml permet d’Øcrire des instructions conditionnellement rØpØtØes. La syntaxe de l’instruction tant que est dØcrite de mani?re gØnØrale ci-dessous.
33
34 CHAPITRE 3. INSTRUCTIONS CONDITIONNELLEMENT R P T ES
whiledo (* sequence d’instructions *) done |
Syntaxe : Boucle tant que
Exemple traduction en Caml de l’algorithme dØcrit la section 3.2.
while tas_non_vide(1) do
deplacer_sommet(1,2)
done
Lorsqu’elle sera ØxØcutØe, cette instruction testera si le tas 1 est non vide. Si ce n’est pas le cas (c’est- -dire si le tas 1 est vide) alors l’instruction est terminØe, sinon (si le tas 1 n’est pas vide), une carte sera dØplacØe du tas numØro 1 vers le tas numØro 2. Ce dØplacement e ectuØ, la vacuitØ du tas numØro 1 sera nouveau testØe, et selon le cas l’instruction est terminØe ou un dØplacement est e ectuØ. Et on poursuit ainsi tant que le tas 1 n’est pas vide.
3.5 MØthodologie
La conception d’une boucle tant que nØcessite plusieurs points d’attention :
la situation avant d’entrer dans la boucle (prØ-condition) est elle celle souhaitØe? Par exemple, l’instruction qui suit peut Œtre source d’erreur.
while sommet_trefle(1) do
deplacer_sommet(1,2)
done
En e et, la condition du tant que porte sur la couleur de la carte au sommet du tas 1. Pour cela on utilise la fonction sommet_trefle. Mais pour Œtre utilisØe, celle-ci est nØcessite que le tas numØro 1 ne soit pas vide. la situation la sortie de la boucle (post-condition) est elle bien celle souhaitØe? la boucle ne risque t elle pas d’Œtre in nie (probl?me de l’arrŒt)?
Par exemple, l’instruction qui peut conduire une rØpØtition in nie de dØplacement d’une carte du tas 1 vers le tas 2, puis d’un retour de la carte dØplacØe vers son tas d’origine. En e et si le tas 1 n’est pas vide au moment d’exØcuter cette instruction, la condition du tant que est satisfaite et l’action est exØcutØe, action qui aboutit la mŒme situation que celle de dØpart : le tas 1 ne sera jamais vide.
while tas_non_vide(1) do deplacer_sommet(1,2); deplacer_sommet(2,1) done
3.6. EXERCICES 35
3.6 Exercices
Exercice 3-1
DØcrivez les relations satisfaites entre a, b et c l’issue des boucles qui suivent
1. tant que a = b faire
actions
n tant que
2. tant que a ? b faire
actions
n tant que
3. tant que (a 6= b) ou (a > c) faire
actions
n tant que
Exercice 3-2
Les exercices de manipulation de cartes.
36 CHAPITRE 3. INSTRUCTIONS CONDITIONNELLEMENT R P T ES
Chapitre 4
Constantes, variables
4.1 Types de donnØes
En programmation, les donnØes manipulØes peuvent Œtre de natures di Ørentes : nombres entiers, nombres rØels, cha nes de caract?res, boolØens, . Ces di Ørentes natures de donnØes sont appelØes types de donnØes.
Le langage Caml dispose d’un certain nombre de types prØdØ nis.
4.1.1 Les boolØens
Le type bool est le type des expressions boolØennes permettant d’Øcrire les conditions des instructions if et while. Les donnØes de ce type ne peuvent prendre que deux valeurs.
Nom : bool
Ensemble des valeurs : true, false
LittØraux : true et false
OpØrateurs : &&, ||, not Exemple 1 :
# true;;
- : bool = true
# not(true);;
- : bool = false
# true || false;;
- : bool = true
4.1.2 Les nombres entiers
Le type int est le type des expressions numØriques enti?res.
Nom : int
37
Ensemble des valeurs : le type int est limitØ aux entiers appartenant un intervalle [[emin,emax]], et il y a donc un plus petit et un plus grand entier. Cet intervalle dØpend de l’architecture du processeur de l’ordinateur utilisØ. Sur des architectures 32 bits, on a
[[emin,emax]] = [[?230,230 ? 1]] = [[?1073741824,1073741823]]. Sur des architectures 64 bits, on a
[[emin,emax]] = [[?262,262 ? 1]] = [[?4611686018427387904,4611686018427387903]].
LittØraux : les entiers dans leur forme Øcrite usuelle. Par exemple : 24.
Constantes prØdØ nies : les constantes min_int et max_int donnent les valeurs du plus petit (emin) et du plus grand (emax) entier.
OpØrateurs arithmØtiques : +, -, *, /, mod
OpØrateurs de comparaison : =, , , >=
Remarque : Les calculs arithmØtiques sur les nombres de type int s’e ectue modulo emax? emin + 1.
Exemple 2 :
La session ci-dessous est e ectuØe sur une machine 32 bits.
# (1+2)*3;; - : int = 9 # 9 / 2;; - : int = 4 # 9 mod 5;; - : int = 4 # max_int;; - : int = 1073741823 # min_int;; - : int = -1073741824# max_int + 1;; - : int = -1073741824 # min_int - 1;; - : int = 1073741823 |
4.1.3 Les nombres ottants
Nom : float
4.1.4 Types dØ nis par le module Cartes
Le module Cartes dØ nit deux types couleur et numero_tas.
Nom : couleur
Ensemble des valeurs : Les donnØes de ce type ne peuvent prendre que quatre valeurs notØes :
CARREAU, TREFLE, PIQUE et COEUR.
Nom : numero_tas
Ensemble des valeurs : Les donnØes de ce type ne peuvent prendre que quatre valeurs : 1, 2, 3 et 4.
4.2 Variables
4.2.1 Notion de variable
Les variables servent nommer des valeurs.
Elles sont caractØrisØes par leur nom ou identi cateur, leur type et leur valeur.
4.2.2 DØclaration simple de variables
La dØclaration des variables se fait l’aide du mot rØservØ (ou mot-clØ) let. Syntaxe : DØclaration d’une variable
let =
oø identificateur> est le nom de la variable, et expression> l’expression qui dØ nit sa valeur.
Exemple 3 :
Voici la dØclaration d’une variable nommØe a, de type int et de valeur 12.
# let a = 12;; val a : int = 12 # a;;
- : int = 12
# 2 * a;;
- : int = 24
L’expression qui dØ nit la valeur d’une variable peut faire rØfØrence d’autres variables condition que celles-ci aient ØtØ prØalablement dØclarØes.
Exemple 4 :
la suite de la dØclaration de la variable a qui prØc?de, on peut dØclarer une nouvelle variable b comme ci-dessous
# let b = 2*a + 1;; val b : int = 25
4.2.3 Identi cateurs de variables
Les variables sont nommØes par un identi cateur. En Caml, les identi cateurs de variables doivent obligatoirement commencer par une lettre minuscule ou un blanc soulignØ (_) et peuvent Œtre complØtØs par n’importe quelle quantitØ de lettres minuscules ou majuscules non accentuØes, ou chi res, ou blancs soulignØs.
Exemple 5 :
Le tableau ci-dessous montre quelques exemples d’identi cateurs de variables corrects et incorrects.
Identi cateurs corrects | Identi cateurs incorrects |
a | A |
a1 | 1a |
a_b | a-b |
_a | -a |
deplacer_sommet | deplacer-sommet |
En plus de ces r?gles, certains mots ne peuvent pas Œtre utilisØs comme identi cateurs : ce sont les mots rØservØs ou mots-clØs du langage (cf annexe C.2).
4.2.4 Environnement
L’ensemble des variables dØ nies dans un contexte de calcul s’appelle un environnement.
Lorsqu’on dØclare une variable, on augmente l’environnement courant de cette nouvelle variable. Ainsi si dans un certain environnement E0 on dØclare la variable
# let a = 12 ;;
val a : int = 12
l’environnement qui suit cette dØclaration est augmentØ d’une variable nommØe a et de valeur 12, et l’environnement est maintenant
E1 =12 >: E0.
Apr?s la dØclaration
# let b = 5 ;; val b : int = 5
l’environnement est
E2 =5 >: E1 =5 >:12 >: E0.
On voit donc que la dØclaration de variables peut augmenter l’environnement. Mais rien ne peut faire diminuer l’environnement : une variable dØclarØe le reste pour toute la durØe de la session.
4.2.5 valuation d’une expression
Lorsqu’une expression contient une ou plusieurs variables, pour chacune de ces variables on cherche dans l’environnement courant la variable de mŒme nom la plus rØcemment dØclarØe, et on la remplace par la valeur correpondante.
Par exemple dans l’environnement E2 prØcØdemment dØcrit, l’expression a*b est transformØe en 12*5 qui nalement donne la valeur 60.
a?b ? 12?5 ? 60.
4.2.6 Masquage d’une variable
Nous l’avons vu un environnement ne peut qu’augmenter. Que se passe-t-il lorsque nous dØclarons une variable dont le nom est identique celui d’une variable dØj dØclarØe? Que se passe-t-il si on dØclare une nouvelle variable nommØe a dans l’environnement E2 ?
Et bien, rien de neuf. Une nouvelle variable est ajoutØe l’environnement. Par exemple, si dans l’environnement E2 on fait la dØclaration
# let a = 9 ;; val a : int = 9
l’environnement devient
E3 =9 >: E2 =9 >:5 >:12 >: E0.
On constate que l’environnement E3 contient deux variables de mŒme nom a : l’une valant 12 qui dans le temps a ØtØ la premi?re Œtre dØclarØe, l’autre valant 9 qui est la plus rØcente.
Quelle est alors la valeur de l’expression a*b dans l’environnement E3 ? Dans l’expression, on remplace la variable b par sa valeur 5, mais qu’en est-il pour a? 9 ou 12? La r?gle d’Øvaluation dit de choisir la valeur de la variable la plus rØcemment dØclarØe, autrement dit 9. Par consØquent, dans l’environnement E3 l’expression a*b vaut 45.
a?b ? 9?5 ? 45. Dans l’environnement E3, toute rØfØrence la variable a est une rØfØrence la variable 9 >. L’autre variable 12 > est masquØe par 9 >.
4.2.7 DØclaration simultanØe de variables
Plusieurs variables peuvent Œtre dØ nies simultanØment dans la mŒme phrase let en utilisant le mot clØ and.
Syntaxe : DØclaration simultanØe de plusieurs variables
let1> = 1>and2> = 2>
andn > = n >
Les expressions i> sont alors toutes ØvaluØes dans l’environnement dans lequel la phrase de dØclaration est exprimØe.
Exemple 6 :
# let a = 1 and b = 2;; val a : int = 1 val b : int = 2 # a + b ;;
- : int = 3
La dØclaration simultanØe de plusieurs variables n’est pas Øquivalente la dØclaration sØquentielle. Par exemple, on peut tout fait e ectuer les deux dØclarations successives suivantes
# let c = 1. ;; val c : float = 1. # let d = c +. 2. ;; val d : float = 3.
mais il n’est pas possible de demander la dØclaration simultanØe qui suit si aucune dØclaration prØalable d’une variable e de type float n’a ØtØ faite.
# let e = 1. and f = e +. 2. ;; Unbound value e |
En e et dans l’environnement d’Øvaluation de cette dØclaration, la variable e n’existe pas, et il n’est donc pas possible d’Øvaluer l’expression e +. 2..
Mais si une dØclaration prØalable a ØtØ faite il n’y a aucun probl?me
# let e = -3.;; val e : float = -3. # let e = 1. and f = e +. 2. ;; val e : float = 1. val f : float = -1. |
noter que dans l’environnement obtenu apr?s ces dØclarations, la variable e vaut 1., et f vaut -1., autrement dit f a ØtØ calculØe avec la valeur de e dans l’environnement prØcØdent.
4.2.8 Variables locales une expression
Nous l’avons vu, l’environnement courant des variables dØclarØes ne peut que cro tre. Cela peut poser deux probl?mes :
un accroissement inutile de l’environnement avec des variables qui ne servent pas, et qui peut provoquer un encombrement, voire une saturation de la mØmoire; un masquage de certaines variables lorsqu’on utilise un mŒme nom.
Bien souvent, on Øprouve le besoin de dØclarer une variable pour faciliter l’Øcriture d’une expression et/ou optimiser son Øvaluation.
Par exemple, si nous souhaitons calculer l’expression
on pourrait Øcrire (en supposant que dans l’environnement courant il y ait deux variables a et b de valeurs ottantes)
sqrt(a**2. +. b**2.) *. (1. +. sqrt(a**2. +. b**2.)) /. (2. +. sqrt(a**2. +. b**2.)) |
mais cela n’est Øvidemment pas satisfaisant parce que d’une part?l’expression n’est pas facilement lisible, et d’autre part dans son Øvaluation, la sous-expression a2 + b2 va Œtre calculØe trois fois.
Pour mener des calculs, il arrive souvent que, pour ne pas noyer le propos par de longues formules, on utilise des notations pour les simpli er. On pose que tel symbole vaut temporrairement telle valeur, et ensuite on utilise ce symbole en lieu et place de celle-ci.?
Sur notre exemple cela pourrait donner : soit ? = a2 + b2 dans l’expression
dont une traduction possible en Objective Caml est
let alpha = sqrt(a**2. +. b**2.) alpha *. (1. +. alpha) /. (2. +. alpha)
Cette fa on de mener le calcul remØdie aux deux dØfauts signalØs ci-dessus :
le code est beaucoup?plus lisible; la sous-expression a2 + b2 n’est calculØe qu’une seule fois, et donc on gagane en e cacitØ.
Cependant, en procØdant de la sorte on a introduit dans l’environnement courant une nouvelle variable dont l’intØrŒt est limitØ au seul calcul de notre expression. Par la suite la variable ? ne sera probablement plus utilisØe mais persistera dans l’environnement : c’est une pollution.
Il existe une solution pour Øviter la pollution de l’environnement par des variables d’intØrŒt temporaire : c’est la notion de variable locale une expression.
Ce qui manque dans notre exemple c’est la traduction de posons ? = dans l’expression Il ne faut pas dØclarer une variable, puis calculer une expression, mais dØclarer une variable utiliser dans une expression. En Objective Caml, cela se traduit avec la forme letin . Notre exemple devient alors
let alpha = sqrt(a**2. +. b**2.) in alpha *. (1. +. alpha) /. (2. +. alpha) |
Avec une telle dØclaration, la variable alpha ne vient s’ajouter l’environnement courant que pour la durØe de l’Øvaluation de l’expression qui suit. Sit t cette Øvaluation terminØe, elle est supprimØe, et n’existe donc pas dans l’environnement courant l’issue du calcul. Il n’y a aucune di Ørence entre l’environnement avant et apr?s Øvaluation. Le probl?me de pollution d’environnement est rØglØ.
La syntaxe gØnØrale de dØclaration de variables locales est donnØe ci-dessous.
let1> = 1>and2> = 2>in
|
Syntaxe : DØclaration de variables locales une expression
Les variables non locales dØclarØes par une simple forme let sont appelØes variables globales par opposition locales.
4.2.9 Remarque sur la forme let
En Objective Caml, la forme let n’est pas une expression et a fortiori n’est pas une instruction.
UtilisØe dans une sØquence d’instructions elle ne donne pas l’e et auquel on pourrait penser. Dans la sØquence qui suit
# let a = 1 ; a + 1;; Warning S: this expression should have type unit. Unbound value a |
on constate un avertissement sur le fait que la premi?re partie n’a pas le type unit, et un message d’erreur qui montre que dans l’environnement courant la variable a n’est liØe aucune valeur, et ceci malgrØ la forme la dØclaration qui prØc?de.
UtilisØe dans une expression conditionnelle, elle provoque un message d’erreur de syntaxe.
# if true then begin let a = 1; print_string ("Fini") end ;; |
Syntax error
De mŒme dans les instructions rØpØtØes (boucle while ou for).
En conclusion, une dØclaration globale de variable ne peut Œtre encapsulØe dans une sØquence d’instructions, dans une expression conditionnelle ou dans une boucle.
En revanche, la forme letin est une expression. ce titre elle peut Œtre encapsulØe.
# let a = 1 in print_int a ; print_newline () ;; 1 - : unit = () # if true then begin let a = 1 in print_int (a+1) end ;; 2- : unit = () |
4.3 Variables mutables
4.3.1 Motivation
Un probl?me
tat initial : Tas 1 un nombre quelconque de cartes, les autres tas vides. tat nal : peu importe
But : a cher le nombre de cartes situØes initialement sur le tas 1.
Algorithme
Une solution du probl?me consiste dØplacer (une une) toutes les cartes du tas 1 vers un autre tas (le tas 2 par exemple), et compter chaque dØplacement e ectuØ.
Algorithme 4.1 Compter les cartes du tas 1
mise zØro du compteur tant que les tas 1 n’est pas vide faire
dØplacer une carte du tas 1 vers le tas 2 ajouter 1 au compteur n tant que
Comme on peut le voir, dans cet algorithme la valeur du compteur Øvolue durant son exØcution.
Une variable dont la valeur peut Øvoluer durant l’exØcution d’un programme est appelØe variable mutable. Par opposition, nous nommerons parfois les variables non mutables des constantes.
4.3.2 DØclaration d’une variable mutable
La dØclaration d’une variable mutable est analogue celle de toute variable, si ce n’est l’emploi du mot-clØ ref.
4.3. VARIABLES MUTABLES Syntaxe : DØclaration d’une variable mutable
let = ref
Exemple 7 :
DØclaration d’une variable mutable compteur initialisØe 0.
# let compteur = ref 0 ;; val compteur : int ref = {contents = 0}
Comme on peut le voir, cette variable n’est pas de type int, mais de type intref. Et sa valeur est {contents = 0}.
# compteur ;;
- : int ref = {contents = 0}
Comme compteur n’est pas de type int, on ne peut pas l’utiliser tel quel dans le contexte d’une expression oø on attend un int.
# compteur + 1;;
This expression has type int ref but is here used with type
4.3.3 RØfØrence la valeur d’une variable mutable
Pour faire rØfØrence la valeur d’une variable mutable dans une expression, on utilise le prØ xe ! devant le nom de la variable.
Exemple 8 :
# !compteur ;;
- : int = 0
# !compteur + 1;;
- : int = 1
# !compteur;;
- : int = 0
Notez qu’apr?s l’Øvaluation de la deuxi?me expression, la variable compteur a gardØ la valeur 0.
Pour modi er la valeur d’une variable mutable, il faut utiliser l’instruction d’a ectation.
4.3.4 A ectation
L’a ectation est une instruction qui permet de changer la valeur d’une variable mutable. La syntaxe de cette instruction est Syntaxe : A ectation d’une valeur une variable mutable
:=
Le symbole := signi e que la valeur v de l’expression est a ectØe la variable dØsignØe par l’identi cateur . Apr?s l’exØcution de cette instruction la variable vaut v.
Comme toute instruction, le rØsultat d’une a ectation est la valeur () de type unit.
Exemples :
1. Pour mettre zØro la variable compteur prØcØdemment dØclarØe
(* compteur = xxx*) compteur := 0 ; (*compteur = 0 *)
2. ajouter 1 au compteur
(* compteur = n*) compteur := !compteur + 1 ; (*compteur = n + 1 *)
Remarques :
1. Attention ne pas confondre le symbole := utilisØ en Caml pour l’instruction d’a ectation, avec le symbole = utilisØ comme opØrateur de comparaison, ainsi que dans la dØclaration de variables.
2. En programmation, on est souvent amener utiliser des instructions du type
a := !a + 1
qui augmentent de 1 la valeur d’une variable (mutable). Cette opØration s’appelle incrØmentation et on dit qu’on incrØmente une variable.
La dØcrØmentation est la diminution de la valeur d’une variable.
a := !a - 1 | |
On peut penser que le code suivant est Øquivalent | une incrØmentation. |
let a = a+1 |
3.
Il n’en est rien du tout! Il s’agit d’une dØclaration d’une nouvelle variable a qui vient masquer la prØcØdente. De plus, on ne peut pas utiliser cette forme let dans une boucle. Par exemple, on peut Øcrire
# let a = ref 0 ;; val a : int ref = {contents = 0} # while !a do a := !a + 1; print_int !a; print_newline () done ;; 1 2 3 4 5 - : unit = () |
mais on ne peut pas Øcrire
4.4. AFFICHER DES DONN ES
# let a = 0 ;; val a : int ref = {contents = 0} # while a do let a = a + 1; print_int (a); print_newline () ) done ;; Syntax error |
4. L’a ectation est une opØration autorisØe sur les variables mutables uniquement. Elle ne l’est pas sur les variables non mutables (ou constantes).
# let a = 1 ;; val a : int = 1 # a := 2;; This expression has type int but is here used with type ’a ref |
4.4 A cher des donnØes
En Caml, lorsqu’on veut a cher des donnØes, on utilise les instructions print_int pour les entiers, print_float pour les ottants.
Exemple 9 :
# print_int(1234);; 1234- : unit = () # let a = 1234;; val a : int = 1234 # print_int(a*2);; 2468- : unit = () # print_int(1234.);; This expression has type float but is here used with type int # print_float(1234.);; 1234.- : unit = () |
Comme on peut le voir ces instructions impriment la valeur du param?tre sans passer la ligne. Cela peut poser probl?me lorsqu’on veut a cher deux nombres successifs.
Exemple 10 :
# begin print_int(1); print_int(2) end ;; 12- : unit = () |
L’instruction sans param?tre print_newline provoque un passage la ligne.
Exemple 11 :
# begin print_int(1); print_newline(); print_int(2); print_newline() end ;; 1 2 - : unit = () |
L’instruction print_string imprime une cha ne de caract?res. Exemple 12 :
# let a = 12 and b = 21 in begin print_int(a); print_string(" + "); print_int(b); print_string(" = "); print_int(a+b); print_newline() end ;; 12 + 21 = 33 - : unit = () |
4.5 Le programme solution du probl?me 4.3.1
(* compter le nombre de cartes sur le tas 1 *)let cpt = ref 0 in begin init_tas(1,"[T]"); init_tas(2,""); init_tas(3,""); init_tas(4,""); while tas_non_vide(1) do deplacersommet(1,2); cpt := !cpt + 1 done; print_string("Nombre de cartesinitialement sur le tas 1 : "); print_int(!cpt); print_newline() end |
4.6. EXERCICES
4.6 Exercices
Exercice 4-1 DØclarations de variables
DØcrivez les valeurs des variables dØclarØes l’issue des deux sessions suivantes :
let a = 1 ;; let a = 2 ;; let b = 2*a + 1 ;; | let a = 1 ;; let a = 2 and b = 2*a + 1 ;; |
Exercice 4-2 change de variables
Donnez une sØquence d’instructions qui Øchange les valeurs de deux variables mutables de type int.
Exercice 4-3 Calcul de la valeur d’une fonction polynomiale
Soit f(x) = x4 ? 3x3 ? 2x2 + x + 1.
RØalisez un programme qui a che la valeur de f(x) lorsque x = 13. Concevez votre programme pour qu’il soit facile de le modi er pour le calcul de f(x) pour d’autres valeurs de x.
Cette derni?re solution suit le schØma de Horner d’Øvaluation d’un polyn me.
Exercice 4-4 Avec les cartes
RØalisez des programmes qui, partir de la situation initiale Situation initiale :
Tas 1 : "[K+T+P+C]" Tas 2 : ""
Tas 3 : "" Tas 4 : ""
1. calcule le nombre de tr? es,
2. calcule le nombre de cartes de couleur noire,
3. rØpartit Øquitablement les cartes rouges sur les tas 3 et 4, et les cartes noires sur les tas 1 et 2.
50 CHAPITRE 4. CONSTANTES, VARIABLES
Chapitre 5
La boucle pour
5.1 La boucle Pour
On peut calculer la somme des entiers de 1 n l’aide d’une structure itØrative tant que et de deux variables, i pour ØnumØrer les entiers successifs de 1 n, et S pour les cumuler.
Algorithme 5.1 Calcul de la somme des n premiers nombres entiers.
EntrØe : n un entier positif ou nul Sortie :
initialiser S 0 initialiser i 1 {on a bien tant que i ? n faire
ajouter i S
incrØmenter i
{notons qu’on a toujours n tant que
{la mŒme ØgalitØ est satisfaite avec i = n + 1} renvoyer s
Compte tenu de la condition, il est possible de dire avant l’exØcution de cet algorithme que la sØquence d’instructions contenue dans la boucle tant que sera e ectuØe n fois.
De mani?re plus gØnØrale, si un algorithme s’Øcrit de cette fa on initialiser i a tant que i ? b faire
sØquence d’instructions ne modi ant pas i
incrØmenter i n tant que
et que la sØquence d’instructions prØcØdant l’incrØmentation de la variable i ne modi e pas la valeur de cette variable, alors le nombre de fois que la sØquence d’instructions sera exØcutØe est
Øgal b ? a + 1.
51
De telles itØrations dont le nombre d’Øtapes est dØterminØe par une variable qui parcourt l’ensemble des valeurs comprises entre deux bornes est appelØe une boucle pour, et la variable i est appelØe indice de la boucle.
On peut rØØcrire le calcul de la somme des entiers compris entre 1 et n en utilisant une boucle pour.
Algorithme 5.2 Calcul de la somme des n premiers nombres entiers avec une boucle pour
EntrØe : n un entier positif ou nul Sortie :
initialiser S 0 pour i variant de 1 n faire
ajouter i S {on a S = Pik=1 k} n pour
renvoyer s
5.2 La boucle Pour en Caml
5.2.1 Syntaxe de la boucle pour
Toute sØquence de deux instructions de la forme
let i = ref a in while !i do (* sequence d’instructions *) i := !i + 1 done |
peut Œtre remplacØe par une boucle pour
for i = a to b do (* sequence d’instructions *) done |
Syntaxe : Boucle pour
Exemple 1 :
Calcul de la somme des entiers de 1 100
# let s = ref 0 in for i = 1 to 100 do s := !s + i done; !s ;; - : int = 5050 |
5.2. LA BOUCLE POUR EN CAML
5.2.2 Remarque sur l’indice de boucle
L’indice d’une boucle for en Caml est une variable locale la boucle qui n’a pas besoin d’Œtre dØclarØe. Cette variable n’est dØ nie que dans l’environnement de la boucle. Elle n’existe pas dans l’environnement englobant.
# for i = 1 to 5 do print_int(i); print_newline() done; print_int(i);; Unbound value i |
De plus, ce n’est pas une variable mutable, et on ne peut donc pas modi er la valeur de cet indice dans la sØquence d’instructions du corps de la boucle.
5.2.3 Boucle pour indice dØcroissant
Toute sØquence de deux instructions de la forme
let i = ref a in while !i >= b do (* sequence d’instructions *) i := !i - 1 done |
peut Œtre remplacØe par une boucle pour
for i = a downto b do (* sequence d’instructions *) done |
Syntaxe : Boucle pour indice dØcroissant
Exemple 2 :
Calcul de la somme des entiers de 1 100
# let s = ref 0 in for i = 100 downto 1 do s := !s + i done; !s ;; - : int = 5050 |
5.3 Suites rØcurrentes
Soit (un)n?N une suite de nombres rØels dØ nie par son premier terme u0 = a (a ? R) et pour tout n ? 0 une relation de rØcurrence de la forme
un+1 = f(un)
oø f est une fonction rØelle d’une variable rØelle.
Par exemple, on peut considØrer la suite de rØels dØ nie par
on a ici
5.3.1 Calcul du terme d’indice n
On veut calculer le terme un lorsqu’est donnØ l’indice n.
Algorithme 5.3 Calcul du terme d’indice n d’une suite rØcurrente
EntrØe : n un nombre rØel, a un rØel et f : R ? R une fonction.
Sortie : le terme un de la suite u0 ? a
pour i variant de 1 n faire ui ? f(ui?1) n pour
renvoyer un
Pour rØaliser cet algorithme en Caml, il su t d’utiliser une seule variable pour mØmoriser les valeurs successives des termes de la suite.
(* on suppose declarees ici trois variables - a de type float - f de type float? > float - n de type int *) let u = ref a in begin for i = 1 to n do u := f(!u) done; !u end |
5.3.2 Calcul et a chage des termes d’indice 0 n
On veut a cher la valeur de tous les termes de la suite (un) dont les indices sont compris entre 0 et n.
5.3. SUITES R CURRENTES
Il su t de calculer successivement chaque terme de la suite et a cher immØdiatement sa valeur.
(* on suppose declarees ici trois variables - a de type float - f de type float? > float - n de type int *) let u = ref a in begin print_float(!u); print_newline(); for i = 1 to n do u := f(!u); print_float(!u); print_newline() done end |
5.3.3 Calcul du premier terme satisfaisant une condition
On peut aussi vouloir chercher le premier terme de la suite qui satisfait une condition donnØe. Cette condition peut porter sur le dernier terme calculØ, ou bien sur plusieurs termes dØj calculØs.
Algorithme 5.4 Calcul du premier terme satisfaisant une condition
u ? a
tant que u ne satisfait pas la condition voulue faire
on calcule le terme suivant u ? f(u)
n tant que renvoyer u
Remarque : si aucun terme de la suite ne satisfait la condition donnØe, la boucle est in nie (le programme ne s’arrŒte pas). Aussi avant de concevoir de tels programmes est-il important de s’assurer qu’au moins un terme de la suite vØri e la condition.
5.3.4 Autres suites rØcurrentes
Suites rØcurrentes d’ordre plus ØlevØ
ordre 2 : la suite de Fibonacci dØ nie par ses deux premiers termes et une relation de rØcurrence d’ordre 2
u0 | = | |
u1 | = | 1 |
un+2 | = | un+1 + un ?n ? N |
Facile programmer.
ordre total : la suite des nombres de Catalan dØ nie par son premier terme et une relation de rØcurrence s’appuyant sur tous les termes qui prØc?dent
u0 = 1
n
un+1 = Xukun?k ?n ? N
k=0
Di cile programmer sans tableaux (cf cours d’API1).
5.4. EXERCICES
5.4 Exercices
Exercice 5-1 downto n’est pas indispensable
Question 1 l’aide d’une boucle indices croissant, rØØcrivez l’instruction qui suit de sorte que l’a chage soit identique.
for i = n downto 1 do print_int(i); print_newline()
done
Question 2 En supposant que l’instruction action(i) accomplisse une certaine t che qui dØpend de i, comment rØØrire l’instruction
for i = b downto a do action(i)
done
avec une boucle indices croissant?
Exercice 5-2 Tables de multiplication
RØalisez un programme qui a che une table de multiplication par un nombre donnØ. Une trace d’exØcution du programme demandØ est donnØe ci-dessous pour la table par 7 :
1 x 7 = 7
2 x 7 = 14
3 x 7 = 21
10 x 7 = 70
Exercice 5-3 Calcul de puissances
RØalisez un programme qui calcule la valeur de l’entier an pour deux entiers a et n. Exercice 5-4 Calcul de factorielles
RØalisez un programme qui calcule l’entier n!, n Øtant donnØ.
Exercice 5-5
Boucles imbriquØes pour stars acadØmiques
Question 1
RØalisez un programme qui a che l’Øcran une ligne de n Øtoiles, l’entier n Øtant donnØ.
L’a chage du programme demandØ est donnØ ci-dessous pour n = 5 :
*****
Question 2 RØalisez un programme qui a che l’Øcran un carrØ de n × n Øtoiles, l’entier n Øtant donnØ.
L’a chage du programme demandØ est donnØ ci-dessous pour n = 5 :
*****
*****
*****
*****
*****
Question 3 RØalisez un programme qui a che l’Øcran un triangle (isoc?le) de hauteur n, l’entier n Øtant donnØ.
L’a chage du programme demandØ est donnØ ci-dessous pour n = 5 :
*
**
***
****
*****
Question 4 RØalisez un programme qui a che l’Øcran un triangle (isoc?le) de hauteur n pointe en bas, l’entier n Øtant donnØ.
Une trace d’exØcution du programme demandØ est donnØe ci-dessous :
*****
****
***
**
*
Exercice 5-6 Calcul de la suite de Heron
La suite de Heron est la suite rØcurrente de nombres rØels dØ nie par
oø a et B sont deux rØels positifs.
Question 1 Programmez le calcul du terme d’indice n de cette suite avec a = 1 et B = 2.
Question 2 Modi ez votre programme pour qu’ l’exØcution on obtienne un a chage de tous les termes demandØs, raison d’un par ligne.
Par exemple, l’a chage produit aura la forme qui suit pour a = 1, B = 2 et n = 5.
u(1) = 1.5 u(2) = 1.41666666667 u(3) = 1.41421568627 u(4) = 1.41421356237 u(5) = 1.41421356237
Question 3 Utilisez votre programme pour di Ørentes valeurs de a et B.
5.4. EXERCICES
Exercice 5-7 Suite de Fibonacci
Question 1 Programmez le calcul des premiers termes de la suite de Fibonacci. Fa tes le en utilisant le type int, puis le type float. Calculez les termes jusqu’ l’indice 50. Comparez les rØsultats selon le type utilisØ.
Question 2 Cette suite est croissante et tend vers +? lorsque n tend vers +?. crivez une fonction qui calcule l’indice du premier terme supØrieur ou Øgal un rØel positif s passØ en param?tre.
60 CHAPITRE 5. LA BOUCLE POUR
Chapitre 6
Les fonctions
6.1 Les fonctions
Nous avons dØj rencontrØ et utilisØ plusieurs fonctions : tas_non_vide, couleur_sommet, superieur du module Cartes, ainsi que not, et bien d’autres encore.
Le but de ce chapitre est de voir comment crØer nos propres fonctions.
Une fonction permet d’abstraire et de nommer un calcul ou une expression. Une fois dØ nie, une fonction peut Œtre utilisØe pour produire de nouvelles expressions du langage.
Contrairement aux instructions, un appel une fonction ne doit pas modi er l’Øtat courant de l’environnement.
6.1.1 SpØci cation d’une fonction
SpØci er une fonction, c’est choisir un identi cateur pour la nommer;
prØciser le nombre et le type de ses param?tres, et les nommer; indiquer les conditions d’utilisation (CU) que doivent vØri er les param?tres lors d’un appel la fonction; indiquer le type de la valeur qu’elle renvoie; et indiquer quelle est la relation entre la valeur renvoyØe et les param?tres qui lui sont passØs.
Exemple 1 :
La fonction prØdØ nie donnant la nØgation d’un boolØen en Caml est une fonction nommØe not, qui op?re sur un param?tre de type bool, dont la valeur renvoyØe est aussi de type bool et pour laquelle il n’y a aucune contrainte d’utilisation. Nous rØsumons tout cela par la notation :
not : bool ?? bool
.
a 7?? ¬a
Exemple 2 :
Un autre exemple est la fonction du module Cartes qui permet de comparer les hauteurs des cartes situØes au sommet de deux tas. Cette fonction est nommØe superieur, elle prend deux param?tres de type Cartes.numero_tas, et renvoie une valeur de type bool. Elle poss?de aussi
61
une contrainte d’utilisation qui exige qu’aucun des deux tas passØs en param?tre ne soit vide. Tout cela est rØsumØ par la notation :
superieur : numero_tas × numero_tas ?? bool | |
? vrai ??? n,p 7?? faux CU : les tas n et p ne doivent pas Œtre vides. 6.1.2 DØclaration d’une fonction en Caml | si la carte au sommet du tas n a une valeur strictement plus grande que celle du tas p sinon |
Contrairement d’autres langages tels que C, Ada ou Pascal, en Caml il n’est pas nØcessaire d’apprendre de nouvelle forme syntaxique pour dØclarer une nouvelle fonction. On utilise la mŒme forme let que pour la dØclaration des variables.
let () = (* expression simple ou sequence d’instructions definissant la fonction *) |
Syntaxe : DØclaration d’une fonction
Exemple 3 :
Soit Øcrire le prØdicat rouge dont la spØci cation est
rouge : numero_tas ?? bool
vrai si la carte au sommet du tas n
nest rouge
faux sinon CU : le tas n ne doit pas Œtre vide.
Le code en Caml pour cette fonction s’Øcrit tout simplement
let rouge(n) = sommet_coeur(n) || sommet_carreau(n)
Comme on peut le constater, en Caml il n’est pas nØcessaire au programmeur de prØciser le type des param?tres et celui de la valeur renvoyØe, contrairement au cas de langages comme C, Ada ou Pascal. C’est le langage qui calcule ces types. On peut le voir dans la rØponse fournie par l’interpr?te lorsque le code de la fonction rouge lui est fourni.
# let rouge(n) = sommet_coeur(n) || sommet_carreau(n) ;;
val rouge : Cartes.numero_tas -> bool = fun>
6.1. LES FONCTIONS
6.1.3 Variables locales
Certaines fonctions nØcessitent des variables qui leur sont propres pour Øcrire l’algorithme qui les rØalise. Ces variables sont appelØes des variables locales.
Exemple 4 :
La fonction factorielle
factorielle : int ?? int n 7?? n! CU : n ? 0
peut s’Øcrire en Caml
let factorielle(n) = let f = ref 1 in for i=1 to n do f := !f*i done; !f |
On voit par l’utilisation de la forme letin l’utilisation d’une variable locale pour coder cette fonction.
Une fonction peut utiliser toute variable globale, fonction. Exemple 5 : Le code | condition qu’elle soit dØclarØe avant la |
let un = 1 let plus_un(n) = n + un
dØ nit une constante enti?re qui vaut 1 et la fonction | |
plus_un : int ?? n 7?? | int . n + 1 |
L’expression dØ nissant cette fonction utilise la constante prØalablement dØ nie un et se comporte comme on peut s’y attendre.
# plus_un(0);;
- : int = 1
Mais si on redØ nit la constante sans redØ nir la fonction, c’est toujours l’ancienne valeur de la constante qui est prise en compte.
# let un = 2;; val un : int = 2 # plus_un(0);;
- : int = 1
6.1.4 Fonctions plusieurs param?tres
Comme la fonction superieur, une fonction peut avoir plus d’un param?tre. Ces param?tres peuvent Œtre de types identiques ou non.
Exemple 6 :
La fonction puissance qui partir de deux entiers a et n renvoie l’entier an
puissance1 : int × int ?? int
a,n 7?? anCU : n ? 0
peut s’Øcrire en Caml avec le code
let puissance1(a,n) = let p=ref 1 in for i=1 to n do p := !p*a done; !p |
Exemple 7 :
Reprenons la fonction puissance pour des nombres rØels.
puissance2 : float × int ?? float
a,n 7?? anCU : n ? 0
Elle peut s’Øcrire en Caml avec le code
let puissance2(a,n) = let p=ref 1. in for i=1 to n do p := !p*.a done; !p |
Un appel une fonction plusieurs param?tres doit se faire avec le bon nombre et le bon type des param?tres. Ainsi, dans l’exemple
# puissance1(2,10);;
- : int = 1024
# puissance2(2.,10);;
- : float = 1024.
les deux appels de fonction sont corrects car e ectuØs avec le bon nombre et les bons types de param?tres. Mais dans l’exemple
# puissance1(2);;
This expression has type int but is here used with type int * int
6.1. LES FONCTIONS
l’interpr?te signale une erreur dans l’appel la fonction puissance1 parce qu’un seul entier a ØtØ passØ en param?tre au lieu des deux attendus, et dans l’exemple
# puissance2(2,10);;
This expression has type int * int but is here used with type float * int
il signale une erreur parce qu’au lieu du couple (rØel, entier) attendu par la fonction puissance2, un couple (entier, entier) lui a ØtØ passØ.
6.1.5 Fonctions sans param?tre
Il est possible de dØ nir des fonctions sans param?tre. Le type de dØpart est alors le type unit.
Exemple 8 :
C’est le cas de la procØdure prØdØ nie print_newline.
Exemple 9 :
La fonction sans param?tre constante Øgale 1
un : | unit | ?? | int |
se code en Caml | () 7 | ?? | 1 |
let un() = 1 |
et tout appel cette fonction produit l’entier 1.
# un();;
- : int = 1
On peut rØaliser des fonctions sans param?tre non constantes.
Exemple 10 :
Comme son nom l’indique, la fonction
valeur_de_x : unit ?? typedex () 7?? valeur de x
renvoie la valeur de la variable mutable x. En voici le code
let valeur_de_x() = !x
Il est bien entendu prØalablement nØcessaire d’avoir dØclarØ une variable mutable x.
# let valeur_de_x() = !x;;
Unbound value x
Si la variable x est dØclarØe alors le type de la valeur renvoyØe par la fonction valeur_de_x est le mŒme que celui de x.
# let x = ref 1;; val x : int ref = {contents = 1} # let valeurdex() = !x;; val valeur_de_x : unit -> int = fun> # valeur_de_x();;
- : int = 1
# x := 2;;
- : unit = ()
# valeur_de_x();;
- : int = 2
On peut rØaliser des fonctions sans param?tres un peu plus intØressantes.
Exemple 11 :
Supposons que nous voulions programmer une fonction qui simule le lancer d’une pi?ce de monnaie. Cette fonction doit donner le rØsultat "PILE" ou "FACE" de mani?re alØatoire.
pile_ou_face : unit ?? string
() 7?? PILE ou FACE .
On peut la programmer en utilisant la fonction prØdØ nie
Random.int : int ?? int
n 7?? pCU : n > 0
oø p est un entier au hasard compris entre 0 inclus et n exclu.
La fonction pile_ou_face se code alors en faisant un appel (2) qui produira soit l’entier 0, soit l’entier 1, et en prenant la convention que si c’est 0 alors elle renvoie la valeur "PILE" et si c’est 1 elle renvoie la valeur "FACE".
let pile_ou_face() = if (2) = 0 then "PILE" else "FACE" |
Voici une sØrie de quelques appels successifs cette fonction.
# pile_ou_face();;
- : string = "PILE"
# pile_ou_face();;
- : string = "FACE"
# pile_ou_face();;
- : string = "FACE"
# pile_ou_face();;
- : string = "PILE"
6.1.6 IntØrŒt des fonctions
re et de l’analyse du probl?me modularitØ lisibilitØ des programmes factorisation du code
6.2. PROC DURES
6.2 ProcØdures
Nous avons dØj rencontrØ et utilisØ plusieurs procØdures : init_tas et deplacer_sommet du module Cartes.
Une procØdure permet de crØer une nouvelle action, ou encore d’abstraire et nommer une suite d’instructions. Une fois dØ nie, une procØdure peut Œtre utilisØe comme une nouvelle instruction du langage.
Comme toute instruction, un appel une procØdure modi e l’Øtat courant de l’environnement : c’est un e et de bord.
6.2.1 SpØci cation d’une procØdure
SpØci er une procØdure, c’est choisir un identi cateur pour la nommer;
prØciser le nombre de param?tres, leur type, et les nommer; indiquer les conditions d’utilisation (CU) que doivent vØri er les param?tres lors d’un appel la procØdure; et indiquer l’action de la procØdure sur l’environnement (e et de bord).
Par exemple, la procØdure du module Cartes permettant de dØplacer une carte d’un tas vers un autre se nomme deplacer_sommet, poss?de deux param?tres de type numero_tas dØsignant les tas de dØpart et d’arrivØe, poss?de une contrainte d’utilisation qui est que le tas de dØpart ne doit pas Œtre vide, et son action modi e les tas de cartes en dØpla ant une carte du tas de dØpart vers le tas d’arrivØe. Nous rØsumons tout cela par la notation :
deplacer_sommet : numero_tas × numero_tas ?? unit depart,arrivee 7?? ()
Action : dØplace une carte du tas depart vers le tas arrivee
CU : le tas depart ne doit pas Œtre vide
6.2.2 DØclaration d’une procØdure en Caml
En Caml, une procØdure est une fonction dont le rØsultat est de type unit. La seule valeur renvoyØe par cette fonction est donc l’unique valeur du type unit savoir (). Les procØdures se dØclarent donc de la mŒme fa on que les fonctions.
Exemple 12 :
let tout_mettre_sur_tas1 () = (* vider le tas 2 sur le tas 1 *)while tas_non_vide(2) do deplacer_sommet(2,1) done; (* vider le tas 3 sur le tas 1 *)while tas_non_vide(3) do deplacer_sommet(3,1) done; (* vider le tas 4 sur le tas 1 *)while tas_non_vide(4) do deplacer_sommet(4,1) done |
Exemple 13 :
let vider_tas(depart,arrivee) = while tas_non_vide(depart) do
deplacer_sommet(depart,arrivee)
done
Cette procØdure a pour nom vider_tas et poss?de deux param?tres (depart et arrivee) quali Øs de formels, car lors de la conception (ou Øcriture) de cette procØdure, ces param?tres n’ont aucune valeur. Ils servent nommer les (futures) valeurs qui seront passØes lors d’un appel la procØdure.
6.2.3 Appel une procØdure
Un appel une procØdure est une instruction. Le rØsultat de son exØcution est une modi cation de l’Øtat courant de l’environnement ou un a chage de donnØes.
6.2.4 IntØrŒt des procØdures
re et de l’analyse du probl?me; modularitØ; lisibilitØ des programmes; factorisation du code.
6.2.5 MØthodologie
SPECIFIER, SPECIFIER, SPECIFIER
6.3. EXERCICES
6.3 Exercices
6.3.1 Fonctions
Exercice 6-1
Question 1 Donnez les spØci cations des fonctions et procØdures du module Cartes.
Question 2 crivez la fonction sommet_trefle l’aide de la fonction couleur_sommet. Exercice 6-2
RØalisez et testez une fonction tas_tous_vides qui renvoie un boolØen indiquant si tous les tas sont vides.
Exercice 6-3
Question 1 RØalisez une fonction tas_max qui donne le numØro du tas dont le sommet a la carte de valeur la plus ØlevØe, parmi les deux tas passØs en param?tres. Ne pas oublier les CU.
Question 2 RØalisez une fonction tas_max3 analogue la prØcØdente pour trois tas passØs en param?tres.
Question 3 MŒme chose pour quatre tas! (param?tres ou non?)
Exercice 6-4 Ou exclusif
RØalisez une fonction qui renvoie le ou-exclusif des deux boolØens passØs en param?tres.
Exercice 6-5 DivisibilitØ
RØalisez le prØdicat
est_divisible_par : int,int ?? bool
vrai si n est divisible par p
n,p
faux sinon CU : p 6= 0
Exercice 6-6 AnnØes bissextiles
Une annØe bissextile est une annØe qui comprend 366 jours au lieu des 365 pour les annØes ordinaires.
Depuis l’instauration du calendrier grØgorien, sont bissextiles, les annØes :
divisibles par 4 mais non divisibles par 100 ou bien divisibles par 400.
RØalisez la fonction spØci Øe ci-dessous
est_bissextile : int ?? bool
vrai si annee est bissextile
annee faux sinon
Exercice 6-7 Le plus grand
Question 1 RØalisez une fonction qui renvoie le plus grand des deux entiers passØs en param?tres.
Question 2 RØalisez de deux fa ons une fonction qui renvoie le plus grand des trois entiers passØs en param?tres
1. en utilisant dØ nie dans la question prØcØdente;
2. puis sans utiliser cette fonction.
Exercice 6-8 Coe cients binomiaux tant donnØs deux entiers 0 ? p ? n, on dØ nit le coe cient binomial par
.
RØalisez de deux fa ons la fonction qui deux entiers associe le coe cient binomial
1. une premi?re fa on utilisant la fonction factorielle;
2. une seconde fa on exploitant la simpli cation
.
Exercice 6-9 Fonction polynomiale
RØalisez une fonction qui permet de calculer les valeurs de la fonction rØelle de variable rØelle
f(x) = 3x4 ? x2 + 2x + 1.
Exercice 6-10 Plancher et plafond d’un nombre rØel
On appelle plancher d’un nombre rØel le plus grand nombre entier infØrieur ou Øgal x. On le note bxc. Ce nombre est aussi appelØ partie enti?re de x.
On appelle plafond d’un nombre rØel le plus petit nombre entier supØrieur ou Øgal x. On le note dxe.
Ces deux nombres co ncident lorsque x est un nombre entier.
Question 1 RØalisez une fonction nommØe plancher qui calcule le plancher du nombre rØel x passØ en param?tre. Il est conseillØ de se concentrer d’abord sur le cas des rØels positifs ou nuls, puis de gØnØraliser.
Question 2 De mŒme, rØalisez une fonction nommØe plafond pour le plafond dun rØel.
Exercice 6-11 simulation d’un dØ
RØalisez une fonction qui simule un dØ. Cette fonction renvoie au hasard un entier compris entre 1 et 6.
Exercice 6-12 Tas ordonnØ?
RØaliser et tester un prØdicat tas1_ordonne qui renvoie vrai si le tas numØro 1 est rangØ dans l’ordre croissant. Le tas vide est ordonnØ, les tas d’une cartes le sont aussi. Un tas est ordonnØ lorsque toute carte du tas est supØrieure au sens large toutes celles qu’elle surmonte. (comme pour l’exercice prØcØdent plusieurs versions sont possibles).
6.3. EXERCICES
6.3.2 ProcØdures
Exercice 6-13 crire l’entŒte de la procØdure deplacer_sommet du module Cartes. (Le type qui dØ nit les
couleurs se nomme couleurs, et celui qui dØ nit les tas se nomme numero_tas.)
Exercice 6-14
Expliquez la condition d’utilisation de la procØdure ViderTas.
Exercice 6-15
Question 1 Reprendre la procØdure tout_mettre_sur_tas1 en utilisant la procØdure vider_tas. (attention l’ordre des dØclarations de ces procØdures)
Question 2 Faire une version paramØtrØe par le numØro du tas sur lequel on veut tout mettre.
Exercice 6-16
Les exercices de manipulation de cartes.
Exercice 6-17 Tables de multiplication
SpØci ez et rØalisez une procØdure qui a che la table de multiplication par un entier donnØ en param?tre.
72 CHAPITRE 6. LES FONCTIONS
Chapitre 7
Caract?res et cha nes de caract?res
7.1 Les caract?res
7.1.1 DØ nition
Les caract?res sont un ensemble de symboles comprenant les 26 lettres de l’alphabet latin en versions minuscules et majuscules, les 10 chi res de 0 9, les di Ørents symboles de ponctuation, l’espace, et bien d’autres symboles encore. Ils sont au nombre de 256 au total.
En Caml, ils forment le type de donnØes char.
Il est possible de dØclarer des constantes de type char.
Exemple 1 :
# let espace = ’ ’;; val espace : char = ’ ’
Les constantes littØrales de type char sont dØsignØes entre deux apostrophes. On peut aussi dØclarer des variables mutables de type char.
Exemple 2 :
# let c = ref ’a’;;
val c : char ref = {contents = ’a’}
Il est possible d’Øcrire une donnØe de ce type avec la procØdure print_char.
Exemple 3 :
# print_char(!c);; a- : unit = ()
73
7.1.2 Fonctions int_of_char et char_of_int Les caract?res sont numØrotØs de 0 255.
Exemple 4 :
Par exemple, le caract?re ESPACE porte le numØro 32, le caract?re A porte le numØro 64 et le caract?re a porte le numØro 97.
La gure 7.1 donne pour les 128 premiers caract?res leur numØro associØ (code ASCII).
NUL | ESP | 32 | @ | 64 | ‘ | 96 | |
SOH | 1 | ! | 33 | A | 65 | a | 97 |
STX | 2 | " | 34 | B | 66 | b | 98 |
ETX | 3 | # | 35 | C | 67 | c | 99 |
EOT | 4 | $ | 36 | D | 68 | d | 100 |
ENQ | 5 | % | 37 | E | 69 | e | 101 |
ACK | 6 | & | 38 | F | 70 | f | 102 |
BEL | 7 | ’ | 39 | G | 71 | g | 103 |
BS | 8 | ( | 40 | H | 72 | h | 104 |
HT | 9 | ) | 41 | I | 73 | i | 105 |
LF | 10 | * | 42 | J | 74 | j | 106 |
VT | 11 | + | 43 | K | 75 | k | 107 |
FF | 12 | , | 44 | L | 76 | l | 108 |
CR | 13 | - | 45 | M | 77 | m | 109 |
SO | 14 | . | 46 | N | 78 | n | 110 |
SI | 15 | / | 47 | O | 79 | o | 111 |
DLE | 16 | 48 | P | 80 | p | 112 | |
DC1 | 17 | 1 | 49 | Q | 81 | q | 113 |
DC2 | 18 | 2 | 50 | R | 82 | r | 114 |
DC3 | 19 | 3 | 51 | S | 83 | s | 115 |
DC4 | 20 | 4 | 52 | T | 84 | t | 116 |
NAK | 21 | 5 | 53 | U | 85 | u | 117 |
SYN | 22 | 6 | 54 | V | 86 | v | 118 |
ETB | 23 | 7 | 55 | W | 87 | w | 119 |
CAN | 24 | 8 | 56 | X | 88 | x | 120 |
EM | 25 | 9 | 57 | Y | 89 | y | 121 |
SUB | 26 | : | 58 | Z | 90 | z | 122 |
ESC | 27 | ; | 59 | [ | 91 | { | 123 |
FS | 28 |
| 60 | \ | 92 | | | 124 |
GS | 29 | = | 61 | ] | 93 | } | 125 |
RS | 30 | > | 62 | ^ | 94 | ~ | 126 |
US | 31 | ? | 63 | _ | 95 | DEL | 127 |
Figure 7.1 Table des 128 premiers caract?res (code ASCII)
La fonction int_of_char donne le code du caract?re passØ en param?tre.
Exemple 5 :
7.2. LES CHA?NES DE CARACT¨RES
# int_of_char(’ ’);;
- : int = 32
# int_of_char(’A’);;
- : int = 65
# int_of_char(’a’);;
- : int = 97
Inversement, la fonction char_of_int donne le caract?re associØ l’entier passØ en param?tre qui doit Œtre compris entre 0 et 255.
Exemple 6 :
# for i=65 to 70 do print_char (char_of_int(i)) done;; ABCDEF- : unit = () |
7.1.3 Comparaison de caract?res
Les opØrateurs =, et >= permettent de comparer deux caract?res. Si c1 et c2 sont deux expressions de type CHAR, alors
1. c1 = c2 est vrai si et seulement si les deux caract?res c1 et c2 sont Øgaux;
2. c1
3. c1
4. etc
7.2 Les cha nes de caract?res
7.2.1 DØ nition
Les cha nes de caract?res sont des sØquences nies de caract?res. Le nombre de caract?res composant une cha ne de caract?res est la longueur de cette cha ne. Par la suite nous noterons
|s| = longueur de s.
Une cha ne de longueur nulle ne comprend aucun caract?re : c’est la cha ne vide.
En Caml, les cha nes de caract?res forment le type string et leur longueur est limitØe
224 ? 6 = 16777210 caract?res.
Il est possible de dØclarer des variables de type string.
Exemple 7 :
# let chaine1 = "TIMO" and chaine2 = "LEON";; val chaine1 : string = "TIMO" val chaine2 : string = "LEON"
Les constantes littØrales de type string sont dØsignØes entre deux guillemets.
Il est possible d’Øcrire une donnØe de ce type au moyen des procØdures print_string et print_endline.
Exemple 8 :
# begin print_string("Bonjour, je m’appelle"); print_string(chaine1); print_endline(chaine2); print_endline("Et vous, comment vous appelez-vous?") end;; Bonjour, je m’appelle TIMOLEON Et vous, comment vous appelez-vous ? - : unit = () |
Une cha ne de 1 caract?re n’est pas un caract?re. Et en particulier on ne peut a ecter une valeur de type char une variable mutable de type string.
# let s = ref "" ;; val s : string ref = {contents = ""} # s := ’a’;; This expression has type char but is here used with type string # s := "a" ;; - : unit = () # s;; - : string ref = {contents = "a"} |
7.2.2 Notation indicielle
Une cha ne de caract?res est, par dØ nition, composØe de caract?res. Ces caract?res sont numØrotØs dans l’ordre partir de 0, et ces numØros sont appelØs indices. Le premier caract?re a pour indice 0, le second a pour indice 1, etc Le dernier caract?re a pour indice |s| ? 1.
On acc?de au caract?re d’indice i d’une cha ne s avec la notation indicielle pointØe :
# chaine1.[0];;
- : char = ’T’
# chaine1.[1];;
- : char = ’I’
# chaine1.[2];;
- : char = ’M’
# chaine1.[3];;
- : char = ’O’
7.2. LES CHA?NES DE CARACT¨RES
Les cha nes de caract?res sont des structures de donnØes mutables. On peut modi er un caract?re d’une cha ne de caract?res l’aide de la notation indicielle. Pour modi er le caract?re
val c : string = "TiMOLEON" # c.[1]
- : unit = ()
# c ;;
- : string = "TIMOLEON"
L’acc?s un caract?re d’une cha ne s n’est possible que si l’indice i est compris entre 0 et |s|?1. Toute tentative d’acc?s un caract?re d’indice situØ en dehors de cet intervalle dØclenche l’exception Invalid_argument "index out of bounds".
Exception: Invalid_argument "index out of bounds".
Et voici le code d’une procØdure Øquivalente la procØdure prØdØ nie print_string.
(* ecrire_chaine(s) ecrit a l’ecran la chainescette procedure est equivalente a print_string(s) *)let ecrire_chaine(s) = for i=0 to String.length(s)-1 do print_char(s.[i])
done
7.2.3 ConcatØnation
La concatØnation de deux cha nes de caract?res s1 et s2 est l’opØration consistant mettre bout bout ces deux cha nes. La cha ne ainsi obtenue est appelØe concatØnØe de s1 et s2.
En Caml, c’est l’opØrateur ^ qui permet d’exprimer la concatØnation de deux cha nes de caract?res.
Exemple 11 :
# chaine1^chaine2;;
- : string = "TIMOLEON"
La longueur de la cha ne de caract?res s1^s2 est Øgale la somme des longueurs de chacune des deux cha nes
|s1^s2| = |s1| + |s2|.
7.2.4 Comparaison de cha nes
Les opØrateurs =, et >= permettent de comparer deux cha nes de caract?res. Si s1 et s2 sont deux expressions de type STRING, alors
1. s1 = s2 est vrai si et seulement si les deux cha nes de caract?res s1 et s2 sont Øgales;
2. s1
3. s1
4. etc
7.3 Quelques fonctions prØdØ nies sur les cha nes
Hormis la premi?re, les fonctions prØsentØes ici ne sont pas conna tre par c ur.
Le fonctions prØdØ nies sur les cha nes de caract?res font toutes partie du module String. Leur nom est donc prØ xØ par le mot String (avec un S majuscule).
Longueur d’une cha ne
String.length : Exemple 12 : | string s | ?? 7?? | int . String.length(s) = |s| |
# String.length("TIMOLEON");;
- : int = 8
# String.length("");;
- : int = 0
CrØation d’une cha ne d’une taille donnØe | ||
String.create : int | ?? | string |
n | 7?? | String.create(n) , |
CU : n ? 0
oø String.create(n) est une nouvelle cha ne de n caract?res non spØci Øs.
Exemple 13 :
# String.create(10);;
- : string = "
Copie d’une cha ne
String.copy : string ?? string
,
s 7?? String.copy(s)
oø (s) est une nouvelle cha ne copie de la cha ne s, c’est dire une cha ne Øgale s.
Exemple 14 :
7.3. QUELQUES FONCTIONS PR D FINIES SUR LES CHA?NES
# let s1 = "tIMOLEON" ;; val s1 : string = "tIMOLEON" # let s2 = (s1) ;; val s2 : string = "tIMOLEON" # s1 = s2 ;; - : bool = true # s1.[0] - : unit = () # s1 ;; - : string = "TIMOLEON" # s2 ;; - : string = "tIMOLEON" |
En Objective Caml il n’y a pas de fonction string_of_char qui transforme un caract?re en la cha ne constituØe de ce seul caract?re. C’est un excellent exercice que de rØaliser cette fonction avec les fonctions prØsentØes dans ce chapitre (cf exercice 7-3).
7.4 Exercices
Exercice 7-1
Sur le mod?le de la procØdure ecrire_chaine, rØalisez une procØdure nommØe ecrire_vertical qui Øcrit verticalement la cha ne passØe en param?tre. Par exemple, pour la cha ne vertical la procØdure Øcrira l’Øcran
v e r t i c a l
Exercice 7-2
Sur le mod?le de la procØdure ecrire_chaine, rØalisez une procØdure nommØe ecrire_chaine_a_l_envers qui Øcrit l’envers la cha ne passØe en param?tre. Par exemple, pour la cha ne repus la procØdure Øcrira l’Øcran super
Exercice 7-3 string_of_char RØalisez la fonction
string_of_char : char ?? string
c 7?? s
oø s est la cha ne constituØe du seul caract?re passØ en param?tre. Par exemple on doit avoir
# string_of_char(’a’) ;;
- : string = "a"
# string_of_char(’1’) ;;
- : string = "1"
# string_of_char(’+’) ;;
- : string = "+"
Exercice 7-4 string_of_int RØalisez la fonction
string_of_int : int ?? string
n 7?? s
oø s est la cha ne de caract?re constituØe des chi res de l’Øcriture dØcimale de n. Par exemple on doit avoir
# string_of_int(123) ;;
- : string = "123"
# string_of_int(-12) ;;
- : string = "-12"
7.4. EXERCICES
Exercice 7-5 Sous-cha nes
Une sous-cha ne d’une cha ne de caract?res s est une cha ne composØe de caract?res consØcutifs de s. Elles peuvent Œtre caractØrisØes par l’indice de dØbut et leur longueur.
Voici par exemple quelques sous-cha nes pour la cha ne s = TIMOLEON :
Sous-cha ne | dØbut | longueur |
T | 1 | |
IMO | 1 | 3 |
LEON | 4 | 4 |
TIMOLEON | 8 |
RØalisez la fonction
sous_chaine : string × int × int ?? string s,deb,long 7?? s.[ + long ? 1] CU : 0 ? deb |s| et 0 ? long |s| + 1 ? deb
oø s.[+long ?1] dØsigne la sous-cha ne de s dØbutant l’indice deb et de longueur long, donc terminant l’indice deb + long ? 1. Exemple 15 :
# sous_chaine("TIMOLEON",0,1);;
- : string = "T"
# sous_chaine("TIMOLEON",1,3);;
- : string = "IMO"
# sous_chaine("TIMOLEON",4,4);;
- : string = "LEON"
# sous_chaine("TIMOLEON",0,8);;
- : string = "TIMOLEON"
Exercice 7-6 Miroir
La cha ne miroir d’une cha ne s est la cha ne dont les caract?res successifs sont ceux de la cha ne s dans l’ordre inverse. Par exemple, la cha ne miroir de TIMOLEON est NOELOMIT. RØalisez la fonction
miroir : string ?? string
.
s 7?? miroir(s)
Exercice 7-7 Palindromes
Un palindrome est un mot qui se lit de la mŒme fa on de gauche droite et de droite gauche. ICI, ETE, ELLE et RADAR sont des palindromes.
RØalisez un prØdicat qui est vrai si et seulement si la cha ne passØe en param?tre est un palindrome.
Exercice 7-8 Initialisations de tas de cartes
Les descriptions des tas de cartes sont des cha nes de caract?res.
Question 1 Initialisez le tas 1 avec une description de tas donnØe par l’utilisateur.
Question 2 Initialisez le tas 1 avec des tr? es dont le nombre est donnØ par l’utilisateur.
Question 3 MŒme question mais chaque carte Øtant de couleur quelconque.
Exercice 7-9 Initiale et autres
Question 1 RØalisez une fonction initiale qui donne le caract?re initial (c’est- -dire le premier) d’une cha ne de caract?res. Cette fonction a-t-elle des contraintes d’utilisation?
Question 2 RØalisez une fonction finale qui donne le caract?re nal (c’est- -dire le dernier) d’une cha ne de caract?res. Cette fonction a-t-elle des contraintes d’utilisation?
Question 3 RØalisez une fonction sauf_initiale qui donne la cha ne passØe en param?tre sans son initiale. Cette fonction a-t-elle des contraintes d’utilisation?
Exercice 7-10 PrØ xe
Une cha ne de caract?res s1 est un prØ xe d’une autre s2 si la cha ne s1 est le dØbut de la cha ne s2. titre d’exemple, les prØ xes de ’TIMOLEON’ sont ”, ’T’, ’TI’, ’TIM’, ’TIMO’,’TIMOL’, ’TIMOLE’, ’TIMOLEO’ et ’TIMOLEON’.
RØalisez de deux fa ons di Ørentes une fonction qui teste si une cha ne (premier param?tre de la fonction) est un prØ xe d’une autre (second param?tre de la fonction).
Exercice 7-11
RØalisez une fonction qui retourne le plus petit (aus sens de l’ordre dØ ni dans la section 7.1.3) caract?re de la cha ne de caract?res passØe en param?tre.
Annexe A
Les cartes
A.1 PrØsentation
Le module Cartes o re une extension du langage Caml a n d’Øcrire des programmes destinØs un robot manipulateur de cartes.
Le domaine de travail du robot est constituØ de tas, numØrotØs 1,2,3,4, sur lesquels sont empilØes des cartes jouer. Ces cartes ont les couleurs habituelles (?, ?, ? et ?) et les valeurs habituelles (par ordre croissant : as, deux, trois, , dix, valet, dame, roi). Les cartes proviennent de plusieurs jeux, il est donc possible de trouver plusieurs exemplaires d’une mŒme carte.
Chacun des quatre tas peut contenir un nombre quelconque de cartes, y compris aucune.
A.2 Utilisation du module Cartes
Le module Cartes est un module spØci quement dØveloppØ l’universitØ de Lille 1 pour l’enseignement d’InitProg. Ce module n’est donc pas livrØ avec les distributions d’Objective Caml, et il est nØcessaire de l’installer sØparØment. Nous supposons ici que cette installation est faite.
Pour utiliser ce module, plusieurs possibilitØs existent :
1. depuis un interpr?te, invoquer la directive #load
# #load "" ;; Chargement des images. Patientez quelques instants.
.
#
2. en lan ant un interpr?te, ajouter le module sur la ligne de commande
$ ocaml
Chargement des images. Patientez quelques instants.
. Objective Caml version 3.10.0
#
3. en lan ant l’interpr?te dØdiØ au module
83
$ ocamlcartes
Chargement des images. Patientez quelques instants.
. Objective Caml version 3.10.0
Camlcartes
FIL IEEA univ. Lille 1 (2009) pour obtenir de l’aide : aide_moi () ;;
#
Dans tous les cas, une fenŒtre graphique s’ouvre.
Les noms des di Ørentes variables, fonctions et procØdures dØclarØes dans ce module doivent normalement Œtre prØ xØs par le nom du module. Par exemple, l’instruction init_tas pour initialiser un tas (cf ci-dessous) doit Œtre invoquØe par le nom Cartes.init_tas. Pour se dispenser de prØ xer systØmatiquement tous les noms par celui du module, il su t d’exØcuter la commande
# open Cartes;;
#
Ceci accompli, on peut faire rØfØrence tous les ØlØments dØclarØs dans le module en utilisant leur nom non prØ xØ par celui du module.
# init_tas (1,"T") ;;
- : unit = ()
Dans toute la suite, nous supposerons que l’instruction open Cartes a ØtØ exØcutØe.
A.3 Le langage du module Cartes
A.3.1 Description de tas
Une fois le module Cartes chargØ, la fenŒtre graphique montre quatre tas de cartes. Ces tas, numØrotØs de 1 4 de gauche droite, contiennent des cartes en nombre quelconques choisies au hasard. Les probl?mes que nous traiterons nØcessitent de pouvoir imposer certaines con gurations de l’Øtat de ces quatre tas.
A n de dØcrire en dØbut de programme, la con guration initiale des tas de cartes, le module Cartes o re une procØdure init_tas. Syntaxe :
init_tas(n,s)
oø n est le numØro du tas dØcrit, et s est une cha ne de description du tas.
En Caml, les cha nes sont dØlimitØes par des guillemets " (cf chapitre 7).
La cha ne de description, lue de gauche droite, indique les cartes d’un tas du bas vers le haut avec les conventions suivantes :
Les lettres T, K, C, P reprØsentent respectivement : ?, ?,?, ?;
Si A et B sont des cha nes de description, la cha ne AB est aussi une cha ne de description qui reprØsente les cartes de A surmontØes de celles de B.
Si A et B sont des cha nes de description, la cha ne A+B est aussi une cha ne de description qui reprØsente un choix entre les cartes de A ou celles de B ;
Si A est une cha ne de description, [A] reprØsente la rØpØtition des cartes de A un nombre quelconque (dØ ni de mani?re alØatoire) de fois (y compris zØro). Les parenth?ses sont autorisØes pour Øviter les ambigu tØs.
Exemple 1 :
1. init_tas(1,"") dØclare le tas numØro 1 vide.
2. l’instruction init_tas(2,"TCK") dØcrit le tas numØro 2 contenant de bas en haut un ?, un ? et un ?.
3. l’instruction init_tas(3,"T+P") dØcrit le tas numØro 3 contenant une carte qui est soit un ? soit un ?.
4. init_tas(4,"[T+P]") dØcrit le tas numØro 4 contenant un nombre quelconque, non dØterminØ, de cartes de couleur ? ou ?.
5. l’instruction init_tas(1,"T+[P]CC") dØcrit le tas numØro 1 contenant soit une seule carte de couleur ?, soit un nombre quelconque de ? surmontØ de deux ?.
6. l’instruction init_tas(1,"(T+[P])CC") dØcrit le tas numØro 1 contenant soit trois cartes un ? surmontØ de deux ?, soit un nombre quelconque de ? surmontØ de deux ?. noter qu’une autre fa on de dØcrire la mŒme initialisation est d’utiliser la cha ne "TCC + [P]CC".
Une instance possible de l’Øtat des quatre tas apr?s exØcutions des instructions numØrotØes 1, 2, 3 et 5 est donnØe par la partie gauche de la gure A.1 page 86.
Remarque : Tout programme de rØsolution d’un probl?me sur les cartes doit dØbuter par une initialisation des quatre tas l’aide de l’instruction init_tas. Une fois cette initialisation e ectuØe, cette instruction n’est plus utilisØe. Il s’en suit qu’apr?s l’Øtape d’initialisation, le nombre de cartes globalement prØsentes sur les quatre tas ne varie pas.
A.3.2 Action
La seule action permettant de modi er l’Øtat des tas est le dØplacement de la carte situØe au sommet d’un tas vers le sommet d’un autre tas. Cette action est donnØe par un appel la procØdure deplacer_sommetparamØtrØe par un couple :
Syntaxe :
deplacer_sommet(n,p)
oø n est le numØro du tas duquel on prend une carte, et p est celui du tas sur lequel on la pose.
Exemple 2 :
L’instruction deplacer_sommet(2,4) a pour e et de dØplacer la carte au sommet du tas 2 pour la poser au sommet du tas 4. AppliquØe l’Øtat des tas dØcrits par la partie gauche de la gure A.1, cette instruction transforme les tas 2 et 4 comme le montre la partie droite.
CU : Il n’est pas permis de dØplacer une carte situØe sur un tas vide. Toute tentative d’action deplacer_sommet(n,p) dØclenche l’exception Tas_Vide si le tas n est vide.
(a) 1 (b) 2
Figure A.1 Transformation des tas par dØplacement d’une carte
A.3.3 Tests sur les tas
Certains traitements nØcessitent des tests. Pour cela on dispose de fonctions.
Test de vacuitØ
Pour tester si un tas est vide, on fera appel la fonction Syntaxe :
tas_vide(n)
qui donne la valeur vrai (true en anglais, et en Caml) si le tas numØro n est vide, faux (false en anglais et en Caml) dans le cas contraire.
On peut faire le test contraire en faisant appel la fonction Syntaxe :
tas_non_vide(n)
Test sur la couleur
Les quatre couleurs sont dØcrites dans le module Cartes par les quatre identi cateurs (prØ xØs par le nom du module Cartes) :
Cartes.TREFLE, Cartes.CARREAU, Cartes.COEUR, Cartes.PIQUE.
Si la commande open Cartes a ØtØ exØcutØe, on peut se dispenser de prØ xer les noms des couleurs dans l’Øcriture des programmes.
Il est important de dØsigner les couleurs par ces identi cateurs en lettres MAJUSCULES.
Il est possible de conna tre la couleur au sommet d’un tas en faisant appel la fonction
int?bool Syntaxe : couleur_sommet(n)
qui donne la couleur de la carte situØe au sommet du tas numØro n.
Exemple 3 :
if couleur_sommet(2)=PIQUE then
CU : Il est normalement dØnuØ de sens de tester la couleur de la carte situØe au sommet d’un tas vide. Toute tentative d’appel couleur_sommet(n) dØclenche l’exception Tas_Vide si le tas n est vide.
Quatre autres fonctionspermettent aussi de tester la couleur du sommet d’un tas Syntaxe :
sommet_trefle(n) sommet_carreau(n) sommet_coeur(n)
sommet_pique(n)
qui donnent la valeur vrai si le sommet du tas n est un ? (?,?,?) et faux dans le cas contraire. Elles sont soumises la mŒme contrainte d’utilisation que la fonction couleur_sommet, et dØclenchent la mŒme exception en cas de non respect de cette contrainte.
A.3.4 Comparaison des valeurs
Une fonction permet de comparer les valeurs des cartes au sommet de deux tas : Syntaxe :
superieur(n,p)
qui donne la valeur vrai si la carte au sommet du tas numØro n a une valeur supØrieure ou Øgale celle du tas numØro p, et la valeur faux dans le cas contraire.
CU : On ne peut comparer les cartes situØes au sommet de deux tas que s’ils ne sont pas vides.
Tout appel superieur(n,p) dØclenche l’exception Tas_Vide si l’un des tas n ou p est vide.
A.3.5 Contr le de l’a chage
Modes d’a chage
l’exØcution, l’a chage peut se faire de trois fa ons :
1. mode graphique : Dans ce mode, on visualise l’Øvolution des tas de cartes dans une fenŒtre graphique. C’est le mode par dØfaut.
2. mode texte : Dans ce mode, on visualise l’Øvolution des tas de cartes dans le terminal oø s’exØcute le programme. Voici un exemple d’a chage textuel produit par l’exØcution d’une instruction :
# deplacer_sommet(4,1) ;; deplacer_sommet(4,1);;
(* ._____. *) (* | 3P | *) (* ._____. *)
(* | 10P | *)
(* ._____. *) (* | vP | *) (* ._____. *) (* | 5P | *)
(* ._____. ._____. *) (* | 5T | | 4P | *)
(* ._____. ._____. ._____. ._____. *) (* | 7P | | 6T | | 6K | | dP | *)
(*____________________________________________*)
- : unit = ()
3. mode texte et graphique : Dans ce mode, on visualise l’Øvolution des tas de cartes la fois dans le terminal et dans une fenŒtre graphique.
Le mode d’a chage par dØfaut est le mode graphique. L’instruction
affichage_en_mode_texte ()
permet de passer en mode texte. L’instruction
affichage_en_mode_graphique ()
permet de passer en mode graphique. Et l’instruction
affichage_en_mode_texte_et_graphique ()
permet de combiner les deux modes texte et graphique.
Remarque : Le mode texte permet de conserver une trace de l’exØcution d’un programme dans un chier texte. Par exemple, si un chier nommØ contient un programme de rØsolution d’un probl?me sur les cartes, et s’il contient une instruction demandant un a chage textuel, alors dans un terminal la commande
$ ocamlcartes > exo.result
produit un chier texte nommØ exo.result contenant toutes les instructions exØcutØes suivies de l’Øtat des tas de cartes qu’elles transforment.
Vitesse d’exØcution
Un dØlai est imposØ entre l’exØcution des instructions de manipulation des tas. Le temps d’attente peut Œtre ajustØ en fonction des besoins. Le module fournit deux ØlØments permettant de consulter (quel_delai)et de modi er (fixer_delai)cette temporisation.
Pour augmenter la vitesse d’exØcution, il su t de diminuer la valeur rØelle.
fixer_delai(0.1)
L’instruction prØcØdente permet de xer la durØe de l’attente un dixi?me de seconde.
Pause
L’instruction pausepermet de faire une pause durant l’exØcution d’un programme. Elle s’utilise en communiquant un message en param?tre, message qui sera imprimØ dans le terminal lors de la pause. La pause s’arrŒte d?s l’appui sur la touche EntrØe.
pause ("un petit repose bien merite") |
A.3.6 RØparer l’automate
Lorsqu’une contrainte d’utilisation n’est pas respectØe, par exemple lorqu’on veut dØplacer une carte situØe sur un tas vide, une exception est dØclenchØe, et la fenŒtre graphique appara t barrØe de deux lignes rouges qui indique que l’automate est cassØ . partir de ce moment plus aucune action sur l’automate n’est possible.
La session qui suit suppose que la situation actuelle est celle montrØe la gure A.1, et montre le dØclenchement de l’exception LesExceptions.Tas_Vide 1 dß la tentative de dØplacer une carte depuis le tas 1 qui est vide, puis le dØclenchement de l’exception LesExceptions.AutomateCasse qui montre l’impossibilitØ d’agir sur l’environnement des tas puisque l’automate a ØtØ cassØ par la commande prØcØdente.
# deplacer_sommet(1,2) ;; Exception: LesExceptions.Tas_Vide 1.
# deplacer_sommet(2,3);; Exception: LesExceptions.AutomateCasse.
Plus rien n’est possible avant l’exØcution de l’instruction Admin.repare (). Cette instruction permet de rØparer l’automate (les lignes rouges de la fenŒtre graphique disparaissent), et de poursuivre les actions sur les tas de cartes.
# Admin.repare ();;
- : unit = ()
# deplacer_sommet(2,3) ;;
- : unit = ()
A.3.7 Obtenir de l’aide
Pour obtenir un aide-mØmoire des principales fonctions et instructions du module Cartes, on fait appel la fonction aide_moi.
# aide_moi () ;; Les principaux elements du Module Cartes ---------------------------------------- * init_tas : numero_tas * string -> unit init_tas(num_tas,chaine) : initialise le tas numero num_tas avec la description donnee par chaine. |
A.4 Exercices
Ils sont classØs en facile , moyen et di cile (les premiers sont tr?s faciles).
A.4.1 Descriptions de tas
Exercice A-1
Pour chacune des descriptions qui suivent, donnez l’instruction d’initialisation du tas qui convient :
le tas 1 contient une carte de couleur ?; le tas 1 contient une carte de couleur ? ou ?; le tas 1 contient une carte de couleur quelconque; le tas 1 contient deux cartes de couleur ?; le tas 1 contient une carte de couleur ? surmontØe d’un ?; le tas 1 contient un nombre quelconque de ?;
le tas 1 contient un nombre quelconque de ? ou bien un nombre quelconque de ?; le tas 1 contient un nombre quelconque de cartes de couleur ? ou ?; le tas 1 contient un nombre quelconque de cartes de couleur quelconque; le tas 1 contient au moins un carreau; le tas 1 contient un ? surmontØ soit d’un nombre quelconque de ?, soit d’un nombre quelconque non nul de ?; le tas 1 contient un nombre pair de ?; le tas 1 contient un nombre impair de ?;
le tas 1 contient un nombre pair de ? ou un nombre multiple de 3 de ?; les deux cartes extrŒmes du tas 1 (la plus basse et la plus haute) sont des ?, entre les deux il y a un nombre quelconque de successions de deux cartes de couleur ??.
A.4.2 SØquence
Dans tous les exercices qui suivent, l’ØnoncØ dØcrit une situation initiale des quatre tas de cartes (dans la syntaxe du module Cartes), et la situation nale atteindre.
Exercice A-2 Situation initiale :
Tas 1 : "TT" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "" Tas 2 : "TT" Tas 3 : "" Tas 4 : ""
Exercice A-3 Situation initiale :
Tas 1 : "TK" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "KT" Tas 2 : ""
Tas 3 : "" Tas 4 : ""
Exercice A-4 Situation initiale :
Tas 1 : "TKTK" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "KKTT" Tas 2 : ""
Tas 3 : "" Tas 4 : ""
Exercice A-5 Situation initiale :
Tas 1 : "TKCP" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "PCKT" Tas 2 : ""
Tas 3 : "" Tas 4 : ""
A.4.3 Conditionnelle
Exercice A-6 Situation initiale :
Tas 1 : "T+P" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "" Tas 2 : "[T]" Tas 3 : "[P]" Tas 4 : ""
Exercice A-7
Situation initiale :
Tas 1 : "(T+K+C+P)(T+K+C+P)" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "" Tas 2 : ""
Tas 3 : "(T+K+C+P)(T+K+C+P)"? Tas 4 : ""
le symbole ? signi ant que les cartes sont dans l’ordre croissant (i.e. la carte du dessous a une valeur infØrieure ou Øgale celle du dessus).
Exercice A-8 Situation initiale :
Tas 1 : "T+K+C+P" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "[T]" Tas 2 : "[K]"
Tas 3 : "[C]" Tas 4 : "[P]"
Exercice A-9 Situation initiale :
Tas 1 : "(T+K+C+P)(T+K+C+P)" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "[K+C]" Tas 2 : "[T+P]"
Tas 3 : "" Tas 4 : ""
A.4.4 ItØration
Situation initiale : | |
Tas 1 : "[T]" | Tas 2 : "" |
Tas 3 : "" Situation nale : | Tas 4 : "" |
Tas 1 : "" | Tas 2 : "[T]" |
Tas 3 : "" Exercice A-11 Situation initiale : | Tas 4 : "" |
Tas 1 : "[K+C][T+P]" | Tas 2 : "" |
Tas 3 : "" Situation nale : | Tas 4 : "" |
Tas 1 : "[T+P][K+C]" | Tas 2 : "" |
Tas 3 : "" Exercice A-12 Situation initiale : | Tas 4 : "" |
Tas 1 : "[K]" | Tas 2 : "[T]" |
Tas 3 : "" Situation nale : | Tas 4 : "" |
Tas 1 : "[K]" | Tas 2 : "" |
Tas 3 : "[KT]" ou bien : | Tas 4 : "" |
Tas 1 : "" | Tas 2 : "[T]" |
Tas 3 : "[KT]" Exercice A-13 Situation initiale : | Tas 4 : "" |
Tas 1 : "[T]" | Tas 2 : "" |
Tas 3 : "" Situation nale : | Tas 4 : "" |
Tas 1 : "" | Tas 2 : "[T]" |
Tas 3 : "[T]" | Tas 4 : "" |
Exercice A-10 le nombre de cartes des deux tas 2 et 3 di Ørant d’au plus 1 dans la situation nale.
Exercice A-14 Situation initiale :
Tas 1 : "[T]" Tas 2 : "[K]"
Tas 3 : "[P]" Tas 4 : ""
Situation nale :
Tas 1 : "" Tas 2 : "[T]"
Tas 3 : "[K]" Tas 4 : "[P]"
En faire deux versions, la seconde utilisant une procØdure vider_tas(depart,arrivee) qui vide le tas depart sur le tas arrivee.
Exercice A-15 Situation initiale :
Tas 1 : "[T]" Tas 2 : "[K]"
Tas 3 : "[C]" Tas 4 : "[P]"
Situation nale :
Tas 1 : "[P]" Tas 2 : "[T]"
Tas 3 : "[K]" Tas 4 : "[C]"
Exercice A-16 Situation initiale :
Tas 1 : "[T][K][C][P]" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "[P][C][K][T]" Tas 2 : ""
Tas 3 : "" Tas 4 : ""
Exercice A-17 Situation initiale :
Tas 1 : "[T]" Tas 2 : "[K]"
Tas 3 : "[P]" Tas 4 : ""
Situation nale :
Tas 1 : "" Tas 2 : ""
Tas 3 : "" Tas 4 : "[TKP][XY ][Z]"
oø X et Y dØsignent les deux couleurs restantes lorsque l’une des couleurs manque, et Z dØsigne la couleur restante lorsque X ou Y manque.
Situation initiale : | |
Tas 1 : "[T+K+C+P]" | Tas 2 : "" |
Tas 3 : "" Situation nale : | Tas 4 : "" |
Tas 1 : "[T]" | Tas 2 : "[K]" |
Tas 3 : "[C]" Exercice A-19 Situation initiale : | Tas 4 : "[P]" |
Tas 1 : "T[T]" | Tas 2 : "" |
Tas 3 : "" Situation nale : | Tas 4 : "" |
Tas 1 : "" | Tas 2 : "T"? |
Tas 3 : "[T]" | Tas 4 : "" |
Exercice A-18 le symbole ? indique que la carte est de valeur minimale.
Exercice A-20 Situation initiale :
Tas 1 : "[T]" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "" Tas 2 : "[T]?
Tas 3 : "" Tas 4 : ""
le symbole ? signi ant que les cartes sont rangØes par ordre croissant de valeurs de bas en haut.
Exercice A-21
Situation initiale :
Tas 1 : "[T+K]" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "[X][Y ]" Tas 2 : ""
Tas 3 : "" Tas 4 : ""
Le symbole X dØsigne la couleur (? ou ?) la plus nombreuse, l’autre couleur Øtant dØsignØe par
Y .
Exercice A-22 Situation initiale :
Tas 1 : "K[T]" Tas 2 : "" Tas 3 : "" Tas 4 : ""
Situation nale :
Tas 1 : "[T+K]" Tas 2 : "[T+K]" Tas 3 : "[T+K]" Tas 4 : "[T+K]"
les tr? es Øtant Øquitablement rØpartis sur les quatre tas, l’unique carreau se trouvant n’importe oø.
Remarque : ce probl?me est infaisable sans le carreau.
Exercice A-23 Situation initiale :
Tas 1 : "[T]" Tas 2 : "[K]"
Tas 3 : "[C]" Tas 4 : "[P]"
Situation nale :
Tas 1 : "[T]?" Tas 2 : "[K]?"
Tas 3 : "[C]?" Tas 4 : "[P]?"
le symbole ? signi ant que les cartes sont rangØes par ordre croissant de valeurs de bas en haut.
A.4.5 Fonctions et procØdures
Exercice A-24
Soit la fonction dØ nie en Caml par
let meme_couleur (couleur, tas) =
couleur = couleur_sommet(tas) ;;
Question 1 Quel probl?me pose cette fonction si lors d’un appel le tas tas passØ en param?tre est vide?
Question 2 Comment modi er la fonction meme_couleur pour qu’elle renvoie la valeur faux si le tas tas est vide.
Exercice A-25 galitØ de deux cartes
Question 1 crivez une fonction qui teste l’ØgalitØ de la valeur de deux cartes situØes au sommet de deux tas que l’on supposera non vide.
Question 2 Puis Øcrivez une fonction qui teste l’ØgalitØ de deux cartes (valeur et couleur) situØes au sommet de deux tas supposØs non vides.
Exercice A-26 Inverser l’ordre des cartes d’un tas
Il s’agit d’Øcrire une procØdure inverser_tas1 pour inverser l’ordre des tas du tas 1. Par exemple, si on a Tas 1:"TCCPK" alors apr?s exØcution de l’instruction inverser_tas1 (), on doit avoir Tas 1:"KPCCT".
Question 1 Fa tes-le avec l’hypoth?se que les autres tas sont vides.
Question 2 RØaliser la procØdure sans supposer que les autres tas sont vides.
Annexe B
Le module Camlgraph
B.1 PrØsentation
Le module Camlgraph est une adaptation du module graphics livrØ avec toutes les distributions de Objective Caml. Il reprend les mŒmes fonctions avec les mŒmes noms. La seule di Ørence rØside dans le fait que toutes les fonctions y sont dØcurry Øes.
Ce module permet de dessiner des points, des segments, des polygones, des cercles, de remplir certaines zones dans une fenŒtre graphique. Cette fenŒtre graphique peut Œtre considØrØe comme un tableau de points repØrØs par leurs coordonnØes (cf gure B.1). Ces coordonnØes sont des nombres entiers. Seuls les points dont les deux coordonnØes sont positives ou nulles et infØrieures
la largeur et la hauteur de la fenŒtre sont visibles.
Figure B.1 Syst?me de coordonnØes du module Camlgraph
Le programme ci-dessous illustre une utilisation de ce module. Son exØcution produit l’image prØsentØe sur la gure B.2.
97
(* auteur : EW *) (* date : mai 2009 *) (* objet : dessin de cercles *) (* concentriques de *) (* couleurs aleatoires *) (* utilise le module Camlgraph *) open Camlgraph ;; let largeur = 600 (* largeur de la fenetre graphique *)and hauteur = 400 (* hauteur de la fenetre graphique *) ;; let n = (hauteur - 20) / 2 (* le nombre de cercles a dessiner *)and cx = largeur / 2 (* abscisse du centre des cercles *)and cy = hauteur / 2 (* ordonnee du centre des cercles *);; begin (int_of_float (())); open_graph (""^string_of_int(largeur)^"x"^string_of_int(hauteur)) ; set_window_title ("Cercles") ; for i = 1 to n do set_color (rgb((256),(256),(256))); draw_circle (cx,cy,i) done; print_endline "appuyez sur une touche pour terminer"; ignore(read_key ()) ; close_graph () end |
B.2 Module Camlgraph
Author(s) : FIL
B.2.1 Gestion des fenŒtres graphiques val open_graph : string -> unit open_graph (s) ouvre une fenŒtre graphique dont les dimensions sont indiquØes par la cha ne s Pour une ouverture de la fenŒtre sur l’Øcran par dØfaut, la cha ne doit commencer par un espace. val close_graph : unit -> unit close_graph () ferme de la fenŒtre graphique. val set_window_title : string -> unit set_window_title (s) donne un titre la fenŒtre graphique.
B.2. MODULE CAMLGRAPH 99
Figure B.2 Figure produite en utilisant le module Camlgraph
val resize_window : int * int -> unit resize_window (w,h) redimensionne la fenŒtre graphique w = largeur, h = hauteur. val clear_graph : unit -> unit clear_graph () e ace le contenu de la fenŒtre graphique. val size_x : unit -> int size_x () donne la largeur de la fenŒtre graphique. val size_y : unit -> int size_y () donne la hauteur de la fenŒtre graphique.
B.2.2 Gestion des couleurs
type color = Graphics.color
reprØsentation des couleurs
val rgb : int * int * int -> color rgb (r,g,b) donne une couleur partir de ses trois composantes rouge, vert, bleu. val set_color : color -> unit set_color (x) xe la couleur courante.
val background : color couleur courante de l’arri?re plan.
val foreground : color couleur courante de l’avant plan.
Couleurs prØdØ nies val black : color val white : color val red : color val green : color val blue : color val yellow : color val cyan : color val magenta : color
B.2.3 Point et dessin de lignes
.
val plot : int * int -> unit plot (x,y) dessine un point de coordonnØes (x,y).
val point_color : int * int -> color point_color (x,y) donne la couleur du point de coordonnØes (x,y).
val moveto : int * int -> unit moveto (x,y) positionne le crayon au point de coordonnØes (x,y).
val rmoveto : int * int -> unit rmoveto (x,y) translate le crayon selon le vecteur de coordonnØes (x,y). val current_x : unit -> int current_x () donne l’abscisse de la position courante du crayon. val current_y : unit -> int current_y () donne l’ordonnØe de la position courante du crayon. val current_point : unit -> int * int current_point () donne les coordonnØes de la position courante du crayon.
val lineto : int * int -> unit
lineto (x,y) trace un segment depuis la positon courante jusqu’au point de coordonnØes (x,y).
val rlineto : int * int -> unit
rlineto (x,y) trace un segment depuis la positon courante selon le vecteur de coordonnØes (x,y).
val curveto : (int * int) * (int * int) * (int * int) -> unit
B.2. MODULE CAMLGRAPH 101
curveto (b,c,d) trace une courbe de Bezier du point courant jusqu’au point d avec les points b et c pour points de contr le.
val draw_rect : int * int * int * int -> unit
draw_rect (x1,y1,x2,y2) dessine un rectangle dont le coin infØrieur gauche a pour coordonnØes (x1,y1) et le point supØrieur droit (x2,y2).
val draw_arc : int * int * int * int * int * int -> unit
draw_arc (x,y,rx,ry,a1,a2) dessine un arc d’ellipse de centre (x,y), de rayon horizontal rx, de rayon vertical ry, entre les angles a1 et a2.
val draw_ellipse : int * int * int * int -> unit
draw_ellipse (x,y,rx,ry) dessine une ellipse de centre (x,y), de rayon horizontal rx, de rayon vertical ry.
val draw_circle : int * int * int -> unit draw_circle (x,y,r) dessine un cercle de centre (x,y), de rayon r. val set_line_width : int -> unit set_line_width (n) xe l’Øpaisseur des traits
B.2.4 Texte
val draw_char : char -> unit draw_char (c) dessine le caract?re c la position courante. val draw_string : string -> unit draw_string (s) dessine la cha ne de caract?res s la position courante. val set_font : string -> unit set_font (s) xe la police pour dessiner les textes. val set_text_size : int -> unit set_text_size (n) xe la taille des caract?res pour dessiner les textes. val text_size : string -> int * int
text_size (s) donne les dimensions du texte s s’il Øtait dessinØ avec les police et taille courantes.
B.2.5 Remplissage val fill_rect : int * int * int * int -> unit
fill_rect (x,y,w,h) remplit le rectangle dont le coin infØrieur gauche a pour coordonnØes (x,y), de largeur w et de hauteur w, avec la couleur courante
val fill_arc : int * int * int * int * int * int -> unit
fill_arc (x,y,rx,ry,a1,a2) remplit l’arc d’ellipse dont le centre a pour coordonnØes (x,y), de rayon horizontal rx et de rayon vertical ry, entre les angles a1 et a2, avec la couleur courante
val fill_ellipse : int * int * int * int -> unit
fill_ellipse (x,y,rx,ry) remplit l’ellipse dont le centre a pour coordonnØes (x,y), de rayon horizontal rx et de rayon vertical ry, avec la couleur courante
val fill_circle : int * int * int -> unit
fill_circle (x,y,r) remplit le cercle dont le centre a pour coordonnØes (x,y), de rayon r, avec la couleur courante
Annexe C
lØments du langage ØtudiØs dans ce cours
C.1 Syntaxe
C.1.1 Commentaires
Syntaxe : Commentaires en Caml
(*ceci est un commentaire*)
C.1.2 Expressions et instructions
Syntaxe : SØquence d’instructions
begin (* sequence d’instructions *) end |
Syntaxe : Bloc d’instructions
C.1.3 Expressions conditionnelles
ifthen 1>else 2> |
Syntaxe : Expression conditionnelle
103
ANNEXE C. L MENTS DU LANGAGE TUDI S DANS CE COURS
C.1.4 Instructions conditionnelles
if (* | condition >thenbloc d’instructions *) |
else (* | bloc d’instructions *) |
Syntaxe : Instruction conditionnelle simple | |
if | condition >then |
(* | bloc d’instructions *) |
Syntaxe : Instruction conditionnelle compl?te
C.1.5 Instructions conditionnellement rØpØtØes
whiledo (* sequence d’instructions *) done |
Syntaxe : Boucle tant que
C.1.6 Constantes, variables
let | = | ||
Syntaxe : DØclaration simultanØe de plusieurs variables | |||
let and | 1> = 1> 2> = 2> | ||
and | n > = n > | ||
Syntaxe : DØclaration de variables locales une expression | |||
let and | 1> 2> | = = | 1> 2> |
in |
| ||
Syntaxe : DØclaration d’une variable mutable | |||
let | = ref | ||
Syntaxe : A ectation d’une valeur une variable mutable | |||
:= |
Syntaxe : DØclaration d’une variable
C.2. MOTS-CL S DU LANGAGE 105
C.1.7 La boucle pour
for i = a to b do (* sequence d’instructions *) done | |
Syntaxe : Boucle pour | indice dØcroissant |
for i = a downto b do (* sequence d’instructions *) done |
Syntaxe : Boucle pour
C.1.8 Les fonctions
let () = (* expression simple ou sequence d’instructions definissant la fonction *) |
Syntaxe : DØclaration d’une fonction
C.1.9 Caract?res et cha nes de caract?res
C.2 Mots-clØs du langage
Liste des mots-clØs (ou encore mots rØservØs) du langage rencontrØs dans ce cours.
and, begin, do, done, downto, else, end, false, for, if, in, let, open, ref, then, to, true,
while.
Rappel Les mots-clØs du langage ne peuvent pas servir d’identi cateurs de variables.
C.3 Fonctions prØdØ nies du langage
C.3.1 Fonctions de conversion int_of_float : float ? int int_of_float x convertit le ottant x en un entier.
ANNEXE C. L MENTS DU LANGAGE TUDI S DANS CE COURS
float_of_int : int ? float float_of_int n convertit l’entier n en un ottant. int_of_char : char ? int int_of_char x convertit le caract?re c en un entier (son code ASCII). char_of_int : int ? char char_of_int n convertit l’entier n en le caract?re de code n.
DØclenche l’exception Invalid_argument "char_of_int" si n n’est pas un entier compris entre 0 et 255. int_of_string : string ? int int_of_string s convertit la cha ne s en un entier.
DØclenche l’exception Failure "int_of_string" si s n’est pas l’Øcriture d’un entier. string_of_int : int ? string string_of_int n convertit l’entier n en une cha ne de caract?res : son Øcriture dØcimale. float_of_string : string ? float float_of_string s convertit la cha ne s en un ottant.
DØclenche l’exception Failure "float_of_string" si s n’est pas l’Øcriture d’un ottant. string_of_float : float ? string
string_of_float x convertit le ottant x en une cha ne de caract?res : son Øcriture dØcimale.
C.3.2 Impressions print_int : int ? unit print_int n imprime l’entier n. print_float : float ? unit print_float x imprime le ottant f. print_char : char ? unit print_char c imprime le caract?re c. print_string : string ? unit print_string s imprime la cha ne de caract?res s. print_endline : string ? unit print_endline s imprime la cha ne de caract?res s et passe la ligne. print_newline : unit ? unit print_newline () imprime un passage la ligne.
C.3.3 Du module String
String.length : string ? int
String.length s donne la longueur de la cha ne s.
String.create : int ? string
String.create n crØe une nouvelle cha ne de longueur n.
: string ? string
s crØe une copie de la cha ne s.
C.4 Directives
#quit : pour quitter l’interpr?te.
#use : pour charger un chier contenant des dØclarations et expressions
Øvaluer.
Annexe D
Messages d’erreurs de l’interpr?te du langage
Syntax error message d’erreur lorsqu’une phrase (expression ou dØclaration) est malformØe.
# 1 + ;;
Syntax error
# let = 3+1 ;; Syntax error
# let f(x) = x + 1;; val f : int -> int = fun> # f(1)(2);; This function is applied to too many arguments, maybe you forgot a ‘;’ |
This expression has type . . . but is here used with type . . . message d’erreur lorsqu’une expression n’est pas typable par inadØquation des types de certaines sous-expressions.
# 1 + 2. ;;
This expression has type float but is here used with type int
# print_string (1);;
This expression has type int but is here used with type string
Unbound value message d’erreur lorsque dans l’Øvaluation d’une expression une variable non prØalablement dØclarØe intervient.
# a + 1;;
Unbound value a
Unbound constructor message d’erreur lorsque dans une expression intervient un constructeur non dØclarØ. En Caml, les constructeurs sont dØsignØs par des identi cateurs dØbutant par une lettre majuscule.
# init_tas(2,TT);;
Unbound constructor TT
# let a = 1 in a*a + A ;; Unbound constructor A
This function is applied to too many arguments, maybe you forgot a ‘ ;’ message d’erreur lorsqu’on prØcise d’avantange de param?tres qu’il n’est nØcessaire.
ANNEXE D. MESSAGES D’ERREURS DE L’INTERPR¨TE DU LANGAGE
This expression is not a function, it cannot be applied message d’erreur lorsqu’on essaie d’utiliser une valeur comme une fonction
# let a = 3 ;; val a : int = 3 # a(4);; This expression is not a function, it cannot be applied |
Bibliographie
[EC00] Bruno Pagano Emmanuel Chailloux, Pascal Manoury. DØveloppement d’applications avec Objective Caml. O’Reilly, 2000. Disponible en ligne l’adresse .
110 BIBLIOGRAPHIE
Liste des algorithmes
0.1 Calcul de n! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1 Mettre les trois cartes du tas 1 vers les tas 2, 3 et 4 . . . . . . . . . . . . . . . . . 16
2.1 Solution du probl?me . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1 Solution du probl?me . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1 Compter les cartes du tas 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.1 Calcul de la somme des n premiers nombres entiers. . . . . . . . . . . . . . . . . 51
5.2 Calcul de la somme des n premiers nombres entiers avec une boucle pour . . . . 52
5.3 Calcul du terme d’indice n d’une suite rØcurrente . . . . . . . . . . . . . . . . . . 54
5.4 Calcul du premier terme satisfaisant une condition . . . . . . . . . . . . . . . . . 55
112 LISTE DES ALGORITHMES
Table des gures
1 QR-code du site du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1 Le tas 1 apr?s l’instruction init_tas (1,"TCP") . . . . . . . . . . . . . . . . . . 16
1.2 Situation obtenue apr?s l’instruction deplacer_sommet (1,2) . . . . . . . . . . . 17
1.3 Situation nale souhaitØe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1 Un Øtat des tas de cartes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.1 Table des 128 premiers caract?res (code ASCII) . . . . . . . . . . . . . . . . . . . 74
A.1 Transformation des tas par dØplacement d’une carte . . . . . . . . . . . . . . . . 86
B.1 Syst?me de coordonnØes du module Camlgraph . . . . . . . . . . . . . . . . . . . 97
B.2 Figure produite en utilisant le module Camlgraph . . . . . . . . . . . . . . . . . . 99
114 TABLE DES FIGURES
Table des mati?res
1 Expressions et instructions 9
1.1 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Le logiciel Objective Caml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Premi?res expressions en Caml . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Expressions numØriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Expressions boolØennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Caract?res et cha nes de caract?res . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 Instructions d’impression . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Instructions du module Cartes . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.3 SØquence d’instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.1 Expressions numØriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Conditions, expressions et instructions conditionnelles 21
2.1 Le probl?me . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Expressions boolØennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 BoolØens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.2 Expressions simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.3 Expressions composØes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.4 PropriØtØs des opØrateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 En Caml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 BoolØens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.2 Expressions boolØennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.3 Attention! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.4 Remarque sur les opØrateurs && et || . . . . . . . . . . . . . . . . . . . . 26
2.4 Expressions conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Instructions conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.1 Remarque sur le parenthØsage . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6 MØthodologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
116 TABLE DES MATI¨RES
3 Instructions conditionnellement rØpØtØes 33
3.1 Un probl?me . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Sortie d’une boucle tant que . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4 La boucle tant que en Caml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5 MØthodologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Constantes, variables 37
4.1 Types de donnØes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.1 Les boolØens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.2 Les nombres entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.3 Les nombres ottants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.4 Types dØ nis par le module Cartes . . . . . . . . . . . . . . . . . . . . . 38
4.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.1 Notion de variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.2 DØclaration simple de variables . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.3 Identi cateurs de variables . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.4 Environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.5 valuation d’une expression . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.6 Masquage d’une variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.7 DØclaration simultanØe de variables . . . . . . . . . . . . . . . . . . . . . . 41
4.2.8 Variables locales une expression . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.9 Remarque sur la forme let . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3 Variables mutables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 DØclaration d’une variable mutable . . . . . . . . . . . . . . . . . . . . . . 44
4.3.3 RØfØrence la valeur d’une variable mutable . . . . . . . . . . . . . . . . 45
4.3.4 A ectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 A cher des donnØes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5 Le programme solution du probl?me 4.3.1 . . . . . . . . . . . . . . . . . . . . . . 48
4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5 La boucle pour 51
5.1 La boucle Pour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2 La boucle Pour en Caml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2.1 Syntaxe de la boucle pour . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2.2 Remarque sur l’indice de boucle . . . . . . . . . . . . . . . . . . . . . . . 53
5.2.3 Boucle pour indice dØcroissant . . . . . . . . . . . . . . . . . . . . . . . 53
5.3 Suites rØcurrentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.1 Calcul du terme d’indice n . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.2 Calcul et a chage des termes d’indice 0 n . . . . . . . . . . . . . . . . . 54
5.3.3 Calcul du premier terme satisfaisant une condition . . . . . . . . . . . . . 55
5.3.4 Autres suites rØcurrentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
TABLE DES MATI¨RES 117
6 Les fonctions 61
6.1 Les fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.1 SpØci cation d’une fonction . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.2 DØclaration d’une fonction en Caml . . . . . . . . . . . . . . . . . . . . . 62
6.1.3 Variables locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.1.4 Fonctions plusieurs param?tres . . . . . . . . . . . . . . . . . . . . . . . 64
6.1.5 Fonctions sans param?tre . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.1.6 IntØrŒt des fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2 ProcØdures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2.1 SpØci cation d’une procØdure . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2.2 DØclaration d’une procØdure en Caml . . . . . . . . . . . . . . . . . . . . 67
6.2.3 Appel une procØdure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.2.4 IntØrŒt des procØdures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.2.5 MØthodologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.3.1 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.3.2 ProcØdures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7 Caract?res et cha nes de caract?res 73
7.1 Les caract?res . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.1.1 DØ nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.1.2 Fonctions int_of_char et char_of_int . . . . . . . . . . . . . . . . . . . 74
7.1.3 Comparaison de caract?res . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2 Les cha nes de caract?res . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2.1 DØ nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2.2 Notation indicielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.2.3 ConcatØnation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.2.4 Comparaison de cha nes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7.3 Quelques fonctions prØdØ nies sur les cha nes . . . . . . . . . . . . . . . . . . . . 78
7.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
A Les cartes 83
A.1 PrØsentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
A.2 Utilisation du module Cartes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
A.3 Le langage du module Cartes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
A.3.1 Description de tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
A.3.2 Action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
A.3.3 Tests sur les tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
A.3.4 Comparaison des valeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
A.3.5 Contr le de l’a chage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
A.3.6 RØparer l’automate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
A.3.7 Obtenir de l’aide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
A.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
A.4.1 Descriptions de tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
A.4.2 SØquence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
A.4.3 Conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
A.4.4 ItØration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
A.4.5 Fonctions et procØdures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
118 TABLE DES MATI¨RES
B Le module Camlgraph 97
B.1 PrØsentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
B.2 Module Camlgraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
B.2.1 Gestion des fenŒtres graphiques . . . . . . . . . . . . . . . . . . . . . . . . 98
B.2.2 Gestion des couleurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
B.2.3 Point et dessin de lignes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
B.2.4 Texte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
B.2.5 Remplissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
C lØments du langage ØtudiØs dans ce cours 103
C.1 Syntaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
C.1.1 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
C.1.2 Expressions et instructions . . . . . . . . . . . . . . . . . . . . . . . . . . 103
C.1.3 Expressions conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . 103
C.1.4 Instructions conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . 104
C.1.5 Instructions conditionnellement rØpØtØes . . . . . . . . . . . . . . . . . . . 104
C.1.6 Constantes, variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
C.1.7 La boucle pour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
C.1.8 Les fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
C.1.9 Caract?res et cha nes de caract?res . . . . . . . . . . . . . . . . . . . . . . 105
C.2 Mots-clØs du langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
C.3 Fonctions prØdØ nies du langage . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
C.3.1 Fonctions de conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
C.3.2 Impressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
C.3.3 Du module String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
C.4 Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
D Messages d’erreurs de l’interpr?te du langage 107
(version du 12 septembre 2013.)
(coßt approximatif du poly : 3,50 euros)
[1] . en rØalitØ, il existe deux modes compilØs : une compilation en code-octet qui doit ensuite Œtre interprØtØ par une machine virtuelle : et une compilation en code natif pour une architecture donnØe.
[2] . Les Øtudiants qui poursuivront leurs Øtudes en informatique dØcouvriront dans un cours de 3?me annØe consacrØ la programmation fonctionnelle les avantages des fonctions curry Øes.
[3] . Il existe aussi un excellent ouvrage d’introduction : DØveloppement d’applications avec Objective Caml (cf [EC00])
[4] . En Caml, les directives ne sont pas proprement parler des expressions ou instructions. Ce sont plut t des commandes qui modi ent le comportement de l’interpr?te. Les directives dØbutent toutes par le symbole di?se.
3. Cette notion de typage sera abordØe petit petit dans ce cours et les suivants.
. Ces nombres correspondent approximativement aux nombres dØcimaux.
[7] . Cette dØ nition n’est pas tout fait exacte, mais nous nous en contenterons pour le cours de ce semestre. Nous verrons dans le cours qui suit qu’il existe des instructions dont la valeur est d’un autre type.
. Ce dialogue suppose aussi que le module Cartes soit prØalablement chargØ.
[9] . Par parenthØser, il faut entendre le fait de placer une expression entre un symbole d’ouverture et un symbole de fermeture, symboles qui peuvent Œtre e ectivement une parenth?se ouvrante (() et une parenth?se fermante ()), ou tout autre couple de symboles convenus comme { et }, ou bien [ et ], ou bien encore begin et end.
. du nom du mathØmaticien anglais du XIX?me si?cle George Boole.
[11] . Le nom complet de ces types est en fait Cartes.couleur et Cartes.numero_tas. Dans le texte du poly nous n’employons que la notation raccourcie.
. Ce n’est pas le cas dans tous les langages de programmation, comme par exemple C ou Pascal
. Cette fonction est prØdØ nie dans l’unitØ math et se nomme floor.
. ASCII = American Standard Code for Information Interchange
[15] . init_tas est une fonction dont le rØsultat est l’unique valeur du type unit, c’est ce qu’on appelera une procØdure. Le param?tre de la procØdure init_tas, est un ØlØment du produit cartØsien de l’ensemble des entiers par l’ensemble des cha nes int?string?unit.
. dont le type est int?int?unit.
3. dont le type est .
. dont le type est int?couleur.
. dont le type est int?unit.
. Ces trois procØdures sont de type unit?unit
. dont le type est unit?float
. dont le type est float?unit
. dont le type est string?unit