Newsgroup: it.comp.lang.c
Titolo: Re: Combinazioni di 0 e 1

 Ciobin wrote:
[Super CUT]
Seconde te è corretto?
  checkMem(xopt = calloc(n+1, sizeof(int)));
Dove:
void checkMem(void *array){
  if (array==NULL){
    perror("Errore di allocazione");
    exit(1);
  }
}
ed
int *xopt.
TNX

 Quale garantisce migliori prestazioni?
sicuramente il mio. :-)
Anche se non e' detto che non si possa  velocizzare ulteriormente.
Per esempio si potrebbe implementare come un contatore in
base 2, in cui ad ogni iterazione non rigeneri tutti i valori di B[],
ma semplicemente lo incrementi partendo dal bit piu' corto:
/* inizializzo B */
int i,j,B[32]={0};
for (i=0; i<(1u<<n); i++)
{
    /* Stampo B o lo uso in qualche modo... */
    /* ...... */
    /* Aggiorno B */
    for (j=0; B[j]; j++) B[j]=0;
    B[j]=1;
}
Questa sopra dovrebbe essere auto esplicativa, e a seconda del sistema 
su cui operi forse anche piu' veloce di quella che ti ho fatto
vedere prima. Questa si generalizza facilmente anche per numeri con 32
e piu' bit. Basta stare attenti a modificare il for esterno per non 
sforare i valori massimi per gli interi.
Quella che ti ho
fatto vedere prima si puo' spiegare cosi'
unsigned long i,k;
int n, B[31];
for (k=0; k < (1u<<n); k++)
   printf("config. %u-esima = ",k);
  for (i=0; i<n; i++) B[i]=(k&(1<<i)?1:0);
   for (i=0; i<n; i++) printf("%d",B[i]);
   printf("\n");
}
la riga essenziale e' questa:
for (i=0; i<n; i++) B[i]=(k&(1<<i)?1:0);
in cui dato il numero k scrivo in B la sua
versione in binario.
allora 1<<i  e' come dire 2^i ovvero un numero
binario in cui solo il bit i-esimo e' settato ad 1.
x & y fa l'operazione di AND binario bit a bit tra x e y.
quindi fare k & (1<<i) mi restituisce
0  , se il bit i-esimo di k e' uguale a 0
1<<i, se il bit i-esimo di k e' uguale a 1.
poi la sintassi
(cond ? a : b) viene valutata come a se la condizione cond e' vera e 
come b se la condizione cond e' falsa.
in particolare un intero == 0 e' come una condizione falsa quindi
(k&(1<<i)?1:0);
varra' 1 se k&(1<<i) e' diverso da 0, ovvero se il bit i-esimo di k e' 
settato  e varra' 0 nel caso contrario.
A parte queste considerazioni sul linguaggio il resto dovrebbe essere 
chiaro se hai chiara la rappresentazione in base 2 dei numeri interi.
Il ciclo piu' esterno semplicemente replica la cosa per
tutti i 2^n valori compresi tra 0 (in binario 0000...000)
e   (1<<n)-1  = 1111...1111 in binario (incluso).
ciao,
g.

 che vuol dire (1u<<n)???
che 1 deve essere considerato un unsigned.
Questo non e' detto che serva. E' una cosa che mi porto
dietro come abitudine quando faccio degli shift che potrebbero
portarmi oltre al limite dei numeri signed.
Anzi, supponendo che serva, avrei dovuto scrivere 1ul per
dire long unsigned.
E' che ormai sono abituato a lavorare su sistemi in cui 
sizeof(int)=sizeof(long)=4 e non penso alla portabilita'.
ciao,
g.

 Da quanti anni ci lavori?
