Tester si sommes correspondantes

**ToxiK** · 27/07/2012, 18h21

Bonjour,

cet après-midi je ne suis pas en forme et je suis bloqué sur la réalisation d'un petit algo...

Alors c'est un test sur les sommes,

il faudra que je trouve dans une liste avec N éléments toutes les additions possibles entre les nombres de cette liste qui soient égale à la valeur X.

Ensuite il faudra que je le mettre en place avec deux listes de N éléments, et tester pour chaque somme possible dans la liste 1, il y a une somme égale dans la liste 2.

Invité · 28/07/2012, 01h35

salut,

ta première question rappèle le classique jeu "le compte est bon" sauf que tu n'es muni que de l'opération addition.

L'idée, c'est que tu prends deux nombres dans ta liste. (et tu fais pour tous les couples de deux nombres possibles)
Tu fais la somme.
Si ta somme est inférieure à N, tu replaces ce nouveau nombre à la place des anciens, et tu réitères
Si ta somme est supérieure à N, tu t'arrêtes.
Sinon (elle est égale à N), t'as trouvé une liste de sommes à faire.

Concernant ta deuxième question. Tu peux par exemple (à commutativité pres) trier les nombres de ta somme et écrire dans un vecteur :
valeurDuNombre, nbOccurrences, valeurDuNombre2,nbOccurrencesDuNombre2, ...
et comparer avec ton autre somme

**ToxiK** · 30/07/2012, 13h38

Salut,

j'ai toujours du mal à trouver l'algo oO

En fait je veux récupérer toutes les sommes possibles avec N nombres de ma liste.

Invité · 30/07/2012, 16h43

Qu'est-ce que tu n'as pas compris dans ce que j'ai dis?

**ToxiK** · 30/07/2012, 19h09

Et bien je n'ai pas besoin de savoir si la somme est inférieure ou supérieure ou égale.

Si j'ai 4 nombres, je dois récupérer toutes les sommes possibles :

A
A+B
A+B+C
A+B+C+D
B
B+C
B+C+D
C
C+D
A+C
etc....

Invité · 30/07/2012, 19h11

ben t'as quand même écrit que ta somme devait valoir X non?

**ToxiK** · 30/07/2012, 20h02

Ha oui pardon, je me suis perdu dans les explications. Mais au final dans le deuxième cas, j'ai besoin de tester chaque somme possible dans une liste, avec chaque somme possible dans l'autre liste.

Du coup il faut que je parte sur un algo qui me permettent de récupérer toutes les sommes possibles avec les nombres d'une liste.

**pseudocode** · 30/07/2012, 20h10

Envoyé par ToxiK

Ha oui pardon, je me suis perdu dans les explications. Mais au final dans le deuxième cas, j'ai besoin de tester chaque somme possible dans une liste, avec chaque somme possible dans l'autre liste.

Du coup il faut que je parte sur un algo qui me permettent de récupérer toutes les sommes possibles avec les nombres d'une liste.

L = {X1, X2, X3, ..., Xn}, une liste à N éléments.

Les sommes s'écrivent toutes sous la forme : (0 ou 1)*X1 + (0 ou 1)*X2 + ... + (0 ou 1)*Xn.

Le problème revient donc a trouver toutes les séquences possibles de N valeurs 0 ou 1. C'est à dire trouver toutes les séquences binaires de N éléments. C'est à dire toutes les valeurs à N bits...

Par exemple, il suffit de compter de 0 à (2^N)-1 et de regarder la représentation binaire.

Invité · 30/07/2012, 21h10

Le problème revient donc a trouver toutes les séquences possibles de N valeurs 0 ou 1.

ok

C'est à dire trouver toutes les séquences binaires de N éléments.

ok a supposer qu'on teste que la correspondance vaut bien X

C'est à dire toutes les valeurs à N bits...

de fait je ne te suis plus.

Par exemple, il suffit de compter de 0 à (2^N)-1 et de regarder la représentation binaire.

si je prends 0. Sa rep binaire est 0000...0
quelle information cela m'apporte-t-il?

Je pense que je te comprends mal. Si tu peux étayer

**pseudocode** · 30/07/2012, 23h34

Envoyé par galerien69

ok

ok a supposer qu'on teste que la correspondance vaut bien X

de fait je ne te suis plus.

si je prends 0. Sa rep binaire est 0000...0
quelle information cela m'apporte-t-il?

Je pense que je te comprends mal. Si tu peux étayer

0 (décimal) = 00..0000 (binaire) ---> S0 = 0*X1 + 0*X2 + 0*X3 + ... + 0*Xn
1 (décimal) = 00..0001 (binaire) ---> S1 = 1*X1 + 0*X2 + 0*X3 + ... + 0*Xn
2 (décimal) = 00..0010 (binaire) ---> S2 = 0*X1 + 1*X2 + 0*X3 + ... + 0*Xn
3 (décimal) = 00..0011 (binaire) ---> S3 = 1*X1 + 1*X2 + 0*X3 + ... + 0*Xn
...
k (décimal) = 11..1111 (binaire) ---> Sk = 1*X1 + 1*X2 + 1*X3 + ... + 1*Xn

avec k = (2^N)-1

Invité · 31/07/2012, 00h08

@pseudocode,

ouioui, j'ai bien compris la représentation.
Mais en quoi ca permet de dénombrer les sommes qui valent X.
Tu comptes pas tester les 2^n valeurs non?

edit:edit2:ok

**pseudocode** · 31/07/2012, 00h30

Envoyé par galerien69

@pseudocode,
ouioui, j'ai bien compris la représentation.
Mais en quoi ca permet de dénombrer les sommes qui valent X.
Tu comptes pas tester les 2^n valeurs non?

Bah si. Pas d'autre moyen (simple) de trouver toutes les sommes possibles de la liste comme le demande ToxiK.

Après on peut partir sur les algos dynamiques du "subset sum problem", mais c'est peut être trop compliqué vu l'énoncé du problème/exercice.

Invité · 31/07/2012, 00h56

ben dans ce cas là, ta méthode est pas optimisée (sans parler de sous division).
On peut au moins s'arrêter (de compléter la séquence) avant d'aller plus loin une fois qu'on a dépassé le compte (supposant que les nombres sont positifs).

**pseudocode** · 31/07/2012, 09h27

Envoyé par galerien69

ben dans ce cas là, ta méthode est pas optimisée (sans parler de sous division).
On peut au moins s'arrêter (de compléter la séquence) avant d'aller plus loin une fois qu'on a dépassé le compte (supposant que les nombres sont positifs).

C'est clair que ce n'est pas du tout optimisé. C'est la méthode naive pour parcourir l'espace des solutions.

**Aleph69** · 31/07/2012, 10h27

Bonjour,

il doit y avoir quelques astuces simples pour optimiser. Par exemple, si la somme S est pair, elle s'écrit S=X+Y avec X et Y de même parité. Si elle est impaire, X et Y sont de parités différentes. Si tu te restreins à la somme d'entiers naturels, X et Y sont nécessairement inférieurs ou égaux à S, etc.

**Alexis.M** · 31/07/2012, 10h41

Dans un problème combinatoire il est rare d'avoir beaucoup mieux qu'une exploration complète.

La méthode la plus rapide sera une exploration par arbres avec élagage (par exemple si la somme courante est déjà supérieure a X tu ne continues pas l'exploration.

Tu dois aussi pouvoir accélérer la recherche en triant tes N nombres par ordres croissant, et en les explorant toujours dans cet ordre comme ça si

en ajoutant un nombre à la somme courante tu dépasses X, tu sais qu'il est inutile d'explorer les suivants.

C'est déjà mieux que de tout tester...

**Aleph69** · 31/07/2012, 11h03

Si tu trouves deux nombres X et Y qui sommés donnent S, alors toutes les autres solutions (X',Y') se sommant en S seront telles qu'il existe un entier relatif Z satisfaisant à X'=X+Z et Y'=Y-Z :
S = X+Y = (X+Z)+(Y-Z) = X'+Y'.
Dès lors, la question est en fait de savoir quels sont les couples (X,Y) et (X',Y') qui sont "Z-connectés". Il s'agit d'une relation d'équivalence. C'est intéressant car cela permet de déterminer ces connections de façon plus rapide par transitivité. Tu peux également profiter de l'antisymétrie suivante : si (X,Y) et (X',Y') sont Z-connectés, alors (Y,X) et (Y',X') sont (-Z)-connectés. Ainsi, dans ta recherche des connections, tu peux te restreindre au cas X<Y. Le cas particulier X=Y est évidemment trivial.

Si tu arrives à trouver un algorithme performant pour déterminer ces connections, alors il te suffira de chercher une solution particulière (X,Y) pour ensuite déterminer rapidement les autres solutions (X',Y'). Le comportement de la première étape est assez similaire à celui d'un tri, le cas le pire étant celui où aucune solution n'existe.

**ToxiK** · 31/07/2012, 12h23

Bonjour,
merci à tous pour vos réponses, pour l'instant je n'ai rien optimisé mais j'ai réussi à faire ce que je voulais.

J'ai suivi l'idée de pseudocode d'utiliser les séquences binaires.

Code :

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
nNbrElements : nbr d'éléments de mon tableau
 
nNombrePossibilites  = (2^nNbrElements)-1
 
nLongueurValeurBinaire = ValeurBinaire(nNombrePossibilites)
 
// Pour chaque possibilitée
POUR j = 1 A nNombrePossibilites
 
	moSomme = 0
 
	sValeurBinaire = ValeurBinaire(j)
 
	// Pour chaque élément du tableau
	POUR i = 1 A nNbrElements
 
		moSomme += sValeurBinaire[i] * monTableau[i]
 
	FIN
 
	Afficher : moSomme et sValeurBinaire
 
FIN

En fonction des cas, il reste à trier les tableaux, puis stopper la boucle si on dépasse la somme recherchée, comparer les sommes égales de deux tableaux, etc...

Invité · 31/07/2012, 12h24

@Aleph69
ce que tu dis ca se rapproche pas mal dun dynamique.

Ca revient a ecrire pour une somme donnee la liste des sous somme (a deux deux nombres) possibles.

En effet, donnes 4 nombres A,B,C,D
le test de Z connection de (A,B); (C,D)
est donne par A+B==C+D
autrement dit le stockage de linformation de la Zconnection equivaut a stocker la liste des sommes de meme (sous-)total.

malheureusement, on ne peut pas se permettre de proceder ainsi, car si on denote S=S1+S2 avec S1 qui contient 3+4 et S2 qui vaut 3+5 avec la liste [3,4,5], alors 3 est employe deux fois.

**Aleph69** · 31/07/2012, 13h10

Envoyé par galerien69

malheureusement, on ne peut pas se permettre de proceder ainsi, car si on denote S=S1+S2 avec S1 qui contient 3+4 et S2 qui vaut 3+5 avec la liste [3,4,5], alors 3 est employe deux fois.

J'ai du mal comprendre le problème. Je pensais ce cas impossible puisque S1=7 n'est pas dans la liste [3,4,5]. Si on autorise des sommes de plus de deux nombres de la liste, le problème devient extrêmement compliqué.

Tester si sommes correspondantes

Algorithmes et structures de données

Discussions similaires

Partager

Partager