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<=k<=n), senza tener conto del loro ordine e senza ripetizione degli n elementi stessi; (esempio di utilizzo, partite di un torneo di n squadre dove tutte si scontrano una volta).
    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; i<k; i++)
    printf(“%d ”, sol);
    printf(“\n”);
    return count+1;
    }

    for(i = start; i<n; 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<=k), senza considerarne l’ordine; la ripetizione degli elementi un diverso numero di volte genera differenti soluzioni. (esempio di utilizzo, risultati del lancio di due dadi).
    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; i<k; i++)
    printf(“%d ”, sol);
    printf(“\n”);
    return count+1;
    }

    for(i = start; i<n; i++){
    sol[pos] = val;
    count = comb_r(pos+1, val, sol, n, k, start, count);
    start++;
    }
    return count;
    }

Hai bisogno di aiuto in Informatica?
Trova il tuo insegnante su Skuola.net | Ripetizioni
Registrati via email