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

[zpalm]

Un petit MPO au rabais en cette période de solde, crise oblige...

Combien y a t'il de façons différentes d'obtenir 1€ en utilisant les différentes pièces existantes: 1c, 2c, 5c, 10c, 20c, 50c et 1€?

Note: on suppose qu'après avoir fait la manche on dispose d'autant de pièces de chaque sorte que nécessaire.

Sortez votre(vos) machine(s) favorite(s) et trouvez le programme le plus optimisé donnant le résultat!

[Marge]

Bonne idée ! Mais pour éviter la triche, il faudrait interdire d'aller fouiller dans la série des OP, car il s'y trouve un programme du genre. Je ne participerai pas, beaucoup de travail en cette rentrée...

[dprtl]

[EDIT] ma version naïve précédente n'avait aucun intérêt, juste bonne à bouffer les piles, avec plus de 21 millions d'itérations !

Voici un programme en C "potable" pour Casio Z-1 :

Code : Tout sélectionner

main(){
int b,c,d,e,f,B,C,D,E,F,n;
n=1;
for(f=0;f<3;f++){F=f*50;if(F<100){
for(e=0;e<6;e++){E=F+e*20;if(E<100){ 
for(d=0;d<11;d++){D=E+d*10;if(D<100){
for(c=0;c<21;c++){C=D+c*5;if(C<100){
for(b=0;b<51;b++){B=C+b*2;if(B<100){
/* a=B-100 */
n++;
} else if (B==100) {n++;}}
} else if (C==100) {n++;}}
} else if (D==100) {n++;}} 
} else if (E==100) {n++;}}
} else if (F==100) {n++;}}
printf("n=%d\n",n);beep(0);}

Résultat obtenu en 1 minute environ (le CPU du Z-1 est un x86, probablement cadencé à 3,8 MHz) : n=4563

[treza]

