-

Esercizio c++

Stato
Discussione chiusa ad ulteriori risposte.
#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?
 
3,128
853
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
 
3,128
853
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.
 
Stato
Discussione chiusa ad ulteriori risposte.

Discussioni Simili


Entra