[PROBLEMA] Esercizio c++

  • Il Forum di Tom's Hardware, la più grande community dedicata all'Hardware e all'Informatica. Iscriviti Ora!
#1
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?
 
2,897
735
Hardware Utente
CPU
i7 3770
Dissipatore
stock intel
Scheda Madre
Gigabyte GA-H67A-UD3H-B3
Hard Disk
SSD SAMSUNG 850EVO 250GB + HDD WD GREEN CAVIAR 2TB
RAM
16GB = Corsair XMS3 4x4GB DDR3 1600MHz CL9
Scheda Video
ATI Firepro V7900 2GB
Scheda Audio
Soundblaster X-Fi
Monitor
HP 27'' + Benq 19''
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#2
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
 
2,897
735
Hardware Utente
CPU
i7 3770
Dissipatore
stock intel
Scheda Madre
Gigabyte GA-H67A-UD3H-B3
Hard Disk
SSD SAMSUNG 850EVO 250GB + HDD WD GREEN CAVIAR 2TB
RAM
16GB = Corsair XMS3 4x4GB DDR3 1600MHz CL9
Scheda Video
ATI Firepro V7900 2GB
Scheda Audio
Soundblaster X-Fi
Monitor
HP 27'' + Benq 19''
Sistema Operativo
Windows10-pro64/OpenSUSE-QL42.3/Manjaro-17.0.2-KDE
#4
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
 
#5
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.
 

Discussioni Simili