Exercice 1 : Des polygones.
On représente des polygones par des listes de sommets.
type point = (float * float)
type polygon = point list
Écrivez une fonction qui étant donnée une liste de polygones, retourne le point d'abscisse minimale parmi tous les polygones.
Écrivez une fonction qui calcule les coordonnées du plus petit rectangle parallèle aux axes, contenant tous les polygones de la liste.
Exercice 2 : Déjà vu.
On nous donne les fonctions suivantes :
val levenshtein : string -> string -> int
val jaccard : string -> string -> float
Écrivez une fonction qui à un mot target : string et une liste de mots words : string list, calcule les mots parmi words à distance de Levensthein de 3 ou moins de word, triés par distance croissante. On ne doit calculer la distance de Levenshtein d'une paire de mots qu'au plus une fois.
Modifiez la solution pour supprimer dans un premier temps tous les mots dont la distance de Jaccard à target est au moins
$0.2$.
Exercice 3 : Palindrome
Donnez une fonction vérifiant si une liste est un palindrome. La liste
$[e_0;e_1;\ldots;e_n]$ est un palindrome si $e_i = e_{n-i}$ pour tout
$i \in [0,n]$.
Exercice 4 : Tri rapide
Écrivez une fonction smaller qui prend un entier $a$ et une liste d'entier $l$, et calcule la sous-liste des entiers de $l$plus petits que ou égaux à $a$.
Ajoutez une fonction bigger, qui renvoie cette fois la liste des éléments strictement plus grand que $a$.
En déduire l'algorithme de tri rapide.
bigger et smaller nous obligent à faire deux parcours de la liste à chaque appel récursif. Utilisez fold_left pour calculer en même temps les deux listes : celle des éléments plus petits et celle des éléments plus grand.
Exercice 5 : Triplets Pythagoriciens
Comment calculer la liste de tous les triplets pythagoriciens
$(a,b,c)$ avec $a^2 + b^2 = c^2$ d'entiers inférieurs à 100 , en utilisant map, filter et concat ? Il faudra aussi utiliser la fonction range déjà vue plusieurs fois.
Exercice 6 : Rendu de monnaie
Soit $m$ une quantité de monnaie en centimes. Donnez un algorithme qui produit la liste de toutes les façons de payer $m$. Par exemple, une façon de rendre 243 centimes est d'utiliser deux pièces de 1 € , deux pièces de 20 ¢ , et trois pièces de 1 ¢ . On considère que le nombre de pièces disponibles est illimité.
Exercice 7 : Problème des $n$-reines
On souhaite trouver les solutions du problème des $n$-reines : placer
$n$ reines sur un échiquier de dimension $n \times n$, sans qu'aucune ne soit menacée par une autre.
type position = (int * int)
Donnez une fonction are_not_threatening : position ->
position -> bool vérifiant que deux reines ne se menacent pas.
Étendez cette fonction en is_not_threatened : position list
-> position -> bool, vérifiant qu'une reine n'est pas menacée par une des reines déjà placées.
Écrivez une fonction board : int -> position list créant la liste des cases de l'échiquier, pour une dimension donnée.
Donnez une fonction énumérant les solutions du problème des
$n$-reines.
