Retour Monnaie Glouton Récursif Non-Terminal Sans-Environnement

**laghal** · 02/04/2016, 14h32

Bonjour, bonsoir

Je précise tout d'abord que j'utilise Caml Light.

Je suis étudiant en classe préparatoire, et un algorithme de l'option info me donne du fil à retordre.

Il s'agit d'une variante du classique algorithme glouton de retour de monnaie.

L'énoncé est le suivant : la caisse est faite de billets aux valeurs décroissantes (ex [200;100;50;20]) présents un nombre illimité de fois, on donne une certaine somme au caissier et on veut la liste des billets rendus (sous la forme [20;50;50;200;200]) ainsi que le reliquat.

Deux versions sont demandées

La première ne m'a posée aucun problème : une simple version récursive terminale avec environnement (ie avec une fonction interne).
Je n'exclu pas des maladresses de programmation, donc voici mon algorithme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec caissier_term d c =
     let rec cais d = fun
          | [] billets -> d, billets
          | (h::q) billets when h <= d -> cais (d - h) (h::q) (h::billets)
          | (h::q) billets -> cais d q billets
     in cais d c [];;

Une deuxième version est demandée, plus délicate, c'est elle qui me pose problème.
Cette fois on ne doit renvoyer QUE le reliquat, dans une version récursive NON TERMINALE et SANS ENVIRONNEMENT (ie sans fonction interne).

J'arrive sans trop de problème et en respectant les critères à renvoyer la somme retournée par le caissier :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let rec caissier_s d = function
     | [] -> 0
     | h::q -> let k = d/h in h*k + caissier_s (d-k*h) q;;

Là je me dis qu'il suffit de soustraire la somme initiale par ce que je trouve... Sauf que ça demande un environnement ça !

Je me suis alors dit que je pouvais corriger le tir en conservant la valeur initiale à tous les niveaux d'appels de cette manière :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let rec caissier init d = function
     | [] -> init
     | h::q -> let k = d/h in (caissier init (d-k*h) q) - h*k;;

Ça fonctionne bien, mais l'appel doit se faire sous la forme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

caissier 485 485 [200;100;50;20];;

Et c'est un peu dégueux d'avoir deux fois le même argument... On pourrait s'en débarrasser, mais sans environnement je vois mal comment ?

Bref, je suis dans l'impasse, et je suis en train de me dire que ce n'est pas du tout comme ça qu'il fallait voir le problème.

Si vous avez des pistes je suis preneur.

Merci o/

[EDIT]

J'ai décidé de prendre le problème à l'envers, et plutôt que de chercher à faire baisser la valeur initiale donnée, plutôt l'atteindre...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let rec caissier_bis d = fun
     | [] atteint -> d - atteint
     | (h::q) atteint when atteint + h <= d -> caissier_bis d (h::q) (atteint+h)
     | (h::q) atteint -> caissier_bis d q atteint;;

En bidouillant un peu on a un algo terminal qui fonctionne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let rec caissier_bis d = fun
     | [] atteint -> d
     | (h::q) atteint when atteint + h <= d -> caissier_bis d (h::q) (atteint+h) - h
     | (h::q) atteint -> caissier_bis d q atteint;;