Clasa X - Ora 2: Maximul și minimul prin Divide et impera

SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei putea să determini maximul unui tablou cu metoda Divide et impera și să adaptezi ușor algoritmul pentru minim.

Funcția recursivă maxim(st, dr)

Compararea rezultatelor celor două jumătăți

Varianta pentru minim

Urmărirea algoritmului pas cu pas

Ideea algoritmului pentru maxim

Definiție: Pentru a găsi maximul elementelor dintre st și dr, împărțim intervalul în două jumătăți, aflăm maximul fiecărei jumătăți prin apeluri recursive (apeluri ale funcției asupra unor intervale mai mici), apoi comparăm cele două valori și returnăm pe cea mai mare. Când intervalul are un singur element (cazul de bază, care oprește recursivitatea), maximul este chiar acel element.

Analogie: cel mai înalt elev din clasă

Pentru a afla cine este cel mai înalt elev al clasei, împărțim clasa în două jumătăți. Aflăm cel mai înalt elev din fiecare jumătate, apoi îi comparăm pe cei doi: câștigă cel mai înalt dintre ei. Fiecare jumătate se împarte la rândul ei, până ajungem la grupuri de câte un singur elev, unde răspunsul este evident.

Etapă	Pentru maxim	Pentru minim
Caz de bază	`st == dr` returnăm `v[st]`	`st == dr` returnăm `v[st]`
Divizare	`mij = (st + dr) / 2`	`mij = (st + dr) / 2`
Combinare	returnăm valoarea mai mare	returnăm valoarea mai mică

Urmărim algoritmul pas cu pas

exemplu: v = [3, 8, 1, 9, 5, 2, 7, 4]

maxim(1, 8)

st maxim(1, 4) = 9 și maxim(5, 8) = 7

st maxim(1, 2) = 8 și maxim(3, 4) = 9, deci maxim(1, 4) = 9

st maxim(1, 1) = 3 și maxim(2, 2) = 8, deci maxim(1, 2) = 8

st maxim(3, 3) = 1 și maxim(4, 4) = 9, deci maxim(3, 4) = 9

st maxim(5, 8) = 7: maxim(5, 6) = 5 și maxim(7, 8) = 7

dr comparăm 9 cu 7: maximul global este 9

Observă: toate valorile sunt comparate „la bază", iar câștigătorii urcă treptat, două câte două, până la rădăcina arborelui de apeluri.

Programul complet: maxim și minim

Scriem funcția maxim(st, dr) și funcția minim(st, dr), ambele cu aceeași structură; se schimbă doar comparația. Tabloul v este global, ca la Bacalaureat.

citește n citește v[1], v[2], ..., v[n] scrie maxim(1, n), minim(1, n) funcție maxim(st, dr): dacă st == dr atunci returnează v[st] // cazul de bază mij = (st + dr) / 2 // descompunere a = maxim(st, mij) // rezolvare: jumătatea stângă b = maxim(mij + 1, dr) // rezolvare: jumătatea dreaptă dacă a > b atunci // combinare returnează a altfel returnează b sfârșit dacă sfârșit funcție // minim(st, dr) este identică, singura diferență fiind comparația a < b

C++ - maxim și minim prin Divide et impera

#include <iostream>
using namespace std;

int v[1001];

int maxim(int st, int dr) {
    if (st == dr) {
        return v[st];
    }
    int mij = (st + dr) / 2;
    int a = maxim(st, mij);
    int b = maxim(mij + 1, dr);
    if (a > b) {
        return a;
    }
    return b;
}

int minim(int st, int dr) {
    if (st == dr) {
        return v[st];
    }
    int mij = (st + dr) / 2;
    int a = minim(st, mij);
    int b = minim(mij + 1, dr);
    if (a < b) {
        return a;
    }
    return b;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cout << maxim(1, n) << " " << minim(1, n) << endl;
    return 0;
}

Ce învățăm: funcțiile se definesc înainte de main(); diferența dintre maxim și minim este doar operatorul de comparație (> față de <).

Exercițiu de completare

Completează descrierea funcției maxim:

În funcția maxim: dacă st == ______, maximul este v[st]; altfel calculăm mij = (st + dr) / ______; determinăm maximul celor două ______; apoi comparăm și returnăm valoarea ______.

Bancă de cuvinte:

dr 2 jumătăți mai mare

Exercițiu de completare: varianta minim

Completează enunțul despre funcția minim:

Pentru funcția minim se modifică doar ______ dintre rezultate: dacă a ______ b, returnăm ______; altfel returnăm ______. Cazul de bază este identic: st == ______.

Bancă de cuvinte:

comparația < a b dr

Test de înțelegere

Test rapid - maxim și minim:

1. În cazul de bază (st == dr), maximul intervalului este:

v[st] mij st

2. Pentru determinarea minimului, comparația folosită la combinare este:

< > ==

3. Complexitatea algoritmului maxim prin Divide et impera este:

O(n) O(n) O(log n)

Ai grijă la: rezultatele celor două jumătăți se rețin în variabile înainte de comparație; scrierea maxim(st, mij) > maxim(mij+1, dr) direct în return dublează apelurile și este punctată greșit la barem.

Aprofundare

Numărul de comparații: pentru n elemente, funcția maxim efectuează exact n - 1 comparații, la fel ca și parcurgerea clasică. Avantajul metodei nu este aici numărul de comparații, ci faptul că împărțirea pe jumătăți permite, în general, tratarea subproblemelor independent, iar adâncimea stivei de apeluri este doar log₂(n).

Interval cu lungime impară: când intervalul are un număr impar de elemente, jumătatea stângă [st, mij] și cea dreaptă [mij + 1, dr] au lungimi diferite, dar algoritmul funcționează identic, fiindcă cazul de bază se atinge oricum la elemente singure. Nu trebuie tratat niciun caz special.

Elemente egale: dacă maximul apare de mai multe ori, funcția returnează una dintre valori; nu contează care, pentru că valoarea este aceeași. La combinare, comparația a > b preferă jumătatea stângă la egalitate, dar rezultatul este corect.

O singură funcție pentru ambele: putem scrie o singură funcție extrem(st, dr, tip) care compară cu > sau cu < în funcție de parametrul tip. La Bacalaureat se preferă însă două funcții separate, pentru claritate și pentru a evita verificări suplimentare în apeluri recursive.

Exemplu din viața reală: un jurnalist primește măsurătorile de temperatură de la 64 de stații meteo și trebuie să găsească temperatura maximă a zilei. Împarte cele 64 de valori în două liste de 32, fiecare coleg analizează câte o jumătate și întoarce maximul ei; apoi compară cele două maxime. Chiar dacă munca totală rămâne aceeași, lucrul pe jumătăți independente permite distribuirea pe mai mulți oameni sau pe mai multe procesoare.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Maximul (prin Divide et impera)

Enunț:

Cerință: Se citește un număr natural n și apoi n numere întregi, memorate într-un tablou. Să se afișeze valoarea maximă din tablou, determinată cu metoda Divide et impera.

Date de intrare:

Programul citește de la tastatură numărul n, apoi cele n numere, separate prin spații.

Date de ieșire:

Programul va afișa pe ecran valoarea maximă din tablou.

Restricții și precizări:

1 ≤ n ≤ 1000; elementele tabloului sunt numere întregi din intervalul [-1000000000, 1000000000]; numerotarea se face de la 1.

Exemplu:

Intrare:

5
7 3 9 2 5

Ieșire:

Cum gândim soluția:

Declarăm tabloul global v[1001] și citim n cu elementele
Definim maxim(st, dr): caz de bază st == dr
Împărțim la mij și returnăm maximul celor două jumătăți
Afișăm maxim(1, n)

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int v[1001];

int maxim(int st, int dr) {
    if (st == dr) {
        return v[st];
    }
    int mij = (st + dr) / 2;
    int a = maxim(st, mij);
    int b = maxim(mij + 1, dr);
    if (a > b) {
        return a;
    }
    return b;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cout << maxim(1, n) << endl;
    return 0;
}

