Clasa a 8-a lecția 2 - 30 sep 2015

From Algopedia
Jump to navigationJump to search

Exemple

Permutări

Permutările numerelor de la 1 la N sunt toate modurile în care pot fi ordonate numerele de la 1 la N.

De exemplu, pentru N = 3, toate modurile în care pot fi ordonate numerele 1, 2 și 3 sunt:

  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1

Aranjamente

Aranjamentele numerelor de la 1 la N luate câte K sunt toate modurile în care pot fi luate (alese) K numere dintre numerele de la 1 la N și ordonate (aranjate).

De exemplu, pentru N = 3, și K = 2 toate modurile în care pot fi aranjate 2 dintre numerele 1, 2 și 3 sunt:

  • 1, 2
  • 2, 1
  • 1, 3
  • 3, 1
  • 2, 3
  • 3, 2

Combinări

Combinările numerelor de la 1 la N luate câte K sunt toate modurile în care pot fi luate (alese) K numere dintre numerele de la 1 la N (fără a ține cont de ordinea în care le alegem).

De exemplu, pentru N = 3, și K = 2 toate modurile în care pot fi alese 2 dintre numerele 1, 2 și 3 sunt:

  • 1, 2
  • 1, 3
  • 2, 3

Implementare

Generarea permutărilor, aranjamentelor și combinărilor se face cel mai ușor prin backtracking recursiv. Dinferențele de implementare dintre cele trei probleme sunt minore și le vom analiza în continuare.

Permutări

Pentru generarea permutărilor vom ține minte, în timpul execuției backtracking-ului:

  • permCurenta: începutul (prefixul) permutării curente (cea pe care urmează să o generăm);
  • lista: o listă cu toate elementele de la 1 la N care nu fac parte din începutul permutării curente.

Condiția de oprire a recursivității (backtracking-ului) este ca începutul permutării curente să fie o permutare completă (să aibă dimensiunea N).

Atunci în backtracking-ul nu se oprește, încearcă să completeze prefixul permutării curente cu un element care nu face parte din prefix. De accea vva parcurge elementele din lista și pe rând, va completa prefixul curent cu fiecare și va completa apoi restul permutării în mod recursiv.

Operații pe listă

Vom avea nevoie de trei operații pe lista elementelor nefolosite încă:

  • void listaInit(int N): Inițializarea liste cu toate elementele de la 1 la N;
  • void stergeDinLista(int pozitie): Eliminarea elementului de pe o anumită poziție din listă (și mutarea ultimului element din listă în locul celui eliminat);
  • void adaugaInLista(int pozitie, int valoare): Adăugarea unei valori pe o anumită poziție din listă (și mutarea fostei valori la sfârșitul listei).

Implementare

#include <stdio.h>

const int MAX_N = 10;

int lista[MAX_N];
int lungimeLista;

void listaInit(int N) {
    int i;
    for (i = 0; i < N; ++i) {
        lista[i] = i + 1;
    }
    lungimeLista = N;
}

void stergeDinLista(int pozitie) {
    lungimeLista--;
    lista[pozitie] = lista[lungimeLista];
}

void adaugaInLista(int pozitie, int valoare) {
    lista[lungimeLista] = lista[pozitie];
    lungimeLista++;
    lista[pozitie] = valoare;
}

int N;
int permCurenta[MAX_N];

void permN(int poz) {
    if (poz == N) {
        int i;
        for (i = 0; i < N; ++i) {
            printf("%d ", permCurenta[i]);
        }
        printf("\n");
    } else {
        int i;
        for (i = 0; i < lungimeLista; ++i) {
            permCurenta[poz] = lista[i];
            stergeDinLista(i);
            permN(poz + 1);
            adaugaInLista(i, permCurenta[poz]);
        }
    }
}

int main(void) {
    // citirea datelor
    scanf("%d", &N);

    // calcularea solutiei
    // afisarea solutiei
    listaInit(N);
    permN(0);

    return 0;
}

Aranjamente

Pentru generarea aranjamentelor vom face o singură modificare la algoritmul de generare al permutărilor: vom modifica condiția de oprire astfel încât lungimea aranjării curente să fie K.

Implementare

#include <cstdio>

const int MAX_N = 18;

int lista[MAX_N];
int lungimeLista;

void listaInit(int N) {
    int i;
    for (i = 0; i < N; ++i) {
        lista[i] = i + 1;
    }
    lungimeLista = N;
}

void stergeDinLista(int pozitie) {
    lungimeLista--;
    lista[pozitie] = lista[lungimeLista];
}

void adaugaInLista(int pozitie, int valoare) {
    lista[lungimeLista] = lista[pozitie];
    lungimeLista++;
    lista[pozitie] = valoare;
}

int N, K;
int aranjCurenta[MAX_N];

void aranjNK(int poz) {
    if (poz == K) {
        int i;
        for (i = 0; i < K; ++i) {
            printf("%d ", aranjCurenta[i]);
        }
        printf("\n");
    } else {
        int i;
        for (i = 0; i < lungimeLista; ++i) {
            aranjCurenta[poz] = lista[i];
            stergeDinLista(i);
            aranjNK(poz + 1);
            adaugaInLista(i, aranjCurenta[poz]);
        }
    }
}

int main(void) {
    // citirea datelor
    scanf("%d %d", &N, &K);

    // calcularea solutiei
    // afisarea solutiei
    listaInit(N);
    aranjNK(0);

    return 0;
}

Combinări

Pentru generarea combinărilor numerelor de la 1 la N luate câte K vom ține un vector de elemente bool (folosind biții unui întreg - combCurenta) cu rol de vector de frecvență: numărul i face sau nu face parte din prefixul curent al combinării în curs de generare.

Vom folosi shiftări pe biți pentru generarea de măști și operația ^ (xor) pentru schimbarea valorii unui anumit bit.

Implementare cu vector global

#include <cstdio>

const int MAX_N = 18;

int N, K;
int combCurenta[MAX_N];

void combK(int poz = 0, int ultim = 0) {
    if (poz == K) {
        int i;
        for (i = 0; i < K; ++i) {
            printf("%d ", combCurenta[i]);
        }
        printf("\n");
    } else {
        int i;
        for (i = ultim + 1; i <= N; ++i) {
            combCurenta[poz] = i;
            combK(poz + 1, i);
        }
    }
}

int main(void) {
    freopen("combinari.in", "r", stdin);
    freopen("combinari.out", "w", stdout);

    // citirea datelor
    scanf("%d %d", &N, &K);

    // calcularea solutiei
    // afisarea solutiei
    combK();

    return 0;
}

Implementare cu întreg global

#include <cstdio>

const int MAX_N = 18;

int N, K;
int combCurenta;

void combK(int poz = 0, int ultim = -1) {
    if (poz == K) {
        int i;
        for (i = 0; i < N; ++i) {
            if (combCurenta & (1 << i)) {
                printf("%d ", i + 1);
            }
        }
        printf("\n");
    } else {
        int i;
        for (i = ultim + 1; i < N; ++i) {
            combCurenta ^= 1 << i;
            combK(poz + 1, i);
            combCurenta ^= 1 << i;
        }
    }
}

int main(void) {
    freopen("combinari.in", "r", stdin);
    freopen("combinari.out", "w", stdout);

    // citirea datelor
    scanf("%d %d", &N, &K);

    // calcularea solutiei
    // afisarea solutiei
    combK();

    return 0;
}

Implementare cu întreg dat ca parametru

#include <cstdio>

const int MAX_N = 18;

int N, K;
int combCurenta[MAX_N];

void combK(int poz = 0, int ultim = 0) {
    if (poz == K) {
        int i;
        for (i = 0; i < K; ++i) {
            printf("%d ", combCurenta[i]);
        }
        printf("\n");
    } else {
        int i;
        for (i = ultim + 1; i <= N; ++i) {
            combCurenta[poz] = i;
            combK(poz + 1, i);
        }
    }
}

int main(void) {
    freopen("combinari.in", "r", stdin);
    freopen("combinari.out", "w", stdout);

    // citirea datelor
    scanf("%d %d", &N, &K);

    // calcularea solutiei
    // afisarea solutiei
    combK();

    return 0;
}

Programare dinamică

Astăzi am discutat rezolvarea problemei 1635 - Mnemonics and Palindromes (Timus). Celor care au fost atenți, au înțeles și au reținut idea rezolvării le va fi mai ușor să rezolve această problemă dată și ca temă.

Temă

Pentru data viitoare veți avea de rezolvat următoarele probleme: