[C++, programare dinamică] Problema subșirului crescător maximal




Considerăm un vector A cu N elemente numere întregi. Un subșir a lui A este o secvență de elemente nu neapărat consecutive ale lui A, dar a căror ordine relativă în A este păstrată. Un subșir crescător al lui A este un subșir al lui A ale cărui elemente sunt ordonate crescător. Un subșir crescător maximal este un subșir crescător la care nu se mai pot adăuga elemente fără a strica proprietatea de subșir crescător. Se cere determinarea celui mai lung subșir crescător maximal al vectorului A.
Datele de intrare se citesc din fișierul subsir.in. In fișierul subsir.out se va afișa pe prima linie lungimea lg a celui mai lung subșir crescător maximal găsit, iar pe următoarea linie se vor afișa valorile (în număr de lg) care constituie un astfel de subșir. Se poate afișa orice soluție dacă există mai multe.

Exemplu:
subsir.in
subsir.out
10
6 3 8 9 1 2 10 4 -1 11
5
6 8 9 10 11

Problema admite o rezolvare prin programare dinamică în timp O(N2), dar și o rezolvare greedy în timp O(N·log N). Vom prezenta ambele rezolvări.


Rezolvarea prin programare dinamică presupune găsirea unei formule de recurență care fie va furniza direct răspunsul problemei, fie va fi doar un pas intermediar în rezolvarea problemei. In acest caz, putem găsi o formulă de recurență pentru Lg care va conduce direct la calcularea acestei valori. Raționamentul este unul similar cu cel de la problema anterioară. Fie L[i] = lungimea celui mai lung subșir crescător maximal care se termină e poziția i. Inițial vom considera L[i] = 1 pentru fiecare 1 ≤ i ≤ N. Evident, L[1] va rămâne întotdeauna 1, deoarece singurul subșir al unui vector cu un singur element este însuși acel vector.

Să presupunem acum că avem calculate valorile L[1], L[2], …, L[k] pentru un k < N. Ne propunem să calculăm L[k + 1]. Folosind definiția lui L, ne propunem așadar să calculăm lungimea celui mai lung subșir crescător maximal care se termină pe poziția k + 1, știind lungimile celor mai lungi subșiruri crescătoare maximal care se termină pe pozițiile 1, 2, …, k. Stiind aceste valori, este evident că pentru a maximiza lungimea subșirului care se termină pe poziția k + 1 trebuie adăugat A[k + 1] unui subșir maximal care se termină pe o poziție j < k + 1, pentru care L[j] are valoarea maximă și pentru care A[j] < A[k + 1], deoarece subșirul trebuie să fie crescător. Așadar obținem recurența:

    L[1] = 1
    L[i] = 1 + max{L[j] | A[j] < A[i]} sau 1 dacă mulțimea respectivă e vidă, unde 1 ≤ j < i.

( n.e. Trebuie adăugat A[k + 1] ca o continuare la subșirul crescător maximal de lungime maximă descoperit până la k, acest subșir se termină pe o poziție j < k + 1 și e necesar ca A[j] < A[k + 1]. )

Timpul O(N2) rezultă din faptul că pentru fiecare i trebuie să determinăm minimul subsecvenței [1, i – 1], rezultând un număr pătratic de operații. Valoarea lg este dată de valoarea maximă din vectorul L.

Pentru determinarea valorilor care fac parte din subșirul crescător maximal vom folosi un vector P unde P[i] = poziția ultimului element care a intrat în calculul lui L[i] sau 0 dacă nu există. In alte cuvinte, dacă L[i] = 1 + max{L[j] | A[j] <  A[i]} = 1 + L[max], 1 ≤ j < i, atunci vom avea P[i] = max.


Vom evidenția în continuare modul de execuție al algoritmului pe exemplul dat. Inițial avem:

i
1
2
3
4
5
6
7
8
9
10
A[i]
6
3
8
9
1
2
10
4
-1
11
L[i]
1
1
1
1
1
1
1
1
1
1
P[i]
0
0
0
0
0
0
0
0
0
0


La pasul i = 2 căutăm poziția max a celui mai mare element din subsecvența [1, 1] a vectorului L pentru care A[max] < A[2]. Nu se găsește nicio astfel de poziție, așa că totul rămâne neschimbat.

La pasul i = 3 căutăm același max din subsecvența [1, 2] a vectorului L pentru care are loc A[max] < A[3]. Putem alege de data aceasta fie max = 1, fie max = 2, ambele poziții respectând condițiile impuse. Vom alege max = 1. Așadar, L[3] devine L[max]+1 = L[1]+1 = 2, iar P[3] devine max, adică 1. Am marcat cu roșu actualizările:

i
1
2
3
4
5
6
7
8
9
10
A[i]
6
3
8
9
1
2
10
4
-1
11
L[i]
1
1
2
1
1
1
1
1
1
1
P[i]
0
0
1
0
0
0
0
0
0
0


Se procedează în acest fel până la completarea vectorilor L și P. Forma lor finală este prezentată mai jos. Este ușor de verificat corectitudinea calculării acestor vectori conform definiției lor.

i
1
2
3
4
5
6
7
8
9
10
A[i]
6
3
8
9
1
2
10
4
-1
11
L[i]
1
1
2
1
3
1
4
3
1
5
P[i]
0
0
1
3
0
5
4
6
0
7


Am marcat mai sus coloanele care identifică o soluție optimă. Vom explica în continuare cum putem folosi vectorul P pentru a obține valorile soluției optime. Fie sol poziția celui mai mare element din vectorul L. In acest caz, sol = 10. Este clar că ultima valoare din subșirul crescător maximal este atunci A[10]. Deoarece P[i] reprezintă ultima valoare care a intrat în calcului lui L[i] (sau predecesorul lui i), P[10] reprezintă poziția penultimei valori a subșirului crescător maximal găsit. Atunci A[ P[10] ] reprezintă penultima valoare a soluției. Mergând în continuare cu acest raționament, A[ P[ P[10] ] ] va reprezenta antepenultima valoare și așa mai departe până când ajungem la o valoare k pentru care P[k] = 0. Când acest lucru se întâmplă, am găsit prima valoare a subșirului soluție.

Vom folosi așadar o funcție recursivă care va reconstitui soluția folosind vectorul P. Acest vector se numește vector de predecesori, iar ideea folosită în construcția sa poate fi aplicată la orice problemă de programare dinamică la care se cere afișarea unor obiecte care constituie un optim cerut. Prezentăm întregul program care rezolvă problema.


Această rezolvare poate fi optimizată folosind structuri de date avansate, cum ar fi arbori de intervale sau arbori indexați binar, dar aceste structuri nu vor fi prezentate în cadrul acestui capitol și nu sunt nici cea mai bună metodă de a rezolva optim această problemă.

Vom prezenta în continuare o rezolvare optimă cu timpul de execuție O(N · log N) care nu presupune decât noțiuni algoritmice elementare.

