Misez P'tit, Optimisez - N°34 (Tout à 1 Euro!)

[dprtl]

C'est avec ce genre de problème qu'on voit que nos calculatrice sont vraiment très lentes et que les progrès fait en 20 ans sont énormes.
Sur l'émulateur sur mon PC, le résultat est trouvé en 2 secondes. Mais bon ce n'est pas comparable

Lentes ? De quelles machines parles-tu ? Je crois que ce sont surtout leurs propriétaires qui ont du mal à suivre

Ma Z-1 abat toutes les itérations nécessaires à la résolution du problème en 10 secondes avec le programme suivant, en C interprété :

Code : Tout sélectionner

main(){
int b,c,d,e,f,n;
n=1;
for(f=0;f<=100;f+=50){
for(e=f;e<=100;e+=20){
for(d=e;d<=100;d+=10){
for(c=d;c<=100;c+=5){
for(b=c;b<=100;b+=2){n++;}
}}}}
printf("n=%d\n",n);}

Et le même code C, compilé sur un Atari ST de 1987, affiche le résultat instantanément !

[zpalm]

Les différentes approches sont très intéressantes, mais il y a de la place pour de l'optimisation ...

Pour info je suis à 13 secondes sur WP 34S et 3mn 32s sur la HP-41C qui est normalement beaucoup plus lente qu'une HP 28 ou 48.

Et n'oubliez-pas la version pour TI-57 indispensable à tout MPO digne de ce nom.

@dprtl: belle optimisation entre ta première version au début du fil et la dernière ci-dessus !

[C.Ret]

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

[C.Ret]

[quote="dprtl"]Je crois que ce sont surtout leurs propriétaires qui ont du mal à suivre [/code]

C'est très clair... Pour ma part c'est bien moi qui suis très lent.
J'ai toujours étais lent d'ailleurs. mais jamais compilé.

[Gilles59]

Algorithme récursif naif sur 39GII

Code : Tout sélectionner

LPiece:={100,50,20,10,5,2,1}  ;

EXPORT MPO34(Reste, NPiece)
BEGIN
 IF Reste==0 THEN RETURN 1; END;
 IF Reste<0 OR NPiece<1 THEN RETURN 0; END;
 RETURN MPO34(Reste,NPiece-1)+MPO34(Reste-LPiece(NPiece),NPiece);
END;

MPO(100,7)

