📘 Lecție de C++ pentru clasa a 11-a, BAC și olimpiadă, cu explicații video de la profesor. Mai jos ai rezumatul. În lecția completă găsești aplicații rezolvate cu simulator, în care vezi pas cu pas cum se schimbă variabilele, compilator C++ în browser, exerciții propuse cu indicii și rezolvare, și pe Alex, asistentul care îți dă indicii, îți explică algoritmul și îți corectează codul.
🎯 Apare la BAC? Parțial. Căutarea binară și ideea de împărțire în subprobleme te ajută la BAC. MergeSort și aplicațiile avansate sunt mai ales pentru olimpiadă.
void mergeSort(int v[], int st, int dr) {
if (st >= dr) return;
int mij = (st + dr) / 2;
mergeSort(v, st, mij);
mergeSort(v, mij + 1, dr);
interclaseaza(v, st, mij, dr);
}1. Ce este metoda Divide et Impera? Împarți problema în subprobleme mai mici, le rezolvi recursiv și combini rezultatele.
2. Ce complexitate are MergeSort? O(n log n), mult mai rapid pe date mari decât metoda bulelor, care are O(n²).
3. Ce probleme se rezolvă cu Divide et Impera? Sortarea prin interclasare, QuickSort, căutarea binară, ridicarea rapidă la putere, maximul dintr-un vector.
4. Care e diferența dintre MergeSort și QuickSort? MergeSort împarte la mijloc și interclasează; QuickSort alege un pivot și împarte elementele în mai mici și mai mari decât el.
5. Ce se face în etapa de combinare? Rezultatele subproblemelor se unesc în soluția finală, de exemplu prin interclasarea celor două jumătăți sortate.