Ce învățăm: tabloul este global, deci funcția recursivă poate accesa direct elementele; main() doar citește, apelează și afișează.

PbInfo - Minimul (prin Divide et impera)

Enunț:

Cerință: Se citește un număr natural n și apoi n numere întregi. Să se afișeze valoarea minimă din tablou, determinată cu metoda Divide et impera.

Date de intrare:

Programul citește de la tastatură numărul n, apoi cele n numere.

Date de ieșire:

Programul va afișa pe ecran valoarea minimă din tablou.

Restricții și precizări:

1 ≤ n ≤ 1000; elementele tabloului sunt numere întregi; minimul se calculează printr-o funcție recursivă de tip Divide et impera.

Exemplu:

Intrare:

5
7 3 9 2 5

Ieșire:

Cum gândim soluția:

Copiem structura funcției maxim, schimbând doar comparația
La combinare returnăm a dacă a < b, altfel b
Cazul de bază rămâne st == dr
Afișăm minim(1, n)

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int v[1001];

int minim(int st, int dr) {
    if (st == dr) {
        return v[st];
    }
    int mij = (st + dr) / 2;
    int a = minim(st, mij);
    int b = minim(mij + 1, dr);
    if (a < b) {
        return a;
    }
    return b;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cout << minim(1, n) << endl;
    return 0;
}

Ce învățăm: maximul și minimul au aceeași schemă; schimbarea unui singur operator transformă complet algoritmul.

EXERCIȚII PRACTICE

Exercițiul Practic: maxim, minim și poziții

Sarcini de lucru

Rezolvă sarcinile de mai jos pentru a exersa algoritmii de maxim și minim prin Divide et impera

Sarcina 1: Maximul și poziția sa

Cerință: Scrie o funcție pozMaxim(st, dr) care returnează poziția elementului maxim. În main() afișează valoarea maximă și poziția ei.

Scrie programul C++ aici:

Soluție pentru Sarcina 1:

#include <iostream>
using namespace std;

int v[1001];

int pozMaxim(int st, int dr) {
    if (st == dr) {
        return st;
    }
    int mij = (st + dr) / 2;
    int p1 = pozMaxim(st, mij);
    int p2 = pozMaxim(mij + 1, dr);
    if (v[p1] > v[p2]) {
        return p1;
    }
    return p2;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    int p = pozMaxim(1, n);
    cout << v[p] << " " << p << endl;
    return 0;
}

Verifică: pentru v = 4 9 2 7, maximul este 9 la poziția 2, deci se afișează 9 2. La egalități, funcția preferă poziția mai din stânga.

Sarcina 2: Minimul unui tablou

Cerință: Scrie un program C++ complet care citește n și n numere întregi, apoi afișează minimul, determinat cu funcția recursivă minim(st, dr).

Scrie programul C++ aici:

Soluție pentru Sarcina 2:

#include <iostream>
using namespace std;

int v[1001];

int minim(int st, int dr) {
    if (st == dr) {
        return v[st];
    }
    int mij = (st + dr) / 2;
    int a = minim(st, mij);
    int b = minim(mij + 1, dr);
    if (a < b) {
        return a;
    }
    return b;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cout << minim(1, n) << endl;
    return 0;
}

Verifică: pentru n = 6 și valorile 8 3 5 1 9 2, minimul este 1. Funcția este definită înainte de main(), iar tabloul este global.

SCRIE PE CAIET

Scrie pe caiet - Maximul și minimul prin Divide et impera

Titlul lecției

Ora 2: Maximul și minimul prin Divide et impera

Definiția lecției

Pentru a afla maximul unui tablou, intervalul [st, dr] se împarte la jumătate, se calculează recursiv maximul fiecărei jumătăți, iar la combinare se reține valoarea mai mare; cazul de bază (st == dr) întoarce chiar elementul v[st]. Minimul se obține identic, singura diferență fiind operatorul de comparație (< în loc de >). Tabloul se declară global, iar funcțiile se definesc înainte de main(). Pentru a evita dublarea apelurilor recursive, rezultatele jumătăților se rețin în variabilele a și b înainte de comparație. Această schemă de agregare cu comparație stă la baza problemelor de Bacalaureat care cer maximul sau minimul unui interval.