No, non scherziamo. Ho una conoscenza a livello hobbistico.
E' solo che nel mio settore cose come quelle
(tipo generare combinazioni, permutazioni, giocare un po' coi bit)
mi capitano spesso.
A tempo perso programmo da circa 27 anni (da quando ne avevo 14).
Ma non sempre in C. Il C direi che lo uso stabilmente da circa 16 anni.
(Acc. Mi fate 'ste domande e mi sento veramente decrepito!)
Ho cominciato con cobol, fortran, algol quando ancora potevo solo
far "girare" i programmi sulla carta... eseguendoli a mano...
e poi basic, molto pascal, un po' di apl, di forth e di lisp.
Java mi da la nausea e il C++ sono troppo tardo per capirlo per
bene. La mia mente e' inesorabilmente refrattaria alla programmazione
ad oggetti (anche se certe cose del C++ mi fanno gola, in particolare
certe  strutture dati predefinite nella SDL).
Se cerchi un luminare e' meglio se ascolti il Laforgia,
che penso abbia lo standard C99 tatuato a rovescio sul petto.
ciao,
g.

 Grazie
questo genera e stampa tutte le configurazioni
di n valori 0,1.
suppondendo che n sia minore di 32.
unsigned long i,k;
int n, B[31];
for (k=0; k < (1u<<n); k++)
   printf("config. %u-esima = ",k);
   for (i=0; i<n; i++) B[i]=(k&(1<<i)?1:0);
   for (i=0; i<n; i++) printf("%d",B[i]);
   printf("\n");
}
ciao,
g.

 ha scritto nel messaggio
news:d9c3lg$juq$8...@newsfeed.cineca.it...



che vuol dire (1u<<n)???

 precedente?
Io ti consiglio quella che ti e' piu' chiara.
Per quel che riguarda i tempi, sulla mia macchina, la seconda che ti
ho detto (il contatore) e' decisamente piu' veloce.
per n=28 (ovvero 268435456 combinazioni) che chiaramente genero ma non
stampo, la prima versione con gli shift ci mette
ben 33 secondi circa, mentre la seconda (il contatore) ci mette 3.6 secondi.
E' chiaro che se sai a priori che al massimo dovrai generare poche
combinazioni (tipo 65536) te ne puoi infischiare.
ciao,
g.

 ha scritto nel messaggio
news:d9c3lg$juq$8...@newsfeed.cineca.it...

Grazie, me li studio per bene.



Insomma, per un lavoro di tesi mi consigli questa sopra o quella del post
precedente?
Per la spiegazione dell'altro codice, alcune cose mi sfuggono, ma credo sia
la stanchezza. Me lo rileggo più tardi con calma.
Ti ringrazio tantissimo. Ti dovrebbero fare santo. (santo subito, santo
subito).
GRazie

 Ciobin wrote:
[CUT]
Il tuo codice è decisamente sintetico.
Io avevo pensato a qualcosa del genere:
#include<stdio.h>
#define DIM 32       // dimensione di un vettore int (4 byte)
void binario();      // converte il numero decimale in binario
int vet[DIM]; // vettore per memorizzare le cifre del numero convertito
int n;        // numero decimale da convertire
main()   // funzione principale
{
int i; // Conatore
int k; // scelta del menu iniziale
  for(i=0;i<DIM;i++)  // azzeramento elementi del vettore
  {
    vet[i]=0;
  }
  printf("Numero decimale: "); scanf("%d",&n); // immissione del valore
  binario();
void binario()
{
int i; // Conatore
  for (i = 0;i<DIM; i++)
  {
    vet[DIM-1-i]=n%2;
    n=n/2;
  }
}
Seconde te quale è più efficiente? Questo oppure il tuo?
Quale garantisce migliori prestazioni?
Infine, potresti spiegarmi un po' il codice che hai postato? NOn lo riesco a
capire.
Grazie, come sempre !!!



 E tu consideri un luminare quel maleducato :-(
Sicuramente conosce lo standar meglio di me e la
sua esperienza sul campo e' certamente maggiore della mia.
Sulle vostre beghe casalinghe preferisco non entrarci... :-)
ciao,
g.

 sua esperienza sul campo e' certamente maggiore della mia.
Be', considerato che ho circa 10 anni meno di te non lo credo ;-)
E comunque non tutto lo standard sul petto, solo una buona metą.
Il resto sto pensando di farmelo tatuare sulla schiena.
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 Il resto sto pensando di farmelo tatuare sulla schiena.
Quello tatuato a rovescio sul petto ha il vantaggio che
lo puoi ripassare quando al mattino ti fai la barba
davanti allo specchio....
ciao,
g.


Conoscere lo standard NON fa` un buon programmatore progettista.
I migliori sono quelli che sanno ragionare, te lo dice chi per 15 anni 
ha fatto anche colloqui per l'assunzione.


 Conoscere lo standard NON fa` un buon programmatore progettista.
Te l'ho già detto più volte: taci, farai miglior figura.
p.s.: "fa" si scrive senza apostrofo.


 ha scritto nel messaggio 
news:TJeue.16447$yM4.2...@twister2.libero.it...

Potresti usare una struttura ad albero binario con affiancato uno stack ed 
eseguire un preorder per esempio;
tipo per 4 bit:
                1                    0
        1        0            1        0
    1    0    1    0    1    0    1    0
    10 10 10   10  10   10  10  10
ogni volta che lo stack contiene 4 elementi  fai una lettura...
E' dispendioso dal punto di vista di codifica, ma è sicuramente ELEGANTE! 
^_^ ihihih cia
___________
Se la so rispondo sempre...(quasi dai)

 eseguire un preorder;
ah si cmq cosi è come ammazzare una zanzara con un cannone... 

 ha scritto nel messaggio
news:RGyue.62687$75.31...@news4.tin.it...

LOL

 davanti allo specchio....
Esatto, mentre quello tatuato dritto sulla schiena lo fai leggere alla tua
ragazza, mentre ti insapona la schiena sotto la doccia... ;-)
