Ligorin
Messages postés3Date d'inscriptionvendredi 19 juin 2009StatutMembreDernière intervention21 juin 2009
-
19 juin 2009 à 20:58
Ligorin
Messages postés3Date d'inscriptionvendredi 19 juin 2009StatutMembreDernière intervention21 juin 2009
-
21 juin 2009 à 21:09
Bonjour,
je souhaiterai avoir votre aide,en langage C ,sur le problème de monnaie,en générale.
Soit a+4b+6c=8. Objectif : Min a+b+c
La solution existe si pgcd (1,4,6) divise 8.C'est le cas de cette équation.
[ Il faut tout d'abord programmer le pgcd de trois nombres...]
Par l'algorithme de Glouton,
on c=1,b=0,et a=2;ce qui fait 3.
Mais la solution optimale,c'est a=0,b=2,c=0;ce qui fait 2.
[Ensuite programmer la solution optimale] .Merci d'avance.
Ligorin
Messages postés3Date d'inscriptionvendredi 19 juin 2009StatutMembreDernière intervention21 juin 2009 21 juin 2009 à 20:54
Il est vrai que je suis débutant,mais de là à penser que je ne fais "aucun effort",ça me parâit déplacé et injustifié...
J'ai un problème,et j'essaie de savoir si certains ont des tuyaux ,des indices,des astuces,une méthode de résolution (ou un programme) afin de trouver la solution...
/*j'ai réussi à implémenter l'algorithme de Glouton,mais je me demande s'il y'a un moyen de résoudre ce problème avec une solution optimale pour tous les cas... */
Ligorin
Messages postés3Date d'inscriptionvendredi 19 juin 2009StatutMembreDernière intervention21 juin 2009 21 juin 2009 à 21:09
Trier les valeurs dans un tableau ne suffit pas.
Je pense qu'il faudrait réaliser toutes les permutations du tableau (ou des coefficients de a,b et c) et caculer à chaque fois le Z(Z=a+b+c) de chaque permutation...Puis choisir le le plus petit z=min Z.
Mais ça me semble difficile de l'implémenter en C? Vous chosirez plutôt des pointeurs ou des tableaux pour faire celà...