Backtracking

Backtracking (visszalépéses keresés)

Feladatmegoldási módszer, leggyakrabban kombinatorikai elemek generálására vagy ezek közötti keresésre használjuk.

Bevezető feladatok

1. Írjuk ki az összes kétjegyű számot, amit az {1,2,3,4} számjegyekből alkothatunk (ismétlődhetnek is)!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <iostream>
using namespace std;

int main()
{
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            cout << i << j << endl;
            // cout << i*10 + j << endl;
        }
    }

    return 0;
}

2. Írjuk ki az összes háromjegyű számot, amit az {1,2,3,4} számjegyekből alkothatunk (ismétlődhetnek is)!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <iostream>
using namespace std;

int main()
{
    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++)
            for (int k = 1; k <= 4; k++)
                cout << i << j << k << endl;

    return 0;
}

3. Adott k esetén (bemenet) írjuk ki az összes k-jegyű számot, amit az {1,2,3,4} számjegyekből alkothatunk (ismétlődhetnek is)!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
using namespace std;

void f(int szint, int k, int megoldas[])
{
    if (szint > k) {
        for (int i = 0; i < k; i++)
            cout << megoldas[i];
        cout << endl;
    }
    else {
        for (int i = 1; i <= 4; i++) {
            megoldas[szint-1] = i;
            f(szint+1, k, megoldas);
        }
    }
}

int main()
{
    int k;
    cin >> k;
    cout << "-----------" << endl;

    int megoldas[100];

    f(1, k, megoldas);

    return 0;
}