Vom considera A ca fiind vectorul citit și vom folosi încă doi vectori L și P, dar care nu vor avea aceeași semnificație ca până acum.

Mai întâi inițializăm vectorul L cu valoarea infinit. Aplicăm apoi următorul algoritm:

  • Pentru fiecare i de la 1 la N execută
    • Suprascrie A[i] peste cel mai mic element din L, dar care este strict mai mare decât A[i]. (1)
    • Fie k poziția peste care a fost suprascris A[i]. P[i] ia valoarea k.
  • Lungimea vectorului L (făcând abstracție de pozițiile marcate cu infinit) reprezintă lungimea celui mai lung subșir crescător maximal.
  • Fie lg lungimea vectorului L. Pentru a reconstitui soluția, se caută în vectorul P poziția ultimei apariții a valorii lg. Fie această poziție klg. Se caută apoi ultima apariție a valorii lg – 1, dar care apare înainte de poziția klg. Aceasta va fi așadar pe o poziție klg – 1klg. Se procedează similar pentru valorile lg – 2, lg – 3,, 2, 1. Soluția va fi dată de subșirul: A[k1], A[k2], A[klg]. Putem implementa reconstituirea tot recursiv.
La pasul (1), dacă A[i] este mai mare decât toate elementele diferite de infinit din L, atunci A[i] se va suprascrie peste cea mai din stânga valoare egală cu infinit. Putem implementa acest pas eficient în timp O(log N) folosind o căutare binară.
Să prezentăm modul de execuție al algoritmului pe exemplul dat. Inițial avem:
i
1
2
3
4
5
6
7
8
9
10
A[i]
6
3
8
9
1
2
10
4
-1
11
L[i]
inf
inf
inf
inf
inf
inf
inf
inf
inf
inf
P[i]

La pasul i = 1, se suprascrie A[1] = 6 peste cea mai mică valoare din L, dar care este strict mai mare decât 6. Singura posibilitate este să suprascriem elementul A[1] peste primul inf. In P[1] vom reține 1:
i
1
2
3
4
5
6
7
8
9
10
A[i]
6
3
8
9
1
2
10
4
-1
11
L[i]
6
inf
inf
inf
inf
inf
inf
inf
inf
inf
P[i]
1

La pasul i = 2, A[2] = 3 se va suprascrie peste L[1] = 6, iar P[2] devine 1:
i
1
2
3
4
5
6
7
8
9
10
A[i]
6
3
8
9
1
2
10
4
-1
11
L[i]
3
inf
inf
inf
inf
inf
inf
inf
inf
inf
P[i]
1
1

A[3] se va suprascrie peste L[2], iar P[3] va deveni 2. Se procedează în acest mod pentru fiecare element din A, iar forma finală a vectorilor este:
i
1
2
3
4
5
6
7
8
9
10
A[i]
6
3
8
9
1
2
10
4
-1
11
L[i]
-1
2
4
10
11
inf
inf
inf
inf
inf
P[i]
1
1
2
3
1
2
4
3
1
5

Lungimea lg este așadar 5, deoarece există 5 elemente diferite de inf în L. Soluția este dată de A[2], A[3], A[4], A[7] și A[10].
Prezentăm în continuare implementarea acestei metode de rezolvare.

Deși acest algoritm este mai eficient, spre deosebire de metoda clasică, nu poate fi adaptat la toate variațiunile problemei.

Exercițiu: scrieți un program care determină cel mai scurt subșir crescător maximal și altul care determină numărul de subșiruri crescătoare maximal.

[C++, programare dinamică] Problema subsecvenței de produs maxim

Problema este de la finalul acestui fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Enunțul problemei

b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative).

Rezolvarea completă

Este aici. Mai jos sunt rezolvări care funcționează doar pe anumite date de intrare.

Cod sursă 1

In această secțiune se rezolvă problema pentru cazul numerelor reale strict pozitive, rezolvarea fiind foarte asemănătoare cu problema subsecvenței de sumă maximă.
Rezolvarea care folosește programarea dinamică este funcția subsecv6.
#include <fstream>
#include <iostream>
using namespace std;

const int inf = 1 << 30;
const int maxn = 2001;

float subsecv4(float A[], int N,
int &inceput, int &sfarsit)
{
float max = -inf;

for (int st = 1; st <= N; ++st)
{
for (int dr = st; dr <= N; ++dr)
{
float temp = 1;
for (int i = st; i <= dr; ++i)
temp *= A[i];

if (temp > max)
{
inceput = st;
sfarsit = dr;
max = temp;
}
}
}

return max;
}


float subsecv5(float A[], int N,
int &inceput, int &sfarsit)
{
float max = -inf;

for (int st = 1; st < N; ++st)
{
float temp = 1;
for (int dr = st; dr <= N; ++dr)
{
temp *= A[dr];
if (temp > max)
{
inceput = st;
sfarsit = dr;
max = temp;
}
}
}

return max;
}

float subsecv6(float A[], int N,
int &inceput, int &sfarsit)
{
float max = A[1];
int inceput_temp = 1;
float S[maxn];
S[1] = A[1];
inceput = sfarsit = 1;

for (int i = 2; i <= N; ++i)
{
if (S[i - 1] * A[i] > A[i])
{
S[i] = S[i - 1] * A[i];
}
else
{
inceput_temp = i;
S[i] = A[i];
}

if (S[i] > max)
{
inceput = inceput_temp;
sfarsit = i;
max = S[i];
}
}

return max;
}

int main()
{
float A[maxn], N;

ifstream in("subsecv.in");
in >> N;
for (int i = 1; i <= N; ++i)
{
in >> A[i];
}
in.close();

ofstream out("subsecv.out");
int inceput, sfarsit;
// Toate cele 3 functii de mai sus se
// apeleaza identic.
float max = subsecv6(A, N,
inceput, sfarsit);
out << max << " " << inceput <<
" " << sfarsit << endl;
out.close();

return 0;
}

Cod sursă 2

In această secțiune se rezolvă problema pentru cazul numerelor întregi (negative, zero și pozitive).
#include <fstream>
#include <vector>
using namespace std;

const int inf = 1 << 30;
const int maxn = 100001;

double produs(vector<double> &A, int a, int b)
{
double r = A[a];
for (int i = a + 1; i <= b; ++i)
{
r *= A[i];
}
return r;
}

