TP3

Tous les documents du cours sont autorisés. Vous avez, bien évidemment, le droit de consulter la documentation OCaml. Néanmoins, ce TP étant à faire seul-e, il est naturellement interdit d'aller sur les réseaux sociaux ou de poser des questions sur des sites d'entraide tels que developpez.com ou stackoverflow.com.

Ce TP noté évalue vos connaissances et votre compréhension d'OCaml. N'hésitez pas à demander à votre encadrant de vous aider en cas d'erreur de syntaxe, certaines sont dues à de l'inattention et ne méritent pas de rester bloqué-e dessus. En revanche, les erreurs de type sont de votre entière responsabilité.

Ce sujet est long pour deux heures, on ne s'attend pas à ce que vous finissiez tout (si vous y arrivez, bravo !), donc faites ce que vous pouvez et faites-le bien.

Le TP est à rendre à la fin de la séance. Chaque exercice précise le nom du fichier .ml à rendre, veuillez nommer vos fichiers en conséquence. Vous mettrez vos fichiers sources (donc uniquement les .ml) dans un répertoire nom_prenom dans une archive au format tgz de la forme nom_prenom.tgz

Vous enverrez cette archive à votre chargé de TP. Les adresses mails sont les suivantes :

Triangles

Nom du fichier à rendre : triangle.ml

  1. Définissez un type enregistrement point comportant deux champs x et y de type int
  2. Définissez une fonction new_point de type int->int->point qui prend deux entiers en arguments et renvoie un nouveau point
  3. Définissez un type enregistrement triangle comportant trois champs a, b et c de type point
  4. Définissez une fonction new_triangle de type point -> point -> point -> triangle qui permet de construire un nouveau triangle à partir de trois points
  5. Définissez une fonction vect de type point -> point -> point qui renvoie les coordonnées du vecteur défini par les deux points passés en argument
  6. Définissez une fonction sprod de type point -> point -> int qui renvoie le produit scalaire de des deux vecteurs passés en argument
  7. Définissez une fonction dist de type point -> point -> float qui renvoie la distance entre les deux points passés en argument
  8. Définissez une fonction cosangle de type point -> point -> point -> float qui renvoie le cosinus de l’angle défini par la succession des trois points passé en argument. On rappelle à cet effet que le produit scalaire entre deux vecteurs OA et OB (orientés dans ce sens) est égal à |OA|.|OB|.cos(angle(AOB))
  9. On rappelle que:

    On rappelle également que le cosinus d’un angle est nul pour un angle droit, strictement positif pour un angle aigu, strictement négatif pour un angle obtus.

  10. Définissez la fonction is_degenerate de type triangle -> bool qui détermine si le triangle passé en argument est dégénéré
  11. Définissez les fonctions is_rectangle, is_acutangle, is_obtusangle, toutes de type triangle -> bool qui déterminent si le triangle passé en argument est respectivement rectangle, acutangle, obtusangle
  12. Définissez un type typed_triangle comportant quatre constructeurs Rectangle, Acutangle, Obtusangle, et Degenerate prenant chacun un triangle en argument.
  13. Définissez une fonction to_typed_triangle de type triangle -> typed_triangle qui renvoie la version typée du triangle passé en argument.
  14. Définissez une fonction descr_triangle de type typed_triangle -> unit qui utilise Printf pour renvoyer sur la sortie standard une description du triangle donnant les coordonnées de ses trois sommets et son type
  15. On rappelle que deux triangles sont dits semblables si les côtés de l’un sont proportionnels à ceux de l’autre, ce qui est équivalent pour le cas non-dégénéré à avoir les mêmes angles (pas forcément dans le même ordre).

  16. Définissez une fonction semblable de type triangle -> triangle -> bool qui détermine si les deux triangles passés en arguments sont semblables s'ils sont tous deux non-dégénérés, et renvoie faux sinon.

Nombre premier

Nom du fichier à rendre: premier.ml

On veut écrire un programme qui détermine si un entier fourni par l'utilisateur est premier.

Pour cela, on utilise la méthode naïve qui vient directement de la définition : un nombre premier est un nombre strictement supérieur à 1 qui a exactement deux diviseurs, 1 et lui-même.

Un nombre non premier n a nécessairement un diviseur inférieur à la racine carrée de n, qui soit 2, 5 ou un entier se terminant par 1,3,7 ou 9.

Cela permet d'énumérer moins de cas que d'effectuer tous les tests de divisibilité entre 2 et n.

On commence par coder des fonctions intermédiaires récursives

Fonction racine carrée

Écrire une fonction sqrt_int_floor : int -> int -> int -> int qui permettra de calculer récursivement la partie entière de la racine carrée, par recherche dichotomique:

sqrt_int_floor n a b sera appelé avec n>1, a²<=n et b² >n pour renvoyer la racine carrée de n:
  • si b = a+1, renvoie a
  • si b>a+1 on calcule c = (a+b)/2 et c². Si c² > n, on appelle sqrt_int_floor n a c et sinon sqrt_int_floor n c b .
  • Si n>1, l'arrondi inférieur de la racine carrée de n s'appelle avec sqrt_int_floor n 1 n

    Fonction test divisibilité

    La fonction test divisibilité, de signature test_div : int -> int -> int -> bool est appelée avec test_div n a b pour chercher si il existe un diviseur de n de la forme a + 10k <= b.

    La fonction renvoie vrai si un diviseur a été trouvé, et faux sinon. Cette fonction peut etre récursive

    On rappelle que a mod b renvoie le reste de la division entière de a par b, par exemple 10 mod 3 = 1.

    On peut à présent coder le test de primalité:

    Exemples d'affichage

    ./premier 5
    5 est premier

    ./premier 21
    21 n'est pas premier

    ./premier -1
    -1 n'est pas premier

    Modification

    Nom du fichier à rendre: premier2.ml

    Modifier le code précédent pour retourner un diviseur (le plus petit diviseur) lorsqu'un nombre n'est pas premier

    Exemples d'affichage

    ./premier 5
    5 est premier

    ./premier 21
    21 n'est pas premier car divisible par 3

    ./premier
    -1 n'est pas premier car inférieur ou égal à 1

    Jeu du morpion

    Nom du fichier à rendre: morpion.ml

    Le morpion est un jeu à deux joueurs dont le but est de créer le premier un alignement de symbole sur une grille. Les joueurs inscrivent tour à tour leur symbole sur une grille. Le premier qui parvient à aligner un nombre fixé de ses symboles horizontalement, verticalement ou en diagonale gagne la manche.

    Dans cet exercice on se propose de programmer un tel jeu du morpion. Pour des raisons de simplicité on décide de se restreindre à un jeu sur une grille de dimension 2x2 où un alignement de deux symboles est requis pour gagner. Le programme se généralise toutefois aux grilles de dimensions supérieures.

    1. Définir un type somme cell de constructeurs PlayerO, PlayerX et Empty représentant la présence ou non du symbole d'un des deux joueurs O et X.
    2. Écrire une fonction cell_to_char : cell -> char qui renvoie le caractère associé au symbole passé en paramètre.
    3. Définir un type record grid à quatre champs c1, c2, c3, c4 de type cell représentant une grille de 2x2 cellules.
    4. En utilisant la fonction cell_to_char, écrire une fonction print_grid : grid -> unit qui affiche dans le terminal une grille de morpion dont les cellules sont séparées par le caractère '|'.
    5. Déclarer une valeur empty_grid : grid représentant la grille vide.
    6. Écrire une fonction update_cell : cell -> cell -> cell telle que update_cell cell content renvoie cell si cell contient la marque d'un des deux joueurs, et renvoie content si cell est vide.
    7. En utilisant la fonction update_cell, écrire une fonction update_grid : grid -> int -> cell -> grid telle que update_grid grid index content renvoie une nouvelle grille dans laquelle la case index a été mise à jour avec content. La grille est renvoyée inchangée si l'indice n'est pas un indice valable de la grille ou si la case index n'est pas vide.
    8. Écrire une fonction are_equal_not_empty : cell -> cell -> bool telle que are_equall_not_empty c1 c2 est vraie si c1 et c2 ne sont pas vide et contiennent la marque d'un même joueur.
    9. En utilisant la fonction are_equal_not_empty, écrire une fonction exists_winner : grid -> cell telle que exists_winner grid renvoie PlayerO si grid contient un alignement gagnant pour le joueur O, PlayerX si grid contient un alignement gagnant pour le joueur X, Empty sinon.
    10. Écrire une fonction exists_empty_cell : grid -> bool telle que exists_empty_cell grid est vraie si grid contient au moins une case vide.
    11. En utilisant la fonction read_int : unit -> int définie dans la bibliothèque standard ainsi que les fonctions précédemment définies, écrire une fonction récursive game : grid -> unit effectuant les actions suivantes :

      À noter que si un joueur veut inscrire son symbole à un indice invalide (parce que ne correspond à aucune case ou que la case en question est non vide), le joueur perd son tour.

      Enfin, jouer une manche après avoir affiché la grille initiale vide.

    La suite de Fibonacci

    Nom du fichier à rendre: fibonacci.ml

    Dans cette exercice on se propose d'implémenter de différente manière la suite de Fibonacci. La suite de Fibonacci est définie par la suite récursive d’ordre 2 suivantes:

    1. Écrire une fonction fibo_slow : int -> int , qui implémente cette suite de manière naïve pour un n donné. L’appelle à cette fonction doit vous donner les résultats suivant :

      Attention le dernier test peut prendre un peu de temps, ce qui nous amène à la suite qui consiste à rendre le calcul de la suite de Fibonacci plus rapide.

    2. Écrire une fonction fibo : int -> int qui calcul la suite de Fibonacci pour un n donné, avec un unique appel récursive. Effectuer les mêmes tests que pour la fonction précédente. Que remarqué vous ?
    3. Si l’on est désireux de rendre les choses encore plus rapides, il est possible d’utiliser la formule de Binet :

      Fibn = 1/√(5)*(phin - phi'n) avec phi = (1+ √(5))/2 et phi' = -1/phi

    4. Avant d’utiliser cette définition, on propose d'implémenter un algorithme de calcul d’exponentiation  exp(x,n) = xn avec exp(x,n) =:

      Implémenté la fonction exp : float -> int -> float qui implémente cet algorithme.

    5. Implémenté la fonction fibo_fast : int -> float qui calcul la valeur de la suite de Fibonacci pour un n donné, en utilisant la formule de Binet et un unique appel à la fonction exp_fast. Effectuer les mêmes tests que pour les fonctions précédentes.

      Que remarquez-vous en comparant fibo_fast 48 avec fibo 48.

    6. Une autre alternative pour la suite de Fibonacci est de considérer l’application linéaire associé, qui peu être utilisé pour obtenir la formule de Binet. Soit :

      (Fib2,Fib1) = (1,1,1,0)*(Fib1,Fib0)

      Plus généralement:

      (Fibn+1,Fibn) = (1,1,1,0)^n*(Fib1,Fib0)

    7. Définir un type record vecteur à deux champs e1, e2 de type int représentant un vecteur d'ordre 2. Implémenté une fonction make_vect: int -> int -> vecteur pour créer un vecteur.
    8. Définir un type record matrice à quatre champs a1, a2, a3, a4 de type int représentant une matrice d'ordre 2. Implémenté une fonction make_matrice: int -> int -> int -> int -> matrice pour créer un matrice.
    9. Implémenté la fonction prod_matrice_vect qui calcul le produit entre une matrice et un vecteur. Nous rappelons que :

      (a1,a2,a3,a4)*(e1,e2) =(a1*e1 + a2*e2,a3*e1 + a4*e2)

    10. Implémenté la fonction prod_matrice qui calcul le produit de deux matrices. Nous rappelons que :

      (a1,a2,a3,a4)*(b1,b2,b3,b4)= (a1*b1 + a2*b3, a1*b2 + a2*b4, a3*b1 + a4*b3, a3*b2 + a4*b4)

    11. En vous inspirant de la question 3., proposer une fonction fast_exp_matrice: matrice -> int -> matrice qui calcul une exponentiation de matrice.
    12. Finalement, implémenter la fonction fibo_matrice: int -> int qui calcul la valeur de la suite de Fibonacci en utilisant la matrice (1,1,1,0) et le vecteur (1,0). Effectuer les mêmes tests que pour les fonctions précédentes.