Clasa a 8-a lecția 3 - 7 oct 2015
Rezolvare temă
1635 - Mnemonics and Palindromes (Timus)
Pal[i][j] = Secvența V[i..j] este palindrom
Pal[i][j] = true, dacă i == j (lungime 1)
= true, dacă i - 1 == j (lungime 0)
= true, dacă V[i] == V[j] și Pal[i + 1][j - 1]
Cost[i] = numărul minim de palindroame în care poate fi împărțit
textul cu ultimul palindrom terminându-se pe poziția i
Cost[i] = min(j < i și Pal[j + 1][i], Cost[j] + 1)
Subprobleme suprapuse
Problemele decompozabil în subprobleme suprapuse pot fi împărțite în trei categorii:
- probleme de numărare: probleme în care se cere numărarea tuturor configurațiilor care au o anumită formă specificată în enunț;
- probleme de optim (numite de probleme de programare dinamică): probleme în care se cere alegerea unei soluții de cost minim;
- probleme de existență: probleme în care se cere să se spună dacă există o configurație de o anumită formă specificată în enunț.
Aceste categorii de probleme pot fi rezolvate prin explorarea (generarea) tuturor configurațiilor posibile (de regulă prin recursivitate). Din păcate, această abordare are un timp de execuție exponențial și va trebui redus.
Tehnica generală de rezolvare a unei probleme decompozabilă în subprobleme suprapuse
Orice problemă care se poate descompune în subprobleme suprapuse poate fi abordată astfel:
- Vom implementa o soluție de recursivă, care va explora toate soluțiile posibile.
- Dacă această implementare folosește variable globale, vom face în așa fel încât toate aceste variable să devină parametri ale funcției recursive.
- Vom elimina toțo parametrii redundanți ai funcției.
- Vom aplica tehnica memoizării asupra acestei funcții.
Observație: Toți acești pași sunt doar un ghid care să vă ajute să treceți de la o soluție de tip recursiv la o soluție de tip calcul tabelar. Pentru început rezolvați câteva probleme trecând prin toți pașii, apoi puteți sări peste o parte din ei, până când veți putea scrie direct codul în forma sa finală, după aplicarea tuturor acestor pași.
Problemă de existență
Dându-se un cuvânt (format numai din litere mici ale alfabetului englez) și o mască (formată din *, ? și litere mici ale alfabetului englez), să se determine dacă masca se potrivește peste cuvânt.
O literă mică din mască se potrivește cu aceeași litară mică din cuvânt. Caracterul ? se potrivește cu orice literă mică din cuvânt. Iar caracterul * se potrivește cu oricâte litere mici din cuvânt (zero, una sau mai multe).
#include <cstdio>
#include <cctype>
const int MAX_SIZE = 100;
char Cuvant[MAX_SIZE + 1];
char Masca[MAX_SIZE + 1];
char Verifica[MAX_SIZE + 1][MAX_SIZE + 1];
char verifica(int i, int j) { // sufixele care incep de
// pe pozitiile i si j in cuvant respectiv masca
// se pot transforma unul in celalalt
if (Verifica[i][j] == -1) {
if (Cuvant[i] == 0 && Masca[j] == 0) {
Verifica[i][j] = 1; // true
} else if (Masca[j] == 0) {
Verifica[i][j] = 0; // false
} else if (isalpha(Masca[j])) {
if (Cuvant[i] == Masca[j]) {
Verifica[i][j] = verifica(i + 1, j + 1);
} else {
Verifica[i][j] = 0; // false
}
} else if (Masca[j] == '?') {
if (Cuvant[i] == 0) {
Verifica[i][j] = 0; // false
} else {
Verifica[i][j] = verifica(i + 1, j + 1);
}
} else if (Masca[j] == '*') {
int k = i;
while (Cuvant[k] != 0 && verifica(k, j + 1) == 0) {
++k;
}
Verifica[i][j] = verifica(k, j + 1);
}
}
return Verifica[i][j];
}
int main(void) {
// citirea datelor
scanf("%s", Cuvant);
scanf("%s", Masca);
// calcularea solutiei
int i, j;
for (i = 0; i < MAX_SIZE + 1; ++i) {
for (j = 0; j < MAX_SIZE + 1; ++j) {
Verifica[i][j] = -1;
}
}
int answer = verifica(0, 0);
// afisarea solutiei
printf("%d\n", answer);
return 0;
}Problemă de optim (de programare dinamică)
#include <cstdio>
#include <cmath>
const int MAX_N = 1000;
const int MAX_M = 1000;
int N, M;
int Diag[1 + MAX_N][1 + MAX_M];
int max(int a, int b) {
return a > b ? a : b;
}
int NrDiagMax[1 + MAX_N][1 + MAX_M];
int nrDiagMax(int i, int j) {
if (NrDiagMax[i][j] == -1) {
if (i == N && j == M) {
NrDiagMax[i][j] = 0;
} else if (Diag[i][j]) {
NrDiagMax[i][j] = nrDiagMax(i + 1, j + 1) + 1;
} else {
NrDiagMax[i][j] = max(
nrDiagMax(i + 1, j),
nrDiagMax(i, j + 1));
}
}
return NrDiagMax[i][j];
}
int main(void) {
// citirea datelor
scanf("%d %d", &N, &M);
// calcularea solutiei
int i, j;
for (i = 0; i < N + 1; ++i) {
for (j = 0; j < M + 1; ++j) {
NrDiagMax[i][j] = -1;
}
}
double answer = 100 *
(N + M + (sqrt(2) - 2) * nrDiagMax(0, 0));
// afisarea solutiei
printf("%.0lf\n", answer);
return 0;
}Probleme de numărare
Temă
Pentru data viitoare veți avea de rezolvat următoarele probleme:
