Discussion :

[b_zakaria]

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 :

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

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 :

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

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!).

[vierax]

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

[b_zakaria]

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

[b_zakaria]

Plus de précisions:

Code :

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

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

[Vakhyw]

Tes nombres sont forcément positifs ?

[FR119492]

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

[Zavonen]

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

Code Python :

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

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()

[b_zakaria]

Tes nombres sont forcément positifs ?

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

[b_zakaria]

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!

[b_zakaria]

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 :

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

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

Merci d'avance!

[Zavonen]

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.

[Leonhart]

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

[b_zakaria]

Re,

Merci Zavonen ... rien à dire!