Algorithmique Programmation - L1 Université de Poitiers

Chapitre 6 : Variables mutables, Affectation, Bloc d’instructions,

Entrées-sorties
Objectifs :
— Comprendre la notion de variable mutable,
— comprendre la notion d’affectation,
— savoir faire des entrées-sorties.

1 Éléments de cours
Les notions présentées dans ce cours, en particulier les notions de variables et d’affectation,
prendront leur intérêt à partir du chapitre suivant. Il s’agit donc pour l’instant de pratiquer afin
de comprendre ces notions ; l’utilisation de ces notions sera abordée un peu plus tard.

1.1 Variables mutables et affectation

Nous avons vu qu’une variable non mutable correspond à une valeur. En OCaml, c’est l’as-
sociation d’un nom et d’une valeur d’un certain type. Par exemple, let x : int = 3 définit la
variable de nom x, de type int et de valeur 3.
Une variable mutable est une variable dont la valeur peut changer au cours du temps. In-
tuitivement, c’est un contenant (pensez à un tiroir, un sac, etc), qui contient quelque chose à
un instant donné. Cette image a ses limites, car, pour éviter de nombreuses erreurs de pro-
grammation, la plupart des langages imposent des restrictions sur la manière de se servir de ces
"contenants".
En Ocaml :
— le mot-clé correspondant à cette notion de "contenant" est ref,
— différents types de "contenants" sont distingués, suivant le type de ce qu’ils peuvent
contenir. Par exemple, int ref est le type des "contenants pouvant contenir des entiers" ;
— une valeur d’un tel type s’écrit ref suivi de la valeur contenue. Par exemple, ref 8 est
un contenant de type int ref, qui contient la valeur 8 : l’interpréteur OCaml ne nous dit
pas autre chose :
# ref 8 ;;
- : int ref = {contents = 8}

Une variable mutable est déclarée en OCaml de la même manière qu’une variable non mu-
table, par exemple :
# let x : int ref = ref 8 ;;
val x : int ref = {contents = 8}

Le nom de la variable est x, son type est int ref, sa valeur est "un contenant qui contient
8". Le contenu d’une variable mutable x est désigné par !x :
# !x ;;
- : int = 8

Ce contenu peut être utilisé dans n’importe quelle expression compatible avec son type, par
exemple :
# 3 + !x ;;
- : int = 11

1
 NB. Attention aux risques de confusion : il arrive souvent que le terme "valeur d’une
variable mutable" désigne en fait la valeur contenue dans cette variable. Il faut donc être attentif
à bien identifier de quoi on parle réellement.

L’opération permettant de modifier la valeur d’une variable mutable est l’affectation, dont
le symbole est := ; par exemple, la suite ci-dessous contient une affectation :
# x ;;
- : int ref = {contents = 8}
# !x ;;
- : int = 8
# x := 15 ;;
- : unit = ()
# x ;;
- : int ref = {contents = 15}
# !x ;;
- : int = 15
On note que la réponse de l’interpréteur, lors de l’affectation de la valeur 15 à la variable x, est :
- : unit = ()
Ceci signifie qu’une affectation n’est pas une expression qui a une valeur en soi : en fait, elle
change la valeur d’une variable mutable, mais elle n’a pas de valeur qui lui est propre, contrai-
rement par exemple à l’expression :
# !x + 3;;
- : int = 18

Une expression qui n’a pas de valeur en soi est une instruction ; en OCaml, son type est unit
et sa valeur est ().
NB. Il est possible de définir des variables mutables de n’importe quel type : dans ce cours,
nous nous restreindrons dans un premier temps aux types de base.

1.2 Bloc d’instructions

Un bloc d’instructions est une suite d’instructions séparées par des virgules, qui se termine
par une expression de type quelconque (qui peut dont être ou non une instruction). Par exemple,
supposons que l’on dispose de deux variables mutables min et max, de type int ref, qui vont
servir à stocker respectivement le minimum et le maximum de deux variables non mutables p
etq :
# if p < q
then
(
min := p ;
max := q
)
else
(
min := q ;
max := p
)
;;
- : unit = ()

Voici un autre exemple de bloc, qui permet d’échanger le contenu de deux variables mutables
y et z, de type int ref :
# let x : int = !y in
(

2
 y := !z;
z := x
)
;;
- : unit = ()

Comme dit précédemment, en toute généralité, un bloc peut éventuellement se terminer par
une expression.
Dans tous les cas, la valeur de la dernière expression définit la valeur du bloc. Dans les
exemples ci-dessus, comme la dernière expression est de type unit, la valeur du bloc est () (voir
aussi l’exemple de saisie contrôlée dans la section consacrée aux entrées-sorties).

Convention d’écriture.
Un bloc est délimité par des parenthèses ouvrantes et fermantes. Afin d’alléger l’écriture, si
le bloc ne contient qu’une instruction, les parenthèses sont omises.
Les instructions d’un bloc sont séparées par un point-virgule, comme par exemple :
(
min := p ;
max := q
)

1.3 Les entrées-sorties

Il est parfois utile d’afficher des valeurs au cours de l’exécution d’une fonction, ou de saisir
des valeurs au clavier. Le langage OCaml fournit des fonctions d’affichage prédéfinies, listées dans
le tableau suivant :
Signature affichage à l’écran
print_int : int-> unit affiche un entier à l’écran
print_char : char->unit affiche un caractère à l’écran
print_float : float->unit affiche un flottant à l’écran
print_string : string->unit affiche une chaine de caractères à l’écran
print_newline : unit->unit affiche un saut de ligne à l’écran

Le langage OCaml fournit aussi les fonctions de saisie listées dans le tableau suivant :
Signature lecture au clavier
read_line : unit -> string lit une chaîne de caractères
read_int : unit -> int lit un entier
read_float : unit -> float lit un flottant

Par exemple, la fonction ci-dessous a pour objectif de saisir une valeur entière positive au
clavier. Si la valeur saisie n’est pas positive, elle échoue.
let read_positive_int() : int =
let c : int ref = ref 0 in
(
c := read_int() ;
if !c < 0
then failwith("erreur read_positive_int : valeur saisie < 0")
else !c
)
;;

Voici deux exemples d’exécution de la fonction :

3
# read_positive_int();;
-9
Exception: Failure "erreur read_positive_int : valeur saisie < 0 ".

# read_positive_int();;
8
- : int = 8

La fonction read_char : unit -> char est fournie dans les fonctions utilitaires du fichier
"AP1util.ml" : ce n’est pas une fonction prédéfinie en OCaml.

2 Exercices de TP
Exercice 1
Saisissez ce qui suit, et expliquez ce qui se passe en suivant les (évolutions de) valeurs des
différentes variables.
let a : int ref = ref 8 ;;
let b : int = 5 ;;
let c : int ref = ref 2 ;;
a ;;
b ;;
c ;;
!a ;;
!b ;;

!c ;;
!a + b ;;
a ;;
b ;;
a := !a + b ;;
a ;;
b ;;
b := !a + b ;;

a ;;
b ;;
a := b * !c ;;
a ;;
b ;;
c ;;
c := 3 + !a + 20 ;;
a ;;
c ;;
c := 3 + a + 20 ;;

!a ;;
!c ;;
En particulier, d’où viennent les erreurs détectées par l’interpréteur ?

Exercice 2
Saisissez ce qui suit, et expliquez ce qui se passe en suivant les (évolutions de) valeurs des
différentes variables.
let a : int ref = ref 8 ;;

4
let b : int ref = a ;;

let c : int ref = ref 8 ;;

a ;;
b ;;
c ;;
!a ;;
!b ;;
!c ;;
b := !a + 1 ;;
a ;;
b ;;
c ;;
Pourquoi les valeurs contenues dans a et b sont elles modifiées, et non celle contenue dans c ?
Continuez à saisir et à exécuter les expressions suivantes :
c := !a + 20 ;;
!a ;;
!b ;;
!c ;;
Pourquoi la valeur contenue dans c est elle modifiée, et non celles contenues dans a et b ?
Saisissez la fonction ci-dessous :
let inc(px : int ref) : unit =
px := !px + 1
;;
Expérimentez la :
let x : int ref = ref 3 ;;
inc(x) ;;
x ;;
let y : int = 3 ;;
inc(y) ;;

y ;;
inc(3);;

Exercice 3
Écrivez une fonction shift_left qui, étant données trois variables mutables x, y et z de type
int ref, effectue un décalage vers la gauche de ces trois variables. Par exemple, si !x = 3, !y
= 7 et !z = 11, les valeurs des trois variables à la fin de l’exécution de la fonction seront !x =
7, !y = 11 et !z = 3.
NB. le type du résultat de la fonction est unit : en effet, la fonction ne calcule pas de résultat à
proprement parler, elle se contente de modifier le contenu de variables mutables.

Écrivez une fonction shift_right qui, étant données trois variables mutables x, y et z de
type int ref, effectue un décalage vers la droite de ces trois variables.

Exercice 4
Saisissez la suite d’instructions suivantes :

(
print_string("Quel est votre nom : ");
let nom : string = read_line() in

5
 (
print_newline() ;
print_string("Bonjour ") ;
print_string(nom);
print_string(",");
print_newline();
print_string("J’espère que vous passez une bonne journée.");
print_newline()
)
)
;;

Que fait elle ? Expérimentez-la à plusieurs reprises en saisissant différents noms.

Exercice 5
Écrivez une fonction récursive print_list(m : int list) : unit qui affiche chaque élément
d’une liste d’entiers suivi par trois tirets. Testez votre fonction et vérifiez l’affichage produit sur
plusieurs exemples.
Créez un fichier test_print.ml contenant la déclaration de plusieurs listes d’entiers, la fonc-
tion print_list, ainsi que les appels de cette fonction sur les listes préalablement déclarées.
Exécutez le contenu du fichier avec la commande #use "test_print.ml" ;;.

Exercice 6
Écrivez, dans un fichier star_line.ml, une fonction qui permet d’afficher une ligne composée
de k caractères * à l’écran (avec k >=1). Exécutez le contenu du fichier avec la commande #use
"star_line.ml" ;;.
Créez un deuxième fichier get_print_name_age.ml, qui contient la ou les fonctions néces-
saires pour demander à l’utilisateur de saisir son prénom et son âge, et qui les affiche à l’écran,
entourés de caractères *. Testez votre code, en utilisant la commande #use. Par exemple, si le
prénom et l’âge saisis sont Éric et 19, le programme affiche :

************
* Éric, 19 *
************
NB. la fonction String.length : string -> int retourne la longueur de la chaîne de caractères
passée en paramètre.

6
 Chapitre 7 : Itérativité
Objectifs :
— savoir manipuler les boucles for,
— savoir manipuler les boucles while.

3 Résumé de cours
De même que les fonctions récursives, les instructions itératives, appelées aussi boucles, per-
mettent de décrire des enchaînements de calculs : cf. section 4 pour une courte discussion sur ces
deux mécanismes.
Ces instructions nécessitent la plupart du temps de manipuler des variables mutables (cf.
chapitre 6), qui vont stocker, au fur et à mesure des calculs, les résultats intermédiaires.
Sont étudiées dans ce chapitre deux instructions itératives : la boucle for et la boucle while
du langage OCaml, dont des variantes se retrouvent dans la plupart des langages de progammation.
Ces instructions permettent de décrire des séquences de calculs :
— pour une boucle for, le nombre de calculs effectués est fixé au départ ;
— pour une boucle while, le nombre de calculs n’est pas connu au départ ; la poursuite ou
l’arrêt des calculs est contrôlé par une expression booléenne.

3.1 Boucle for

Une instruction for permet de décrire une suite de calculs de longueur donnée : par exemple,
la fonction suivante calcule la somme des n premiers entiers positifs.
let sum_n_int(n : int) : int =
let s : int ref = ref 0 in
(
for i = 1 to n
do s := !s + i
done ;
!s
)
;;

Supposons qu’on appelle la fonction : sum_n_int(10) ;;

