Esercizio c++

Stato
Discussione chiusa ad ulteriori risposte.

olegfresi

Nuovo Utente
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?
 

rctimelines

Utente Èlite
4,067
1,325
Hardware Utente
CPU
AMD Ryzen 7 2700X | INTEL i5-6600k | INTEL i5-4460... altri
Dissipatore
wraith MAX | Arctic Freezer 11LP | stock
Scheda Madre
Asrock Fatal1ty 4K | Asus Prime Z270P | Acer Veriton
Hard Disk
Samsung 970evo m.2 | vari | Samsung 860 evo
RAM
16GB G.Skill TridentZ 3000 | 16GB CORSAIR 2133 | 8GB DDR3 1600
Scheda Video
RadeonPro WX3100 4G | Asus R9 280x 3G | Quadro k620 2G
Monitor
DELL 2419P 2K + Benq 17" | Acer 24" FHD | Benq 19" FHD
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
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
 

rctimelines

Utente Èlite
4,067
1,325
Hardware Utente
CPU
AMD Ryzen 7 2700X | INTEL i5-6600k | INTEL i5-4460... altri
Dissipatore
wraith MAX | Arctic Freezer 11LP | stock
Scheda Madre
Asrock Fatal1ty 4K | Asus Prime Z270P | Acer Veriton
Hard Disk
Samsung 970evo m.2 | vari | Samsung 860 evo
RAM
16GB G.Skill TridentZ 3000 | 16GB CORSAIR 2133 | 8GB DDR3 1600
Scheda Video
RadeonPro WX3100 4G | Asus R9 280x 3G | Quadro k620 2G
Monitor
DELL 2419P 2K + Benq 17" | Acer 24" FHD | Benq 19" FHD
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
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
 

olegfresi

Nuovo Utente
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.

Entra

oppure Accedi utilizzando