Newsgroup: it.comp.lang.c
Titolo: Questo problema mi sembra davvero difficile.....

Salve a tutti!
Allora. Il mio problema è questo: ho un array di N interi e devo sommarne
tutti gli elementi in tutti i modi possibili. Faccio un esempio:
 0   1   2   3
__________
| 1 | 2 | 3 | 4 |
Tutte le somme possibili di questo array sono:
1
2
3
4
1+2                            for (j=0;j<N-1;j++)
1+3                            {    for (i=1;i<N-0;i++)
1+4                                  {  x=arr[j]+arr[i];
2+3                                   }
2+4                            }
3+4
1+2+3                        for (i=0;i<N-2;i++)
1+2+4                        {    for (j=1;j<N-1;j++)
1+3+4                              {  for (k=2;k<N-0;k++)
2+3+4                                  {  x=arr[j]+arr[i]+arr[k];
                                    }}}
1+2+3+4
... e il codice per farle eseguire è accanto. Come posso generalizzare
questo codice in modo da poter calcolare tutte le possibili somme di N
numeri?
Spero di essere stato chiaro e... grazie a quanti mi risponderanno!

 wrote in message
mNi36.961$jT6....@twister2.tin.it...



Una cosa da notare è che tutte le somme sono le pemutazioni senza
ripetizione del vettore, quindi potresti andare anche in questa
direzione.
-- 
Ciao, gengisdave
http://digilander.iol.it/gengisdave
Linux Registered User    # 198292
Linux Registered Machine # 88280

 numeri?
n numeri ==> 2 ^ n possibili somme
ti costruisci una tavola di verita' con 0 e 1
se c'e' 1 il numero viene sommato 
semplicissimo.
esempio:
N = 3 (ovvero ho tre numeri da sommare, a b c)
abc
000 ==> 0
001 ==> c
010 ==> b
011 ==> b+c
100 ==> a
101 ==> a+c
110 ==> a+b
111 ==> a+b+c
il codice C per generare la matrice[2^n][n] non credo sia un problema...
ciao
--
Carlo Perassi
carlo at linux dot it
http://www.linux.it/~carlo
--


La tua idea mi sembra davvero buona... ma c'è una cosa che mi sfugge: Come
si costruisce una tavola di verità per N numeri? e inoltre: il simbolo ^
puo' essere usato nella dichiarazione di un array? (es. int arr[d^s][d];)
grazie ancora...
ric

 puo' essere usato nella dichiarazione di un array? (es. int arr[d^s][d];)
Io uso questo sistema per scegliere alcuni files presenti in una cartella in
modo da ottenere la dimensione totale voluta.
Questo è il frammento di codice, vedi se riesci ad adattarlo per i tuoi
scopi:
(UI64 è un numero senza segno a 64 bits, ULONG uno a 32)
 // Esegue le suddivisioni: bit a 1=file scelto, 0=file scartato
 ULONG SM=0xffffffff; UI64 I,IM; // i migliore
 while(SM>1000) { // Scandisce le permutazioni
  ULONG S=0, // somma delle dimensioni dei files
   k=0; // contatore dei files scanditi
  UI64 i=I;
  while(I) {
   if(I&1) S+=int(F->Objects[k]); // CONTIENE LA DIMENSIONE DEL FIL
   I>>=1; k++;
  }
  // Soluzione migliore
  if(SPAZIO-S<SM && SPAZIO-S>0) {
   SM=SPAZIO-S; IM=i; _ui64toa(i,buf,10);
// MOSTRA LA SOLUZIONE MIGLIORE FINO AD ORA
   REp->Lines->Append(String(buf)+"  "+IntToStr(SPAZIO-S));
  }
 }
Cristiano

Da quello che dici cio' che ti serve e' analizzare tutte le
COMBINAZIONI (non permutazioni o disposizioni), che sono appunto il
coefficiente binomiale di (n su 1) + il coefficiente binomiale di (n
su 2) + ... , ovvero 2^n. Ecco un programma facile facile:
==================
#include "stdio.h"
#include "math.h"
#define N 4
void main(void)
{
 int vettore[N];
 int idx;
 long idx_comb , idx_elemento , somma ;
 /* caricamento vettore*/
 for (idx=0;idx<N;idx++)
  scanf("%d",vettore+idx);
 for (idx_comb=0;idx_comb<pow(2.0,N);idx_comb++) {
  printf("\nsomma degli elementi:");
 for (somma=0,idx_elemento=0;idx_elemento<N;idx_elemento++)
  if (idx_comb & (long)pow(2.0,idx_elemento)) {
   somma+=vettore[idx_elemento];
   printf("%u ",idx_elemento+1);
  }
 printf(" = %ld",somma);
 }
}