Probablement pas le plus rapide (pas tester sur la vraie calc, ~14 sec avec l'émulateur)
Ca semble tout bête mais çà m'a bien pris la tête :O dodo

[ledudu]

MPO(100,7)

Impressionnant !

[Gilles59]

Ma Z-1 abat toutes les itérations nécessaires à la résolution du problème en 10 secondes avec le programme suivant, en C interprété :

Code : Tout sélectionner

main(){
int b,c,d,e,f,n;
n=1;
for(f=0;f<=100;f+=50){
for(e=f;e<=100;e+=20){
for(d=e;d<=100;d+=10){
for(c=d;c<=100;c+=5){
for(b=c;b<=100;b+=2){n++;}
}}}}
printf("n=%d\n",n);}

Et le même code C, compilé sur un Atari ST de 1987, affiche le résultat instantanément !

Copier-Collé sauce HP39GI

Code : Tout sélectionner

EXPORT MPO34
BEGIN
 N:=1;
 FOR F FROM 0 TO 100 STEP 50 DO
 FOR E FROM F TO 100 STEP 20 DO
 FOR D FROM E TO 100 STEP 10 DO
 FOR C FROM D TO 100 STEP 5 DO
 FOR B FROM C TO 100 STEP 2 DO
  N:=N+1;
 END; END; END; END;  END; END;
END;

Intantané sur l'émulateur
Time(MPO34) -> 0,009s
. A voir avec la vraie clalc
Les variable A à Z étant des varaible globale pas de bensoin de les déclarer

[ledudu]

Salut Gilles, dprtl

Dans ces deux dernières versions, Je pense qu'il manque le test if b+c+d +e+f=100:;n:=n+1

[zpalm]

Salut Gilles, dprtl

Dans ces deux dernières versions, Je pense qu'il manque le test if b+c+d +e+f=100:;n:=n+1

Et non, pas besoin du test vu la définition des variables

C'est de l'optimisation (qui peut encore l'être)....

Sur HP-28S le calcul donne 4365 en environ 20 min.

Lexiedys?

[ledudu]

J'ai écrit ce même algo en Basic.

Première itération : b=c=d=e=f=0 et la somme vaut 0, je ne vois pas ce qui empêche de compter cette combinaison ...

Pour moi, ça reste magique. Essaye avec un print (n).

[ledudu]

J'ai compris,, il reste les pièces à 1 ct...

Ok.

Malin

[zpalm]

J'ai écrit ce même algo en Basic.

Première itération : b=c=d=e=f=0 et la somme vaut 0, je ne vois pas ce qui empêche de compter cette combinaison ...

Pour moi, ça reste magique.

Il faut la compter! En théorie il y a 7 pièces différentes donc il faudrait 7 boucles imbriquées.
La première boucle à l'extérieur pour la pièce de 1€ est remplacé par n=1 au lieur de n=0 au début:
La dernière boucle à l'intérieur pour les pièces de 1cent est inutile, en effet toute combinaison de pièces de 50c, 20c, 10c, 5c et 2c dont la somme est inférieur ou égale à 100c peut être complétée par des pièces de 1c pour arriver à 1€:

[C.Ret]

Sur HP-28S le calcul donne 4365 en environ 20 min.

Lexiedys?

Oui, très surement, et de plus catalysée par quelques rasades d'un bon grog bien trop chaud qu'il a fallu refroidir avec quelques dosettes de rhum et cuillères à soupe de sucre roux.

En plus, pour suivre l'avancement de mon programme j'avais inséré l'affichage de la liste des pièces restantes. Une fois cet affichage retiré, l'HP-28C donne 4563 (à jeun c'est plus facile) en moins de 8 min.

Code : Tout sélectionner

main(){
int b,c,d,e,f,n;
n=1;
for(f=0;f<=100;f+=50){
for(e=f;e<=100;e+=20){
for(d=e;d<=100;d+=10){
for(c=d;c<=100;c+=5){
for(b=c;b<=100;b+=2){n++;}
}}}}
printf("n=%d\n",n);}

La dernière boucle ressemble étrangement à une multiplication : compter de c à 100 par pas de 2 en incrémentant n de 1 à chaque pas ne revient-il pas à calculer n = n + INT((100-c)/2) ?

Traduction de ce code en RPN :

Code : Tout sélectionner

« 1                                 // Initialise total
  0 100 FOR a                       //  Boucle 50c
     a 100 FOR b                    //    Boucle 20c
        b 100 FOR c                 //      Boucle 10c
           c 100 FOR d              //        Boucle 5c
              102 d – 2 / FLOOR +   //          Comptages 2c et 1c
           5 STEP                   //        5c 
        10 STEP                     //      10c
     20 STEP                        //    20c
  50 STEP                           //  50c
»

Sur l’HP-28S, on obtient 4563 en moins de 12 secondes soit moins de 2s de plus que les trucs CASIO compiqulés.


Et comme il n'y a plus que quatre boucles imbriquées, cela donne un algo directement utilisable sur SHARP PC-1211 et un "one-line-shoot":

Code : Tout sélectionner

1 T=5:FOR A=0TO €2STEP 50:FOR B=ATO €2STEP 20:FOR C=BTO €2STEP 10:FOR D=CTO €2STEP 5:T=T+INT ((102-D)/2:NEXT D:NEXT C:NEXT B:NEXT A:PRINT T

80 octets (et 5 variables).
Temps de calcul : ~3min35s

Aussi vite qu'une HP-41 !!! Na!

[zpalm]

La dernière boucle ressemble étrangement à une multiplication : compter de c à 100 par pas de 2 en incrémentant n de 1 à chaque pas ne revient-il pas à calculer n = n + INT((100-c)/2) ?

Code : Tout sélectionner

              102 d – 2 / FLOOR +   //          Comptages 2c et 1c 

Je vois que tu as modifié ta formule dans le code

[Gilles59]

Dans ces deux dernières versions, Je pense qu'il manque le test if b+c+d +e+f=100:;n:=n+1

Non il ne manque rien...

L'algo de dprtl est vraiment très simple et très malin ! Et hyper rapide au passage ... je confirme qu'il donne le résultat correct, mais à vrai dire je ne comprends pas _pourquoi_ çà marche :O Je l'ai adapté 'bêtement'

Il y a là un subtilité mathématique qui m'echappe

EDIT :

La clé est celle proposée par Zpalm :

La dernière boucle à l'intérieur pour les pièces de 1cent est inutile, en effet toute combinaison de pièces de 50c, 20c, 10c, 5c et 2c dont la somme est inférieur ou égale à 100c peut être complétée par des pièces de 1c pour arriver à 1€:

Le programme génère (de façon très maline), l'ensemble des façons de construire des totaux de 0 à 100 sans prendre en compte les pièces de 1 cent. A l'évidence on peut à chaque fois compléter par des piéces de 1 (de zéro à 100 pieces) pour avoir 1 solution , donc pas besoin de test : il a y une solution forcément (et une seule) quand on arrive dans le niveau de boucle le plus bas. Et là je dis : chapeau ! ... Et C.ret en rajoute une couche en supprimant la boucle des 2 centimes ... Et pourquoi pas la boucle de 5 centimes ? Existerait il une formule qui donne directement le nombre de solutions sans boucle aucune ?