Discussion :

[gilles81]

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

[Graffito]

une solution bien bourrin avec quadruple boucle devrait faire l'affaire :

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 ;

[lcfseth]

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)