Université Paris 6 Licence d'informatique	Module de Programmation Année 1999-2000

Travaux dirigés n° 1

Exercice 1

Évaluez les expressions ci-dessous. On supposera qu'à chaque question correspond une nouvelle session camllight interactive.

1.

4 < 3;;
"debut " ^ "fin";;
4.0 * 6;;
string_of_int 34;;
4.0 >= 45.6;;
4.0 >= 45;;

let x = false;;
let y = (x = true);;
let z = if x = true then false else true;;
let nb1 = 4 and nb2 = nb1;;

let x = 3;;
let x = false;;
let x = x + 2;;

let a = 3 and b = 1;;
let f x = a * x + b;;
f 1;;
let a = 0 and b = 0;;
f 1;;

let y = 1;;
let y = 3 and z = y;;

Exercice 2

À quoi sert la fonction inconnue décrite ci-dessous :

let inconnue a b epsilon f =
   let rec autre_inconnue a b =
      let c = (a +. b) /. 2. in
         if b -. a <=. epsilon then c 
         else if f(a) *. f(c) <=. 0. then autre_inconnue a c
              else autre_inconnue c b
   in
      if (f(a) *. f(b) >. 0.) or (epsilon <=. 0.) then print_string "erreur"
      else print_string ("resultat = " ^ (string_of_float (autre_inconnue a b)));;

Exercice 3

La fonction suivante prend un nombre entier en argument. Elle renvoie une exception si ce nombre n'est pas strictement positif, et un booléen indiquant si le nombre en question est un nombre premier sinon.

let premier x = 
   if x <= 0 then failwith "ce nombre n'est pas strictement positif"
   else
      let rec iter  nb = (x = nb) or ((x mod nb <> 0) && (iter (nb+1)))
      in iter 2;;

Lorsque l'on exécute cette fonction, iter peut être appelée sucessivement avec nb = 2, puis nb = 3, nb = 4, et ainsi de suite jusqu'à nb = x. Or c'est totalement inefficace car il suffit d'exécuter iter jusqu'à ëxû pour obtenir le même résultat, tous les autres appels à iter étant superflus. Modifiez la fonction premier de telle sorte que iter soit appelée pour nb variant de 2 à au plus y = ëxû. Vous ferez en sorte que le calcul de y ne soit réalisé qu'une seule fois.

Remarque: La modification ci-dessus améliore sensiblement la rapidité de l'algorithme. Néanmoins, celui-ci reste très inefficace lorsque x est grand et il existe des algorithmes bien plus performants pour calculer si un nombre est premier ou pas.

Exercice 4

Écrivez une fonction prenant en argument deux nombres entiers strictement positifs x et y, et renvoyant le PGCD de ces deux nombres. Pour calculer le PGCD, on utilisera les règles suivantes :

si x = y alors PGCD(x,y) = x ;
si x > y alors PGCD(x,y) = PGCD(x-y,y) ;
si y > x alors PGCD(x,y) = PGCD(x,y-x).

Exercice 5

On cherche à trouver le plus grand entier camllight. Cet entier correspond au nombre x > 0 tel que x + 1 < 0. Pour le trouver, vous réaliserez une fonction calc_2 qui prend en argument un entier n positif ou nul et qui renvoie le plus grand entier p, qui est une puissance de 2 telle que p + n ³ 0 et 2*p + n < 0 (il se peut que le p en question soit égal à 0). En remarquant que tout nombre x entier positif, y compris le nombre que l'on recherche, peut se décomposer comme une somme de puissances de 2 :

x =

i ³ 0

e_i 2ⁱ, où e_i Î {0,1},

vous en déduirez une fonction calc_max, prenant en argument un unit et renvoyant l'entier le plus grand de camllight.

Exercice 6

On veut créer une fonction générant, pour un entier k > 0, la suite de k lignes suivantes :

ligne 1	:	1
ligne 2	:	1 1
ligne 3	:	2 1
ligne 4	:	1 2 1 1
ligne 5	:	1 1 1 2 2 1
ligne 6	:	3 1 2 2 1 1

En fait, on obtient la ligne k en lisant ce qui est écrit sur la ligne k-1. Par exemple, la ligne 5 s'obtient en lisant la ligne 4 : sur cette dernière on voit 1 « 1 », 1 « 2 » et 2 « 1 ».

Écrivez une fonction calc_prefixe qui prend en argument une chaîne de caractères str ayant la forme des lignes mentionnées ci-dessus, et qui renvoie 0 si str est vide, ou le nombre de chiffres identiques au début de la chaîne str. Par exemple calc_prefixe "1 1 1 2 2 1 " renvoie la valeur 3 car la chaîne de caractères commence par trois « 1 ».
Écrivez une fonction genere_ligne qui prend en argument une chaîne de caractères correspondant à l'une des lignes décrites ci-dessus, et qui renvoie la ligne suivante. Pour simplifier, on supposera qu'après chaque nombre, il y a un espace. On admettra en outre que tous les nombres affichés sont compris entre 1 et 9.
Écrivez une fonction genere qui prend en argument un entier k > 0, et qui renvoie une chaî ne de caractères contenant les k premières lignes de la suite. La chaîne de caractères permettant d'aller à la ligne suivante est « \n ».
Écrivez une fonction ecrit_suite qui prend en argument un entier k > 0, et qui affiche la chaîne de caractères contenant les k premières lignes de la suite. La fonction permettant d'afficher une chaîne de caractères s'appelle print_string.

Exercice 7(QUELQUES PIÈGES À LA SAUCE CAML)

Évaluez les expressions ci-dessous. On supposera qu'à chaque question correspond une nouvelle session camllight interactive.
Remarque : Les expressions ci-dessous sont ignobles et vous ne devriez jamais écrire de codes aussi immondes. Néanmoins, ces expressions peuvent être utiles pour « bien » comprendre camllight, ou tout simplement pour maintenir du code mal écrit par quelqu'un d'autre.
1.

let x = 4 < 3;;
let x = x = true;;

let g x y = x + y;;
g 4 g 5 6;;
sub_string "abcdef" 0 3 ^ "gh";;

let x = 4;;
let f = let x = 3 in
   function x -> x + 2;;
f 2;;

let x = 4 and f x = 4 * x in
   let x = 2 and y = f x in
      x + y;;

Ce document a été traduit de L^AT_EX par H^EV^EA.