Trouver une formule d'addition

Bonjour,

J'ai le problème suivant:
J'ai deux colonnes A et B de nombres réels et un nombre C (réel aussi):

Code:

---

1 2 3 4 5 6 7 8

ligne A B 1 5.5 3.2 2 1.05 6.1 3 0.6 7.8 4 6.4 4.13   C = 8.98

---

L'objectif est que l'algorithme me fournisse la formule qui a mené au nombre C
qui est, dans cet exemple:

Code:

---

1 2	C = B(1) + A(2) + A(3) + B(4) = 3.2 + 1.05 + 0.6 + 4.13 = 8.98

---

sachant qu'on ne peut prendre qu'un nombre par ligne (un des deux colonnes).

Merci d'avance pour tout bout de réponse (ou toute réponse!).

;)

Il faut partir de la formule d'addition que tu donne?

Bonjour,
merci pour ta réponse.
Non, justement, cette formule il faut la trouver.

En entrées, on a les colonnes A et B et puis le total C.

En sortie, il nous faut la formule qui a mené au nombre C qui est le total des éléments de .A et B sachant qu'on doit pas prendre deux éléments de la même ligne, donc pas de A(1) + B(1) .

Merci d'avance

Plus de précisions:

Code:

---

1 2 3 4 5 6

Entrées: Sorties: colonne A---> colonne B---> ---> Quels nombres de A et B on contribué nombre C---> à obtenir le nombre C sachant qu'on ne peut prendre qu'un nombre par ligne.

---

Merci d'avance

Tes nombres sont forcément positifs ?

Salut!
Premièrement, rien ne prouve ni que la solution existe, ni qu'elle existe.

Deuxièmement, à ta place, j'essaierais en considérant les nombres comme des chaînes de caractères. Tu regardes d'abord les chiffres correspondant aux centièmes, soit 5 pour A(2), 3 pour B(4) et 8 pour C; tu en déduis que A(2) et B(4) doivent figurer dans ta formule. Et ainsi de suite...
Jean-Marc Blanc

Voilà un script Python qui résout ce problème:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

A=[5.5,1.05,0.6,6.4] B=[3.2,6.1,7.8,4.13]   def PartiesDe(E): P=[[]] yield P while E: P=[x+[a] for x in P for a in E if all(a>y for y in x) ] yield P return   def Eval(X,K): L=[K[i] for i in X] return 0 if L==[] else reduce(lambda x,y:x+y,L)   def EvalAB(C): return Eval(C[0],A)+Eval(C[1],B)   def main(): E=[0,1,2,3] P=PartiesDe(E) L=[] for i in range(0,len(E)): L+=P.next() M=[ [X,Y] for X in L for Y in L if not any ([x in Y for x in X])] R=[Z for Z in M if EvalAB(Z)==8.98] print R   if __name__ == '__main__': main()

---

Citation:

---

Envoyé par Vakhyw

Tes nombres sont forcément positifs ?

---

Bonjour,
ils sont pas forcément positifs.
Tu penses que ça pourrait changer quelque chose?

Bonjour Zavonen,
merci pour ton programme en Python.
J'avoue que je ne connais pas ce langage mais je prendrai le temps d'étudier ton code dimanche.
Merci!

Re,
Par contre, y a-t-il un moyen pour généraliser le cas? ça veut dire au cas où le résultat est composé de N valeurs:

Code:

---

1 2	C := A(1)||B(1) + A(2)||B(2) + ... + A(N-1)||B(N-1) + A(N)||B(N)

---

Merci d'avance!

Sans aucun problème !
La méthode est la suivante:
Je considère l'ensemble de tous les indices des suites A et B.
Je construis l'ensemble de ses parties. Attention 2^n éléments, ça va vite.
Ensuite je fais le produit cartésien de cet ensemble par lui-même, mais en ne gardant que les couples de parties pour lesquelles on ne retrouve jamais le même élément dans les deux.
puis pour tout tel couple (X,Y) je calcule la somme des Ai pour i dans X + la somme des B(j) pour j dans Y et je regarde si je trouve le résultat espéré.
Tu peux généraliser à 3.
Au lieu de prendre un produit cartésien de 2 ensembles de parties tu auras un produit cartésien de 3 ou de 4.
mais attention à l'explosion !!! 2^n x ....x2^n p fois cela fait 2^np .
Cette méthode est 'bourine'. On pourrait l'optimiser si tous les coefficients étaient de même signe et/ou ordonnés.

Ton problème est en fait très classique, il s'agit de l'algorithme du sac à dos (à la base de RSA).

Voici un lien wiki où tu trouvera des solutions plus ou moins optimisées :

!!! Super lien de la mort !!!

Cordialement, BG

Re,

Merci Zavonen ... rien à dire!