double produs_maxim_secv_fara_0(vector<double> &A, int a, int b,
int &inceput, int &sfarsit)
{
if (a == b)
{
inceput = a;
sfarsit = a;
return A[a];
}

int primul_negativ = -1;
int negative = 0;
int ultimul_negativ;

for (int i = a; i <= b; ++i)
{
if (A[i] >= 0)
{
continue;
}

++negative;
if (primul_negativ < 0)
{
primul_negativ = i;
}
ultimul_negativ = i;
}

if (negative % 2 == 0)
{
inceput = a;
sfarsit = b;
return produs(A, a, b);
}

if (primul_negativ + 1 > b)
{
inceput = a;
sfarsit = b - 1;
return produs(A, a, b - 1);
}

if (ultimul_negativ - 1 < a)
{
inceput = a + 1;
sfarsit = b;
return produs(A, a + 1, b);
}

double p1 = produs(A, primul_negativ + 1, b);
double p2 = produs(A, a, ultimul_negativ - 1);
if (p1 > p2)
{
inceput = primul_negativ + 1;
sfarsit = b;
return p1;
}

inceput = a;
sfarsit = ultimul_negativ - 1;
return p2;
}

double subsecv(vector<double> &A, int N,
int &inceput, int &sfarsit)
{
double maxim = A[1];
int i = 1, j;
while (i <= N)
{
while (i <= N && A[i] == 0)
{
++i;
}
j = i;
while (j <= N && A[j] != 0)
{
++j;
}

int inceput_temp, sfarsit_temp;
double p_nou = produs_maxim_secv_fara_0(A, i, j - 1,
inceput_temp, sfarsit_temp);
if (maxim <= p_nou)
{
maxim = p_nou;
inceput = inceput_temp;
sfarsit = sfarsit_temp;
}

i = j;
}

return maxim;
}

Intrări și ieșiri

1. (pentru primul cod sursă)
6
2 3 4 2 3 1
rezultă ieșirea:
144 1 5
2. (pentru primul cod sursă)
5
2 2 0.1 2 2

rezultă ieșirea:

4 1 2

Alte intrări

4
3 5 1 2
10
-6 1 -3 4 5 -1 3 -8 -9 1
6
-2 -3 -4 -2 -3 1
5
2 5 -1 -2 -4
9
1 2 0 -4 5 6 0 7 1
2
3 -8
2
-8 3
1
-3

[C++, programare dinamică] Subsecvența de sumă maximă – aflarea pozițiilor de început și sfârșit din cei doi vectori, nerecursiv

Aceasta este o continuare la articolul de la acest link. Aici nu se scrie în fișier ci pe ecran.

Vizual

Rezolvare

#include <iostream>
using namespace std;

void subsecv(int A[], int S[], int n, int &st, int &sf)
{
sf = -1;
int max = -(1 << 30); // -infinit
for (int i = 1; i <= n; ++i)
{
if (S[i] > max)
{
max = S[i], sf = i;
}
}

int crt = sf;
while (A[crt] != S[crt])
{
--crt;
}

st = crt;
}

int main()
{
int st, sf;

//int n = 10;
//int A[] = {0, -6, 1, -3, 4, 5, -1, 3, -8, -9, 1};
//int S[] = {0, -6, 1, -2, 4, 9, 8, 11, 3, -6, 1};

//int n = 8;
//int A[] = {0, -2, -3, 4, -1, -2, 1, 5, -3 };
//int S[] = {0, -2, -3, 4, 3, 1, 2, 7, 4 };

int n = 10;
int A[] = { 0, 0, -2, -3, 4, -1, -2, 1, 5, -3, 0 };
int S[] = { 0, 0, -2, -3, 4, 3, 1, 2, 7, 4, 4 };

subsecv(A, S, n, st, sf);

cout << "Inceput: " << st << endl
<< "Sfarsit: " << sf << endl;

return 0;
}

[C++, programare dinamică] Problema subsecvenței de sumă maximă

Considerăm un număr natural N și un vector A cu N elemente numere întregi. O subsecvență [st, dr] a vectorului A reprezintă suma tuturor elementelor acelei subsecvențe. Se cere determinarea unei subsecvențe de sumă maximă.
Datele de intrare se citesc din fișierul subsecv.in, iar suma maximă se va afișa în fișierul subsecv.out.
Exemplu:

subsecv.in subsecv.out
6 1 -3 4 5 -1 3 -8 -9 1 11

Vom prezenta trei metode de rezolvare, începând de la o metodă trivială și sfârșind cu metoda optimă de rezolvare, care constă într-o singură parcurgere a vectorului.

In implementările oferite ca model vom prezenta doar o funcție subsecvi(A, N) care primește ca parametri vectorul A respectiv dimensiunea acestuia și returnează suma maximă a unei subsecvențe. Considerăm citirea și afișarea ca fiind cunoscute.

Prima metodă constă în verificarea tuturor subsecvențelor vectorului de intrare A. Pentru fiecare subsecvență [st, dr] vom parcurge elementele A[st], A[st + 1], …, A[dr] și vom face suma acestora. Dacă această sumă este mai mare decât maximul curent (inițializat la început cu o valoare foarte mică: -infinit), actualizăm maximul curent. Complexitatea acestei metode este O(N3), deoarece există O(N2) subsecvențe și fiecare dintre acestea trebuie parcursă pentru a-i afla suma.

Putem implementa această metodă în felul următor:

A doua metodă de rezolvare are complexitatea O(N2) și este o simplă optimizare a primei metode. Vom încerca să eliminăm parcurgerea prin care facem suma subsecvenței [st, dr], sau, altfel spus, vom încerca să calculăm suma fiecărei subsecvențe pe măsură ce acestea sunt generate și nu pentru fiecare în parte printr-o parcurgere. Să presupunem că știm care este suma temp a unei subsecvențe [st, dr]. Atunci suma subsecvenței [st, dr + 1] va fi temp + A[dr + 1]. Vom inițializa așadar temp cu 0 pentru fiecare st, iar apoi vom aduna, pentru fiecare dr, pe A[dr] la temp și îl vom compara pe temp cu max:

Această implementare este deja relativ eficientă pentru vectori cu un număr de elemente de până la ordinul miilor, spre deosebire de prima implementare care este aplicabilă doar pentru un număr de elemente de ordinul sutelor. Putem obține însă o rezolvare și mai eficientă, care funcționează rapid pe vectori cu sute de mii sau chiar milioane de elemente.

Cea de-a treia metodă folosește paradigma programării dinamice pentru a obține o rezolvare în O(N). Fie S[i] = suma maximă a unei subsecvențe care se termină cu elementul i. Să presupunem că, pentru un anume 1 ≤ k < N, cunoaștem valoarea lui S[k]. Ne interesează să-l obținem pe S[k + 1] din S[k]. Observăm că avem două posibilități:

1. Adăugăm elementul k + 1 la sfârșitul subsecvenței de sumă maximă care se termină cu elementul k, obținând o subsecvență de sumă A[k + 1] + S[k],

2. Ignorăm subsecvența de sumă maximă care se termină cu elementul k și considerăm subsecvența formată doar din elementul k + 1, aceasta având suma A[k + 1].

Evident vom alege maximul sumelor aferente celor două cazuri. Așadar, obținem următoarea formulă de recurență:

S[k + 1] = max(A[k + 1] + S[k], A[k + 1]).

Să evidențiem modul de execuție al algoritmului pe exemplul dat. Inițial avem:

i
1
2
3
4
5
6
7
8
9
10
A[i]
-6
1
-3
4
5
-1
3
-8
-9
1
S[i]
-6


Pentru S[2] luăm maximul dintre S[1] + A[2] și A[2].
S[1] + A[2] = -1, iar A[2] = 1. Maximul este așadar A[2] = 1:

i
1
2
3
4
5
6
7
8
9
10
A[i]
-6
1
-3
4
5
-1
3
-8
-9
1
S[i]
-6
1


Se observă ușor că subsecvența de sumă maximă care se termină pe poziția 2 are suma 1 (cealaltă posibilitate fiind doar subsecvența [1, 2] care are suma -5), deci se respectă definiția lui S.

La sfârșit, vectorul S este următorul. Se poate verifica, folosind eventual implementările precedente, că acesta este corect calculat.

i
1
2
3
4
5
6
7
8
9
10
A[i]
-6
1
-3
4
5
-1
3
-8
-9
1
S[i]
-6
1
-2
4
9
8
11
3
-6
1


[ n.e. In loc de max = -inf trebuia max = A[1]. ]

Exerciții:

a) Modificați implementările date pentru a afișa și pozițiile de început și de sfârșit a unei subsecvențe de sumă maximă.

b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative).

c) Se dă o matrice și se cere determinarea unui dreptunghi de sumă maximă. Ultimul algoritm prezentat poate fi extins pentru rezolvarea problemei în O(N3). Cum?

[C++, programare dinamică] Problemă – algoritmul lui Lee (c) – afișarea tuturor drumurilor optime

Introducere în problema labirintului aici.

Enunț

c) Modificați funcția de afișare a drumului astfel încât să afișeze toate drumurile minime existente.

Explicație

Cum se cere modificarea funcției existente, nu crearea unei noi funcții, există opțiunea de a transforma funcția din recursivă în nerecursivă și de a folosi un arbore (fiecare nod al arborelui are cel mult 4 descendenți direcți, în structura de nod a arborelui se rețin coordonatele x – implicit -1, y – implicit -1 și părintele – implicit NULL).

Funcția recursivă de aflare a unui singur drum optim este următoarea:

void drum_unic(int D[maxn][maxn], int N, int x, int y,
ofstream &out)
{
if (D[x][y] == 0)
{
out
<< 2 5\n; // aici se înlocuiește „2 5” cu poziția de pornire
return;
}

for (int i = 0; i < 4; ++i)
{
int newx = x + dx[i];
int newy = y + dy[i];

if (valid(N, newx, newy))
if (D[newx][newy] == D[x][y] 1)
{ drum_unic(D, N, newx, newy, out);
break;
}
}

out << x << ‘ ‘ << y << \n;
}

Funcția nerecursivă de aflare a unui singur drum optim este următoarea:

void drum_unic_nerec(int D[maxn][maxn],
int N, ofstream &out)
{
queue<pair<int, int>> Q;

Q.push(make_pair(2, 5)); // aici se înlocuiește (2, 5) cu poziția de pornire

while (!Q.empty())
{
pair<int, int> p = Q.front();
Q
.pop();

out << p.first << ‘ ‘ << p.second << endl;

for (int i = 0; i < 4; ++i)
{
int newx = p.first + dx[i];
int newy = p.second + dy[i];

if (valid(N, newx, newy))
if (D[newx][newy] == D[p.first][p.second] + 1)
{
Q
.push(make_pair(newx, newy));
break;
}
}
}
}

Funcția nerecursivă de afișare a tuturor drumurilor optime este următoarea:

void toate_drumurile_nerec(int D[maxn][maxn],
int N, ofstream &out)
{
Nod *nod = new Nod;
nod->x = 2; // aici se înlocuiește (2, 5) cu poziția de pornire
nod->y = 5;

queue<Nod *> Q;
Q.push(nod);

while (!Q.empty())
{
Nod *p = Q.front();
Q.pop();

for (int i = 0; i < 4; ++i)
{
int newx = p->x + dx[i];
int newy = p->y + dy[i];

if (valid(N, newx, newy))
if (D[newx][newy] == D[p->x][p->y] + 1)
{
Nod *v = new Nod;
v->x = newx;
v->y = newy;
v->parinte = p;

if (p->copil1 == NULL)
{
p->copil1 = v;
}
else if (p->copil2 == NULL)
{
p->copil2 = v;
}
else if (p->copil3 == NULL)
{
p->copil3 = v;
}
else if (p->copil4 == NULL)
{
p->copil4 = v;
}
else
{
// eroare
}

Q.push(v);
}
}
}

// afisare:

stack<Nod *> s;
s.push(nod);

// parcurgere in adancime pentru gasirea tuturor frunzelor
while (!s.empty())
{
Nod *n = s.top();
s.pop();

bool are_descendenti_directi = false;
if (n->copil1 != NULL)
{
s.push(n->copil1);
are_descendenti_directi = true;
}
if (n->copil2 != NULL)
{
s.push(n->copil2);
are_descendenti_directi = true;
}
if (n->copil3 != NULL)
{
s.push(n->copil3);
are_descendenti_directi = true;
}
if (n->copil4 != NULL)
{
s.push(n->copil4);
are_descendenti_directi = true;
}

// daca este frunza (nu are descendenti directi)
if (!are_descendenti_directi)
{
afiseaza_drum_radacina_frunza(n, out);
// sau: afiseaza_drum_frunza_radacina(n);
}
}
}


Această funcție folosește următoarea structură:

struct Nod
{
Nod *parinte = NULL;
Nod *copil1 = NULL;
Nod *copil2 = NULL;
Nod *copil3 = NULL;
Nod *copil4 = NULL;
int x = -1,
y = -1;
};

și în plus, următoarele două funcții de afișare:

// afiseaza drumul de la o frunza la radacina
void afiseaza_drum_frunza_radacina(Nod *f, ofstream &out)
{
while (f != NULL)
{
out << f->x << " " << f->y << endl;

f = f->parinte;
}
out << endl;
}

// afiseaza drumul de la radacina la o frunza
void afiseaza_drum_radacina_frunza(Nod *f, ofstream &out)
{
stack<Nod *> s;

while (f != NULL)
{
s.push(f);

f = f->parinte;
}

while (!s.empty())
{
f = s.top();
s.pop();

out << f->x << " " << f->y << endl;
}
out << endl;
}

In rest codul este la fel ca in articolul de la link-ul de la începutul acestui articol. In funcția main se face apelul:

toate_drumurile_nerec(D, N, out);


după deschiderea fișierului lee.out care se face după apelul la funcția Lee.

Exemplu

Pentru datele de intrare:

5
1 1 1 1 1
1 0 0 0 0
1 0 0 1 1
1 0 0 1 1
1 0 1 1 1

datele de ieșire sunt:

6

2 5
2 4
2 3
2 2
3 2
4 2
5 2

2 5
2 4
2 3
3 3
3 2
4 2
5 2

2 5
2 4
2 3
3 3
4 3
4 2
5 2

[C++, programare dinamică] Problema labirintului – algoritmul lui Lee

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Am prezentat problema labirintului în cadrul secțiunii despre backtracking. Similar, se dă o matrice pătratică de dimensiune N, cu valori de 0 sau de 1, codificând un labirint. Valoarea 0 reprezintă o cameră deschisă, iar valoarea unu o cameră închisă. Se cere de data aceasta cel mai scurt drum de la poziția (1, 1) la poziția (N, N), mergând doar prin camere deschise și doar la stânga, dreapta, în jos sau în sus. Nu se poate trece de două ori prin același loc. Lungimea unui drum este dată de numărul de pași necesari parcurgerii drumului.
Vom citi datele de intrare din fișierul lee.in, iar în fișierul de ieșire lee.out vom afișa pe prima linie lungimea drumului minim, iar pe următoarele linii coordonatele care descriu un drum de lungime minimă.

Exemplu:

lee.in
lee.out
4
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
6
1 1
2 1
3 1
3 2
3 3
3 4
4 4

Rezolvarea prin metoda backtracking de la problema în care se cereau toate ieșirile din labirint se poate aplica și la această variantă a problemei. Trebuie doar să generăm toate drumurile, iar apoi să-l alegem pe cel de lungime minimă. Această rezolvare nu este însă eficientă, deoarece are la bază o căutare exhaustivă.

Problema se poate rezolva eficient în timp O(N2) folosind algoritmul lui Lee (care este de fapt o parcurgere în lățime pentru cei familiarizați cu noțiuni de teoria grafurilor). Algoritmul poate fi privit ca un algoritm de programare dinamică. Pentru a evidenția acest lucru, să presupunem că vrem să aflăm lungimea drumului minim de la poziția (1, 1) a matricei până la poziția (p, q). Deoarece dintr-o poziție (x, y) ne putem deplasa în pozițiile învecinate cu (x, y) la nord, sud, est sau vest, putem scrie următoarea formulă:

D[p][q] = 1 + min(D[p – 1][q], D[p + 1][q], D[p][q – 1], D[p][q + 1]), unde D[x][y] reprezintă distanța minimă de la (1, 1) la (x, y). Pentru indici invalizi sau care reprezintă un zid, distanța minimă va fi infinit.

Există mai multe metode de implementare a acestui algoritm. Fie A matricea dată. Prima metodă reprezintă implementarea relației de recurență exact așa cum este dată, cu ajutorul unei funcții recursive. Vom folosi pentru această metodă o matrice D cu semnificația anterioară și o funcție recursivă Lee(A, N, x, y, D) care va construi această matrice. Vom iniția D[1][1] cu 0, iar în restul matricei cu infinit, semnificând faptul că acele valori nu au fost calculate încă.

Funcția Lee poate fi implementată astfel:

  • Pentru fiecare vecin (newx, newy) al lui (x, y) execută:
    • Dacă (newx, newy) este o poziție validă, nu reprezintă un zid și D[newx][newy] > D[x][y] + 1 execută
      • D[newx][newy] = D[x][y] + 1
      • Apel recursiv Lee(A, N, newx, newy, D)
După apelul inițial lee(A, N, 1, 1, D), matricea D va fi calculată conform definiției sale, deci D[N][N] va conține distanța minimă.
Deși această metodă este cel mai ușor de implementat, nu este cea mai eficientă, deoarece funcția lee poate fi apelată de mai multe ori pentru aceeași poziție. Pentru a evidenția acest lucru vom prezenta modul de execuție al funcției de mai sus pe exemplul dat. Vom considera că vectorii de direcție (acest concept a fost definit la secțiunea dedicată metodei backtracking) sunt:
dx[] = {1, 0, -1, 0};
dy[] = {0, 1, 0, -1};


Inițial avem:
A D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
Primul vecin al poziției (1, 1), conform vectorilor de direcție folosiți este (2, 1). Această poziție este validă, nu conține un zid și ∞ > 0 + 1. Se observă că și al doilea pas va conduce la poziția validă (3, 1). Așadar, după primii doi pași avem:

A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ ∞ ∞
2 ∞ ∞ ∞
∞ ∞ ∞ ∞

Primul vecin al poziției (3, 1), este (4, 1), poziția invalidă deoarece conține un zid. Al doilea vecin este poziția (3, 2), poziție validă. Funcția se autoapelează pentru această poziție și obținem:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ ∞ ∞
2 3 ∞ ∞
∞ ∞ ∞ ∞

Din poziția (3, 2) prima dată se încearcă vecinul (4, 2), care este însă un zid. Se va merge în continuare la stânga încă doi pași, până obținem:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ ∞ ∞
2 3  4  5
∞ ∞ ∞ ∞

Din poziția (3, 4) funcția se va apela prima dată pentru poziția (4, 4), obținându-se următoarea configurație:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ ∞ ∞
2 3  4  5
∞ ∞ ∞ 6

Deoarece niciun vecin al poziției (4, 4) nu este valid pentru a se efectua apeluri recursive, se revine din recursivitate la poziția (3, 4), din care se efectuează apoi un autoapel pentru vecinul de sus, (2, 4):
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ ∞ 6
2 3  4  5
∞ ∞ ∞ 6

Singurul apel recursiv valid din poziția (2, 4) este pentru poziția (2, 3), obținându-se:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ 7  6
2 3  4  5
∞ ∞ ∞ 6

Se revine din recursivitate până la poziția (3, 3), de unde, când se verifică vecinul (2, 3) se vor îndeplini toate condițiile necesare efectuării unui apel recursiv deoarece 7 > 4 + 1 = 5 și poziția (2, 3) este validă și conține o cameră deschisă. Forma finală a matricei D va fi:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ 5  6
2 3  4  5
∞ ∞ ∞ 6

Așadar, am actualizat de două ori valoarea D[2][3]. Vom încerca să găsim un algoritm care actualizează fiecare valoare o singură dată, dar vom prezenta mai întâi implementarea acestei metode:
Precizăm că am omis intenționat funcția care determină coordonatele ce descriu un drum de lungime minimă. Această funcție va fi prezentată la sfârșit.
Am afirmat la începutul acestei secțiuni că algoritmul lui Lee este de fapt o parcurgere in lățime. Acei cititori care cunosc parcurgerea în lățime și cea în adâncime probabil au observat că prima metodă este de fapt o parcurgere în adâncime, deoarece se merge în aceeași direcție până când se întâlnește un obstacol și abia apoi se revine la un pas anterior sau se schimbă direcția. Parcurgerile grafurilor vor fi prezentate într-un alt capitol, așa că nu vom detalia aici parcurgerea în lățime. Ideea de bază este să verificăm la fiecare pas toți vecinii poziției curente, iar apoi toți vecinii acestora și așa mai departe, până când se parcurge întreaga matrice. Datorită faptului că vom parcurge matricea uniform, fiecare element va fi analizat o singură dată.
Ideea de bază rămâne aceeași, diferind doar implementarea. Pentru a putea implementa parcurgerea descrisă anterior vom folosi o structură de date numită coadă F.I.F.O. Această structură de date a fost descrisă în capitolul Introducere în S.T.L.

Vom prezenta în continuare noul algoritm în pseudocod. Notațiile rămân aceleași, iar Q reprezintă coada F.I.F.O. folosită, p reprezintă poziția primului element din coadă, iar u poziția ultimului element din coada:
  • p = u = 1
  • Q[p] = (1, 1)
  • Cât timp p ≤ u execută
    • (x, y) = Q[p++]
    • Pentru fiecare vecin (newx, newy) al lui (x, y) execută
      • Dacă (newx, newy) este o poziție validă, nu reprezintă un zid și D[newx][newy] > D[x][y] + 1 execută
        • D[newx][newy] = D[x][y] + 1
        • Q[++u] = (newx, newy)
Datorită modului în care parcurgem matricea, toate drumurile posibile vor fi parcurse în același timp, deci nu va exista posibilitatea completării unei părți a matricei D cu valori care vor trebui ulterior corectate, așa cum a fost cazul în implementarea inițială. Pentru a evidenția acest lucru vom prezenta modul de execuție al algoritmului pe exemplul dat.
Inițial avem:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
Se extrage primul element din coada Q și anume (1, 1). Se actualizează toți vecinii acestuia care se supun condițiilor de mai sus. Singurul vecin valid este (2, 1), care se actualizează, iar poziția (2, 1) se introduce în coadă. Avem configurația:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
La următorul pas e extrage Q[p], adică (2, 1). Singurul vecin valid este (3, 1), care se actualizează și se introduce în coadă:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ ∞ ∞
2 ∞ ∞ ∞
∞ ∞ ∞ ∞
Similar, singurul vecin valid al poziției Q[p] = (3, 1) este (3, 2), care se va introduce în coadă si se va actualiza. La următorul pas se va extrage (3, 2) din coadă și se va introduce singurul vecin valid al acestei poziții (3, 3):

A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ ∞ ∞
2  3 4 ∞
∞ ∞ ∞ ∞
Se extrage (3, 3) din Q. Poziția (3, 3) are doi vecini valizi: (3, 4) și (2, 3), care se actualizează și se introduc amândoi în coadă:
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ 5 ∞
2  3 4 5
∞ ∞ ∞ ∞

Se extrage elementul (3, 4), care va actualiza pozițiile (4, 4) și (2, 4) și le va introduce în coadă. Se observă că după acest pas matricea este deja completată corect.
A
D
0 1 1 1
0 1 0 0
0 0 0 0
1 1 1 0
0 ∞ ∞ ∞
1 ∞ 5  6
2  3 4  5
∞ ∞ ∞ 6
Dacă ne interesează doar poziția (N, N), putem returna D[N][N] imediat ce această valoare a fost calculată. Dacă ne interesează întreaga matrice D, algoritmul trebuie continuat până când p devine mai mare decât u.
Datorită faptului că am introdus fiecare poziție a matricei (care nu reprezintă un zid) în coadă exact o singură dată și pentru că am evitat recursivitatea, timpul de execuție al acestei implementări este cu mult mai bun decât cel al implementării recursive.
Pentru a determina coordonatele care alcătuiesc traseul vom folosi o funcție recursivă drum(x, y). Observăm că dacă D[x][y] == k (k > 0, k != ∞) atunci poziția imediat anterioară lui (x, y) în cadrul drumului minim este acel vecin (p, q) al lui (x, y) pentru care D[p][q] == k – 1. Dacă D[x][y] este 0, atunci (x, y) == (1, 1); această condiție este chiar condiția de ieșire din recursivitate. Așadar funcția drum(x, y) poate fi scrisă astfel:
  • Dacă D[x][y] == 0 afișează (1, 1) și oprește execuția
  • Caută un singur vecin (p, q) al lui (x, y) pentru care D[p][q] == D[x][y] – 1
  • Apel recursiv drum(p, q)
  • Afișează (x, y)
In C++ această funcție poate fi implementată în felul următor. Funcția funcționează atât pentru implementarea deja prezentată, cât și pentru implementările ce vor urma.
Funcția determină un singur traseu, iar apelul inițial este drum(D, N, N, N, out) pentru cerința problemei prezentate.
Vom prezenta în continuare două variante de funcții Lee care implementează ultimul algoritm descris. Avem mai multe posibilități de a implementa o coadă. Prima și cea mai evidentă posibilitate este să folosim un vector cu N2 perechi de numere întregi (deoarece fiecare poziție poate fi introdusă cel mult o singură dată în coadă) și să reținem poziția primului element al cozii în variabila p și poziția ultimului element în variabila u, exact așa cum se poate vedea în evidențierea exemplului dat. Pentru această implementare avem nevoie de o structură care grupează două variabile întregi:

Noua funcție lee poate fi implementată în felul următor:
Iar apelul inițial devine Lee(A, N, D).
Putem scrie un cod mai compact și mai natural limbajului C++ folosind utilitățile puse la dispoziție de către biblioteca S.T.L. și anume containerele pair și queue, care pun la dispoziție programatorului ceea ce noi ar trebui să implementăm singuri în codul anterior: posibilitatea de a reține perechi de numere, respectiv o coadă F.I.F.O. Avantajul containerului queue este că acesta nu va folosi niciodată memorie pentru N2 elemente, deoarece este implementat în așa fel încât elementele scoase din coadă să fie șterse și din memorie. In implementarea precedentă memoria folosită pentru coadă este întotdeauna maximă și nici nu ștergem efectiv elementele, ci doar incrementăm o limită inferioară pentru poziția primului element.
Nu vom prezenta pe larg aici aceste două containere întrucât au fost prezentate în cadrul capitolului Introducere în S.T.L. Precizăm doar că pentru folosirea lor trebuie incluse fișierele antet și . Noua implementare este:
Recomandăm cititorilor să se familiarizeze cât mai bine cu biblioteca S.T.L., mai ales pentru capitolele ce vor urma, deoarece facilitățile oferite de aceasta sunt de multe ori foarte folositoare și conduc la implementări mai ușoare sau mai eficiente. De aceea, de fiecare dată când acest lucru este posibil și preferabil, următoarele implementări vor fi prezentate exclusiv folosind facilitățile S.T.L.
Exerciții:

a) Considerăm că o persoană pornește din (1, 1) și alta din (N, N). Cele două persoane se mișcă exact în același timp. Scrieți un program care determină coordonatele spre care acestea ar trebui să se îndrepte pentru a se întâlni cât mai rapid.
b) Dați un exemplu pe care soluția recursivă efectuează cu mult mai mulți pași decât e necesar.
c) Modificați funcția de afișare a drumului astfel încât să afișeze toate drumurile minime existente.

