1
Écrire une fonction shortestDivider : int -> int qui renvoie à un entier n>1 son plus petit diviseur supérieur ou égal à 2. Pour cela, on testera successivement si les entiers de 2 à n divisent n. Le premier diviseur est retourné, c’est au plus n. On rappelle que a mod b renvoie le reste de la division entière de a par b, par exemple 10 mod 3 = 1.
Écrire une fonction reverse : ‘a list -> ‘a list qui renvoie à une liste l sa liste miroir, en inversant tous les éléments. Par exemple, reverse [1;2;3] = [3; 2; 1]. On notera que cette fonction existe déjà sous OCaml avec List.rev, on demande de recoder cette fonction sans utiliser List.rev.
Écrire une fonction factorSlow : int -> int list qui renvoie à un entier n la liste l de ses diviseurs dans l’ordre croissant, avec leur ordre de multiplicité. Ainsi, n doit etre le produit des éléments de l, et tous les éléments de l sont des nombres premiers. Pour coder la fonction factorSlow : int -> int list , on utilisera le fait qu’une fois un diviseur trouvé d, on se ramène à factoriser n/d et que shortestDivider renvoie nécessairement un nombre premier. Par exemple:
# factorSlow 24;;
– : int list = [2; 2; 2; 3]
# factorSlow 1300;;
– : int list = [2; 2; 5; 5; 13]
# factorSlow 100000001;;
– : int list = [17; 5882353]
# factorSlow 1000000001;;
– : int list = [7; 11; 13; 19; 52579]
Plusieurs améliorations permettent d’accélérer l’algorithme de factorisation précédemment décrit.
Écrire une fonction shortestDividerUpper : int -> int -> int , tel que shortestDividerUpper n d renvoie à un entier n>1 son plus petit diviseur supérieur ou égal à d>1. Pour accélérer la résolution, on traitera le cas d=2 séparément, et on testera les divisions par les entiers impairs compris entre d et la racine carrée de n. Si aucun diviseur n’est trouvé sur ces tests, cela signifie que la fonction doit renvoyer n.
Écrire une fonction factorFaster : int -> int list qui renvoie à un entier n la liste ordonnée l de ses diviseurs, avec leur ordre de multiplicité. Pour accélérer la résolution de factorSlow, on utilisera le fait qu’une fois un diviseur trouvé d, on se ramène à factoriser n/d et qu’on cherche alors pour la suite des diviseurs supérieurs ou égaux à d.
2
On veut écrire un programme qui permet de calculer les points d’un tournoi un peu particulier : le tournoi est composé d’un certain nombre d’épreuves prises parmi les épreuves du pentathlon moderne: la course, le tir, l’équitation, la natation et l’escrime.
Écrire le type constructeur epreuve correspondant aux cinq possibilités d’épreuve: Course, Tir, Equitation, Natation et Escrime.
Pour chaque épreuve de ce tournoi, un score entier est donné à chaque joueur en premier lieu, puis sera ensuite pondéré lors du calcul final.
Donnez un type epreuve_score formant la paire epreuve et score entier
Puis, donnez le type enregistrement joueur comportant le champ id correspondant au numéro de dossard, et le champ competition contenant une liste d’ epreuve_score.
enfin, donnez le type ponderation , un tuple comprenant un int pour chacune des épreuves possibles.
On a maintenant les ingrédients pour pouvoir faire notre comptage des points, mais dans un premier temps, il faut enregistrer ces points:
Créez une fonction qui, étant donnée un identifiant de joueur et une épreuve, demande a la console le nombre de points qu’a fait le joueur de l’identifiant a cette épreuve particulière: points_epreuve : epreuve -> int -> int (On rappelle que la fonction read_int: unit -> int permet de récupérer un nombre dans la console)
Créez une fonction new_competition : epreuve list -> int -> epreuve_score list prenant en argument une liste d’épreuve et un identifiant et retournant la liste des épreuves assortie des points fait par le joueur correspondant à l’identifiant
Créez une fonction new_joueur : epreuve list -> int -> joueur créant un nouveau joueur.
Donnez une fonction new_ponderation : demandant la pondération de chacune des épreuves possibles et retournant le tuple correspondant. Maintenant que les points peuvent être rentrés, on va calculer la somme: unit -> ponderation
Donnez la fonction score_pondere : epreuve_score -> ponderation -> int qui prend une épreuve et la pondération de chaque épreuve, et renvoie le score pondéré
Donnez la fonction points_comp : list epreuve_score -> ponderation -> int qui, de manière récursive terminale, prend une liste d’épreuve d’un joueur et la pondération et renvoie la somme des points.
On veut maintenant pouvoir retourner automatiquement le gagnant entre deux joueurs.
Donnez la fonction match_2 : joueur -> joueur -> ponderation -> unit qui prend deux compétiteurs en entrée, ainsi que la pondération des épreuves, et écrit sur la console le numéro du gagnant (celui qui a le plus de points) avec son score.
On veut maintenant créer un tournoi avec plus de personnes, mais avec des éliminations de certains participant avant la fin du tournoi :
Créez une fonction resultat_partiel : epreuve_score list -> ponderation -> int qui fait la somme des scores pondérés jusqu’à la fin de la liste ou jusqu’à l’épreuve qui arrive à la position max. Cette fonction doit être récursive terminale.
Enfin, donnez la fonction tournoi_a_4 : epreuve list -> unit qui en prenant une liste d’épreuves, demande la pondération, créez 4 joueurs en demandant leur score et dans un premier temps regarde lequel des deux premiers joueurs est devant après deux épreuves, puis regarde lequel des deux autres joueurs est devant après le même nombre d’épreuves, et enfin regarde parmi ces deux finalistes lequel gagne le match sur toutes les épreuves
palindrome.ml
Une technique pour vérifier qu’une liste est un palindrome est de vérifier que l’élément de tête est de queue sont identiques, puis de supprimer l’élément de tête et de queue et de vérifier que la liste résultante est un palindrome.
Implémentez une fonction get_last de type ‘a list -> ‘a option qui renvoie le dernier élément d’une liste (None si la liste est vide).
Implémentez une fonction remove_last de type ‘a list -> ‘a list qui prend en paramètre une liste et renvoie la même liste avec le dernier élément retirer.
Implémentez une fonction is_palindrome_1 de type ‘a list -> bool qui renvoie true si la liste en paramètre est un palindrome (false sinon) et utilise les fonctions get_last et remove_last.
Testez votre fonction sur les listes «”de” “la” “sa” “la” “de”» et «1 2 3 2 3».
L’implémentation précédente utilise deux fonctions get_last et remove_last. Il peut être intéressant de fusionner ces deux fonctions en une seule fonction get_remove_last de type ‘a list -> ‘a option * ‘a list qui renvoie le dernier élément d’une liste et la liste sans son dernier élément.
Implémentez la fonction get_remove_last.
Implémentez une fonction is_palindrome_2 de type ‘a list -> bool qui renvoie true si la liste en paramètre est un palindrome (false sinon) et utilise la fonction get_remove_last.
Testez votre fonction sur les listes «”de” “la” “sa” “la” “de” » et « 1 2 3 2 3».
Définir un type enregistrement hanoi à trois champs t1, t2 et t3, tous trois de type int list, représentant les trois tours du jeu.
Écrire une fonction check : int list -> bool, qui renvoie un booléen indiquant si la liste passée en paramètre représente un tour valide. Les entiers de la liste représentant les tailles des disques, il faut s’assurer que pour deux entiers consécutifs de la liste, le premier est strictement plus petit que le second.
En utilisant la fonction check précédemment définie et la fonction de la bibliothèque standard assert : bool -> unit permettant de s’assurer de la validité d’une assertion, écrire une fonction make : int list -> int list -> int list -> hanoi telle que make t1 t2 t3 vérifie que t1, t2 et t3 sont bien des tours valides, et renvoie le jeu composé de celles-ci.
Écrire une fonction récursive terminale rev : ‘a list -> ‘a list qui inverse la liste passée en paramètre. On pourra passer par une fonction auxiliaire et/ou un accumulateur.
En utilisant la fonction hd_tl_opt : ‘a list -> ‘a option * ‘a list donnée ci-dessous, écrire une fonction récursive terminale combine : int list -> int list -> int list -> (int option * int option * int option) list telle que:
En utilisant la fonction print_option : int option -> unit donnée ci-dessous, écrire une fonction print_list : (int option * int option * int option) list -> unit telle que print_list [(None, None, Some 3); (Some 1, None, Some 5); (Some 4, Some 2, Some 6)] affiche: