Version imprimable
Salut.
Je dois résoudre un problème d'algo :
Combien de possibilité y a t il dans un pays avec système de pièces avec des valeurs 2,5,9,13 cent de payer les montants 0,1,10,101,1010,10101,101010,1010101,10101010 et 101010101.
Comment dois je m'y prendre
Merci
une solution bien bourrin avec quadruple boucle devrait faire l'affaire :
Citation:
n=10101 // par exemple
NbSoluce=0
for i=0 to n/2 for j=0 to n/5 ... if (i*2+j*5+...)=n then NbSoluce=NbSoluce+1 ;
L'utilisation des nombres premiers devrait t'être d'une grande aide.
Tu commence par prendre tous les nombres premiers composants tes pièces de monnaie. Ici ce serait (2,5,3,13). Grâce à cette technique, tu saura rapidement si oui ou non une composition est possible. Ensuite tu construis un simple graphe de toutes les possibilités. Par exemple si tu a un jeu de pièces (2,5,3,9,13), il est évident qu'a chaque fois que tu trouve un 2 pendant ta décomposition, cela ne peut être qu'une pièce de 2. Un 3 c'est soit une pièce de 3 ou de 9...
En éliminant les DeadEnds, tu devrais pouvoir construire un graphe de toutes les possibilités.
Cela ressemble beaucoup à ce que ferait un compilateur (cf: automates cellulaires):)