[C++, programare dinamică] Problemă cu algoritmul lui Lee (b)

Introducere în problema labirintului aici.

Enunț

b) Dați un exemplu pe care soluția recursivă efectuează cu mult mai mulți pași decât e necesar.

Explicație

Soluția recursivă efectuează mai mulți pași decât soluția nerecursivă cu cât se fac mai multe apeluri recursive pentru poziții deja calculate, ceea ce echivalează cu cât există mai multe poziții în care se poate ajunge prin multiple căi.

In exemplul dat în pagina de la link-ul de la începutul acestui articol, poziția (2, 3) are la primul apel recursiv asupra ei valoarea 7, apoi la al doilea apel primește valoarea 5. Ordinea apelurilor recursive este determinată de ordinea valorilor din vectorii de direcție, fiind o parcurgere în adâncime.

Aici este codul care a generat fișierele de ieșire de mai jos (am modificat ordinea elementelor din vectorii de direcție pentru ca să se parcurgă în ordinea aceasta: dreapta, jos, stânga, sus). Codul afișează în fereastra linie de comandă, dar se poate selecta tot conținutul ei cu: clic stânga pe un caracter sau spațiu din fereastră, Ctrl-A și apoi clic dreapta pe oricare caracter sau spațiu din fereastră. Apoi se poate da Ctrl-V sau Paste în oricare alt program care poate primi text, inclusiv într-un editor text.

  • Aici este fișierul de ieșire cu fiecare pas dezvoltat al problemei de la link-ul de la începutul acestui articol (prima variantă a algoritmului) cu datele de intrare din exemplul din carte.
  • In același format, dar pentru o matrice 4×4 cu camere doar deschise, aici este fișierul de ieșire.

Puteți deschide aceste fișiere în Visual Studio Code, editor care suportă automat colapsarea secțiunilor intentate diferit. Notă: inițial matricea D este plină de valori pseudo-infinite, adică valori foarte mari care cu greu pot fi depășite.

In aceste două fișiere se poate folosi căutarea textului „Urmeaza parcurgerea vecinilor lui” (fără diacritice) și într-un editor care suportă acest lucru, de exemplu Visual Studio Code, se afișează câte rezultate au fost găsite. In fișierul rezultat din exemplul din carte, acest șir de caractere apare de 10 ori. In fișierul rezultat din exemplul nou, sunt 52 de apariții ale acestui șir. Fiecare astfel de apariție reprezintă un apel recursiv.

Exemplul din carte Exemplul 4×4 doar cu camere deschise
Algoritm recursiv 10 apeluri recursive 52 de apeluri recursive
Algoritm optim nerecursiv 9 pași 16 pași

Cum 16 este mult mai mic decât 52 având în vedere aceeași dimensiune a matricei labirint, deci am găsit un exemplu bun pentru cerința de la începutul acestui articol.

In figură, apare direcția de parcurgere în adâncime a matricei 4×4 cu camere doar deschise, și cu vectorii de poziție din fișierul de la ultimul link de mai sus:

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
După parcurgerea din figură urmează revenirea din apelurile recursive care poate începe alte apeluri recursive.

[C++, programare dinamică] Problemă cu algoritmul lui Lee (a)

Introducere în problema labirintului aici.

Enunț

a) Considerăm că o persoană pornește din (1, 1) și alta din (N, N). Cele două persoane se mișcă exact în același timp. Scrieți un program care determină coordonatele spre care acestea ar trebui să se îndrepte pentru a se întâlni cât mai rapid.

Rezolvare

#include <fstream>
#include <queue>
#include <utility>

using namespace std;

const int maxn = 101;
const int inf = 1 << 30;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

void citire(bool A[maxn][maxn], int &N)
{
ifstream in("ex-a.in");
in >> N;
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
{
in >> A[i][j];
}
}
in.close();
}

bool valid(int N, int x, int y)
{
return x >= 1 && y >= 1 &&
x <= N && y <= N;
}

void Lee_optim(bool A[maxn][maxn], int N,
int x, int y,
int D[maxn][maxn])
{
queue<pair<int, int>> Q;
Q.push(make_pair(x, y));

while (!Q.empty())
{
pair<int, int> poz = Q.front();
Q.pop();

for (int i = 0; i < 4; ++i)
{
int newx = poz.first + dx[i];
int newy = poz.second + dy[i];

if (valid(N, newx, newy))
{
if (!A[newx][newy] &&
D[newx][newy] > D[poz.first][poz.second] + 1)
{
D[newx][newy] = D[poz.first][poz.second] + 1;
Q.push(make_pair(newx, newy));
}
}
}
}
}

void init(int D[maxn][maxn], int N, int x, int y)
{
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
{
D[i][j] = inf;
}
}
D[x][y] = 0;
}

int main()
{
int N;
bool A[maxn][maxn];
int D1[maxn][maxn];
int D2[maxn][maxn];

citire(A, N);

init(D1, N, 1, 1);
Lee_optim(A, N, 1, 1, D1);

init(D2, N, N, N);
Lee_optim(A, N, N, N, D2);

int max = -inf;
int x = -1, y = -1;
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
{
if (!A[i][j] &&
D1[i][j] == D2[i][j])
{
if (D1[i][j] > max)
{
max = D1[i][j];
x = i;
y = j;
}
}
}
}

ofstream out("ex-a.out");
out << x << ' ' << y << endl;
out.close();

return 0;
}

Explicație

Fișierul de intrare este ex-a.in și cel de ieșire este ex-a.out.

Se folosesc două matrice D construite din matricea de intrare A, se aplică același algoritm pt. ambele (algoritmul lui Lee) dar din puncte de pornire diferite (cele specificate în enunț). Se lasă algoritmul să ruleze pe toată suprafața matricelor. Se compară fiecare celulă din matricea D1 cu cea din matricea D2 de pe aceeași poziție, și dacă au aceeași valoare, se calculează treptat poziția valorii minime care se găsește în ambele matrice D pe aceeași poziție. Se ignoră valorile de 1 care reprezintă ziduri.

[C++, programare dinamică] Distanța Levenshtein

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Se dau două șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Asupra șirului A putem face următoarele trei operații:

1. Inserăm un caracter.
2. Ștergem un caracter.
3. Înlocuim un caracter cu orice alt caracter din alfabetul folosit.

Se cere determinarea numărului minim de operații necesare transformării șirului de caractere A in șirul de caractere B.

Cele două șiruri de caractere se citesc din fișierul lev.in, iar numărul minim de operații se va afișa în fișierul lev.out.

Exemplu:

lev.in           lev.out
–––        –––
afara            3
afacere

Explicație: se inserează caracterele c și e după afa și se înlocuiește ultimul a cu e.

Problema cere determinarea distanței Levenshtein dintre cele două șiruri de caractere. Aceasta este o distanță de editare, adică un metric folosit pentru măsurarea gradului de asemănare a doua șiruri.

