Modul 11 — Divide et impera · Clasa a X-a Fable

Schema în trei pași

Orice algoritm divide et impera are aceeași coloană vertebrală:

① DIVIDE

Sparge problema în subprobleme de ACELAȘI fel, de obicei două jumătăți: [st..m] și [m+1..dr].

② STĂPÂNEȘTE

Rezolvă fiecare jumătate prin ACELAȘI algoritm — apel recursiv! Cazul de bază: o bucată de 1 element.

③ COMBINĂ

Lipește răspunsurile jumătăților în răspunsul întregului: un max(), o interclasare (M02!)…

Ai folosit-o deja fără să știi! Căutarea binară (Modulul 01) e divide et impera în forma cea mai pură: divide în două jumătăți, stăpânește DOAR una (cealaltă se aruncă!), combinarea e gratis. De-asta face log₂ n pași.

Șablonul de BAC: maximul din vector

Cea mai des cerută funcție divide et impera la examen — schema în stare pură.

1int maxim(int v[], int st, int dr) {

2 if (st == dr) return v[st]; // bucată de 1

3 int m = (st + dr) / 2; // ① divide

4 int a = maxim(v, st, m); // ② stânga

5 int b = maxim(v, m+1, dr); // ② dreapta

6 return (a > b) ? a : b; // ③ combină

7} // apel: maxim(v, 0, n-1)

1def maxim(v, st, dr):

2 if st == dr: return v[st]

3 m = (st + dr) // 2

4 a = maxim(v, st, m)

5 b = maxim(v, m + 1, dr)

6 return a if a > b else b

Rețeta se reciclează: schimbi doar cazul de bază și combinarea — suma elementelor (return a + b), minimul, numărul de valori pare… Aceeași schelă, alt „combină".

Sortarea prin interclasare (Merge Sort)

Capodopera: divide până la bucăți de 1 (gata sortate!), apoi combină cu interclasarea de la Modulul 02. Apasă Pas:

vectorul de sortat: [6, 3, 8, 1, 5, 9, 2, 7] — apasă Pas 👆

De ce e rapid? log₂ 8 = 3 niveluri de împărțire, iar pe fiecare nivel interclasarea atinge fiecare element o dată → O(n·log n). Selecția și bulele din clasa a IX-a (M09) făceau O(n²): la n = 1.000.000, diferența e dintre ~20 de milioane și 1.000 de miliarde de operații!

Fișa de sinteză

Divide et impera, condensată.

Schema: ① divide în subprobleme de același fel · ② rezolvă-le RECURSIV (baza: 1 element) · ③ combină răspunsurile.

Șablonul BAC: m = (st+dr)/2; a = f(v, st, m); b = f(v, m+1, dr); return combină(a, b).

Căutarea binară = divide et impera cu o SINGURĂ subproblemă păstrată → O(log n).

Merge Sort = divide până la 1 + combinare prin interclasare (M02) → O(n·log n), mereu.

Reciclarea rețetei: max, min, sumă, numărări — schimbi doar baza și pasul „combină".

Motorul e recursivitatea (M10): desenează arborele apelurilor când urmărești codul pe hârtie.

Exersează: pe pbinfo.ro, categoria „Divide et impera" — începe cu maximul și suma, apoi Merge Sort.

Împarte și stăpânește