Discussion :

[7ider5]

Bonjour à tous

Je développe une appli en VBA et j'aurais besoin de retrouver toutes les solutions de sommes de termes d'un nombre plus grand. exemple :

Voici mes nombre sources:
48 50 51 52 54 56 57 58 60 62 63 64

Voici le nombre à factoriser : 321

Solutions :
- 2*64+58+3*45
- 6*45+51
- 5*54+51
...

si je ne me trompe pas, cela reviendrait à trouver les solutions de :
321 = a*48 + b*50 + c*51 + d*52 + e*54 +...
sachant que le nombre à factoriser n'est jamais un nombre premier.

J'avais commencé à faire un code du genre :
NbPv=321
Nsource(12)=(48,50,51,52,54,56,57,58,60,62,63,64)

pour j = 1 à 12
si NbPv/Nsource(12-j) > 0
NbNsource = entier(NbPv / Nsource(12-j))
NbPv = NbPv - NbNsource*Nsource(12-j)
FinSi
Suivant

Mais je me retrouve avec une partie entière qui me gène.

est ce que vous avez déjà eu à faire une factorisation en somme de termes?
Quelle méthode vous semble abordable?

Merci beaucoup pour votre aide!

Pierre

[Qwazerty]

Salut
Une piste à suivre serait déjà de comprendre la résolution de ton équation polynomiale(si c'est bien ça[Edit]<- heureusement que je l'avais mis celui la!!^^ parce que visiblement j'ai fait fausse route[/Edit]), ensuite convertir le raisonnement en code... bon courage

Une autre piste, ce site qui fourmille d'algo de toutes sortes
A++
Qwaz

[pgz]

Bonjour.

Les coefficients a, b, c, ... sont des varaiables. Dans ton exemple il y en a 12, et une seule équation. Cela veut dire qu'il y a entre 0 et n solutions, n ne ne pouvant être calculé simplement.

Voici une idée de méthode, qui peut suivant les cas conduire à des calculs trop longs et qui ne marche que si tu cherches des coefficients positifs.
Tu crées un tableau des "valeurs sources", et un tableau des coef, éventuellement le même avec 2 colonnes.

si NbPv = a*S1 + b*S2 + ..., alors a<= int(Nbpv/S1)
Tu peux ainsi calculer aMax, bMax, ... valeurs à enregistrer dans le tableau des coef.

Il reste à faire :
Pour a = 0 à aMax
Pour b = 0 à bMax
Pour c ...
...
si NbPv = a*S1 + b*S2 + ... alors
'ici j'ai une solution
fin si
....
c suivant
b suivant
a suivant

Reste à voir où tu ranges toutes les solutions...

Cordialement,

PGZ

[pgz]

Bonjour Quaz.

Je crois qu'il ne s'agit pas d'un polynome.

Cordialement,

PGZ

[Qwazerty]

Salut Pgz

Bonjour Quaz.

Je crois qu'il ne s'agit pas d'un polynome.

Cordialement,

PGZ

A ca... c'est loin dêtre impossible

[Edit]
Ceci étant dit, il y a bien matière a résolution avec une fonction de type
48a+50b+26c+... j'avoue humblement, que les maths, même si je ne les détestais pas, elles, elles n'ont visiblement jamais eu d'attirance pour moi ^^

Le problème avec les méthode brute comme celle que tu proposes, c'est qu'il faut prévoir le café ou manipuler les intégrales si mes souvenirs sont bons :s
[/Edit]

[7ider5]

Bonjour à vous,

Merci pour vos réponses, pgz, c'est une solution que je vais essayer de développer, effectivement, ça va être assez lourd.
Une méthode peut être proche serait d'y aller par brute force : définir des valeurs de 1 à 10 par exemple et tester les sommes de produits qui sont égales à la valeur cible.
Une autre solution qu'on m'a suggéré, serait d'utiliser l'algorithme du simplexe, que je ne connais pas encore, je vais m'y pencher.

Merci encore

Cordialement,

Pierre

[pgz]

Re,

Je ne crois pas que ce soit un développement lourd.
Si tu reviens demander de l'aide, il faudra préciser

• Où et comment est saisi NbPv
• Où et comment sont saisis les nombres sources
• Si le nombre de nombres sources est variable
• Où sont rangées les solutions

Bon courage,

PGZ