Clasele 9-10 lecția 2 - 25 sep 2015
Prima oră
Stiva
Stiva este o structură de date elementară care menține intern o listă de elemente. Inițial această listă este vidă. Asupra listei se pot efectua doar următoarele operații:
- push(value) - inserează o valoare dată la sfârșitul listei;
- top - returnează valoarea de la sfârșitul listei;
- pop - șterge valoarea de la sfârșitul listei.
Coada
Coada este o structură de date elementară care menține intern o listă de elemente. Inițial această listă este vidă. Asupra listei se pot efectua doar următoarele operații:
- push(value) - inserează o valoare dată la sfârșitul listei;
- front - returnează valoarea de la începutul listei;
- pop - șterge valoarea de la începutul listei.
Deque
Deque este o structură de date elementară care menține intern o listă de elemente. Inițial această listă este vidă. Asupra listei se pot efectua doar următoarele operații:
- push_front(value) - inserează o valoare dată la începutul listei;
- push_back(value) - inserează o valoare dată la sfârșitul listei;
- pop_front - șterge valoarea de la începutul listei;
- pop_back - șterge valoarea de la sfârșitul listei;
- front - returnează valoarea de la începutul listei;
- back - returnează valoarea de la sfârșitul listei.
Implementare
La oră am implementat un deque cu ajutorul unui vector prealocat (de lungime fixă) și a două referințe care îl parcurg circular.
const int SIZE;
int data[SIZE];
int top = 0; // poziția de început - front
int bottom = 0; // poziția imediat următoare după sfârșit - back
int size() {
return bottom - top;
}
void push_front(value) {
top--;
if (top == -1) {
top += SIZE;
bottom += SIZE;
}
data[top % SIZE] = value;
}
void push_back(value) {
data[bottom % SIZE] = value;
bottom++;
}
void pop_front() {
top++;
}
void pop_back() {
bottom--;
}
int front() {
return data[top % SIZE];
}
int back() {
return data[(top - 1) % SIZE];
}A doua oră
Programare dinamică O(N3)
Am discutat o problemă clasică de programare dinamică numită Parantezare optimă de matrice (Infoarena). Fără a explica ce sunt matricele ca obiecte matematice și cum se înmulțesc acestea, vom reformula problema astfel:
Se citesc N și un șir V de N + 1 numere naturale. La un pas se poate elimina elementul i (1 < i <= N) din șirul de numere plătind un cost egal cu produsul V[i - 1] * V[i] * V[i + 1]. Toate elementele trebuie eliminate succesiv până când vom rămâne doar cu primul și cu ultimul. Se cere găsirea unei ordini în care trebuie eliminate elementele astfel încât suma costurilor operațiilor de eliminare să fie minimă.
Soluția se bazează pe calcularea costului total optim de eliminare a tuturor elementelor dintre pozițiile i și j pentru orice pereche de poziții i și j. Calcularea acestui cost se va realiza printr-o formulă recursivă care va presupune că ultimul element eliminat dintre i și j poate fi k (i < k < j):
C[i][j] = min(k = i+1..j-1, C[i][k] + C[k][j] + V[i] * V[k] * V[j]), dacă j - i >= 2 (i<j) = 0, dacă j - i == 1
Soluția problemei se va regăsi în C[1][N + 1].
Pentru a găsi o ordine optimă de eliminare a elementelor va trebui să reconstituim soluția, pornind de la perechea (1, N + 1), care ne va spune care este ultimul element șters (= k). Apoi vom face același lucru recursiv pentru perechile (1, k) și (k, N + 1) până vom ajunge la perechi de forma (i, i + 1) în care se va opri recursivitatea.
Tot pe o recurență cu aceeași structură se bazează și problema 1183 - Brackets Sequence (Timus) pe care nu am dus-o la bun sfârșit în clasă.
Temă
Pentru data viitoare veți avea de rezolvat următoarele 5 probleme:
