TP 2 : Corrigé

MPSI {831, 832}
Lycée Masséna
TP 2 : Corrigé
1
Quelques exos en vrac
Exercice 1. Écrire une fonction qui renvoie le « symétrique » d’un entier. Par exemple, le symétrique de 123 est 321.
Corrigé. Dans l’idée, on part d’un nombre m entier positif. On considère a initialement à 0. A chaque étape, on
effectue la division euclidienne de m par 10, en réaffectant le quotient à m, tout en stockant le reste. Dans le même
temps, on multiplie a par 10 et on rajoute le reste.
let symetrique n=
let a=ref 0 and m=ref n in
while !m<>0 do
let q, r = !m/10, !m mod 10 in
m:=q ;
a:=10* !a + r
done ;
!a
;;
Exercice 2. Écrire deux fonctions pgcd a b et ppccm a b prenant deux entiers positifs non tous deux nuls et retournant... ce qu’elles doivent retourner.
Corrigé. On applique l’algorithme d’Euclide, basé sur l’identité :
a
si b est nul.
PGCD(a, b) =
PGCD(b, a mod b)
sinon.
let pgcd a b=
let c=ref a and d=ref b in
while !d <> 0 do
let u= !c mod !d in
c:= !d ;
d:= u
done ;
!c
;;
Pour la fonction PPCM, on utilise simplement la relation classique ab = PGCD(a, b) × PPCM(a, b). Notez qu’ici on
n’a pas besoin d’introduire de références ou même de variables intermédiaires.
let ppcm a b=
a*b / (pgcd a b)
;;
Svartz
Page 1/3
2014/2015
MPSI {831, 832}
Lycée Massena
√
Exercice 3. Écrire une fonction racine x epsilon qui retourne x avec une précision de ε, en utilisant l’algorithme
suivant, appelé algorithme de Babylone :

 u0 = 1
1
x
un +
 un+1 =
2
un
x < ε. Cette fonction aura pour type float -> float -> float = <fun>. On pourra
qui s’arrête lorsque un −
un utiliser la fonction abs_float.
Corrigé. On suit simplement l’énoncé.
let racine x eps=
let u=ref 1. in
let v=ref (!u -. x/. !u) in
while abs_float (!v) >= eps do
u:=0.5*.(!u +. x/. !u) ;
v:=(!u -. x/. !u)
done ;
!u
;;
2
Exercices sur les tableaux
Exercice 4. Écrire une fonction inverse t prenant en entrée un tableau t et produisant un nouveau tableau dont
les éléments sont dans l’ordre inverse.
Corrigé. La taille d’un tableau (vecteur) en Caml se fixe à la création et n’est plus modifiable ensuite, on ne peut
pas, contrairement à Python, partir d’un tableau (list Python) vide qu’on remplit peu à peu. On pourrait partir d’un
tableau vide, et utiliser la concaténation de tableaux mais cette solution est gourmande en complexité (quadratique).
Il y a plusieurs solutions possibles, la plus simple est peut-être de réaliser une copie du tableau d’entrée, et de le
parcourir pour modifier chaque entrée.
let inverse t=
let u=copy_vect t and n=vect_length t in
for i=0 to n-1 do
u.(i)<-t.(n-1-i)
done ;
u
;;
En fait, on peut partir de n’importe quel tableau, du moment qu’il ait le même type que t, par exemple un tableau
contenant n fois l’élément t.(0), obtenu avec u=make_vect n t.(0), où n est la longueur du tableau t.
Exercice 5. Même question avec une fonction qui modifie le tableau passé en entrée, c’est-à-dire une fonction de type
'a vect -> unit = <fun>.
Corrigé. La solution la plus simple est certainement d’utiliser la fonction précédente :
let inverse_en_place t=
let n=vect_length t and u=inverse t in
for i=0 to n-1 do
t.(i) <- u.(i)
done
;;
Svartz
Page 2/3
2014/2015
MPSI {831, 832}
Lycée Massena
On peut aussi, sans utiliser de tableau intermédiaire, modifier le tableau t en place, en faisant des échanges.
Attention à ne parcourir que la moitié du tableau, sinon on ne change rien ! La solution ci-dessous utilise la fonction
echange de l’exercice suivant.
let inverse_en_place_2 t=
let n=vect_length t in
for i=0 to (n-1)/2 do
echange t i (n-1-i)
done
;;
3
Quelques algorithmes de tris
Exercice 6. Écrire une fonction echange t i j prenant en entrée un tableau et deux indices i et j, qui échange les
éléments en positions i et j de t. Elle doit avoir le type 'a vect -> int -> int -> unit. Cette fonction va nous
être utile dans les exercices suivants.
Corrigé. On utilise une variable intermédaire pour réaliser l’échange. Pas besoin de créer une référence ici !
let echange t i j=
let a=t.(i) in
t.(i) <- t.(j) ;
t.(j) <- a
;;
Svartz
Page 3/3
2014/2015

Download Report