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: Tout sélectionner
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: Tout sélectionner
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: Tout sélectionner
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: Tout sélectionner
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: Tout sélectionner
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: Tout sélectionner
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;;
Mais l'appel est dégueux lui aussi (3 paramètres)..
- Code: Tout sélectionner
caissier_bis 485 [200;100;50;20] 0;;
Retour au même problème, les algorithmes sont équivalents
Mais si ça vous inspire ?...