Utilisez cette méthode pour modifier la définition

  let rec fib1 n =
      if n < 2
      then n
      else fib1 (n-1) + fib1 (n-2)

Proposez un algorithme simple pour trouver une solution optimale. Programmez la fonction correspondante :

monnaie_glouton : int list -> int -> (int*int) list

qui devra prendre en argument la liste des pièces qu'on a le droit d'utiliser et le montant total qu'on veut obtenir. Le résultat sera une solution qui minimise le nombre total de pièces utilisées.

Par exemple :

# monnaie_glouton [1; 2; 5; 10] 9;;
- : (int * int) list = [(5, 1); (2, 2)]

car il suffit d'une pièce de 5 centimes et de 2 pièces de 2 centimes pour faire 9 centimes.

Sur la planète Nethack, les habitants utilisent des pièces de 1, 4 et 6 zorkmid. Faites fonctionner votre fonction sur les entiers de 1 à 10. Que constatez-vous ?

Pour corriger le problème de la question précédente, nous allons utiliser un algorithme récursif plus complexe. Nous allons commencer par seulement calculer le nombre total de pièces utilisées : si les la liste des valeurs de pièces possible est p,

• il faut 0 pièces pour obtenir 0 centimes,
• il n'est pas possible d'obtenir n > 0 centimes si la liste p est vide,
• si p = { p₁, p₂, ...} et n > 0, il y a deux choix possibles : soit on n'utilise pas la pièce p₁, soit on l'utilise. On calcule donc
  1. le nombre N₁ de pièces qu'il faut pour obtenir n avec {p₂, ...}
  2. le nombre N₂ de pièces qu'il faut pour obtenir n-p₁ avec {p₁, p₂, ...}
  Le nombre cherché est le minimum entre N₁ et N₂+1. (Attention, si l'un des deux résultat est impossible, on prend forcément l'autre, et si les deux sont impossibles, il n'y a pas de solution.)

Si on modélise les cas impossibles par un nombre "infini" de pièces, on obtient la fonction récursive suivante :

    compte_monnaie 0 _ = 0
    compte_monnaie _ [] = "+infini"
    compte_monnaie n (p::l) = min (compte_monnaie n l)
                                  (1 + (compte_monnaie (n-p) (p::l)))

Écrivez la fonction compte_monnaie en Caml.

Écrivez une version mémoizée de cette fonction.

Estimez, en fonction de n et de la taille de l, la complexité des fonctions

• monnaie_glouton,
• compte_monnaie,
• monnaie_memoizee.

(Essayez juste de donner un ordre de grandeur...)

Testez expérimentalement ces fonctions :

• peu de pièces et n grand,
• beaucoup de pièces et n petit,
• beaucoup de pièces et ngrand.

Généralisez ce principe pour obtenir le nombre de chacune des pièces utilisées, et écrivez la fonction correspondante :

monnaie_rec : int list -> int -> (int*int) list

Par exemple :

# monnaie_rec [1; 4; 6] 8 ;;
- : (int * int) list = [(2, 4)]