Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - [C] Generare tutte le combinazioni possibili di 0 e 1
Forum - C/C++ - [C] Generare tutte le combinazioni possibili di 0 e 1

Avatar
Lafa_96 (Normal User)
Pro


Messaggi: 111
Iscritto: 09/03/2011

Segnala al moderatore
Postato alle 14:53
Mercoledì, 30/11/2016
Salve a tutti, sono piantato da 2 giorni su un problema abbastanza stupido che però mi sta facendo diventare pazzo (probabilmente, anzi sicuramente, sono più stupido io del problema):
sto cercando di creare una funzione (possibilmente ricorsiva) che dato n mi generi tutti i vettori possibili di n elementi 0 e 1.
In sostanza se n=3 il numero di vettori sarà 2^3=8.
Ho cercato un po' in giro ma non ho trovato codice utile al mio scopo e non so più dove sbattere la testa perchè le soluzioni più simili (e comunque poco utili) al mio problema sono tutte iterative!

Grazie in anticipo :)


Non hai bisogno di vedere l’intera scalinata. Inizia semplicemente a salire il primo gradino. (Martin Luther King)
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1455
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 18:26
Mercoledì, 30/11/2016
Se non sai passare da una funzione iterativa a una ricorsiva torna indietro e ristudia meglio.

In realtà l'esercizio è una stupidaggine, ti danno n, che è il numero di bit: tu fai un ciclo (implementato come ti pare) che va da 0 a 2^n-1.


quindi qualcosa del genere:

Codice sorgente - presumibilmente C#

  1. void stampaCombinazione(int n, int k = 0) {
  2.     if (k == pow(2,n))
  3.         return;
  4.    
  5.     // qui stampi k in formato binario e vai a capo
  6.  
  7.     stampaCombinazione(n, k + 1);
  8. }



La chiamata alla funzione sarà qualcosa del genere:

Codice sorgente - presumibilmente Plain Text

  1. stampaCombinazione(lunghezzaVettore);



Il codice fa schifo e non so neanche se sia compilabile, ma il concetto è sicuramente quello corretto.

Ultima modifica effettuata da TheDarkJuster il 30/11/2016 alle 18:26
PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 413
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 18:55
Mercoledì, 30/11/2016
L'idea principale è questa, se hai ad esempio l'insieme di tutte le combinazioni di due cifre, {00, 01, 10, 11} allora quelle di tre cifre le ottieni aggiungendo davanti a tutte queste 0 e poi 1, e poi unendole: {000, 001, 010, 011} U {100, 101, 110, 111}
Come puoi notare generandole così puoi anche dimostrare per induzione che sono proprio 2^n, perché ogni volta ne aggiungi il doppio.

Il problema principale qui forse è la gestione della memoria, anche se non so bene se vuoi fare una funzione che ritorni qualcosa o semplicemente stampi tutto.

PM Quote
Avatar
torn24 (Normal User)
Pro


Messaggi: 138
Iscritto: 04/01/2008

Segnala al moderatore
Postato alle 8:28
Giovedì, 01/12/2016
Personalmente prenderei spunto dal brute force per le password.
Trovare tutte le combinazioni di zero e uno, è come trovare le combinazioni di una password composta dai caratteri 0 e 1, e di lunghezza n.


Se si impara dai propri sbagli
non è cosi drammatico  sbagliare !
PM Quote
Avatar
Template (Member)
Pro


Messaggi: 175
Iscritto: 09/12/2015

Segnala al moderatore
Postato alle 15:57
Giovedì, 01/12/2016
Testo quotato

Postato originariamente da Lafa_96:
Ho cercato un po' in giro ma non ho trovato codice utile al mio scopo e non so più dove sbattere la testa



Il codice non si "cerca", si SCRIVE.
E se non sai scriverlo, vuol dire che non ci hai pensato abbastanza.

Possibile, banalissimo, algoritmo:

Funzione ricorsiva:
- Se hai finito le cifre, stampa
- Altrimenti:
---- Poni la k-esima cifra a zero
---- Richiama la funzione sulla (k+1)-esima
---- Poni la k-esima cifra a uno
---- Richiama la funzione sulla (k+1)-esima
- Return

Ultima modifica effettuata da Template il 01/12/2016 alle 15:58


"Nel curriculum scrivete quello che sapete fare... e anche quello che non sapete fare! Tipo: "Già vescovo di Cracovia, partecipai alla Coppa America, vincendola!""
[...]
"Sto giocando al piccolo Dio e mi sta venendo pure alla grande."
PM Quote