Esplorazione dello spazio - Disposizioni semplici e ripetute in C


  • Disposizioni semplici: le disposizioni semplici permettono di esplorare lo spazio delle soluzioni di k elementi dato un insieme di n elementi distinti (con 0 <= k <= n), tenendo conto del loro ordine e senza ripetizione dei k elementi stessi; (esempio di utilizzo, quanti numeri da 2 cifre si possono creare con 4, 5 , 2, 1).
    Vi sono esattamente (n!)/(n-k)! disposizioni semplici.

    Esempio:

    int disp_s(int pos, int *val, int *sol, int *mark, int n, int k, int count){
    int i;
    if(pos>=k){
    for(i = 0; i<k; i++)
    printf(“%d ”, sol);
    printf(“\n”);
    return count+1;
    }

    for(i = 0; i<n; i++){
    if(mark == 0){
    mark
    = 1;
    sol[pos] = val;
    count = disp_s(pos+1, val, sol, mark, n, k, count);
    mark
    = 0;
    }
    }
    return count;
    }


  • Disposizioni ripetute: permettono di esplorare lo spazio delle soluzioni di k elementi dato un insieme di n elementi distinti (con 0 <= k), considerandone l’ordine e permettendo la ripetizione degli elementi; (esempio di utilizzo, tutti i possibili numeri binari formati da 3 cifre).
    Vi sono esattamente n^k disposizioni ripetute.

    Esempio:

    int disp_r(int pos, int *val, int *sol, int n, int k, int count){
    int i;
    if(pos>=k){
    for(i = 0; i<k; i++)
    printf(“%d ”, sol);
    printf(“\n”);
    return count+1;
    }

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

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