(* I.1 Decompte de monnaie *)
(* La relation de récurrence est assez simple : soit la tete de la liste est utilisé dans le décompte
soit elle ne l'est pas. Et donc compte n liste est la somme des cas avec au moins une fois c1, et
de ceux sans c1. Ces cas avec au moins une fois c1 sont les mêmes que ceux de n - tete avec la même liste. 
Ceux sans c1 sont simplement compte n queue.

Il faut bien penser à tous les cas de base, c'est surtout là que réside la difficulté.
Si l'entier reçu est négatif, il est impossible de faire le total attendu
Si il est nul, il y a une seule façon (on prend 0 de chaque pièce/billet et ce même si la liste est vide !)
Et enfin si la liste reçue est vide et que n est > 0 on ne peut bien sûr pas faire n.
Il y a donc trois cas de base *)
let rec compte (n : int) (liste : 'a list) : int =
  match n, liste with
  | _, _ when n < 0 -> 0
  | 0, _ -> 1
  | _, [] -> 0
  | _, tete :: queue -> compte (n - tete) liste + compte n queue ;;


compte 10 [];; (* réponse 0 *)
compte 10 [10] ;;  (* réponse 1 *)
compte 10 [5] ;;  (* réponse 1 *)
compte 1 [5];;  (* réponse 0 *)
compte 10 [1; 2; 5] ;;  (* réponse 10 *)
compte 50 [1; 2; 5; 10; 20] ;;  (* réponse 450 *)


(* Version synthétique avec des if et une autre analyse
Pour le cas de base : si on n'a aucun billet ou pièce, soit on doit fabriquer 0 auquel cas c'est possible d'une seule façon (et on rend 1), soit c'est autre chose que 0 que l'on doit fabriquer  et alors on rend 0.
Pour la récurrence on peut protéger l'appel avec la même liste : si n - tete est négatif il est impossible de réaliser le rendu et donc on en fait pas l'appel *)
*)
let rec compte (n : int) (liste : 'a list) : int =
  match liste with
  | [] -> if n = 0 then 1 else 0 
  | tete :: queue -> compte n queue + (if tete <= n then compte (n - tete) liste else 0);;

compte 10 [];; (* réponse 0 *)
compte 10 [10] ;;  (* réponse 1 *)
compte 10 [5] ;;  (* réponse 1 *)
compte 1 [5];;  (* réponse 0 *)
compte 10 [1; 2; 5] ;;  (* réponse 10 *)
compte 50 [1; 2; 5; 10; 20] ;;  (* réponse 450 *)

(* Modification pour rajouter les façons de rendre la monnaie
Pour les cas de bases dans le cas où on a une solution on rend la liste contenant la liste vide (i.e. il y a une solution qui consiste à ne rien rendre...
et dans le cas où il n'y a pas de solution on rend la liste vide (qui veut dire qu'il n'y a pas de solution...)
Dans la récurrence pour l'appel de decompte n queue toutes les solutions doivent être conservées et on les ajoutera avec un @ si nécessaire aux solutions utilisant une fois la tete.
Pour l'appel de decompte (n - tete) liste il faut rajouter tete en tete de toutes les solutions rendues  *)
let rec ajout (e : 'a) (lliste : 'a list list) : 'a list list = 
  match lliste with
  | [] -> []
  | tete :: queue -> (e :: tete) :: ajout e queue ;;

let rec compte (n : int) (liste : 'a list) : int * int list list =
  match liste with
  | [] -> if n = 0 then (1,[[]]) else (0, []) 
  | tete :: queue -> let (dec1, liste1) = compte n queue in
                     let (dec2, liste2) = if tete <= n then compte (n - tete) liste else (0, []) in
                     (dec1 + dec2, liste1 @ (ajout tete liste2)) ;;


compte 10 [];;
compte 10 [10] ;;
compte 10 [5] ;;
compte 1 [5];;
compte 5 [1; 2; 5] ;; 
compte 10 [1; 2; 5] ;; 
compte 13 [1; 2; 5; 10; 20] ;;
compte 50 [1; 2; 5; 10; 20] ;;

compte 10 [];; (* réponse 0 *)
compte 10 [10] ;;  (* réponse 1 *)
compte 10 [5] ;;  (* réponse 1 *)
compte 1 [5];;  (* réponse 0 *)
compte 5 [1; 2; 5] ;; (* réponse 4 *) 
compte 10 [1; 2; 5] ;;  (* réponse 10 *)
compte 13 [1; 2; 5; 10; 20] ;; (* réponse 16 *)
compte 50 [1; 2; 5; 10; 20] ;;  (* réponse 450 *)


let rec compte2 (n : int) (liste : 'a list) : int * int list list =
  match liste with
  | [] -> if n = 0 then (1,[[]]) else (0, []) 
  | tete :: queue -> let (dec1, liste1) = compte2 n queue in
                     let (dec2, liste2) = compte2 (n - tete) liste in
                     (dec1 + dec2, liste1 @ (ajout tete liste2)) ;;


compte 10 [];;
compte 10 [10] ;;
compte 10 [5] ;;
compte 1 [5];;
compte 5 [1; 2; 5] ;; 
compte 10 [1; 2; 5] ;; 
compte 13 [1; 2; 5; 10; 20] ;;
compte 50 [1; 2; 5; 10; 20] ;;

compte 10 [];; (* réponse 0 *)
compte 10 [10] ;;  (* réponse 1 *)
compte 10 [5] ;;  (* réponse 1 *)
compte 1 [5];;  (* réponse 0 *)
compte 5 [1; 2; 5] ;; (* réponse 4 *) 
compte 10 [1; 2; 5] ;;  (* réponse 10 *)
compte 13 [1; 2; 5; 10; 20] ;; (* réponse 16 *)
compte 50 [1; 2; 5; 10; 20] ;;  (* réponse 450 *)

(* I.2 PGCD, Euclide, Bezout *)
let rec pgcd (a : int) (b : int) : int=
  match b with
  | 0 -> a
  | _ -> pgcd b (a mod b) ;;

pgcd 25 80 ;;
pgcd 80 25 ;;

(*
La récurrence pour calculer les coefficients u v pour le couple (a, b), on récupère
ceux de (b, a mod b) qu'on note u' et v'.
On a alors d = u' * b + v' * r en notant r = a mod b, en effet c'est le reste de la division
entière de a par b. On peut donc écrire a = (a/b) * b + r, soit r = a - (a/b) * b (attention a/b est la division entière !). On reporte
dans l'expression ci-dessus
d = u' * b + v' * (a - (a/b) * b) = v' * a + (u' - (a/b) * v') * b.
On a donc u = v' et v = u' - v' * (a/b)
 *)

(* Il y a subtilité pour justifier la terminaison. Il faut bien voir que si a > b > 0, alors l'appel suivant se fera avec (b, a mod b) < (a, b) pour l'ordre produit et comme b < a mod b on restera toujours dans le cas des appels où le premier paramètre est supérieur au second. Ce qui permet de conclure.

 En revanche si a < b l'appel suivant se fera avec (b, a mod b) = (b, a)  qui n'est pas inférieur à (a, b) ! Mais en revanche pour le couple (b, a) b < a et on se retrouve dans le premier cas ! Les appels suivants se feront bien sur des couples formant une suite strictement décroissante pour l'ordre produit, ce qui permettra de conclure sur la terminaison de la fonction *)
  
let rec bezout (a : int) (b : int) : int * int * int =
  match b with
  | 0 -> (a, 1, 0)
  | _ -> let (d, u, v) = bezout b (a mod b) 
         in
         (d, v, u - v * (a / b)) ;;

bezout 25 80 ;;
    
let (p,u,v) = bezout 25 80 in
  u * 25 + v * 80 ;;

(* I.3 Encore les coefficients binomiaux *)
(* On utilise bien sûr la formule de récurrence proposée.
Il faut bien déterminer les cas de bases
Si p = 0, on sait qu'il faut rendre 1
Si n < p on rend 0
Enfin si n >= p > 0 on utilise la formule. Dans l'écriture il faut bien faire attention
à faire la division par p en dernier, sinon on risque d'avoir un résultat faux... *)

let rec binomial (p : int) (n : int) =
  match p with
  | 0 -> 1
  | _ when n < p -> 0
  | _ -> binomial (p - 1) (n - 1) * n / p;;
  
binomial 0 5 ;;
binomial 3 5 ;;
binomial 6 5 ;;

(* La preuve de la terminaison est facile. On prend comme ensemble ordonné bien fondé (N,<=)^2 muni de l'ordre produit.
 Il y a un élément minimal (0,0).
 On voit que les deux premières lignes de code qui correspondent aux cas de base incluent l'élément minimal, et que dans ces cas là il est clair que la fonction termine.

 Soit alors un couple (n, p) ne correspondant pas à un cas de base. Supposons que pour tout couple (m, q) strictement plus petit que (n, p) le calcul termine. Dans le code on voit que pour le calcul de binomial n p  on appelle binomial n-1 p-1, soit binomial m q avec (m=n-1, q=p-1) strictement plus petit que (n, p), dont le calcul termine et on fait une multiplication et une division en plus. Le calcul termine.

 Donc par induction bien fondée le calcul termine dans tous les cas *)
 
(* La preuve de la correction est également facile. Je ne la détaille pas beaucoup.
 En effet pour les cas de base la fonction renvoie la bonne valeur.
 Sinon soit un couple (p, n) avec p non nul et p <= n.
 On suppose que pour tout couple (q, m) avec q < p 
 la fonction calcule la bonne valeur.
 D'après la relation donnée dans l'énoncé il est immédiat que la fonction renvoie
 la bonne valeur.
 On en déduit par induction bien fondée que pour TOUT couple (p, n) la fonction renvoie la bonne valeur *)
 
 (* Pour la complexité on peut analyser les choses ainsi :
 Dans les cas de base, on a un résultat en temps constant.
 Si non c'es qu'on calcule (p parmi n) pour p <= n. Il est clair d'après le code
 qu'il y aura les appels successifs avec les valeurs (p-1, n-1), (p-2, n-2) etc...
 jusqu'à (0, n-p), où on tombera sur un cas de base.
 En notant C(p, n) le coût pour le calcul du couple (p, n) il vient
 C(p, n) = 2 + C(p-1, n -1) (Le 2 vient de la multiplication par n et de la division par p
 C(p-1, n-1) = 2 + C(p-2, n-2)
 C(0, n-p) = 1
 En faisant la somme membre à membre il vient
 C(p, n) = 1 + 2 * p
 On a donc une complexité liénaire en p !!
 C'est donc beaucoup plus efficace que la méthode naïve utilisant le triangle de Pascal... *)
  

(* III.2 *)
(* Fonction 91 *)
let rec f (n : int) : int=
  if n > 100 then  (n - 10) else f (f (n + 11)) ;;

for i = 80 to 110 do
  print_int i ;
  print_string " " ;
  print_int (f i) ;
  print_newline ()
done ;;

(* II.1 Baguenaudier *)
(* La subtilité de la programmation c'est qu'il faut programmer en parallèle le remplissage des n premieres cases.
On dispose donc de deux fonctions :
- vider n qui suppose qu'il y a n jetons sur les n premières cases et qui décrit la suite de manipulations à effectuer pour enlever ces n jetons;
- remplit n, qui suppose au contraire qu'il n'y aucun jeton sur les n premières cases et qui décrit la suite de manipulations à effectuer pour remplir ces n cases avec des jetons.

Pour justifir l'algorithme on peut noter que pour une case n donnée, seul importe ce qu'il y a avant la case, mais pas ce qu'il y a après.
Donc pour vider la case n on peut :
-vider jusqu'à la case n - 2, il ne reste alors plus qu'un jeton en n - 1 et un en n
-enlever le jeton n (ce que l'on a le droit de faire directement d'après les règes du jeu)
-remplir jusqu'à la case n - 2. À ce moment on a globalement juste enlevé le jeton  de la case n.
-vider jusqu'à n-1.

Et pour remplir jusqu'à la case n, on
remplit jusqu'à n - 1
on vide jusqu'à n - 2
on pose un jeton en n
on remplit jusqu'à n - 2. 

Les cas de bases sont triviaux. Si n = 0 il n'y a rien à faire ! Si n = 1 on peut librement mettre ou enlever un jeton.

Note de programmation : on a utilisé dans les fonctions des SEQUENCES, que nous étudierons bientôt. Ce sont des suites d'appels de fonctions à effet de bord (comme des print) séparés par des points virgules (1 seul point virgule) *)

let rec vider (n : int) : unit =
  match n with
  | 0 -> ()
  | 1 -> print_string "Enlever le jeton 1" ; print_newline ()
  | _ -> vider (n - 2); print_string "Enlever le jeton "; print_int n; print_newline (); remplir (n - 2 ); vider (n - 1)
  and remplir (n : int) : unit =
  match n with
  | 0 -> ()
  | 1 -> print_string "Poser un jeton en 1" ; print_newline ()
  | _ -> remplir (n - 1); vider (n - 2); print_string "Poser un jeton en "; print_int n; print_newline (); remplir (n - 2) ;;

vider 1 ;;
vider 2 ;;
vider 3 ;;
vider 4 ;;
vider 10 ;;

(* Un petit calcul de deux suites récurrentes croisées d'ordre 2 montrent que le nombre de mouvements de pion pour vider un baguenaudier de taille n est
2/3 * 2^n -1/6 * (-1)^n -1/2.
On a donc une complexité exponentielle...
qui donne par exemple 682 mouvements pour un baguenaudier de taille 10
et 12297829382473034410 mouvements pour un baguenaudier de taille 64...(soit environ 1,2e19 mouvements...)
A raison d'un mouvement par seconde, c'est à peine plus que l'âge de l'univers... *)