Concetti Chiave
- Le combinazioni semplici consentono di generare configurazioni di k elementi da un insieme di n elementi distinti, utilizzando il coefficiente binomiale per calcolare il numero totale.
- Il codice per le combinazioni semplici utilizza una funzione ricorsiva che incrementa il contatore ogni volta che una combinazione valida viene trovata e stampata.
- Le combinazioni ripetute permettono di selezionare k elementi da un insieme di n elementi distinti, considerando la possibilità di ripetizioni, e il numero totale si calcola con una formula specifica.
- La funzione per le combinazioni ripetute utilizza una logica simile a quella delle combinazioni semplici, ma permette la ripetizione degli elementi modificando il parametro di partenza.
- Entrambe le funzioni stampano tutte le combinazioni generate, aumentando il contatore per tenere traccia del numero di combinazioni esplorate.
Esplorazione dello spazio - Combinazioni semplici e ripetute in C
- Combinazioni semplici: le combinazioni semplici permettono di esplorare lo spazio delle soluzioni di k elementi dato un insieme di n elementi distinti (0
Vi sono esattamente (n|k) (coefficiente binomiale) combinazioni semplici.
Esempio:
int comb_s(int pos, int *val, int *sol, int n, int k, int start, int count){
int i;
if(pos>=k){
for(i = 0; iprintf(“%d ”, sol);
printf(“\n”);
return count+1;
}for(i = start; i
sol[pos] = val;
count = comb_s(pos+1, val, sol, n, k, i+1, count);
}
return count;
} - Combinazioni ripetute: permettono di esplorare lo spazio delle soluzioni di k elementi dato un insieme di n elementi distinti (0
Vi sono esattamente (n+k-1)!/(k!x(n-1)!) combinazioni ripetute.
Esempio:
int comb_r(int pos, int *val, int *sol, int n, int k, int start, int count){
int i;
if(pos>=k){
for(i = 0; iprintf(“%d ”, sol);
printf(“\n”);
return count+1;
}for(i = start; i
sol[pos] = val;
count = comb_r(pos+1, val, sol, n, k, start, count);
start++;
}
return count;
}
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