Algoritmul de rezolvare este similar cu algoritmul de găsire a celui mai lung subșir comun. De fapt, cel mai lung subșir comun poate fi privit ca o distanță de editare în care operațiile permise sunt doar inserarea unui caracter și ștergerea unui caracter.

Pentru a rezolva această problemă, vom construi o matrice D unde D[i][j] = numărul minim de operații necesare transformării secvenței A[1, i] în secvența B[1, j]. Răspunsul problemei va fi evident D[lungime(A)][lungime(B)].

Vom trata mai întâi cazurile de bază, presupunând că indicii șirurilor încep de la 1:

  1. Pentru a transforma o secvență A[1, i] în secvența nulă B[0, 0] trebuie evident să ștergem toate caracterele din secvența A[1, i], deci D[i][0] = i pentru i de la 0 la lungime(A).
  2. Pentru a transforma secvența A[0, 0] într-o secvență B[1, i] trebuie să adăugăm i caractere secvenței A[0, 0], deci D[0][i] = i pentru i de la 0 la lungime(B).

Să presupunem acum că știm valorile D[p][q], D[p + 1][q] și D[p][q + 1] pentru niște poziții p și q valid alese. Putem atunci calcula D[p + 1][q + 1] considerând următoarele cazuri:

  1. A[p + 1] == B[q + 1], caz în care putem face abstracție de caracterele A[p + 1] și B[q + 1], fiind suficient să transformăm A[1, p] în B[1, q], lucru pe care îl putem face cu D[p][q] operații.
  2. Altfel, fie transformăm A[1. p] în B[1, q + 1] după care ștergem caracterul A[p + 1], fie transformăm A[1, p + 1] în B[1, q] după care inserăm caracterul B[q + 1], fie transformăm A[1, p] în B[1, q] după care înlocuim A[p + 1] cu B[q + 1].

    Așadar:

    D[p + 1][q + 1] = 1 + minim(D[p][q], D[p + 1][q], D[p][q + 1]).

Implementarea prezentată folosește tipul de date string, în care caracterele sunt numerotate de la 0. Rezolvarea însă nu suferă nici o modificare majoră, fiind necesar doar să scădem 1 când accesăm un caracter. Prezentăm doar funcția relevantă, restul programului fiind aproape identic cu cel prezentat în cardul problemei celui mai lung subșir comun.

Se poate face și de această dată optimizarea de a păstra doar două linii ale matricei D, deoarece pentru a calcula un rând al matricei nu folosim decât valori de pe aceeași linie sau de pe linia anterioară. Mai mult, la această problemă este puțin probabil să avem nevoie de reconstituirea soluției.

Am precizat la început că distanța Levenshtein este o distanță de editare dintre două șiruri. Pentru cei interesați prezentăm succint și alte distanțe de editare:

  • Distanța Hamming, care se aplică asupra a două șiruri A și B de lungime egală și este egală cu numărul de poziții i pentru care A[i] != B[i].
  • Distanța Damerau – Levenshtein, care adaugă operația de interschimbare setului de operații
    permise de distanța Levenshtein.
  • Distanța Lee, care calculează sumă din min(|A[i] – B[i]|, σ – |A[i] – B[i]|) pentru fiecare caracter i, unde σ ≥ 2 este dimensiunea alfabetului folosit.
Exerciții:

a) Complexitatea algoritmului de calcul a distanței Levenshtein este O(N·M), unde N și M reprezintă lungimile celor două șiruri. Putem însă optimiza algoritmul dacă știm că putem transforma șirul A în șirul B într-un număr relativ mic de operații k. Cum ne poate ajuta această informație?

b) Considerăm existența unor costuri pentru fiecare operație precum și pentru caracterele asupra cărora se efectuează operații. Scrieți un program care rezolvă această variantă a problemei.

c) Scrieți un program care afișează noul șir A pentru fiecare operație efectuată.

d) Scrieți un program care determină numărul minim de caractere care trebuie inserate într-un șir pentru a-l transforma într-un palindrom.

Interfețe C#

Tradus din această pagină oficială de documentație Microsoft.

O interfață definește un contract care poate fi implementat de clase și struct-uri. O interfață poate conține metode, proprietăți, evenimente, și indexatori. O interfață nu furnizează implementări ai membrilor pe care îi definește — ea pur și simplu specifică membrii care trebuie să fie furnizați de clasele sau struct-urile care implementează interfața.
Interfețele pot folosi moștenire multiplă. In următorul exemplu, interfața IComboBox moștenește și de la ITextBox și IListBox.

interface IControl
{
void Paint();
}
interface ITextBox: IControl
{
void SetText(string text);
}
interface IListBox: IControl
{
void SetItems(string[] items);
}
interface IComboBox: ITextBox, IListBox {}

Clasele și struct-urile pot implementa mai multe interfețe. In exemplul următor, clasa EditBox implementează și IControl și IDataBound.

interface IDataBound
{
void Bind(Binder b);
}
public class EditBox: IControl, IDataBound
{
public void Paint() { }
public void Bind(Binder b) { }
}

Când o clasă sau struct implementează o anumită interfață, instanțele acelei clase sau struct-uri pot fi implicit convertite la acel tip de interfață. De exemplu:

EditBox editBox = new EditBox();
IControl control = editBox;
IDataBound dataBound = editBox;

In cazurile în care o instanță nu este cunoscută static că implementează o anumită interfață, convertiri dinamice de tip pot fi folosite. De exemplu, următoarele instrucțiuni folosesc convertiri dinamice de tip pentru a obține implementările de interfețe IControl și IDataBound ale unui obiect. Deoarece tipul concret la timpul rulării al obiectului este EditBox, convertirile reușesc.

object obj = new EditBox();
IControl control = (IControl)obj;
IDataBound dataBound = (IDataBound)obj;

In clasa anterioară EditBox, metoda Paint din interfața IControl și metoda Bind din interfața IDataBound sunt implementate folosind membri publici. C# de asemenea suportă implementări de membri de interfață în mod explicit, dând voie clasei sau struct-urii să evite a face membrii publici. O implementare explicită a unui membru de interfață este scris folosind numele complet calificat al membrului de interfață. De exemplu, clasa EditBox poate implementa metodele IControl.Paint și IDataBound.Bind folosind implementări explicite de membri de interfață după cum urmează.

public class EditBox: IControl, IDataBound
{
void IControl.Paint() { }
void IDataBound.Bind(Binder b) { }
}

Membrii de interfață expliciți pot fi accesați doar prin tipul interfață. De exemplu, implementarea lui IControl.Paint furnizată de clasa anterioară EditBox poate fi invocată doar prin convertirea mai întâi a referinței EditBox la tipul interfață IControl.

EditBox editBox = new EditBox();
editBox.Paint(); // Eroare, nici o asemenea metodă
IControl control = editBox;
control.Paint(); // Ok


Tradus din această pagină oficială de documentație Microsoft.