Recursivitate și backtracking

Ce cere problema

Numerele se împart în două grupe, după comparația cu M = 5:

Prima submulțime este {1, 3, 2, −1, −11}, a doua este {6, 9}. Exemplul le afișează în ordine crescătoare, deci programul le ordonează înainte de afișare.

Enunțul cere ca partiționarea să se facă recursiv. Ea se poate scrie astfel: se cercetează primul element al secvenței, apoi aceeași prelucrare se face, prin autoapel, pentru secvența rămasă.

• dacă primul element este mai mic decât M, el rămâne la începutul tabloului, iar autoapelul cercetează secvența de după el;
• altfel, se schimbă cu ultimul element al secvenței și rămâne la sfârșitul tabloului, iar autoapelul cercetează secvența fără ultima poziție;
• condiția de oprire: secvența nu mai are niciun element.

La sfârșit, elementele mai mici decât M ocupă începutul tabloului, iar celelalte, sfârșitul.

Încearcă împărțirea

Se scriu numerele și valoarea M. Fiecare pas este un apel al funcției imparte. În stânga se adună elementele mai mici decât M, în dreapta celelalte. Sub tablou sunt apelurile în desfășurare. După împărțire, fiecare parte se ordonează, apel cu apel.

Programul și descrierea lui

În stânga sunt subprogramele și programul principal, așa cum se scriu pe foaia de examen. În dreapta este descrierea lor în limbaj natural, cu pașii așezați pe niveluri după structura programului.

Ce cere problema

Suma tuturor elementelor din exemplu este 4 − 1 + 3,7 + 2 + 5,25 − 0,7 = 13,25, deci nu este număr întreg. Se elimină cât mai puține elemente, până când suma celor rămase devine întreagă:

Un singur element eliminat ajunge, deci se afișează 4 -1 3.7 2 -0.7.

Backtracking-ul. Se încearcă întâi k = 0 elemente eliminate, apoi k = 1, k = 2 și așa mai departe. Pentru un k fixat, pozițiile eliminate se generează ca submulțimile cu k elemente ale mulțimii {1, 2, …, n}: în stiva st, în ordine crescătoare. Prima eliminare găsită folosește cel mai mic k, deci numărul minim de elemente eliminate.

Suma, calculată exact. Numerele reale nu se pot aduna exact în calculator: 0,1 + 0,2 nu dă exact 0,3. Fiecare element are cel mult 3 zecimale, deci, înmulțit cu 1000, devine un număr întreg: 3,7 devine 3700, iar −0,7 devine −700. Suma este întreagă dacă suma acestor numere se împarte exact la 1000.

Încearcă eliminarea

Se scriu numerele. La fiecare pas se arată o alegere a pozițiilor eliminate, tăiate în șir, și suma elementelor rămase. Generarea se oprește la prima sumă întreagă.

Programul și descrierea lui

În stânga sunt subprogramele și programul principal, așa cum se scriu pe foaia de examen, cu comentariile cerute de enunț. În dreapta este descrierea lor în limbaj natural, cu pașii așezați pe niveluri după structura programului.

Ce cere problema

Se aleg m numere diferite dintre 1, 2, …, n. Ordinea lor nu contează: {1, 2, 4} și {4, 2, 1} sunt aceeași submulțime. Pentru n = 4 și m = 3 sunt patru submulțimi:

Exemplul din enunț arată numai trei dintre ele: lipsește submulțimea 1 3 4. Programul trebuie să le afișeze pe toate patru.

Ca o submulțime să fie afișată o singură dată, elementele ei se scriu în ordine crescătoare. Soluția se reține în stiva st: st[1] < st[2] < … < st[m].

Ce valori poate primi nivelul k. st[k] pornește de la st[k − 1] + 1, ca să fie mai mare decât elementul dinaintea lui. Valoarea cea mai mare este n − m + k: după nivelul k mai urmează m − k niveluri, care au nevoie de m − k valori mai mari. Pentru n = 4 și m = 3:

Încearcă generarea

Se scriu n și m. La fiecare pas, nivelul curent al stivei primește o valoare. Când toate cele m niveluri sunt completate, submulțimea se afișează. Când un nivel a primit toate valorile, se revine la nivelul dinainte.

Programul și descrierea lui

În stânga sunt subprogramele și programul principal, așa cum se scriu pe foaia de examen. În dreapta este descrierea lor în limbaj natural, cu pașii așezați pe niveluri după structura programului.

Ce cere problema

O modalitate de plată spune câte bancnote se iau din fiecare cupiură. Numărul se reține în tabloul b: b[i] este numărul de bancnote de c[i] lei. Pentru s = 10 și cupiurile 1, 2, 3, 5:

Ordinea în care se numără bancnotele nu contează: o bancnotă de 5 lei și una de 3 lei dau același tablou b, oricare ar fi numărată prima. Cupiurile cu b[i] = 0 nu se afișează.

Backtracking-ul. Tabloul b este stiva. Nivelul i corespunde cupiurii c[i] și primește pe rând valorile 0, 1, 2, …, cât timp bancnotele încap în suma rămasă de plătit. Soluția este completă când toate cupiurile au primit o valoare, iar suma rămasă este 0.

Încearcă generarea

Se scriu suma și cupiurile. La fiecare pas, cupiura curentă primește un număr de bancnote, iar suma rămasă scade. O soluție găsită se afișează pe ecran. O alegere care lasă la sfârșit o sumă diferită de 0 se respinge.

Programul și descrierea lui

În stânga sunt subprogramele și programul principal, așa cum se scriu pe foaia de examen. În dreapta este descrierea lor în limbaj natural, cu pașii așezați pe niveluri după structura programului.

#include <iostream>
using namespace std;

int n, s;
int c[11];   // cupiurile din casierie
int b[11];   // cate bancnote se folosesc din fiecare cupiura

void tipar() {
    for (int i = 1; i <= n; i++)
        if (b[i] > 0) {
            cout << b[i] << "x" << c[i];
            if (c[i] == 1)
                cout << "leu ";
            else
                cout << "lei ";
        }
    cout << endl;
}

void construieste(int i, int ramas) {
    if (i > n) {
        if (ramas == 0)
            tipar();
        return;
    }
    for (int k = 0; k * c[i] <= ramas; k++) {
        b[i] = k;
        construieste(i + 1, ramas - k * c[i]);
    }
}

int main() {
    cin >> s >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    construieste(1, s);

    return 0;
}