116444 afișări Candale Silviu (silviu) 05.10.2021
www.pbinfo.ro

Problema:

Se dă un număr natural n. Să se genereze toate submulțimile mulțimii {1,2,3,...,n}.

Soluție:

Pentru rezolvare folosim metoda backtracking. Acest articol prezintă două metode de rezolvare.

Metoda 1

În vectorul soluție x[] vom memora pe rând câte o submulțime. Deoarece submulțimile au număr variabil de elemente, și vectorul soluție va avea un număr variabil de elemente.

  • semnificaţia vectorului soluție: x[] reprezintă la un moment dat o submulțime
  • condiții externe: x[k] în {1,2,..,n}, k între 1 și n;
  • condiții interne: x[k]>x[i], i între 1 și k-1. Deoarece condițiile interne se aplică pentru toate elementele vectorului soluție, este suficient ca x[k]>x[k-1], pentru k>1;
  • condiții de existența a soluției: fiecare variantă a vectorului soluție corespunde cu o submulțime. Orice valoare validă plasată în vectorul soluție conduce la o soluție.
void afis(int k){
    for(int i=1 ; i<=k ; ++i)
        cout << x[i] << " ";
    cout << endl;
}
bool valid(int k){
    if(k == 1)
        return true;
    if(x[k] > x[k-1])
        return true;
    return false;
}
void back(int k){
    for(int i=1;i<=n;++i)
    {
        x[k]=i;
        if(valid(k))
        {
            afis(k);
            back(k+1);
        }
    }
}

Constatăm că putem rafina condițiile externe; deoarece x[k]>x[k-1], condițiile devin:

  • Condiții externe: x[k] în {x[k-1]+1, ... , n}, k între 1 și n. Pentru a uniformiza algoritmul, considerăm de la început că x[0] = 0;
  • Condiții interne: nu mai avem condiții interne; funcția valid() nu mai este necesară;
  • Condiții de existența a soluției rămân aceleași.
void back(int k){
    for(int i=x[k-1]+1;i<=n;++i)
    {
        x[k]=i;
        afis(k);
        back(k+1);
    }
}

Să observăm că submulțimea vidă nu se regăsește printre soluțiile generate cu acest algoritm. Dacă este cazul, afișarea ei se poate face în afara algoritmului de generare.

Metoda 2

Această metodă se bazează pe observația că pentru fiecare submulțime a mulțimii date, {1,2,...,n} îi corespunde un șir de n biți, notat x[], astfel:

  • dacă bitul x[k] = 0, elementul k nu aparține submulțimii curente;
  • dacă bitul x[k] = 1, elementul k aparține submulțimii curente.

Reamintim că o mulțime cu n elemente are 2 n submulțimi.

Exemplificăm cu mulțimea {1,2,3,4}.

0 0000 {} 8 1000 {1}
1 0001 {4} 9 1001 {1,4}
2 0010 {3} 10 1010 {1,3}
3 0011 {3,4} 11 1011 {1,3,4}
4 0100 {2} 12 1100 {1,2}
5 0101 {2,4} 13 1101 {1,2,4}
6 0110 {2,3} 14 1110 {1,2,3}
7 0111 {2,3,4} 15 1111 {1,2,3,4}

Putem să generăm toate șirurile de n biți, iar pentru fiecare șir să construim submulțimea corespunzătoare. Generarea șirurilor se poate face în mai multe moduri:

  • parcurgem numerele de la 0 la 2n-1 și transformăm fiecare număr în baza 2; obținem astfel pentru fiecare număr un șir de biți care va fi transformat în submulțime;
  • generăm direct șirul de biți cerut cu metoda backtracking.

Vom detalia mai jos rezolvarea cu backtracking:

  • semnificaţia vectorului soluție: x[] conține la un moment dat un șir de biți care va corespunde unei submulțimi
  • condiții externe: x[k] = 0 sau 1;
  • condiții interne nu există. Orice configurație parțială a vectorului x[] va conduce la o soluție validă
  • condiții de existență a soluției: k == n.
void afis(int k){
    for(int i=1 ; i <= k ; ++i)
        if(x[i] == 1)
            cout << i << " ";
    cout << endl;
}

void back(int k){
    for(int i = 0; i <= 1 ; ++i)
    {
        x[k]=i;
        if(k == n)
            afis(k);
        else
            back(k+1);
    }
}

Probleme

#201 Clasa 11 Fișiere medie

SubmDiv

Să se determine toate submulţimile cu m elemente ale mulţimii divizorilor unui număr natural dat.

#198 Clasa 11 Fișiere ușoară

Submultimi

Se citește un număr natural nenul n. Să se afişeze, în ordine lexicografică, toate submulțimile nevide ale mulţimii {1,2,..,n}.

#204 Clasa 11 Fișiere medie

Siruri

Se citesc două numere naturale nenule n și m. Să se determine toate şirurile cu m elemente din mulţimea {1,2,..,n}, ordonate strict crescător, cu proprietatea că oricare două elemente consecutive în şir au diferenţa mai mică sau egală cu cu 2.

Citește și


116444 afișări Candale Silviu (silviu) 05.10.2021
www.pbinfo.ro
Du-te sus!