J'arrive au même résultat.
(J'ai triché, en utilisant un PC)
Avec <nombre de pièces utilisées> : <nombre de combinaisons possibles>
0 : 0
1 : 1
2 : 1
3 : 0
4 : 1
5 : 3
6 : 3
7 : 5
8 : 8
9 : 11
10 : 18
11 : 24
12 : 27
13 : 36
14 : 45
15 : 50
16 : 56
17 : 63
18 : 69
19 : 77
20 : 82
21 : 85
22 : 93
23 : 98
24 : 99
25 : 102
26 : 105
27 : 105
28 : 107
29 : 108
30 : 108
31 : 109
32 : 109
33 : 108
34 : 108
35 : 106
36 : 103
37 : 103
38 : 102
39 : 99
40 : 97
41 : 96
42 : 94
43 : 91
44 : 87
45 : 84
46 : 82
47 : 79
48 : 75
49 : 73
50 : 71
51 : 68
52 : 64
53 : 61
54 : 58
55 : 55
56 : 52
57 : 49
58 : 47
59 : 45
60 : 43
61 : 40
62 : 38
63 : 36
64 : 34
65 : 31
66 : 29
67 : 28
68 : 27
69 : 25
70 : 23
71 : 22
72 : 21
73 : 19
74 : 17
75 : 16
76 : 15
77 : 14
78 : 13
79 : 12
80 : 11
81 : 10
82 : 9
83 : 8
84 : 7
85 : 6
86 : 6
87 : 6
88 : 5
89 : 4
90 : 4
91 : 4
92 : 3
93 : 2
94 : 2
95 : 2
96 : 2
97 : 1
98 : 1
99 : 1
100 : 1

[C.Ret]

Bon petit excercice.

Pour répondre à cette question, j'utilise le programme NCOMB qui appèle de la fonction récursive MPART.

Seule contrainte de mon code est de devoir saisir la somme en centimes. Ainsi pour avoir le nombre de façon de composer 1€ avec un nombre illimité de pièces de 1c, 2c, 5c, 10c, 20c, 50c et 1€, il faut taper 100 [ NCOMB ] pour obtenir le résultat ...

EDIT: Attention, les codes qui suivent sont complètement faux ! Ils calculent longtemps mais ne donnent pas le résultat demandé !

Code : Tout sélectionner

« -> n k                                             // n : somme    k : nombre de pièces
   « IF n k < THEN 0                                 // impossible de composer une somme n avec plus de n pièces
     ELSE IF n k == THEN 1                           // avec les pièce de 1c on peut composer toutes les sommes (une fois)
          ELSE IF k 1 == THEN                        // cas où l'on cherche à composer la somme avec une unique pièce
                  { 1 2 5 10 20 50 100 } n POS SIGN  // n'est possible que si la pièce existe
               ELSE 
                  n 1 - k 1 -  PART                  // relation de récurrence (cf. règle de partition des entiers
                  n k - k      PART +                // p(n,k)=p(n-1,k-1)+p(n-k,k)
               END
          END
     END
   »
»
'PART' STO                                         // PART comme Partitions number


« -> s                                              // saisie somme
   « 0                                              // Initialise nombre de combinaisons
     1 s FOR k                                      // calcule nombre de combinaison à k=1,2,3, ... n pièces
        s k  PART +                                 // et l'ajoute au nombre total de combinaisons
     NEXT                                          
   »
»
'NCOMB'

Octets programmes: 172.5

Evidemment, c'est un calcul très long.

Une version un peu plus élaborée permet d'obtenir le résultat en un temps convenable en utilisant le principe de la mémoziation:

Code : Tout sélectionner

« -> n k                                             // n : somme    k : nombre de pièces
   « MDAT {n k } GET                                 
     IF DUP NOT THEN                                 // si p(n,k) n'a pas était calculé
        DROP                                         // alors on le calcule
        IF n k < THEN 0                                 // impossible de composer une somme n avec plus de n pièces
        ELSE IF n k == THEN 1                           // avec les pièce de 1c on peut composer toutes les sommes (une fois)
             ELSE IF k 1 == THEN                        // cas où l'on cherche à composer la somme avec une unique pièce
                     { 1 2 5 10 20 50 100 } n POS SIGN  // n'est possible que si la pièce existe
               ELSE 
                     n 1 - k 1 - MPART                  // relation de récurrence (cf. règle de partition des entiers
                     n k - k     MPART +                // p(n,k)=p(n-1,k-1)+p(n-k,k)
                  END
             END
        END
        DUP 'MDAT(n,k)' STO                         // et on memonize la nouvelle valeur calculée
     END
   »
»
'MPART' STO                                         // MPART comme Memonized Partitions number


« -> s                                              // saisie somme
   « 
     0                                              // Initialise nombre de combinaisons
     1 s FOR k                                      // calcule nombre de combinaison à k=1,2,3, ... n pièces
        s k MPART +                                 // et l'ajoute au nombre total de combinaisons
     NEXT                                          
   »
»
'NCOMB'

{ 100 100 } 0 CON 'MDAT' STO

Pour que cette nouvelle version fonctionne pour 1€, il faut créer la matrice carrée MDAT d'une taille au moins égale à 100.
Et l'on trouve alors qu'il y a 63 555 796 façons de composer 1€ avec ces pièces.

[dprtl]

Et l'on trouve alors qu'il y a 63 555 796 façons de composer 1€ avec ces pièces.

Je n'arrive pas à comprendre comment tu peux trouver un nombre de combinaisons aussi élevé avec 7 types de pièces ! Je suis à 4563.

[C.Ret]

[...] 3 : 0 [...]

Faut pas utiliser un PC pour ce genre de choses.

Moi, pour payer 3 centimes, je trouve deux arrangements possibles de pièces: (2c)(1c) et (1c)(1c)(1c)

Et je trouve 5 moyens de composer 6 centimes :
(5c)(1c) ; (2c)(2c)(2c) ; (2c)(2c)(1c)(1c) ; (2c)(1c)(1c)(1c)(1c) ; (1c)(1c)(1c)(1c)(1c)(1c)

Edit:
ZUT, pas bien lu !
J'avais pas compris le tableau, c'est pas 0 façons de composer la somme de trois centimes, c'est zéro façon de composer 1€ avec 3 pièces.

Du coup, je me rends compte qu'il y a un gros problème avec mon algo qui en trouve 87 !!

M'a trompé !!

[C.Ret]

Je n'arrive pas à comprendre comment tu peux trouver un nombre de combinaisons aussi élevé avec 7 types de pièces ! Je suis à 4563.

Je viens de trouver une faille dans mon raisonnement. Je dois revoir ma relation de récurrence, il est clair que je compte des plusieurs fois des combinaisons identiques !!

Aihe Aihe !

[dprtl]

Moi, pour payer 3 centimes, je trouve deux arrangements possibles de pièces: (2c)(1c) et (1c)(1c)(1c)

... et si tu arrives à faire 1€ avec 3 pièces, j'achète la formule !

[C.Ret]

Je te vends ma méthode pour 87€, c'est le nombre de façons qu'elle trouve pour composer 1€ en trois pièces (ce doit être à cause des taux de changes !).

Bon, je vais me coucher, j'ai fait et dit assez de bêtises pour aujourd'hui !

[Gilles59]

Code : Tout sélectionner

@ %DIR%=

«
 0

 0 100 FOR p100
  IF p100 100 ‰ THEN
  0 100 FOR p50
   IF  p100 p50 + 100 ‰ THEN
    0 100 FOR p20
     IF  p100 p50 + p20 + 100 ‰ THEN     
      0 100 FOR p10
       IF  p100 p50 + p20 + p10 + 100 ‰ THEN 
        0 100 FOR p5
         IF p100 p50 + p20 + p10 + p5 +  100 ‰ THEN 
          0 100 FOR p2
           IF p100 p50 + p20 + p10 + p5 + p2 + 100 ‰ THEN 
            0 100 FOR p1
              p100 p50 + p20 + p10 + p5 + p2 + p1 +
              100 == { 1 + DUP 1 DISP } IFT
            NEXT
           END
         2 STEP
         END
        5 STEP
        END
       10 STEP
      END
     20 STEP
     END
    50 STEP
   END 
  100 STEP  

»

586 octets. Oups comprendre ‰ comme <=

Même résultat pour cet alogorithme "semi naif"

Doit y a voir beaucoup mieux coté algo...J'ai du voir cela par le passé mais oublié

[C.Ret]

Bon, la nuit porte conseil, ma méthode récursive étant abondonnée, je fais comme Gille59 et dprtl par une méthode itérative.

Mais, au lieu d'accumuler les boucles FOR/NEXT, j'utilise deux vecteurs l'un contient la valeur des pièces (sauf 1€ et 1c) et l'autre sert de compteur.
Avantage de la méthode, on peut facilement changer le nombre et la valeur des pièces sans avoir à resaisir tout le code.

Code : Tout sélectionner

« 2                              // Initialise total
  [ 50 20 10 5 2 ]               // Valeur des pièces (sauf 1€ et 1c)
  DUP 0 CON                      // Mise à zero du compteur vecteur [ 0 0 0 0 0 ]
  5                              // Indice compteur (i)
  DO
    SWAP OVER DUP2 GET 1 + PUT   // Incrémente compteur au niveau de l'indice 
    ROT SWAP                     // Réarrange la pile
    IF 
       DUP2 DOT 100 <=           // Calcule la somme composée et compare avec 100
    THEN
       4 ROLL 1 + 4 ROLLD        // si <100, incrémente nombre total et sauvegarde en haut de pile
       ROT DROP 5                // Remet indice (i) à 5
    ELSE
       3 PICK 0 PUT              // sinon remet à zéro compteur à l'indice (i)
       ROT 1 -                   // décrémente indice (i) <- (i-1)
    END
  UNTIL 
     DUP NOT                     // fin de boucle quand (i<0)
  END
  3 DROPN                        // efface valeur des pièce, compteur et indice (i)
»                                      // (199 octets)                  

Sur HP-28S, le résultat 4563 est obtenu en environ 29min.

Par contre, je ne sais pas combien d'heures sur PC-1211 :

Code : Tout sélectionner

10 CLEAR :T=2,F=50,G=20,H=10,I=5,J=2,K=5
20 A(K)=A(K)+1:IF AF+BG+CH+DI+EJ<=100 LET T=T+1,K=5:GOTO 20
30 A(K)=0:K=K-1:IF K GOTO 20
40 PRINT T

[bernouilli92]

Voici ma version récursive pour hp48 :

Code : Tout sélectionner

«
  IF DUP NOT
  THEN DROP2 1
  ELSE
    IF OVER SIZE 1
==
    THEN SWAP 1 GET
MOD NOT
    ELSE  -> L M
      «
       0 0 M
L 1 GET / IP
          FOR i L
LIST-> 1 - ->LIST M
ROT i * - MPO34 +
          NEXT
      »
    END
  END
»
'MPO34' STO

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

EDIT : optimisation du code + essai sur 48gx réelle pour avoir le temps réel

EDIT : Cela fonctionne également avec les valeurs exprimées en euros : {1 0.5 0.2 0.1 0.05 0.02 0.01} 1

[Gilles59]

@bernouilli

çà marche tel quel sur 50G (mode approx) en 1mn45 (
Demain soir, je fais une version 39GII pour exploser les compteurs Je vois bien moins de 2sec avec le même algo (moins de 5 sur)

[bernouilli92]

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