Clasa a 7-a lecția 26 - 07 apr 2016
From Algopedia
Jump to navigationJump to search
Temă Rezolvari
- Tema 25 clasa a 7 -a
- Problema dreptunghiuri pentru subsecvența crescătoare maximală. Atenţie: cei de clasa a 7a pot pica teste cu TLE, este în regulă.
- Problema subșirul de sumă maximă
- Problema subsecvența comună maximală
- Cel mai lung subșir comun ( subsir comun de lungime maxima ): SCLM
- Opţional pentru clasa a 7a,
Rezolvări aici [1]
Lectie
Am rezolvat impreuna problema Flags
Versiunea 1: Backtracking - am încercat toate posibilitățile de colorare ale steagurilor și le-am numărat. Am folosit o implementare recursivă pentru backtracking. Funcția recursivă returnează numărul de configurații de sufixe de steaguri valide.
#include <cstdio>
const int MAX_N = 45;
const int WHITE = 0;
const int RED = 1;
const int BLUE = 2;
int N;
int v[MAX_N];
int backtracking(int i) {
// i = pozitia curenta (pe care o competam)
// N = numarul de fasii ale steagului
// returneaza numarul de steaguri
int answer = 0;
if (i == 0) {
v[i] = WHITE;
answer += backtracking(1);
v[i] = RED;
answer += backtracking(1);
} else if (i == N) {
if (v[N - 1] != BLUE)
answer++;
} else { // if (i <= N) {
if (v[i - 1] == WHITE) {
v[i] = BLUE;
answer += backtracking(i + 1);//nr de feluri in care putem
// completa steagul curent (de la poz. i + 1 la N)
v[i] = RED;
answer += backtracking(i + 1);//nr de feluri in care putem
// completa steagul curent (de la poz. i + 1 la N)
} else if (v[i - 1] == RED) {
v[i] = WHITE;
answer += backtracking(i + 1);
v[i] = BLUE;
answer += backtracking(i + 1);
} else if (v[i - 1] == BLUE && v[i - 2] == RED) {
v[i] = WHITE;
answer += backtracking(i + 1);
} else { //if (v[i - 1] == BLUE && v[i - 2] == WHITE) {
v[i] = RED;
answer += backtracking(i + 1);
}
}
return answer;
}
int main(void) {
int answer;
// citirea datelor
scanf("%d", &N);
// calcularea solutiei
answer = backtracking(0);
// afisarea solutiei
printf("%d\n", answer);
return 0;
}
Versiunea 2: Am simplificat foarte mult funcția recursivă.
#include <cstdio>
const int MAX_N = 45;
const int WHITE = 0;
const int RED = 1;
const int BLUE = 2;
int N;
int backtracking(int last, int i) {
// i = pozitia curenta (pe care o competam)
// N = numarul de fasii ale steagului
// returneaza numarul de steaguri
int answer = 0;
if (i == N) {
answer++;
} else if (i < N) {
if (last == WHITE) {
answer += backtracking(RED, i + 2);
answer += backtracking(RED, i + 1);
} else { // if (last == RED) {
answer += backtracking(WHITE, i + 1);
answer += backtracking(WHITE, i + 2);
}
}
return answer;
}
int main(void) {
int answer;
// citirea datelor
scanf("%d", &N);
// calcularea solutiei
answer = backtracking(RED, 1) +
backtracking(WHITE, 1);
// afisarea solutiei
printf("%d\n", answer);
return 0;
}
Versiunea 3: Am simplificat și mai mult programul și se constată că acesta calculează șirul lui Fibonacci.
#include <cstdio>
int backtracking(int N) {
if (N == 0)
return 0;
else if (N == 1)
return 1;
else // if (N > 0)
return backtracking(N - 2) + backtracking(N - 1);
}
int main(void) {
int N;
int answer;
// citirea datelor
scanf("%d", &N);
// calcularea solutiei
answer = 2 * backtracking(N);
// afisarea solutiei
printf("%d\n", answer);
return 0;
}
Versiunea 4: Am aplicat memoizare peste calculea șirului lui Fibonacci și am redus complexitatea timp de la exponențial la liniar.
#include <cstdio>
const int MAX_N = 45;
unsigned int Fibo[1 + MAX_N];
unsigned int fibo(int N) {
if (Fibo[N] == 0) {
if (N == 0)
Fibo[N] = 0;
else if (N == 1)
Fibo[N] = 2;
else // if (N > 0)
Fibo[N] = fibo(N - 2) + fibo(N - 1);
}
return Fibo[N];
}
int main(void) {
int N;
unsigned int answer;
// citirea datelor
scanf("%d", &N);
// calcularea solutiei
answer = fibo(N);
// afisarea solutiei
printf("%u\n", answer);
return 0;
}