PDA

Visualizza la versione completa : algoritmo combinazione binaria


stephen71
12-01-2013, 13:43
ciao a tutti,
ho provato a cercare un algoritmo che mi permetesse di ottenere da 4 numeri la seguente combinazione.

I numeri sono es: 3, 6, 21, 8
i risultati:
3, 6, 9, 21, 24, 27, 30, 8, 11, 14, ....
in pratica si tratta di selezionare i numeri sopra in modo binario per provare tutte le combinazioni posibili.
Drovebbe essere un algoritmo conosciuto ma non riesco a trovarlo.
qualcuno mi puo aitare? :ciauz:

MItaly
13-01-2013, 04:04
Fai un ciclo con numeri da 1 a 2^4-1; ad ogni iterazione, fai un and con ogni bit (da 0 a 3) e, se č acceso, somma il numero di posizione corrispondente; otterrai cosė tutte le combinazioni richieste; in C++:


int elems[]={3, 6, 21, 8};
size_t numelems=sizeof(elems)/sizeof(*elems);
for(int i=1; i<(1<<numelems); i++)
{
int result=0;
for(int j=0; j<numelems; j++)
result+=(i & (1<<j))?elems[j]:0;
cout<<result<<'\n';
}

http://ideone.com/0EXYKb

(nota che, a meno che i vari numeri utilizzati non siano tutti potenze diverse dello stesso numero, non č garantito che tutte le combinazioni diano risultati diversi)

stephen71
13-01-2013, 10:01
fantastico e' quello che stavo cercando.
interessante la soluzione con l'and tra 2 numeri interi.
grazie

MItaly
13-01-2013, 14:24
:ciauz:

Loading