Discussion :

[Mourad]

je précise que ce n'est pas un système linéaire ici on a qu'une seule équation comme donnée le problème c'est de trouver ttes les solutions possibles à cette équation qq'un peut-il m'aider là dessus c urgent je cherche à réaliser l'algorithme permettant de parvenir à ttes les solutions possibles

[borisd]

Ton équation a des particularités spéciales (fonction continue, différentiable, intervalle de recherche borné... ?)

[Mourad]

ben voilà elle a la forme suivante
A.X1 + B.X2 + ... + Y.Xn = TOTAL

TOTAL et X1, ..... Xn sont connus et sont des paramètres en entrée pour l'alogorithme
maintenant comment faire pour trouver toutes les solutions possibles càd : A, B .....et Y

et tt ceci se passe ds N ts des entiers positifs

[borisd]

Ta fonction est linéaire discrète donc ?
Une solution brutale est d'utiliser un algo de programmation dynamique (ici de complexité pseudo-polynomiale a priori).
Ton problème est vaguement similaire au problème de sac-à-dos en nombre entiers, sauf que toi tu n'as pas de fonction économique et tu as une égalité au lieu d'une inégalité.
En gros, tu énumères toutes les valeurs possibles :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
reste <- TOTAL
- choisir une valeur entière pour A (tu as le choix entre 0..E(TOTAL/X1)) ; reste<-reste-A
- choisir une valeur entière pour B (tu a le choix entre 0..E(reste/X2))
-...
- faire pareil pour les autres variables ; si tu as l'égalité, tu ajoutes la solution aux possibles
- tu reviens en arrière en passant à une autre valeur possible pour chacune des variables

Tu peux améliorer la méthode en t'arrêtant quand reste<min(Xk,...,Xn), ou des règles simples de ce genre.
Cette méthode a des chances de fonctionner si TOTAL/min(X1,...,Xn) est assez petit et que n aussi.

[Mourad]

à vrai dire c'est la première fois que j'entends parler de ce problème du sac à dos...
j'ai pas trop saisi ton explication mais je vais réfléchir là dessus...
merci

[FrancisSourd]

Ton problème est NP-complet donc il est difficile d'espérer mieux qu'un algo pseudo-polynomial. Comme borisd, la programmation dynamique me semble tout à fait adaptée. Voici un algo possible:
J'utiliserais une tableau T de TOTAL booléens initialisés à false. T[i] est mis à true lorsqu'on sait qu'on peut atteindre i.
A l'étape k, on met à true les totaux qui peuvent être atteint à l'aide des nombres x[1]....x[k]
Pour cela:
A l'étape 0 on met T[0] à true et les autres T[i] à false.

A l'étape k, pour chaque T[i] true, on met à true les valeurs T[i+x[k]], T[i+2x[k]], T[i+3x[k]]....

Si, à la fin de l'étape, n T[TOTAL] est true, c'est qu'il existe un solution. Pour la retrouver, il faut faire le fameux "parcours arrière" de la programmation dynamique (si tu ne connais pas, n'hésite pas à regarder un bouquin du style Cormen: c'est très bien expliqué).

[Freyja]

je précise que ce n'est pas un système linéaire ici on a qu'une seule équation comme donnée le problème c'est de trouver ttes les solutions possibles à cette équation qq'un peut-il m'aider là dessus c urgent je cherche à réaliser l'algorithme permettant de parvenir à ttes les solutions possibles

La ponctuation coûte cher ??

Désolé pour ce message inutile... Mais j'ai eu un peu de mal...

[Mourad]

@Freyja pourtant on apprend à ponctuer dès l'école primaire :p
Donc considères ça, comme un exercice pour toi
à+

[Freyja]

@Freyja pourtant on apprend à ponctuer dès l'école primaire :p
Donc considères ça, comme un exercice pour toi
à+

ghein ? je ne comprend pas ton message.

Ce n'est pas une raison d'aller jusqu'à écrire en langage sms juste pour nous donner du travail de décodage !!!