Programmation Fonctionnelle, TD4

Htmligure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD4 : Listes.

Guyslain Naves

Exercice 1 : Des polygones.

On représente des polygones par des listes de sommets.

  1. type point = (float * float)
  2. type polygon = point list
  1. Écrivez une fonction qui étant donné un polygone, retourne le point d'abscisse minimale de ce polygone (on peut utiliser le flottant infinity).
  2. Écrivez une fonction qui étant donnée une liste de polygones, retourne le point d'abscisse minimale parmi tous les polygones.
  3. É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 : Distance d'édition.

On nous donne les fonctions suivantes :

  1. val levenshtein : string -> string -> int
  2. val jaccard : string -> string -> float
  1. É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.
  2. 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 : Égalité de listes.

Écrivez une fonction d'égalité de listes, prenant en argument le prédicat d'égalité des éléments. On peut utiliser List.zip.

  1. val are_equals :
  2. equals:('elt -> 'elt -> bool)
  3. -> 'elt list -> 'elt list -> bool

Exercice 4 : 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 5 : Tri rapide

  1. É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$.
  2. Ajoutez une fonction bigger, qui renvoie cette fois la liste des éléments strictement plus grand que $a$.
  3. En déduire l'algorithme de tri rapide.
  4. 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 6 : génération de mots de passe.

xkcd password strength

(sources: xkcd.com)

On souhaite générer un mot de passe en tirant $k$ mots aléatoirements dans un dictionnaire, en les capitalisant et en les concaténant. On dispose de :

  1. val dictionary : string list
  2. val k : int
  3. val Random.int : int -> int (* Random.int bound is in [0...bound-1] *)
  4. val String.concat : string list -> string
  5. val String.capitalize : string -> string

Utiliser les fonctions de listes pour écrire le générateur de mots de passe.

Exercice 7 : 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 8 : Rendu de monnaie

  1. 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é. On pourra commencer en considérant seulement des pièces de 5 ¢ , 2 ¢ et 1 ¢ .
  2. Généralisez l'algorithme pour qu'il prenne en argument la liste des monnaies disponibles.

Exercice 9 : 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.

  1. type position = (int * int)
  1. Donnez une fonction are_not_threatening : position -> position -> bool vérifiant que deux reines ne se menacent pas.
  2. É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.
  3. Écrivez une fonction board : int -> position list créant la liste des cases de l'échiquier, pour une dimension donnée.
  4. Donnez une fonction énumérant les solutions du problème des $n$-reines.