Esercizio c++

Pubblicità
Stato
Discussione chiusa ad ulteriori risposte.

olegfresi

Nuovo Utente
Messaggi
102
Reazioni
2
Punteggio
38
Dovrei implemenatare in c++ questo algoritmo: dato un insieme di numeri geneare tutti i sottoinsiemi ordinati per dimensione, per esempio: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.
Il problema qui non è tanto implementare l'algoritmo, ma progettarlo. Potreste darmi una mano per favore?
 
Progettarlo e implementarlo in qualsiasi linguaggio è un po' la stessa cosa.

Comunque: prima ordina l'insieme dei numeri e poi crea tutti gli insiemi possibili (combinazioni) in maniera progressiva con cicli ricorsivi sull'array già ordinato e partendo sempre dal più piccolo.... verranno generati gli insiemi già ordinati in maniera crescente.

Inviato dal mio Nexus 5 utilizzando Tapatalk
 
Quella che ti chiede di fare è, in calcolo combinatorio, una "disposizione semplice" senza ripetizioni.

Prendi il vettore dei numeri e lo ordini (crescente).

Poi fai una matrice (vettore di vettori) in cui il primo indice è un progressivo che raccoglie il numero di combinazioni che ottieni facendo, con cicli ricorsivi, una disposizione semplice senza le ripetizioni, dell'array iniziale.


p.e.

Serie di n numeri: 1,7,3,4,5..

La ordini: 1,3,4,5,7..

Li combini con cicli ricorsivi in un vettore di vettori c[num,lungh] in cui avrai
num=numero di combinazioni, che dovrebbe essere nc=n!/(n-2)! e che per n=5 sono 20.
lungh=lunghezza massima combinazione, che sarà sempre lungh <=n.

Inizi i cicli annidati per tutte le combinazioni che iniziano con 1...

c[0] =1,3;
c[1]= 1,4;
...
c[4]=1,7;

altro ciclo..

c[5]=1,3,4,5,7;
c[6]=1,3,4,5;
c[7]=1,3,4;

c[8]=1,4,5,7;
c[9]=1,5,7

Poi quelle con il 3...

c[10]=3,4;
c[11]=3,5;
...
c[13]=3,4,5,7;
c[14]=3,4,5;
c[15]=3,4,7;
c[16]=3,5,7;

poi il 4...

c[17]=4,5;
..

Il 5...

c[19]=5,7

Che fa appunto 20 righe cioè 20 insiemi ordinati secondo la disposizione semplice ordinata.






Inviato dal mio Nexus 5 utilizzando Tapatalk
 
Grazie tante per la spiegazione! Comunque l'esercizio presuppone ch i numeri vengano già inseriti ordinati, facendo evitare di scrivere un algoritmo di ordinamento. Il focus probabilmente era proprio sull'implementazione degli algoritmi di combinatoria.
 
Stato
Discussione chiusa ad ulteriori risposte.
Pubblicità
Pubblicità
Indietro
Top