TP 1

In [ ]:
#use "/opt/camllight.ml"

L'ensemble des int n'est pas $\mathbf{N}$

Question 1

Écrire la fonction Caml fact n qui donne la factorielle de l'entier naturel n.

In [ ]:
(** fact : int -> int
    Factorielle d'un entier naturel
*)
let rec fact (n : int) : int =
  (* À COMPLÉTER *)
;;

fact 6

Question 2

Utiliser fact pour écrire la fonction comb1 n p qui donne le nombre de combinaisons $n \choose p$.

In [ ]:
(** comb1 : int -> int -> int
    `comb1 n p` est le nombre de combinaisons
    de `p` parmi `n`
*)
let comb1 (n :int) (p : int) : int =
  (* À COMPLÉTER *)
;;

comb1 12 6

Question 3

Calculer $22 \choose 1$ et expliquer le résultat obtenu.

In [ ]:

Question 4

Écrire une version comb2 qui utilise la relation de Pascal

$${n \choose p} = {n-1\choose p-1} + {n-1\choose p}.$$
In [ ]:
(** comb2 : int -> int -> int
    comb2 n p est le nombre de combinaisons
    de p parmi n
*)
let rec comb2 (n : int) (p : int) : int = 
  (* À COMPLÉTER *)
;;

Question 5

Calculer $6\choose 3$, $20\choose 10$, $30\choose 15$ et $40\choose 20$. Commenter.

In [ ]:

Question 6

Écrire une troisième version comb3 qui utilise la relation

$${n\choose p} = \frac{n}{p}{n-1\choose p-1}.$$
In [ ]:
(** comb3 : int -> int -> int
    comb3 n p est le nombre de combinaisons
    de p parmi n
*)
(* À COMPLÉTER *)

comb3 6 3 ;;

comb3 40 20 ;;

Question 7

Quel est le plus grand entier $n$ pour lequel comb3 (2 * n) n retourne une valeur correcte ?

In [ ]:

Question 8

Écrire une version de comb3 qui lève une exception avec le message "Dépassement de capacité" lorsque le calcul sur 64 bits ne permet pas de fournir une valeur correcte.

In [ ]:

Écriture d'un nombre en base seize

En informatique, la représentation des entiers en base seize, qui est une puissance de deux, est plus pratique qu'en base dix. On complète alors les dix chiffres de 0 à 9 par les six chiffres supplémentaires A, B, C, D, E et F. Ainsi, l'écriture 32C représente l'entier $3\times 16^2 + 2\times 16^1 + 12\times 16^0=812$.

Les entiers non signés codés sur un octet sont compris entre 00 et FF.

Le passage de l'écriture en base seize à l'écriture en base deux est très simple. Par exemple l'entier 2F en base seize s'écrit 00101111 en base deux car 2 s'écrit 0010 et F s'écrit 1111.

