Algo en n^(log10(2))*log10(n)???
Bonjour,
je viens avec la solution que j'ai trouvée...
Je ne suis pas expert, donc bon, il y a peut-être une erreur mais je ne pense pas.
Je vais essayer d'expliquer le principe de mon algorithme:
Quand on rends des pièces, le risque le plus grand de ne pas pouvoir rendre les pièces est l'absence de petite monnaie.
Ainsi, si je dois rendre un Euro et un centime, et que je n'ai pas de pièces de 1-2 centimes, c'est raté!
Donc pour pouvoir rendre la monnaie, il faut déjà pouvoir éliminer les unités de centimes pour n'avoir que des dizaines de centimes.
Il y a deux possibilités lorsqu'on veut éliminer des unités de centimes: soit on ramène directement à la dizaine la plus proche (28 centimes - 8), soit à la dizaine suivante (28 centimes - 18), mais avec des pièces différentes (c-à-d des pièces présentes dans le passage 28->20 ne le sont plus dans le passage 28->10), les autres possibilités ne sont pas intéressantes (on peut s'y ramener en enlevant des des dizaines par 2*5 ou 5*2 centimes)
Si on prend l'exemple de 21:
Code:
1 2 3
|
21 = 20 + 1
21 = 10 + 5 + 3*2 |
Le problème est encore présent aux étages supérieurs: dizaines de centimes, euros, dizaine d'euros.
A chaque étage il faut envisager deux possibilités (passage à la prochaine dizaine, ou à la suivante), et il y a min(5, log10(n)) étages.
Une fois qu'on est monté tout en haut: On réduit au maximum le nombre de centaines d'euros en utilisant des centaines d'euros, puis le nombre de dizaines d'euros en utilisant des 10aines d'euros, ....
Ces réductions se faisant chacune en un temps constant sur un étage, elles prennent un temps de l'ordre de min(5, log10(n)) pour tout un parcours (il y a 2^(min(5, log10(n))) parcours)
Ainsi l'algorithme prends 2^(log10(n)) * log10(n) en temps, soit n^(log10(2))*log10(n).
Ceci dans le pire des cas, il peut y avoir moins de 2^log10(n) parcours, et à partir de n = 10000, le temps n'augmente plus...
Comment réduire ??
Considérons le cas où on a un nombre x de centimes, on enlève d'abord les pièces de 5 centimes au maximum. Si on a une pièce de 1 centime en réserve, on peut toujours se ramener à un nombre pair et finir avec des pièces de 2. Sinon, si le nombre sur lequel on est est impair, on reprend une pièce de 5 (si possible) de ce qu'on a enlevé, puis on achève par pièces de 2 et pièces de 1.
Je l'ai testé, il marche à priori dans tous les cas, mais il y a sûrement moyen de réduire l'espace de stockage utilisé (par exemple avec l'allocation dynamique).
C'est une récursion de profondeur log(n), où chaque fonction invoque dans le pire des cas deux fois elle-même. (pour celles qui remontent vers les étages supérieurs)
La complexité de l'algo est max( n^(log10(2))*log10(n), 10000^(log10(2))*log10(10000) ), car à partir de n= 10000, l'algo s'exécute en un temps constant.