Definiții esențiale

Maximul unui interval: cea mai mare valoare dintr-o subsecvență [st, dr] a tabloului v; la cazul de bază (st == dr) maximul este chiar v[st].
Regula de combinare: maximul unui interval este maximul dintre maximele celor două jumătăți: maxim(st, dr) = max(maxim(st, mij), maxim(mij + 1, dr)).
Simetria cu minimul: minimul se calculează identic, singura diferență fiind operatorul de comparație (< în loc de >).
Tablou global: la Bacalaureat, v se declară global, iar funcțiile recursive se definesc înainte de main().

Algoritmul cheie - pseudocod

maxim(st, dr): dacă st == dr returnează v[st]; altfel mij = (st + dr) / 2, calculează a = maxim(st, mij) și b = maxim(mij + 1, dr) și returnează a dacă a > b, altfel b.
minim(st, dr): identic, cu comparația a < b.
În main(): citește n și elementele, apoi scrie maxim(1, n) și minim(1, n).

Algoritmul cheie - cod C++

Declară int v[1001]; global.
Scrie funcția maxim cu structura: caz de bază, mij, două apeluri recursive reținute în a și b, returnarea valorii mai mari.
Copiază funcția pentru minim și schimbă doar comparația din combinare.
Reține: reținerea rezultatelor în variabile (a, b) face codul mai ușor de citit și evită dublarea apelurilor recursive.

Greșeli comune de evitat

Returnarea lui mij sau a poziției în locul valorii v[st] la cazul de bază.
Compararea cu >= în ambele funcții: la minim trebuie <.
Uitarea de a reține rezultatele în variabile și apelarea recursivă de două ori în expresia de return (dublează munca).
Declararea tabloului v local, în main(), caz în care funcțiile recursive nu îl mai văd.

Sfaturi practice și trucuri

Testează funcția mai întâi pe un vector mic, cu valori distincte, apoi pe unul cu valori egale.
Verifică vectorul cu un singur element: ambele funcții trebuie să returneze acel element.
Dacă trebuie doar maximul, nu scrie și minimul; fiecare funcție rezolvă o singură sarcină.
La depanat, urmărește apelurile pe un vector cu 4 elemente și verifică manual fiecare combinare.

Exemplu practic

Direcțiunea unei școli vrea să afle care este cea mai mare prezență zilnică într-o lună de 20 de zile școlare. Notează numărul de elevi prezenți în fiecare zi într-un tablou global v și folosește funcția recursivă de mai jos; pentru minim se schimbă doar comparația din combinare:

C++ - maximul unui tablou prin Divide et impera

int maxim(int st, int dr) {
    if (st == dr) {
        return v[st];
    }
    int mij = (st + dr) / 2;
    int a = maxim(st, mij);
    int b = maxim(mij + 1, dr);
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

Ora 2: Maximul și minimul prin Divide et impera

Înainte de a începe

Ce știi deja?

Ce vei învăța astăzi?

Ideea algoritmului pentru maxim

Analogie: cel mai înalt elev din clasă

Urmărim algoritmul pas cu pas

exemplu: v = [3, 8, 1, 9, 5, 2, 7, 4]

Programul complet: maxim și minim

Exercițiu de completare

Completează descrierea funcției maxim:

Bancă de cuvinte:

Exercițiu de completare: varianta minim

Completează enunțul despre funcția minim:

Bancă de cuvinte:

Test de înțelegere

Test rapid - maxim și minim:

Aprofundare

PbInfo - Maximul (prin Divide et impera)

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

PbInfo - Minimul (prin Divide et impera)

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

Exercițiul Practic: maxim, minim și poziții

Sarcini de lucru

Sarcina 1: Maximul și poziția sa

Soluție pentru Sarcina 1:

Sarcina 2: Minimul unui tablou

Soluție pentru Sarcina 2:

Scrie pe caiet - Maximul și minimul prin Divide et impera

Titlul lecției

Definiția lecției

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic