Somme de n termes :

[ccornaille]

voila j'aimerais savoir comment vous feriez pour avoir toute les somme possible de n terme ?

un exemple avec n=3 : trois termes a b c

les sommes sont

a+b+c

a+b

a+c

b+c

a

b

c

0

on constatera qu'il y en a 2^n

[LePhasme]

pow(2,n) ?

[fabien29200]

Je partirai sur une solution récursive.

A savoir comment calculer la somme de n termes à partir des n-1 sommes.

int[] sommes ( int[] termes )
{
int[] resultats = new int[termes.length ^ 2];
int[] tmp, termes_tmp;

resultats[0] = termes[0];

// condition d'arrêt de la récursivité
if ( termes.length == 1 ) 
{
	return resultats;
}

// on trouve les n-1 termes 
termes_tmp = [ termes sans le 1er élément ];

// on calcule les n-1 sommes
tmp = sommes (termes_tmp);

// on recopie les n-1 sommes dans le tableau résultat
for ( int i=1; i<termes_tmp.length+1;i++)
{
	resultats[i] = termes_tmp[i];
}  

// on ajoute aux n-1 sommes, la somme du 1er terme
for ( int i=termes_tmp.length+1;i<resultats.length;i++)
{
	resultats[i] = termes_tmp[i - termes_tmp.length] + termes[0];
}

}

Voilà, y a ptet des effets de bord, mais je pense que algorithmiquement, ça doit être correct.

[ccornaille]

Je partirai sur une solution récursive.

A savoir comment calculer la somme de n termes à partir des n-1 sommes.

int[] sommes ( int[] termes )
{
int[] resultats = new int[termes.length ^ 2];
int[] tmp, termes_tmp;

resultats[0] = termes[0];

// condition d'arrêt de la récursivité
if ( termes.length == 1 ) 
{
	return resultats;
}

// on trouve les n-1 termes 
termes_tmp = [ termes sans le 1er élément ];

// on calcule les n-1 sommes
tmp = sommes (termes_tmp);

// on recopie les n-1 sommes dans le tableau résultat
for ( int i=1; i<termes_tmp.length+1;i++)
{
	resultats[i] = termes_tmp[i];
}  

// on ajoute aux n-1 sommes, la somme du 1er terme
for ( int i=termes_tmp.length+1;i<resultats.length;i++)
{
	resultats[i] = termes_tmp[i - termes_tmp.length] + termes[0];
}

}

Voilà, y a ptet des effets de bord, mais je pense que algorithmiquement, ça doit être correct.

tu me fais ça en java et je tapelle DIEU

plus sérieusement je comprend pas ton algo.....

[Sentinel]

Chiche...

public class Sommes
{
public static void main(String[] args)
{
	String[] nombres = {"1" , "2" , "3" , "4"}; // Pour tester...

	Sommes sommes = new Sommes();
	sommes.afficherSommes(nombres);		
}		

public void afficherSommes(String[] nombres)
{
	int nbParams = nombres.length;

	long max = (1 << nbParams) - 1;
	long mask = 0l;

	for (int i=1; i<=max; i++)
	{
		StringBuffer buffer = new StringBuffer();
		long somme = 0;

		mask++;
		for (int j=0; j<nbParams; j++)
		{
			long submask = 1 << j;
			if ((mask & submask) == submask)
			{
				int nombre = Integer.parseInt(nombres[j]);
				buffer.append(" + " + nombre);
				somme += nombre;					
			}
		}
		buffer.append(" = " + somme);
		System.out.println(buffer.toString().substring(3));			
	}		
}
}

Et voilà, 10 minutes montre en main.

Simple, non ? Et la solution est élégante

Bon je détaille un peu pour ceux qui ont la flemme de chercher...

Pour passer par toutes les combinaisons, rien de plus simple que d'utiliser l'encodage binaire.

Chaque nombre de notre tableau de nombres est associé à un des bits d'un champ de bits (j'utilise un long pour avoir un peu de place (64 bits), qui s'appelle "mask").

Ainsi, par exemple, pour les combinaisons de 3 nombres, on utilise les 3 premiers bits (à droite) de notre champ de bits; et sur 3 bits, la valeur décimale maximale est 7 (calcul long max = (1 << nbParams) - 1; )

Il est donc simplissime d'obtenir toutes les combinaisons possibles de nos trois nombres : il suffit de compter de 1 à 7 en décimal, et d'examiner la représenation du compteur en binaire.

A chaque itération, on obtient une configuration de bits qui nous indique quels nombres il faut additionner. (ma boucle sur j)

Exemple : si on est à 5 dans notre boucle (= 101 en binaire), on doit additionner le premier et le troisième nombre passés en paramètre.

Et hop :)

Conseil : savoir coder un quelconque langage sans erreurs de syntaxe, c'est bien. Etre bon en algorithmique... priceless :)

[fabien29200]

La solution de Sentinel est effectivement nettement + efficace en terme de complexité ...

Mais le problème, c'est que tu es dans des cas où n<64 voire 128.

On restreint donc le pb de départ.

Mon code, c'est presque du Java ...

[Sentinel]

Dans ce cas, il suffit de faire une structure un poil plus vaste, combinant plusieurs "long", avec des méthodes spéciales d'accès aux bits. Ou en utilisant BitSet au lieu d'un simple long.

Ce n'est pas compliqué, et ce sera toujours plus rapide qu'une solution récursive.

Et puis, dans le cadre d'un exercice scolaire, ce que je suppose être, 64 c'est largement suffisant !

[ccornaille]

tous d'abord : bonjours DIEU !!!!

ensuiteje vais poser des question à l'aide de commentaire

public class Sommes

{

//jusqu'a la je capte

public static void main(String[] args)

{

String[] nombres = {"1" , "2" , "3" , "4"}; // Pour tester...

//la fonction Sommes est définie ou ?

Sommes sommes = new Sommes();

sommes.afficherSommes(nombres);

}

public void afficherSommes(String[] nombres)

{

//ça aussi je capte

int nbParams = nombres.length;

//ça c'est une sorte de formule à connaitre???

long max = (1 << nbParams) - 1;

//pk ya la lettre l dans un long??

long mask = 0l;

//il sert à quoi exactement ce premier for ?? incrémenté mask???prendre toute les valeur supérieur à 0l??

for (int i=1; i<=max; i++)

{

StringBuffer buffer = new StringBuffer();

long somme = 0;

mask++;

//la je commence a etre largué ....

for (int j=0; j<nbParams; j++)

{

// << connait pas .??? en claire je vois pa trop ce que ça fais la ....

long submask = 1 << j;

if ((mask & submask) == submask)

{

int nombre = Integer.parseInt(nombres[j]);

//pour affiché tout les somme?

buffer.append(" + " + nombre)

somme += nombre;

}

}

//affiche le résultat des somme?

buffer.append(" = " + somme);

System.out.println(buffer.toString().substring(3));

}

}

}

Dans ce cas, il suffit de faire une structure un poil plus vaste, combinant plusieurs "long", avec des méthodes spéciales d'accès aux bits. Ou en utilisant BitSet au lieu d'un simple long.

Ce n'est pas compliqué, et ce sera toujours plus rapide qu'une solution récursive.

Et puis, dans le cadre d'un exercice scolaire, ce que je suppose être, 64 c'est largement suffisant !

La solution de Sentinel est effectivement nettement + efficace en terme de complexité ...

Mais le problème, c'est que tu es dans des cas où n<64 voire 128.

On restreint donc le pb de départ.

Mon code, c'est presque du Java ...

vous battez pas les coco , zette tous les deux des dieux

aussi commment faire pour tester si le resultat des sommes sont égaux entre eux , en claire : quoi écrire sur le boucle pour testé l'égalité entre toute les sommes ??

[theocrite]

Ah Sentinel

Ça me rappelle il y a 5 ans, on devait faire un résolveur de chiffres (pour les chiffres et les lettres, la partie chiffres donc) et faire des combinaisons de nombres.

J'ai fait aussi la combinaison bits, mais tout le monde a fait de la récurtion et on s'est moqué de moi avec mon algo

[Sentinel]

On va fonder la LPPCB ! Ligue Pour La Promotion des Champs de Bits !

C'est tellement puissant quand on sait s'en servir convenablement...

[ccornaille]

voila j'ai besoin d'aide (theo ne mayant pas rep en mp je poste ici)

c'est toujour sur le meme pb de toute les somme possible ect....

j'ai mis en commentaire l'endroit ou est mon pb .

voila mon code :

 public class essemble  {
public static void main(String[] args)  {

	int[] tab1 = {1 ,2 ,4};
	int t = tab1.length;
	int n = (int) Math.pow(2,t);

	int[] tabtemp = new int[n];
	for (int i=0; i<n; i++) {
		tabtemp[i]=i;

}
	String[] tabtemp2 = new String[n];
	for (int j=0; j<n;j++) {
		tabtemp2[j] = Integer.toBinaryString(tabtemp[j]);
		while (tabtemp2[j].length()<t) {
		tabtemp2[j]=0+tabtemp2[j];
		}
	}

	int[] somme = new int[n];
	for (int k=0;k<n;k++){
		for (int l=0; l<t;l++){
			char a = 1;
		   // je pense que l'erreure est ici .....le bollean a linterieure du if n'est jamais true.....pourtant  ça ma l'aire correcte ....
				 if (tabtemp2[k].charAt(l)== a) {
				somme[k]=somme[k]+tab1[l];
				 }

		}

	}
	int b = 0;
	for (int p=0;p<n;p++) {
		for(int q=p+1; q<n; q++){
			if (somme[p]==somme[q]){
				b = 1;
			}
		}
	}

	for (int o=0; o<n;o++) {
		System.out.println(""+tabtemp[o]);
		System.out.println(""+tabtemp2[o]);
		System.out.println(""+somme [o]);
		System.out.println("");

	}
	System.out.println("");
	if (b==1) {
		System.out.println("Votre ensemble est n'est pas parfait");
	}
	if (b==0) {
		System.out.println("Votre ensemble est parfait");
	}

}

}

sinon à mon avis le reste est correcte.....(pouvez toujour jeter un oeil ...)

[Sentinel]

Ben heu je t'avais déjà écrit un algo qui faisait toutes les sommes possibles non ?

[theocrite]

voila j'ai besoin d'aide (theo ne mayant pas rep en mp je poste ici)

Ah oui oups, au temps pour moi.

J'ai répondu à 3 MP ce matin, je t'ai oublié dans le tas

De toutes façons, c'est préférable de poster sur le forum, les demandes d'aides en MP c'est pas vraiment la bonne solution (surtout que perso en ce moment, je suis occupé pas mal par des trucs personnels et avec des trucs à régler sur le forum...).

Et puis aussi je suis naze en java

[ramy]

Je reste sceptique quand a l'utilité de ce programme...

[ccornaille]

certe centienel mais tu utilisé des truc que je ne maitrisé pas du tous !!! ==>les buffer et les masque....

donc jme suis lancé dans une solution avec tableau...

[ccornaille]

yen a pas

[ccornaille]

up !!!

[ccornaille]

c bon jai résolu