PROLOG n'est pas rapide, mais il a bien d'autres avantages.
La remarque concernant la convergence des algorithmes est pertinente. Trouver une expression générale n'est pas facile, sauf effectivement pour les sommes composée à partir des pièces de 2c et 1c.
Les cas où s'ajoutent les pièces de 5c peuvent aussi être formalisés. On peut donc théoriquement économiser encore une des boucles emboîtées. A chaque fois que l'on ajoute une pièce de 5c, le nombre de combinaisons de pièce de 2c et 1c pour atteindre 1€ (c'est à dire 100c) diminue de 2.5 en moyenne:
Code : Tout sélectionner
Nb 5c: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Somme composée: 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Somme restante: 100 95 90 85 80 75 70 65 60 55 50 45 40 35 30 25 20 15 10 5 0
Combinaisons 2c 1c: 51 48 46 43 41 38 36 33 31 28 26 23 21 18 16 13 11 8 6 3 1
Cette suite est facilement programmable par exemple en utilisant l’arrondi INT(s/2.5).
Mais l’on peut faire disparaitre les autres boucles (celles des pièces 10c, 20c et 50c). En effet, les valeurs des pièces restantes sont toutes les trois multiples de 5c. Ce qui veut dire que quoi qu’il arrive, la suite de combinaison des pièces de 2c et 1c est toujours la même, quelque soit la composition des pièces de 5c, 10c, 20c ou 50c, au moment de calculer le nombre de combinaison on aura nécessairement affaire à l’une des 21 valeurs ci-dessus.
On peut donc, considérablement simplifier le problème en « factorisant » la décomposition.
En effet, chaque combinaison va être répétées un certains nombre de fois qui dépend directement du nombre d’arrangement possible des pièces de 5c, 10c, 20c et 50c pour composer la somme.
Or, trouver le nombre d’arrangement possible pour former une somme S avec les pièces { 5c 10c 20c et 50c}, cela ne revient-il pas à rechercher les combinaisons de pièces de [ 1x 2x 4x 10x ] pour former S/5 ?
De plus, ce nombre d’arrangement sera le même entre les somme D multiples de dix et D+5, car le arrangement possibles sont strictement identiques et ne diffèrent que par l’adjonction d’une pièce de 5c.
Code : Tout sélectionner
Nb 5c: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Somme composée: 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Somme restante: 100 95 90 85 80 75 70 65 60 55 50 45 40 35 30 25 20 15 10 5 0
Combinaisons 2c 1c: 51 48 46 43 41 38 36 33 31 28 26 23 21 18 16 13 11 8 6 3 1
Arrangements
avec 5c: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
avec 10c: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
avec 20c: 1 1 2 2 5 5 6 6 9 9 12 12 16 16 21 21 35
avec 50c: 1 1 2 2 4 4 6 6 8 8 13
TOTAL: 1 1 2 2 4 4 6 6 9 9 13 13 18 18 24 24 31 31 39 39 49
45631 = 51x1 + 48x1 + 46x2 + 43x2 + 41x4 + 38x4 + 36x6 + 33x6 + 31x9 + 28x9 + 26x13 _
+ 23x13 + 21x18 + 18x18 + 16x24 + 16x24 + 13x24 + 11x31 + 8x31 + 6x39 + 3x39 + 1x49.
D’où ma proposition pour un code n’utilisant qu’une seule boucle (allant de 0 à 20) parcourant les 21 combinaisons.
Code : Tout sélectionner
1 T=2,A=1,B=48,C=10,F=0:FOR D=0 TO 20
2 T=T+B*INT A,A=2.5+A,F=F+1:IF F LET C=C-(D<>16),B=B-C,F=-1
3 NEXT D:PRINT T
J’obtiens ainsi le résultat en moins de 20 s sur SHARP PC-1211 (pour 86 octets et 6 variables).
Et en moins de 4s sur HP-28C avec 183 octets :
Code : Tout sélectionner
« 2 (2.5,-10) (1,48)
0 20 FOR d
ROT OVER C->R SWAP IP * +
ROT
IF
d 2 MOD
THEN
ROT OVER RE
ELSE
IF d 16 =/= THEN i ->NUM + END
ROT OVER
END
+
NEXT
DROP2
»
183 octets
Il reste encore de quoi optimiser !
Par ailleurs, cet algorithme ne me satisfait pas, car il n’est pas paramétrique. J’aurais préférer trouver quelque chose qui prenne en argument la somme 100 et la liste des pièces pour en déduire le nombre de combinaisons.
Par exemple, nous avons calculé le nombre de combinaisons pour obtenir 1€. Mais qu’en est-il du nombre de combinaisons pour 1£ ou 1$ sachant que dans ces monnaies, les pièces de 20c n’existent pas, mais que par-contre, il y a des pièces de 25c et 75c ?
Cela dit le sujet m'a trotté dans la tête et m'a donné l'occasion de tester ma toute nouvelle TI-92+ dans la salle d'attente du médecin ce matin. J'avais apporté le gros manuel car j'avais oublié les structures de contrôle 