La fonction int_of_char qui convertit une valeur de type char (c'est-à-dire un octet) en sa valeur entière (entre 0 et 255).

In [ ]:
int_of_char 'A' ;;

int_of_char '3' ;;
Out[ ]:
- : int = 65
Out[ ]:
- : int = 51

La fonction char_of_int est la fonction réciproque :

In [ ]:
char_of_int 65 ;;

char_of_int 51 ;;
Out[ ]:
- : char = 'A'
Out[ ]:
- : char = '3'

Question 9

Définir la fonction digit_of_int n qui retourne le chiffre qui représente l'entier n en base 16.

  • Servez-vous des fonctions ci-dessus en utilisant le fait que les caractères '0' à '9' sont contigus dans la table ASCII et qu'il en est de même des lettres majuscules.

  • L'appel à la fonction invalid_arg msg permet d'interrompre immédiatement l'exécution en affichant le message d'erreur msg. La fonction invalid_arg est à utiliser lorsque l'argument passé à digit_of_int est invalide.

In [ ]:
(** Retourne le chiffre qui représente l'entier n en base 16.
*)
let digit_of_int (n : int) : char =
  (* À COMPLÉTER *)
;;

digit_of_int 6 ;;

digit_of_int 15 ;;

digit_of_int 16 ;;

Question 10

Écrire une seconde version de la fonction digit_of_int qui utilise la chaîne de caractères "0123456789ABCDEF".

In [ ]:

Question 11

Définir la fonction hexa_of_int n qui retourne la chaîne de caractères qui représente l'entier n en base 16.

Exprimez pour cela hexa_of_int n en fonction de hexa_of_int (n / 16) et de n mod 16.

Vous aurez besoin de concaténer un caractère à une chaîne de caractères. L'opérateur ^ permet de concaténer deux chaînes de caractères. Pour utiliser cet opérateur vous devrez donc au préalable convertir le caractère en une chaîne réduite à ce seul caractère. Ceci peut être fait avec la fonction make_string n car qui retourne une chaîne de n caractères car.

In [ ]:
(** Retourne la chaîne de caractères qui représente
    l'entier n en base 16.
*)
let rec hexa_of_int (n : int) : string =
  (* À COMPLÉTER *)
;;
 
hexa_of_int 44

Question 12

Définir la fonction int_of_digit digit qui retourne la valeur du chiffre hexadécimal digit.

In [ ]:
(** Retourne la valeur du chiffre hexadécimal `digit`
*)
let int_of_digit (digit : char) : int =
  (* À COMPLÉTER *)
;;

int_of_digit 'B' ;;

int_of_digit '7' ;;

int_of_digit 'G' ;;

Question 13

Définir la fonction int_of_hexa digits qui retourne la valeur des chiffres hexadécimaux digits.

La fonction sub_string s start len qui retourne une chaîne de longueur len constituée des caractères de s allant des indices start à start + len - 1.

In [ ]:
(** Retourne la valeur des chiffres hexadécimaux `digits`.
*)
let rec int_of_hexa (digits : string) : int =
  (* À COMPLÉTER *)
;;

int_of_hexa "32C"

Question 14

Définir la fonction hexa_of_frac p q n qui retourne le développement en base 16 de la fraction p / q sous la forme d'une chaîne de caractères.

Pour cela, vous pouvez définir une sous-fonction digits r n qui donne les n premiers chiffres après la virgule de r / q, où r est strictement inférieur q. Il faudra alors définir digits r n en fonction de digits s (n - 1) pour un certain entier s à déterminer.

In [ ]:

Points et droites du plan

Question 15

Un point du plan peut être représenté par son abscisse et son ordonnée. Une droite du plan peut être représentée :

  • par son abscisse si la droite est verticale,
  • ou sinon par son coefficient directeur et son ordonnée à l'origine.

Définir les types point et droite.

In [ ]:

Question 16

Définir la fonction appartient p d qui indique si le point p appartient à la droite d.

In [ ]:
let appartient (p : point) (d : droite) : bool =
  (* À COMPLÉTER *)
;;

appartient {x=2.; y=6.} (Verticale 2.) ;;

appartient {x=2.; y=6.} (Affine (2., 1.)) ;;

appartient {x=2.; y=5.} (Affine (2., 1.)) ;;

Question 17

Définir la fonction parallele d1 d2 qui indique si les droites d1 et d2 sont parallèles.

In [ ]:
let parallele (d1 : droite) (d2 : droite) : bool =
  (* À COMPLÉTER *)
;;

parallele (Affine (2., 1.)) (Affine (2., 3.)) ;;

parallele (Affine (2., 1.)) (Affine (5., 1.)) ;;

parallele (Verticale 7.1) (Affine (2., 3.)) ;;

parallele (Verticale 7.1) (Verticale 2.) ;;

Question 18

Définir la fonction creer_droite p1 p2 qui retourne la droite qui passe par les deux points p1 et p2.

In [ ]:
let creer_droite (p1 : point) (p2 : point) : droite =
  (* À COMPLÉTER *)
;;

creer_droite {x = 2.; y = 5.} {x = 4.; y = 11.} ;;

creer_droite {x = 2.; y = 5.} {x = 2.; y = 11.} ;;

Question 19

Définir la fonction intersect d1 d2 qui retourne le point d'intersection des droites d1 et d2.

In [ ]:
let intersect (d1 : droite) (d2 : droite) : point =
  (* À COMPLÉTER *)
;;

intersect (Affine (2., 1.))  (Affine (-3., 2.)) ;;