Caml : Retour Monnaie Glouton Récursif

Discutez d'informatique ici !
laghal
Messages: 1
Enregistré le: 02 Avr 2016, 18:55

Caml : Retour Monnaie Glouton Récursif

par laghal » 02 Avr 2016, 18:58

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: 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 ?...



 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite