bernouilli92 a écrit :
Taille en octets : 174.5 octets
On entre les paramètres : liste des pièces disponibles et montant souhaité :
{100 50 20 10 5 2 1} 100 MPO34 -> résultat 4563 en environ 5,5 minutes sur une 48gx
L'algorithme est beaucoup plus rapide si la liste des pièces est triée par ordre décroissant :
{1 2 5 10} 20 -> résultat : 40 en environ 25 secondes
{10 5 2 1} 20 -> résultat : 40 en environ 4 secondes
J'aime bien cet algorithme. Même s'il m'a fallu quelques minutes pour en comprendre le principe. Ce qui fait que je l'apprécie d'autant plus.
Il y a plusieurs raisons à cela:
- il est entièrement paramètré: on saisi la liste des pièces et la somme à atteindre. C'est l'idéal pour "jouer" avec le problème proposé.
- sa logique intracèque: quand les lsite du RPL rejoingnent la logique du l.i.s.p.
- son efficacité, il utilise peu de mémoire et que quelque niveau de la pile (même si cela augmente un peu avec le nombre de pièces
- l'astuce << LIST-> 1 - ->LIST >> pour extraire le premier élément et le reste de la liste est génial (on dirait du lisp : head et TAIL)
- il tourne tel quel sur HP-28S (ce qui prouve que c'est du vrai RPL pur et dur !).
- il y a d'autres trouvaille comme << M L(1) MOD NOT >> lorsque la lsite est un singleton et autre test simplifié (avec NOT) qui ont tout à fait leur place dans un MPO. Même si cela nuit un peu à la lisibilité de la logique.
Justement, comme nous sommes dans un MPO, je m'approprie le principe et remodelant "à ma sauce" le code. J'en profite pour optimiser et miser plus petit.
Par exemple la fonction IP est inutile, la boucle FOR se charge de compter par pas entier.
Mais, il y a aussi une répétition << Liste GET 1 >> pour extraire le premier élément 'head' de la iste de pièce.
J'en profite pour mettre en évidence la logique de ce code en précisant ce qui est tête (head) et queue (TAIL).
Les variables locales L et m sont définies dès le début pour éviter les manipulations de pile (m minuscule car scalaire, et L majuscule car c'est une liste). De même pour h (head) et T (pour TAIL) après le coup de génie du LIST-> 1 - ->LIST
J'espère que l'utilisation de h et T va accélérer l'excussion (car cette fois la tête de liste n'est plsu extraite à chaque pas de la boucle, mais mémorisé (dans les varaibles locales). Merci de me confirmer que cette nouvelle version du code est plus rapide.
Sur HP-28S le calcul donne 4365 en environ 20 min.
C'est donc un peut plus rapide que l'utilisation de mon double vecteur et la fonction DOT.
Code : Tout sélectionner
« -> L m // deux arguments (la liste L des pièces et un scalaire m qui donne la somme à composée)
« IF m // test si m est non nul
THEN
L LIST-> 1 - ->LIST // extrait astucieusement le premier élément du reste de la liste
-> h T // h (première pièce) T (liste des pièces restante - éventuellemtn vide)
«
IF T SIZE // test si T est non vide
THEN
0 // Initialise le total de possibilités à 0
0 m h / FOR i // Boucle pour 0,1,2, ... m/h
T m h i * - MPO34 // Compte le nombre de possibilités de composer avec les pièce restante
la somme restante. Récurrence simple et efficace.
+ // Ajoute le nombre de possibilités au total
NEXT
ELSE
m h MOD NOT // si T est vide, voir s'il est possible de composer m avec les seules pièces h
// la fonction MOD est idéale pour cela, le NOT permet de retourner 1
// uniquement si h est multiple de m. Bien joué.
END
»
ELSE
1 // m null, il y a une seule façon de ne rien payé !
END
»
» // Un seul résultat, le nombre de possibilités
'MPO34' STO