Elle s’exécutera de la manière suivante :
— la fonction utilise une variable mutable s pour stocker, à chaque étape de calcul, la valeur
courante de la somme :
— initialement, cette variable contient la valeur 0 ; pour rappel, la déclaration let s : int
ref = ref 0 définit une variable mutable pouvant contenir un entier (le type est int
ref), et qui contient la valeur 0 (c’est ce que dit l’écriture ref 0) ;
— l’instruction for décrit une séquence de n calculs (ici, n = 10) ; chaque calcul consiste
à augmenter la valeur stockée dans la variable s de la valeur de l’indice i. Cet indice,
déclaré par : i = 1 to n
prend successivement l’ensemble des valeurs indiquées, c’est-à-dire 1, puis 2, etc. jusqu’à
prendre la valeur n, donc ici 10 ;
— une fois l’instruction for exécutée, c’est-à-dire après n exécutions de l’instruction :
s := !s + i
l’expression !s donne le résultat de la fonction : comme s contient la somme des n = 10
premiers entiers (ici, la valeur 55), la fonction donne le résultat attendu ;
— il faut remarquer que si on appelle la fonction avec une valeur du paramètre nulle (n =
0), son résultat vaut 0, car l’instruction for n’est pas exécutée.

7
 Plus généralement, une instruction for s’écrit de la manière suivante :
for nom_indice = valeur_depart to valeur_arrivee
do
bloc_d_instructions
done ;

L’instruction for n’est exécutée que si la valeur entière valeur_depart est inférieure ou
égale à la valeur entière valeur_arrivee ; dans ce cas, l’instruction ou la suite d’instructions
bloc_d_instructions est exécutée pour toutes les valeurs entières successives croissantes com-
prises entre ces deux valeurs extrêmes. Il est à noter que l’indice nom_indice :
— est déclaré par la partie de l’instruction for :
nom_indice = valeur_depart to valeur_arrivee,
— n’est connu et utilisable que dans cette boucle for.
On peut noter aussi que l’intervalle d’itération est fixé, et ne peut être changé en cours
d’exécution.
Il existe aussi la variante suivante :
for nom_indice = valeur_depart downto valeur_arrivee
do
bloc_d_instructions
done ;

L’instruction for n’est alors exécutée que si la valeur entière valeur_depart est supérieure
ou égale à la valeur entière valeur_arrivee ; dans ce cas, l’instruction ou la suite d’instructions
bloc_d_instructions est exécutée pour toutes les valeurs entières successives décroissantes com-
prises entre ces deux valeurs extrêmes.

3.2 Boucle while

Une instruction while permet de décrire une suite de calculs, qui sont effectués tant qu’une
certaine condition, décrite par une expression booléenne, est vraie : par exemple, la fonction
suivante calcule le nombre et la somme des premiers entiers positifs qu’il faut sommer pour que
la valeur de la somme dépasse une certaine valeur :

let sum_int_inf_n(n : int) : int * int =

let s : int ref = ref 0 and i : int ref = ref 0 in
(
while !s < n
do
i := !i + 1 ;
s := !s + !i
done ;
(!i, !s)
)
;;

Supposons qu’on appelle la fonction : sum_int_inf_n(12) ;;

Elle s’exécutera de la manière suivante :
— la fonction utilise deux variables mutables i et s pour stocker, à chaque étape de calcul,
l’indice et la valeur courante de la somme :
— initialement, ces deux variables contiennent toutes deux la valeur 0 ;
— l’idée est la suivante : l’instruction while décrit une séquence de calculs ; chaque calcul
consiste à augmenter de 1 la valeur stockée dans la variable i, et à augmenter la valeur
stockée dans la variable s de la nouvelle valeur !i. Dit autrement, les valeurs successives
stockées dans i sont les valeurs des premiers entiers positifs, les valeurs successives stockées

8
 dans s sont les sommes correspondantes des premiers entiers positifs. Le calcul est effectué
tant que l’expression conditionnelle !s < n est vraie.
— en pratique : initialement, !s = 0, et 0 < 12, donc une première itération est effectuée,
à la fin de laquelle !i vaut 1 et !s vaut 1. Afin de savoir s’il faut effectuer une deuxième
itération, l’expression !s < n est évaluée : comme elle vaut true, cette deuxième itération
est effectuée, à la fin de laquelle !i vaut 2, !s vaut 3. Afin de savoir s’il faut effectuer une
troisième itération, l’expression !s < n est évaluée (elle vaut true), etc. Ceci va continuer
jusqu’à la cinquième itération, à la fin de laquelle on a : !i vaut 5, !s vaut 15. Comme
l’expression !s < n vaut false, il n’y aura pas de sixième itération.
— il faut remarquer que si on appelle la fonction avec une valeur du paramètre nulle (n =
0), le résultat de la fonction est (0, 0), car l’instruction while n’est pas exécutée.
Plus généralement, une instruction while s’écrit de la manière suivante :
while expression_conditionnelle
do
bloc_d_instructions
done ;

Le bloc_d_instructions de l’instruction while n’est exécuté que si la valeur de l’expression_booleenne

est true, et tant que sa valeur est true.
Un autre exemple d’utilisation est la saisie contrôlée, par exemple d’une lettre minuscule.
let read_lower_case() : char =
let c : char ref = ref ’1’ and the_end : bool ref = ref false in
(
while not(!the_end)
do
print_string("Veuillez saisir une lettre minuscule, svp : ") ;
c := read_char() ;
the_end := (!c >= ’a’ && !c <= ’z’)
done ;
!c
)
;;
Cette fonction utilise la fonction read_char qui n’est pas une fonction OCaml prédéfinie.
Cette fonction est disponible dans le fichier AP1util.ml.
On peut noter aussi que la première valeur contenue dans la variable c n’est pas utilisée, c’est
pourquoi n’importe quelle valeur peut être donnée (ici, ’1’) sans que cela change quoi que ce
soit à l’exécution de la fonction.

4 Récursivité vs Itérativité
La récursivité et l’itérativité sont deux mécanismes permettant de décrire et d’effectuer des
enchaînements de calculs. Si les intérêts respectifs de ces deux mécanismes ne sont pas toujours
très évidents sur des exemples simples, on constate souvent que, quand les problèmes traités
deviennent complexes :
— il est souvent plus facile de concevoir en utilisant la récursivité ;
— l’exécution peut être plus efficace en utilisant l’itérativité.
Ce ne sont bien sûr que des remarques générales, qui ne sont pas toujours vraies dans des cas
particuliers.
Plus précisément, la traduction d’une fonction itérative en fonction récursive est directe : cf.
exemple en annexe. En revanche, la traduction d’une fonction récursive en fonction itérative n’est
pas directe en général. Néanmoins, il existe une méthode bien connue de traduction du récursif
vers l’itératif : elle ne sera pas vue durant cet enseignement, mais ultérieurement.

9
5 Conventions d’écriture
Nous avons vu au chapitre 6 qu’un bloc d’instructions est délimité par des parenthèses ; nous
faisons une exception à cette règle dans le cas des boucles for et while, car les mots-clés do et
done jouent le rôle de parenthèses : il est donc inutile d’ajouter des parenthèses pour délimiter
le bloc d’instructions d’une boucle : c’est d’ailleurs ce qui a été fait dans les exemples ci-dessus.

6 Annexe
Considérons à nouveau la fonction sum_int_inf_n.
let sum_int_inf_n(n : int) : int * int =
let s : int ref = ref 0 and i : int ref = ref 0 in
(
while !s < n
do
i := !i + 1 ;
s := !s + !i
done ;
(!i, !s)
)
;;

Sa traduction en fonction récursive est directe ; elle se fait via l’écriture d’une fonction prin-
cipale, qui appelle une fonction récursive :
let rec sum_int_inf_n_rec_aux(n, i, s : int * int * int) : int * int =
if s >= n
then (i, s)
else
let i_suiv : int = i + 1 in
let s_suiv : int = s + i_suiv in
sum_int_inf_n_rec_aux(n, i_suiv, s_suiv)
;;

let sum_int_inf_n_rec(n : int) : int * int =

sum_int_inf_n_rec_aux(n, 0, 0)
;;

La fonction principale sum_int_inf_n_rec a le même paramètre que la fonction itérative

sum_int_inf_n, et donne le même résultat. Son rôle est simplement d’initialiser le calcul, c’est-
à-dire d’appeler la fonction récursive sum_int_inf_n_rec_aux avec le paramètre n ET les valeurs
initiales du nombre et de la somme, qui sont 0 et 0.
Les paramètres de la fonction récursive sum_int_inf_n_rec_aux sont la borne n, et les valeurs
courantes du nombre et de la somme. Si on est à la fin du calcul (notez que l’expression s
>= n dans la version récursive est l’inverse de l’expression s < n dans la version itérative), le
résultat est le couple de valeurs courantes, sinon les valeurs suivantes sont calculées et le calcul
se poursuit avec ces nouvelles valeurs. Le principe de l’exécution est donc strictement le même
dans les versions récursive et itérative.
On remarque aussi qu’il est nécessaire d’utiliser des variables mutables dans la version ité-
rative, alors que ce n’est pas le cas pour la version récursive, qui ne manipule que des variables
non mutables.

10
7 Exercices de TD
Exercice 7
Exécutez la fonction mystere1 ci-dessous pour les valeurs -2, 1, 5 ; expliquez ce qu’elle calcule
et comment elle le fait.
let mystere1(n : int) : int =
if n < 0
then failwith "erreur"
else
if n = 0 || n = 1
then 1
else
let x : int ref = ref 1 and y : int ref = ref 1 and a : int ref = ref 0 in
(
for i = 2 to n
do
a := !y ;
y := !x + !y ;
x := !a
done ;
!y
)
;;

Exercice 8
Que fait la fonction ci-dessous ? NB. La fonction rand_int(a, b), présente dans le fichier
AP1util.ml, a pour résultat une valeur entière choisie aléatoirement entre a et b inclus.
let mystere2() : unit =
let valeur : int = rand_int(0, 200) in
let fin : bool ref = ref false and v : int ref = ref 0 in
while not(!fin)
do
print_string("entrez une valeur entiere : ") ;
v := read_int();
if !v < valeur
then print_string("too low")
else
if !v > valeur
then print_string("too high")
else
(
print_string("correct");
fin := true
);
print_newline()
done ;
;;

Exercice 9
On considère une stalactite. On estime qu’elle gagne en moyenne 0,5 cm par siècle, et on souhaite
simuler la croissance de cette stalactite. Pour cela, on considère que la croissance peut varier
aléatoirement d’un siècle à l’autre (en fonction par exemple de la pluviométrie) ; la variation
de taille de la stalagtite est en fait comprise entre 80% et 120% de la taille moyenne gagnée
par siècle. En pratique, la précision de la variation est de deux chiffres après la virgule (NB. la

11
fonction rand_int(a, b), présente dans le fichier AP1util.ml, a pour résultat une valeur entière
choisie aléatoirement entre a et b inclus).
On donne la taille initiale, comprise entre 10 et 50 cm, et on effectue la simulation : la taille
est calculée tous les siècles et elle est affichée tous les 10 siècles seulement. Le calcul s’arrête
quand la stalactite a doublé sa taille initiale.
Le résultat de la fonction est composé du nombre de siècles qui ont été nécessaires au dou-
blement de sa taille, et de la taille atteinte.

Exercice 10
L’objectif de cet exercice d’estimer la valeur du nombre π en utilisant la méthode de Monte-Carlo.
L’idée est la suivante : on génère aléatoirement des points p = (x, y), où x et y appartiennent à
l’intervalle [−n, n[. Cet espace 2D correspond donc à un carré d’aire 4n2 .

Considérons à présent le cercle de rayon n, centré en (0, 0). Parmi les points générés, certains
sont à l’intérieur du cercle, d’autres à l’extérieur. Plus précisément, un point p = (x, y) est à
l’intérieur du cercle si x2 + y 2 ≤ n2 . Notons aussi que le cercle a une aire de π ∗ n2 .

Le ratio entre l’aire du cercle et l’aire du carré est donc de π/4. Autrement dit, un point choisi
aléatoirement dans le carré a une probabilité de π/4 de se trouver dans le cercle. En choisissant
un nombre suffisamment grand de points aléatoires (disons 100000), on peut donc estimer la
valeur de π en calculant le ratio du nombre de points situés à l’intérieur du cercle par rapport
au nombre de points total.
1. La fonction rand_int(a, b) permet d’obtenir une valeur comprise entre a et b. Utilisez
cette fonction afin de créer une fonction generate_point permettant d’obtenir un point
aléatoire dans un carré de longueur 2n, centré en 0, 0 (i.e. x et y appartiennent à [−n, n[).
2. Définissez la fonction is_inside_circle permettant de savoir si un point (x, y) est à situé
à l’intérieur d’un cercle de rayon donné, centré en (0, 0).
3. Définissez la fonction compute_pi qui calcule une approximation de la valeur de π à partir
de n et du nombre de points aléatoires que l’on souhaite générer.

Exercice 11
L’objectif de cet exercice est d’écrire une fonction itérative guess_number : unit -> int qui
"devine" un nombre nb compris entre 1 et 200, choisi par l’utilisateur. Le programme procède de
la manière suivante : il propose un nombre aléatoire compris entre la borne inférieure (initialement
1) et la borne supérieure (initialement 200). Pour chaque proposition, l’utilisateur indique si nb
est inférieur, supérieur, ou bien égal à celui proposé par le programme : les réponses se feront
en saisissant un caractère (’<’, ’>’ ou ’=’). À chaque itération, la borne inférieure ou la borne
supérieure sera mise à jour, réduisant ainsi l’intervalle des possibilités.
Écrivez une fonction get_answer() : char, qui effectue une saisie contrôlée de la réponse
de l’utilisateur.
Écrivez la fonction guess_number en supposant que l’utilisateur joue correctement, c’est-
à-dire qu’il choisit bien un nombre compris entre 1 et 200, et qu’il répond honnêtement aux
propositions faites par le programme.
Dans un second temps, modifiez votre fonction en tenant compte du fait que l’utilisateur
choisit bien un nombre compris entre 1 et 200, mais qu’il pourrait mentir en répondant aux
propositions du programme : dans ce cas, le programme ne peut pas trouver la réponse, mais il
doit détecter la tricherie.
Que faudrait changer, si l’on suppose que l’utilisateur triche sur tous les aspects de son rôle,
c’est-à-dire si, de plus, il n’est même pas sûr qu’il choisisse un nombre compris entre 1 et 200 ?
Modifiez votre code pour faire une recherche dichotomique, qui est plus efficace en général
que la recherche aléatoire. Elle consiste à choisir systématiquement, pour la proposition faite à
l’utiliisateur, la valeur médiane de l’intervalle des possibilités restantes.

12
8 Exercices de TP
Exercice 12
Écrivez une fonction fact : int -> int, qui calcule itérativement la factorielle d’un entier
positif donné n ; si la valeur fournie n est négative, la fonction doit engendrer une erreur.

Exercice 13

Un code est un triplet de caractères vérifiant :

— le second caractère est un chiffre ;
— le premier et le troisième caractères sont des lettres, dans lesquelles il y a une minuscule
et une majuscule.
Écrivez les fonctions suivantes :
1. une fonction get_letter : unit -> char qui saisit une lettre minuscule ou majuscule ;
2. une fonction get_char : char * char -> char qui saisit un caractère compris entre les
deux caractères donnés en paramètre de la fonction (inclus) ;
3. une fonction get_code : unit -> char * char * char, qui saisit un code.
Pour ces fonctions, vous vous servirez de la fonction read_char (qui lit un caractère au
clavier) que vous pouvez utiliser via la commande #use "AP1util.ml" ;;

Exercice 14
Écrivez une fonction qui affiche les lettres minuscules selon l’ordre alphabétique (les lettres sont
séparées par un espace), puis qui affiche sur la ligne suivante les lettres majuscules selon l’ordre
lexicographique inverse (les lettres sont aussi séparées par un espace).

Exercice 15
Ecrivez une fonction qui, étant donné un entier strictement positif n, affiche la table de multi-
plication de n.
Ecrivez une autre fonction qui, étant donné un entier strictement positif p, affiche les tables
de multiplication des entiers de 1 à p (si p = 10, vous aurez la quatrième de couverture de vos
cahiers du primaire...).
Écrivez une fonction qui a pour résultat un entier strictement positif saisi par l’utilisateur.
Enfin, écrivez une fonction qui demande à l’utilisateur de saisir un entier strictement positif,
et qui affiche toutes les tables de multiplication pour les entiers compris entre 1 et l’entier saisi.

Exercice 16
L’exercice 15 du chapitre 4 portait sur la vérification de la conjecture Syracuse. Écrivez une
fonction itérative permettant de tester cette conjecture.

Exercice 17
Écrivez une fonction qui affiche les 100 premiers entiers strictement positifs qui sont multiples
de 3.
Ecrivez une autre fonction qui affiche tous les multiples de 3 inférieurs strictement à 100.

9 Exercices à faire en autonomie

Exercice 18
Écrivez une fonction qui permet à un utilisateur de saisir les notes d’une classe. L’utilisateur ne

13
connaît pas le nombre de notes à l’avance, la fonction s’arrêtera lorsque la note saisie vaut -1.
Les valeurs qui ne sont pas comprises entre 0 et 20 ne seront pas prises en compte. La fonction
se termine en affichant le nombre de notes valides, ainsi que la meilleure note, la moins bonne
note, et la moyenne, et elle a pour résultat ces quatre valeurs.

Exercice 19
Simulation de production d’une exploitation laitière. On considère qu’une vache laitière produit
20 litres de lait par jour à 10 % près (i.e. la production varie dans l’intervalle [20 - 10%, 20 +
10%]).
Lorsqu’une vache allaite son veau, ce qui se produit avec une probabilité de un douzième,
seule la moitié de son lait peut être traité, le reste est bu par le veau.
Par ailleurs, chaque jour, un contrôle sanitaire est effectué, et on estime à 0,12 la probabilité
(pour chaque vache) que le lait trait soit impropre à la consommation.
On utilise le type structuré t_cow = {prod : float ; milk : float ; us : float} afin
de représenter la production d’une vache (volume total, volume obtenu par traite, volume utili-
sable).
Écrivez une fonction qui simule la production journalière de lait d’une vache. Le résultat est
de type t_cow, c’est-à-dire qu’il est composé du volume de lait total des n vaches, du volume de
lait obtenu par traite, et du volume de lait exploitable.
Ecrivez une fonction qui, à partir du nombre de vaches d’une exploitation laitière, simule la
production journalière de ces vaches (le résultat est de type t_cow).
Écrivez une fonction qui simule le fonctionnement d’une exploitation de n vaches sur une
durée de 30 jours. Le résultat est de type t_cow (il contient le volume de lait total des vaches,
la production laitière (i.e. le volume obtenu par traite sur l’ensemble du troupeau), et le volume
de lait exploitable obtenu au cours de ces 30 jours).
Une fromagerie située à proximité de l’exploitation utilise le lait pour fabriquer des reblochons.
Il faut 4 litres de lait pour fabriquer un reblochon de 500g.
Écrivez une fonction qui permet à l’utilisateur de saisir le nombre de fromages qu’il veut
fabriquer, et qui détermine par simulation le temps mis pour récolter le volume requis de lait
pour un nombre donné n de vaches.

Exercice 20
Ocaml possède une petite librairie graphique, dont quelques éléments sont expliqués à la fin de
cette feuille.
On reprend la fonction de calcul de π de l’exercice 4. Modifiez la de manière à afficher le
carré, le cercle et chaque point généré. Choisissez des couleurs différentes selon que le point est
à l’intérieur ou à l’extérieur du cercle.

Exercice 21
Écrivez la fonction draw_sin(n : int) : unit qui calcule de manière itérative n+1 valeurs
également réparties entre 0.0 et 2.0 *. pi (où pi est une variable non mutable à définir, qui
correspond à la valeur π), et, pour chacune de ces valeurs, calcule aussi la valeur sin(x). Il faut
noter que pour l’instant, la fonction ne fait rien de ces points qui sont calculés itérativement.
OCaml possède une petite librairie graphique, dont quelques éléments sont décrits à la fin de
cette feuille. Modifiez maintenant votre fonction draw_sin(n : int) : unit, de manière à ce
qu’elle affiche une approximation de la courbe de la fonction sin(x) entre 0.0 et 2.0 *. pi en
n segments.

Librairie graphique OCaml

OCaml possède une petite librairie graphique, que l’on utilisera via les fonctions décrites ci-
dessous. Pour les utiliser, il faut télécharger le fichier AP1utilbis.ml sur Updago, le mettre dans
votre répertoire de travail, et exécutez la commande #use "AP1utilbis.ml". Ce fichier contient

14
toutes les fonctions du fichier AP1util.ml ainsi que ce qui est nécessaire pour les applications
graphiques.
On peut ouvrir une fenêtre d’affichage avec l’instruction :
open_graph(dx, dy);;
où dx et dy sont deux entiers donnant la taille horizontale et la taille verticale de la fenêtre
(en nombre de pixels). Par exemple, open_graph(1000, 600);; ouvre une fenêtre de taille 1000
(horizontal) par 600 (vertical).
Implicitement, l’origine de la fenêtre est en bas à gauche, et correspond au pixel de coordon-
nées (0, 0). L’autre pixel extrême de la fenêtre a pour coordonnées (dx - 1, dy - 1) (dans
notre exemple, (999, 599)).
L’instruction close_graph();; ferme la fenêtre d’affichage.
L’instruction clear_graph() permet d’effacer la fenêtre d’affichage.
Il existe implicitement un "curseur", qui est positionné à un certain endroit de la fenêtre.
L’instruction moveto(x, y) ;;, où x et y sont deux entiers, positionne le curseur au pixel de
coordonnées (x, y).
L’instruction lineto(x, y);; trace un trait depuis la position courante du curseur jusqu’à
la position (x, y).
Exécutez par exemple la suite d’instructions suivantes :
moveto(100, 100);;
lineto(200, 200);;
lineto(200, 100);;
lineto(300, 100);;
qui trace trois segments, dont un vertical et un horizontal.
Vous pouvez utiliser les couleurs prédéfinies : black, blue, red, green, white, yellow, cyan,
magenta.
La fonction set_color(color) change la couleur courante, qui prend la valeur color (par
défaut, la valeur de la couleur est black).
Pour afficher un point de coordonnées (x,y), vous pouvez utiliser la fonction plot(x,y), ou
la fonction draw_rect(x, y, 2, 2), qui trace un petit rectangle dont le coin inférieur gauche
est au point de coordonnées (x, y) et qui a une longueur et une largeur de 2 pixels.
La fonction draw_rect(x, y, dx, dy : int * int * int * int) : unit trace un rec-
tangle dont les deux points extrêmes sont les points (x, y) et (x + dx, y + dy).
Pour tracer un cercle de centre (x, y) et de rayon r, vous pouvez utiliser la fonction
draw_circle(x, y, r).

15
 Chapitre 8 : Tableaux
Objectifs :
— comprendre les tableaux,
— savoir manipuler les tableaux.

10 Résumé de cours
Schématiquement, un tableau permet de représenter une suite de valeurs de même type, par
exemple :
# [| 3 ; 9 ; 10 ; 2 |] ;;
- : int array = [|3; 9; 10; 2|]
L’interpréteur ocaml a reconnu un tableau d’entiers : le type est int array.
Le contenu d’un tableau s’écrit entre les symboles [| et |].
Une variable se déclare de la manière usuelle :
# let v : int array = [|4 ; 10 ; 3 ; 2 ; 7 |] ;;
val v : int array = [|4; 10; 3; 2; 7|]

Attention : contrairement aux listes, les variables de type tableau sont des variables mu-
tables, dans le sens où il est possible de modifier le contenu du tableau (cf. ci-dessous).

La valeur contenue dans la k eme "case" (ou élément) du tableau t s’écrit t.(k), par exemple
pour le tableau v déclaré précédemment :
# v.(0) ;;
- : int = 4
# v.(1) ;;
- : int = 10
# v.(2) ;;
- : int = 3
# v.(3) ;;
- : int = 2
# v.(4) ;;
- : int = 7
# v.(5) ;;
Exception: Invalid_argument "index out of bounds".

Les cases du tableau v sont donc indicées de 0 à 4. De manière générale, les cases d’un tableau
t sont indicées de 0 à n-1, où n est le nombre de cases du tableau t. On voit sur l’exemple ci-dessus
qu’un indice non compris dans cet intervalle engendre une erreur.
Comme un tableau est mutable, il est possible de modifier les valeurs qu’il contient, par
exemple :
# v ;;
- : int array = [|4; 10; 3; 2; 7|]
# v.(2) <- 15 ;;
- : unit = ()
# v ;;
- : int array = [|4; 10; 15; 2; 7|]

Pour les cases d’un tableau, on utilise donc le symbole d’affectation <- et non le symbole
usuel de l’affectation :=.

16
 La fonction arr_len, appliquée à un tableau, a pour résultat le nombre d’éléments de ce
tableau :
# arr_len(v) ;;
- : int = 5

La fonction arr_make(n, x) : int * ’a -> ’a array a pour résultat un tableau de n

cases, chacune contenant la valeur x. Ces deux fonctions sont contenues dans le fichier AP1util.ml,
disponible sur Updago.

Les instructions itératives sont souvent utilisées pour la manipulation de tableaux : voici par
exemple deux fonctions, l’une calculant la somme des valeurs contenues dans un tableau d’entiers,
l’autre recherchant l’indice de la première valeur négative contenue dans un tableau (si elle existe).

# let sum_int_array(t : int array) : int =

let n : int = arr_len(t) - 1
and s : int ref = ref 0
in
(
for i = 0 to n
do s := !s + t.(i)
done ;
!s
)
;;
val sum_int_array : int array -> int = <fun>
# v ;;
- : int array = [|4; 10; 15; 2; 7|]
# sum_int_array(v);;
- : int = 38

(* la fonction ci-dessous retourne un entier et un booléen : si le booléen vaut false,

il n’y a pas d’entier négatif contenu dans le tableau, et la valeur de l’entier est
égale au nombre d’éléments du tableau ; sinon, l’entier a pour valeur l’indice de
la première valeur négative contenue dans le tableau *)
# let find_neg_val_int_array(t : int array) : int * bool =
let n : int = arr_len(t) - 1 and i : int ref = ref (-1)
and found : bool ref = ref false and the_end : bool ref = ref false
in
(
while not(!the_end)
do
i := !i + 1 ;
if !i > n
then the_end := true
else
(
found := (t.(!i) < 0) ;
the_end := !found
)
done ;
(!i, !found)
)
;;

17
val find_neg_val_int_array : int array -> int * bool = <fun>
# v ;;
- : int array = [|4; 10; 15; 2; 7|]
# find_neg_val_int_array(v);;
- : int * bool = (5, false)
# let w : int array = [| 3 ; 2 ; -5 ; 0 ; 7 ; -4 |] ;;
val w : int array = [|3; 2; -5; 0; 7; -4|]
# find_neg_val_int_array(w) ;;
- : int * bool = (2, true)

Remarque. Les variables de type "liste" sont des variables non mutables ; les variables de
type "tableau" sont des variables mutables.

11 Exercices de TD
Exercice 22
Que calcule la fonction suivante :
let mystery_1(n : int) : int array =
if n < 0
then failwith "erreur mystery_1 : parametre negatif"
else
let v : int array = arr_make(n + 1, 1) in
(
for i = 1 to n
do v.(i) <- v.(i-1) * i
done ;
v
)
;;
Quels sont les résultats des expressions mystery_1(-1), mystery_1(0), mystery_1(1), mystery_1(2),
mystery_1(5), mystery_1(-15) ?

Exercice 23
Que font les fonctions ci-dessous ? Expliquez précisément ce que fait la fonction mystery_2 en
particulier.
let entry_cont(a, b : int * int) : int =
let the_end : bool ref = ref false and c : int ref = ref 0 in
(
while not(!the_end)
do
c := read_int() ;
if (a <= !c && !c <= b)
then the_end := true
else (print_string("valeur non valide") ; print_newline())
done ;
!c
)
;;

let entry(i : int) : int * int * int =

let c1 : int ref = ref 0 and c2 : int ref = ref 0 and c3 : int ref = ref 0 in
(
print_string("valeur CC1 etudiant ") ; print_int(i) ; print_newline() ;

18
 c1 := entry_cont(0, 20) ;
print_string("valeur CC2 etudiant ") ; print_int(i) ; print_newline() ;
c2 := entry_cont(0, 20) ;
print_string("valeur CC3 etudiant ") ; print_int(i) ; print_newline() ;
c3 := entry_cont(0, 20) ;
(!c1, !c2, !c3)
)
;;

let mystery_2(n : int) : (int * int * int) array =

let v : (int * int * int) array = arr_make(n, (0, 0, 0)) and imax : int = n-1 in
(
for i = 0 to imax
do v.(i) <- entry(i)
done ;
v
)
;;

Exercice 24
Des joueurs jouent à la roulette, leur nombre est nbPlayers. Chaque joueur dispose d’une somme
d’argent ; initialement, cette somme est la même pour tous les joueurs : 1000 euros. L’ensemble des
sommes disponibles à un instant donné est représenté par un tableau fortune, où fortune.(j)
est la somme dont dispose le joueur de numéro j.
1) Écrivez une fonction init dont le résultat est le tableau fortune contenant les sommes
dont disposent les joueurs à l’instant initial.

A chaque tour de jeu, chaque joueur mise une certaine somme sur un certain numéro : la
somme misée est strictement positive, mais elle est inférieure ou égale à la somme dont dispose
le joueur à ce moment ; le numéro choisi est compris entre 0 et 36. Les tableaux number et bet
contiennent respectivement les numéros choisis par les joueurs et les mises des joueurs à ce tour
de jeu.
2) Écrivez une fonction get_int(a, b : int * int) : int qui permet de saisir une va-
leur entière comprise entre les valeurs de a et de b. Écrivez deux fonctions choice_number et
choice_bet permettant de saisir les numéros et les mises choisis par les joueurs (on peut bien
sûr utiliser des fonctions intermédiaires, les saisies devant être contrôlées).

Le tableau total doit contenir, pour chaque numéro possible de la roulette, la somme totale
misée par les joueurs sur ce numéro ; la variable totalBet doit contenir la valeur totale des mises
des joueurs.
3) Ecrivez une fonction compute_bet_per_number permettant de calculer les valeurs conte-
nues par ces variables.

La répartition des mises entre les joueurs se fait de la manière suivante (il n’y a pas de
banque !). On utilise un tableau gain pour stocker les gains et les pertes des joueurs pour ce tour
de jeu. Si le joueur j a joué sur le numéro n, et que ce numéro est gagnant, le gain du joueur j
est : gain.(j) <- (totalBet * bet.(j)) / total.(j). Si le joueur j n’a pas joué le numéro
n, sa perte est égale à sa mise. Si aucun joueur n’a joué le numéro n, les sommes misées sont
conservées et seront partagées entre les gagnants lors du tour de jeu suivant.
4) Écrivez une fonction qui calcule le tableau gain pour ce tour de jeu.
5) Écrivez une fonction qui simule un nombre de tours de jeu donné.

Exercice 25

19
On considère le type t_date défini par : type t_date = {d : int ; m : int ; y : int} ;;,
et le type t_member, défini par : type t_member = {name : string ; birth : t_date} ;;. Le
tableau t de type t_member array contient les noms et les dates de naissance des 20 membres
d’un club sportif.
1) Écrivez une fonction permettant de remplacer le j eme membre du club par un nouveau
membre dont on connaît le nom et la date de naissance.
2) Écrivez une fonction qui compare deux dates, et qui indique si la première date est anté-
rieure à la deuxième date.
3) Écrivez une fonction permettant de trouver le nom et la date de naissance du joueur le
plus jeune. Même question pour le joueur le plus âgé.

12 Exercices de TP
Exercice 26
Vous disposez des deux fonctions
get_float(v_min, v_max : float * float) : float
et get_intpos() : int,
qui permettent de saisir une valeur de type float comprise entre deux valeurs données v_min et
v_max, et de saisir un entier positif n (cf. fichier AP1saisie5.ml sur Updago, et annexe en fin de
document).
1) Écrivez une fonction permettant de saisir et de stocker n valeurs flottantes comprises entre
deux valeurs données v_min et v_max.
2) Écrivez une fonction dont le résultat est la somme, la moyenne, la valeur minimale et la valeur
maximale des n valeurs de type float stockées dans un tableau donné.
3) Écrivez une fonction permettant de saisir un entier positif n, puis de saisir et de stocker n
valeurs de type float comprises entre deux valeurs données v_min et v_max, et dont le résultat
est constitué de ces valeurs, de la somme et de la moyenne de ces valeurs, ainsi que de la valeur
minimale et de la valeur maximale.

Exercice 27
Écrire une fonction mirror qui, appliquée à un tableau t, produit un tableau contenant les
valeurs contenues dans t, mais en ordre inverse. Par exemple, le résultat de mirror([|20; 19;
9; 7; 4|]) est [|4; 7; 9; 19; 20|].

Exercice 28
On cherche à savoir si une valeur v est présente dans un tableau t. Écrivez une fonction, qui
retourne un booléen indiquant si v est présente dans t. Modifiez votre fonction afin qu’elle
retourne en plus un entier correspondant à l’indice de la première case contenant la valeur v, si
elle existe.

Exercice 29
On effectue des lancés successifs avec un dé à 20 faces. On arrête les lancés lorsque l’on obtient la
valeur 20 pour la première fois. On souhaite alors connaître le nombre de lancés effectués, ainsi
que, pour chaque valeur 1, 2, etc, 20, le nombre de fois où l’on a obtenu cette valeur. Écrire une
fonction permettant de réaliser cela. Pour simuler le dé, la fonction rand_int peut être utilisée.

13 Exercices supplémentaires
Exercice 30
Écrivez une fonction shift_left(t : int array) : unit qui fait un décalage "circulaire" d’un

20
tableau vers la gauche, c’est-à-dire par exemple que si t = [|4; 7; 9; 19; 20|] avant appli-
cation de la fonction, t = [|7; 9; 19 ; 20 ; 4|] après application de la fonction. Écrivez une
fonction shift_right qui effectue un décalage circulaire vers la droite.

Exercice 31
On s’intéresse à la variation de la fonction sin sur l’intervalle [−π, π]. Écrivez une fonction
qui, étant donnée une valeur entière strictement positive n, calcule la suite de n+1 points (x,
sin(x)), où les valeurs de x sont régulièrement espacées sur l’intervalle [−π, π].

Exercice 32
Un club de vente s’est formé, afin "d’offrir" à ses membres la possibilité d’acheter certains produits
à des prix préférentiels. Le club a décidé de limiter le nombre de ses membres à 100 (et comme
c’est un club recherché, ce nombre est atteint en permanence), et de proposer exactement 1000
produits à ses membres.
Chaque produit a un nom, une catégorie (Jouet, Parfumerie, Vetement, Livre, Audio-Visuel),
un nombre d’exemplaires en stock, un prix. Chaque membre a un prénom, un nom, une date de
naissance, un solde (indiquant le montant dont il dispose pour acheter des produits).
1) Définissez les types et données nécessaires pour représenter les informations dont le club
a besoin.
2) Écrivez une fonction permettant de savoir si un produit de nom name peut être fourni par
le club, et si oui, qui fournit de plus l’indice du produit dans le tableau de produits.
3) Écrivez une fonction permettant d’ajouter n exemplaires du produit de nom name au stock
du club.
4) Écrivez une fonction permettant de modifier d’un certain taux les prix de tous les articles.
5) Écrivez une fonction permettant de réaliser l’achat par le client de nom c_name de n
exemplaires du produit de nom p_name. Bien sûr, l’achat ne pouvant avoir lieu que si le client
dispose de la somme nécessaire, le résultat de la fonction contiendra en particulier un booléen
indiquant que l’achat a pu être réalisé.

14 Annexe
(* saisie controle d’un float dans l’intervalle [v_min, v_max] *)
let get_float(v_min, v_max : float * float) : float =
let v : float ref = ref 0.0 and thend : bool ref = ref false in
(
while not( !thend)
do
print_string("saisissez une valeur comprise entre ") ;
print_float(v_min) ;
print_string(" et ") ;
print_float(v_max) ;
print_string(" : ") ;
v := read_float() ;
thend := ( !v >= v_min && !v <= v_max)
done ;
!v
)
;;
(* saisie d’un entier positif *)
let get_intpos() : int =
let v : int ref = ref 0 and thend : bool ref = ref false in
(

21
 while not( !thend)
do
print_string("saisissez une valeur entiere positive : ") ;
v := read_int() ;
thend := ( !v >= 0)
done ;
!v
)
;;

22