Programmation Fonctionnelle, TP4

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TP4 : Petite énigme mathématique.

Guyslain Naves

L'objectif de ce travail est d'apprendre à manipuler les listes à l'aide de fonctionnelles.

Remark 1: Il sera interdit d'écrire des fonctions récursives, sauf si l'énoncé d'une question le permet explicitement.

Vous devez utiliser autant que possible les fonctions List.map, List.filter, List.flatten et les autres fonctionnelles de listes (cf. le module de liste).

Deux nombres entiers $x$ et $y$, compris strictement entre $1$ et $100$ sont choisis. On communique à Sophie la somme $s = x+y$, et à Philippe le produit $p = x \cdot y$, mais $x$ et $y$ sont soigneusement maintenus secrets. S'en suit une curieuse conversation :

  • " Tu ne connais pas les valeurs de $x$ et $y$", proclame Sophie à Philippe.
  • "Maintenant, si !" , répond Philippe.
  • "Et maintenant, moi aussi" réplique finalement Sophie.

Que valent $x$ et $y$ ?

Le sujet de ce TP est de trouver une réponse à cette énigme. Les premières questions vont nous permettre de définir plusieurs outils mathématiques qui nous seront utiles. Seules les dernières questions sont axées sur la résolution de l'énigme elle-même.

Question : itérateur de fonctions

Écrire une fonction récursive repeat, telle que

$$ \text{repeat}\;n\;f\;v = f\;(f\;(f\;\ldots(f\;v)\ldots))$$

où $f$ est répété $n$ fois dans le membre droit de l'équation.

Question : génération d'un intervalle

En déduire la fonction range de type int -> int -> int list, telle que

$$\text{range}\;a\;b = [a;a+1;a+2;\ldots,b-1;b]$$

Attention, cette fois vous n'avez pas le droit d'utiliser une récursion, mais seulement repeat.

Question : crible d'Ératosthène

On souhaite faire la liste de tous les nombres premiers inférieurs à 100.

  • Écrire une fonction is_divisible prenant un entier n et une liste lst d'entiers en argument, et testant si n est divisible par au moins un entier de lst. Son type sera donc:

    1. val is_divisible : int -> int list -> bool
  • En utilisant List.fold_left, en déduire une fonction primes, prenant un entier $n$, et retournant la liste de tous les nombres premiers inférieurs à $n$. La fonction passée à List.fold_left s'appelera insert_when_prime : int list -> int -> int list.

Question : factorisation d'un entier

Maintenant que nous avons tous les nombres premiers jusqu'à $n$, nous pouvons trouver l'unique factorisation de n'importe quel entier inférieur à $n$ (et même $n^2$ en fait).

  • Écrire une fonction récursive power : int -> int -> int , pour le calcul de la puissance sur les entiers.
  • Écrire une fonction récursive valuation, qui prend deux entiers $p$ et $n$, et calcule le plus grand $k$ tel que $p^k$ divise $n$.
  • Utiliser valuation pour calculer la factorisation d'un entier $q$. Le résultat devra être une liste de couples de la forme $(p_i,k_i)$ tel que $q = \prod_{i} p_i^{k_i}$. Par exemple:

    1. # factorize ps 136;;
    2. - : (int * int) list = [(2, 3); (17, 1)]

    Ici, ps est la liste des nombres premiers à utiliser pour la factorisation.

Remark 2: Il est plus naturel pour les fonctions valuation et power d'utiliser une définition récursive. On pourrait les écrire sans utiliser de récursion, mais le résultat serait significativement moins lisible.

Question : facteurs d'un entier

À partir de la décomposition en nombre premier d'un entier, on peut facilement générer une liste de ses facteurs.

  • Donner d'abord une fonction qui, prenant deux entiers $a$ et $k$, calcule la liste des $a^j$ pour $j \in \{0,1,\ldots,k\}$.
  • Transformer la décomposition en facteurs premiers, en une liste de listes des $a^j$ où $a$ est un nombre premier apparaissant dans la décomposition, et $j$ est inférieur ou égal à la valuation de $a$. Pour $136$, vous obtenez :

    1. - : int list list = [[1;2;4;8];[1;17]]
  • Écrire une fonction qui prend deux listes d'entiers, et calcule la liste des produits $a \times b$, avec $a$ choisi dans la première liste et $b$ choisi dans la seconde liste.
  • En déduire une fonction calculant la liste des facteurs d'un entier.

Question : décomposition valide

Dans le cadre de l'énigme, seules les décompositions d'un entier $p$ en deux facteurs $p = a \cdot b$, avec $2 \leq a \leq b \leq 99$ nous intéressent.

  • Donner une fonction valid_factorisations calculant toutes les décompositions valides (en ce sens) pour un entier $p$ quelconque.
  • Écrire un fonction calculant le nombre de décomposition valide de $p$.

Question : restreindre le choix de $s$

Dans l'énigme, Sophie peut déduire de $s$ que Philippe ne connait pas la décomposition de $p$ en $x \cdot y$. Donc, pour toute paire $u,v$ avec $u+v = s$, $u \cdot v$ admet au moins deux décompositions.

  • pour une valeur de $s$, générer la liste des couples $(u,v)$ possibles,
  • et vérifier que pour chaque couple, $u \cdot v$ admet au moins deux décompositions valides.
  • Testez toutes les valeurs possibles pour $s$ (de 4 à 198), et gardez celles pour lesquelles la propriété est vrai. Vous devriez obtenir une liste admissible_S d'une dizaine de valeurs possibles pour $s$.

En déduire une liste de paires $x,y$ possibles, avec $x < y$.

Question : prendre en compte la remarque de Philippe

Philippe en déduit lui aussi que $s$ prend une valeur parmi cette dizaine de valeurs. Puisqu'il en déduit $x,y$, toutes les décompositions valides de $p$ autre que $x \cdot y$ ont une somme n'appartenant pas à la liste des valeurs encore possible pour $s$.

  • Pour toutes les paires $x,y$ potentielles (dont la somme est admissible), calculer les décompositions valides de $x \cdot y$.
  • Garder seulement les paires qui n'admettent qu'une seule décomposition valide dont la somme est admissible.
  • Appeler cette liste de paires possible_solutions.

Question : Trouver $x$ et $y$:

Enfin, Sophie trouve $x$ et $y$. Il doit donc y avoir une paire $x,y$ parmi toutes celles là, dont la somme $x+y$ est unique. C'est donc la solution. Quel est-elle ?