Somme d'entiers

Bonjour,
Je dispose d'une suite d'un certain nombre d'entiers aléatoires inférieurs ou égaux à 100.
Je dois déterminer s'il est possible de regrouper un certain nombre de .. nombres parmi ceux de la liste dont la somme serait égale à la demi-somme de tous les éléments de la liste ... Quelqu'un as-t-il une autre idée que d'essayer tous les cas ? J'ai déja trouvé quelques cas particuliers pour faciliter les recherches, mais rien de bien efficace ... Merci d'avance

Le plus grand avec le plus petit, puis le plus grand avec le deuxième, avec le troisième .. jusqu'a ce que ca depasse la moitié, ensuite tu prend l'avant dernier et tu recommence et ainsi de suite jusk'a ce ke le plus grand nombre restant soit plus petit que le quart de la liste.

C'est un peu plus rapide que de tous les tester mais il y a surment moyende faire mieux ...

===============================

Funcky

===============================

On dit que seulement dix personnes au monde comprenaient Einstein. Personne ne me comprend. Suis-je un génie ?



-------------------------------
Réponse au message :
-------------------------------

> Bonjour,
> Je dispose d'une suite d'un certain nombre d'entiers aléatoires inférieurs ou égaux à 100.
> Je dois déterminer s'il est possible de regrouper un certain nombre de .. nombres parmi ceux de la liste dont la somme serait égale à la demi-somme de tous les éléments de la liste ... Quelqu'un as-t-il une autre idée que d'essayer tous les cas ? J'ai déja trouvé quelques cas particuliers pour faciliter les recherches, mais rien de bien efficace ... Merci d'avance

Je peux déja vous donner les quelques conditions que j'ai trouvé ... ça peut aider ...

Si le nombre d'entiers est impair, alors c'est impossible.
Si il y a un nombre impair d'entiers pairs, alors c'est impossible.
Si le plus grand entier de la liste est plus grand que la demi-somme totale, alors c'est impossible.
Si la somme de deux entiers est plus grande que la demi-somme totale, alors un seul de ces entiers est dans le groupe.

Bon voila, rien de révolutionnaire, mais encore fallait-il le dire ..

Bein alor, t'as qua appliker ces conditions à ce ke j'ai mis, la ca devrait etre tout bon non ???

===============================

Funcky

===============================

On dit que seulement dix personnes au monde comprenaient Einstein. Personne ne me comprend. Suis-je un génie ?



-------------------------------
Réponse au message :
-------------------------------

> Je peux déja vous donner les quelques conditions que j'ai trouvé ... ça peut aider ...
>
> Si le nombre d'entiers est impair, alors c'est impossible.
> Si il y a un nombre impair d'entiers pairs, alors c'est impossible.
> Si le plus grand entier de la liste est plus grand que la demi-somme totale, alors c'est impossible.
> Si la somme de deux entiers est plus grande que la demi-somme totale, alors un seul de ces entiers est dans le groupe.
>
> Bon voila, rien de révolutionnaire, mais encore fallait-il le dire ..

J'avoue ne pas avoir suivis ton raisonnement à propos du dernier quart ?

donk, si tu par du plus grad et ke tu aditionne chaque fois un plus petit, ca ne sert à rien de tester ceux qui valent moi ke le quart de la somme totale, puiske on n'arrivera jamais à la moitié ....

Je te conseille d'attribuer à chake nombre un flag qui vo 1 au debut, et chake fois ke tu es sur k'il ne sert à rien, tu le met à 0 (avec les conditions que tu as données par exemple) et tu ne teste que ceux qui on un flag de 1 par exmple avec la methode ke j'ai donnée

ma methode :

ex : 1 2 3 5 7 8 (peits nombres pour plus de facilité ...)
somme 26
moitié 13

8 + 1 = 9
8 + 2 = 10
8 + 3 = 11
8 + 5 = 13 flag 0 sur 5 et 8, tu sai kil vont à deux fo plu le tester et ca sert à rien de tester 8 + des valeurs au dessus de 5, vu ke t deja au dessus de la moitié

PS : tu t'arrete quand la somme est plus grande ou egale à la moitié, et tu me un flag 0 sur le nombre)

7 + 1 = 8
7 + 2 = 9
7 + 3 = 10

3 fo plus tester ni en dessous, paske de toute facon, tu as deja essayé tout les nombres au dessus, donk il n'y aura que des nombres inferieurs ou égaux à 3, et leur somme ne vaudrat jamais la moitié (c ca ke je voulai dire par le quart)

En ayant verifié tes conditions avant, je crois que ca sera la meilleur méthode (a moins qu'il n'y ai une formule mathématique mais ca m'etonnerait ....)


Euhhhh je me comprend, j'espère que tu comprendras aussi ...


===============================

Funcky

===============================

On dit que seulement dix personnes au monde comprenaient Einstein. Personne ne me comprend. Suis-je un génie ?



-------------------------------
Réponse au message :
-------------------------------

>
> J'avoue ne pas avoir suivis ton raisonnement à propos du dernier quart ?

Oki, j'ai compris ta méthode.
Mais je peux avoir jusqu'à 100 entiers.
Autrement dit, au cas où je ne trouverais pas avant un groupe qui fonctionne, je suis obligé de tester des groupes qui vont jusqu'a 50 entiers ... Et chaque fois que fois que nombre d'entier par groupe augmente, le nombre de possibilités augmente ... J'ai pas encore trouvé d'idées pour programmer une méga boucle .. pour l'instant, j'arrive à programmer une fonction de vérification pour un nombre d'entier précis d'entiers dans le groupe. Si quelqu'un pouvait méviter de programmer 50 fois la meme fonction avec une boucle incorporée de plus à chaque fois, vous auiez toute ma gratitude ;-)

tu partirait d'une

struct liste
{
int entier;
int flag = 1;
}

avec un

struct liste tab[100];

et un NMAX, correspndant au nombre d'entiers ...
et moitié corrsepondant a la somme des entiers divisé par deux

int i = NMAX - 1;
int j = 0;
int groupe = 3;
bool continue = true;

while (continue == true)
{
while (tab.entier + tab[j].entier <= moitié)
{
if (tab[j].flag == 1)
{
if (tab[i].entier + tab[j].entier == moitié)
{
tab[i].flag = groupe;
tab[j].flag = groupe;
groupe++;
}
}
j++;
}
tab[i].flag = 0;
i--;
if (tab[i].entier < (moitié / 2))
{
continue = false;
}
}


ca te donnerai un tableau avec tout les nombres dont les flags vallent 1 ou 0 si il ne vont pas avec les autres
un flag > 1 correspondant au N° du groupe.

C'est la seulle solution que je vois ...

PS : je viend de taper ca sans le tester, mais normalement ca devrait être bon ...

===============================

Funcky

===============================

[i]On dit que seulement dix personnes au monde comprenaient Einstein. Personne ne me comprend. Suis-je un génie ?



-------------------------------
Réponse au message :
-------------------------------

> Oki, j'ai compris ta méthode.
> Mais je peux avoir jusqu'à 100 entiers.
> Autrement dit, au cas où je ne trouverais pas avant un groupe qui fonctionne, je suis obligé de tester des groupes qui vont jusqu'a 50 entiers ... Et chaque fois que fois que nombre d'entier par groupe augmente, le nombre de possibilités augmente ... J'ai pas encore trouvé d'idées pour programmer une méga boucle .. pour l'instant, j'arrive à programmer une fonction de vérification pour un nombre d'entier précis d'entiers dans le groupe. Si quelqu'un pouvait méviter de programmer 50 fois la meme fonction avec une boucle incorporée de plus à chaque fois, vous auiez toute ma gratitude ;-)

fait chier !!!! j'avait tout bien mis avec les decalages pour voir plus clair et il me remet tout sur la meme ligne !!!!!
ouiiiiiiiiiiiiiiinnnnnnnnnnnnnnnnnnnn

===============================

Funcky

===============================

On dit que seulement dix personnes au monde comprenaient Einstein. Personne ne me comprend. Suis-je un génie ?



-------------------------------
Réponse au message :
-------------------------------

>
> tu partirait d'une
>
> struct liste
> {
> int entier;
> int flag = 1;
> }
>
> avec un
>
> struct liste tab[100];
>
> et un NMAX, correspndant au nombre d'entiers ...
> et moitié corrsepondant a la somme des entiers divisé par deux
>
> int i = NMAX - 1;
> int j = 0;
> int groupe = 3;
> bool continue = true;
>
> while (continue == true)
> {
> while (tab.entier + tab[j].entier <= moitié)
> {
> if (tab[j].flag == 1)
> {
> if (tab[i].entier + tab[j].entier == moitié)
> {
> tab[i].flag = groupe;
> tab[j].flag = groupe;
> groupe++;
> }
> }
> j++;
> }
> tab[i].flag = 0;
> i--;
> if (tab[i].entier < (moitié / 2))
> {
> continue = false;
> }
> }
>
>
> ca te donnerai un tableau avec tout les nombres dont les flags vallent 1 ou 0 si il ne vont pas avec les autres
> un flag > 1 correspondant au N° du groupe.
>
> C'est la seulle solution que je vois ...
>
> PS : je viend de taper ca sans le tester, mais normalement ca devrait être bon ...
>
> ===============================
>
> Funcky
>
> ===============================
>
> [i]On dit que seulement dix personnes au monde comprenaient Einstein. Personne ne me comprend. Suis-je un génie ?
>
>
>
> -------------------------------
> Réponse au message :
> -------------------------------
>
> > Oki, j'ai compris ta méthode.
> > Mais je peux avoir jusqu'à 100 entiers.
> > Autrement dit, au cas où je ne trouverais pas avant un groupe qui fonctionne, je suis obligé de tester des groupes qui vont jusqu'a 50 entiers ... Et chaque fois que fois que nombre d'entier par groupe augmente, le nombre de possibilités augmente ... J'ai pas encore trouvé d'idées pour programmer une méga boucle .. pour l'instant, j'arrive à programmer une fonction de vérification pour un nombre d'entier précis d'entiers dans le groupe. Si quelqu'un pouvait méviter de programmer 50 fois la meme fonction avec une boucle incorporée de plus à chaque fois, vous auiez toute ma gratitude ;-)
>

-------------------------------
Réponse au message :
-------------------------------

>
> tu partirait d'une
>
> struct liste
> {
> int entier;
> int flag = 1;
> }
>
> avec un
>
> struct liste tab[100];
>
> et un NMAX, correspndant au nombre d'entiers ...
> et moitié corrsepondant a la somme des entiers divisé par deux
>
> int i = NMAX - 1;
> int j = 0;
> int groupe = 3;
> bool continue = true;
>
> while (continue == true)
> {
> while (tab.entier + tab[j].entier <= moitié)
> {
> if (tab[j].flag == 1)
> {
> if (tab[i].entier + tab[j].entier == moitié)
> {
> tab[i].flag = groupe;
> tab[j].flag = groupe;
> groupe++;
> }
> }
> j++;
> }
> tab[i].flag = 0;
> i--;
> if (tab[i].entier < (moitié / 2))
> {
> continue = false;
> }
> }
>
>
> ca te donnerai un tableau avec tout les nombres dont les flags vallent 1 ou 0 si il ne vont pas avec les autres
> un flag > 1 correspondant au N° du groupe.
>
> C'est la seulle solution que je vois ...
>
> PS : je viend de taper ca sans le tester, mais normalement ca devrait être bon ...
>
> ===============================
>
> Funcky
>
> ===============================
>
> [i]On dit que seulement dix personnes au monde comprenaient Einstein. Personne ne me comprend. Suis-je un génie ?
>
>
>
> -------------------------------
> Réponse au message :
> -------------------------------
>
> > Oki, j'ai compris ta méthode.
> > Mais je peux avoir jusqu'à 100 entiers.
> > Autrement dit, au cas où je ne trouverais pas avant un groupe qui fonctionne, je suis obligé de tester des groupes qui vont jusqu'a 50 entiers ... Et chaque fois que fois que nombre d'entier par groupe augmente, le nombre de possibilités augmente ... J'ai pas encore trouvé d'idées pour programmer une méga boucle .. pour l'instant, j'arrive à programmer une fonction de vérification pour un nombre d'entier précis d'entiers dans le groupe. Si quelqu'un pouvait méviter de programmer 50 fois la meme fonction avec une boucle incorporée de plus à chaque fois, vous auiez toute ma gratitude ;-)
>