Ce vei învăța astăzi?
După această lecție vei putea să numări inversiunile unui vector cu o interclasare modificată și să cauți un element într-un tablou sortat crescător care a fost rotit, folosind tehnici avansate de tip Divide et impera.
Ce este o inversiune?
Definiție: Se numește inversiune orice pereche de poziții (i, j) cu i < j și v[i] > v[j]. Cu alte cuvinte, o pereche de elemente care se află „întoarse": cel mai mare stă înaintea celui mai mic.
Exemplu: vectorul 5 4 3 2 1
Fiecare pereche (i, j) cu i < j este o inversiune, pentru că orice element este mai mare decât toate cele din dreapta lui: (5,4), (5,3), (5,2), (5,1), (4,3), (4,2), (4,1), (3,2), (3,1), (2,1), deci 10 inversiuni.
Pentru vectorul sortat crescător 1 2 3 4 5 nu există nicio inversiune, iar pentru cel sortat descrescător numărul de inversiuni este maxim, n·(n-1)/2.
Observă: numărul de inversiuni măsoară cât de „răsturnat" este un vector. O forță brută, cu două bucle imbricate, verifică toate perechile în O(n); pentru n = 100000 aceasta este mult prea lentă.
Analogie: coloana de la bibliotecă
La o bibliotecă, cărțile sunt aranjate pe rafturi după anul apariției, de la cel mai vechi la cel mai nou. O pereche de cărți „inversată" (cea mai nouă stând înaintea celei mai vechi) este o inversiune. Numărul total de inversiuni arată cât de mult trebuie rearanjat raftul. Dacă raftul este complet sortat, inversiunile sunt zero; dacă este complet răsturnat, fiecare pereche este inversată.
Numărarea inversiunilor prin interclasare
Modificăm merge sort astfel încât, în timp ce interclasăm, să numărăm inversiunile. Când luăm din jumătatea dreaptă elementul v[j], toate elementele rămase în jumătatea stângă (v[i] până la v[mij]) sunt mai mari decât el și formează inversiuni cu poziția lui j: le numărăm pe toate dintr-o dată.
#include <iostream>
using namespace std;
int v[100001], temp[100001];
long long inversiuni;
void interclaseaza(int st, int mij, int dr) {
int i = st, j = mij + 1, k = st;
while (i <= mij && j <= dr) {
if (v[i] <= v[j]) {
temp[k++] = v[i++];
} else {
temp[k++] = v[j++];
inversiuni += mij - i + 1;
}
}
while (i <= mij) {
temp[k++] = v[i++];
}
while (j <= dr) {
temp[k++] = v[j++];
}
for (int p = st; p <= dr; p++) {
v[p] = temp[p];
}
}
void numaraInversiuni(int st, int dr) {
if (st < dr) {
int mij = (st + dr) / 2;
numaraInversiuni(st, mij);
numaraInversiuni(mij + 1, dr);
interclaseaza(st, mij, dr);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
inversiuni = 0;
numaraInversiuni(1, n);
cout << inversiuni << endl;
return 0;
}
Ce învățăm: linia inversiuni += mij - i + 1 numără toate inversiunile formate de v[j] cu elementele rămase din jumătatea stângă. Rezultatul folosește long long, pentru că pentru n = 100000 pot exista aproape 5 miliarde de inversiuni.
Căutarea într-un tablou sortat și rotit
Definiție: Un tablou sortat crescător rotit se obține luând un tablou sortat și „tăiându-l" într-un punct, apoi mutând prima parte la sfârșit. De exemplu, din 1 2 3 4 5 6 7 rotit la poziția 4 obținem 4 5 6 7 1 2 3. Tabloul nu mai este complet sortat, dar cele două jumătăți (în jurul punctului de rotație) sunt sortate separat.
Ideea căutării
Căutăm x cu o căutare binară adaptată. La fiecare pas, comparăm v[st] cu v[mij] pentru a afla care jumătate este sortată „normal". Dacă jumătatea stângă este sortată și x se află în intervalul ei, căutăm acolo; altfel căutăm în cealaltă jumătate. La fiecare pas renunțăm la o jumătate, deci complexitatea rămâne O(log n).
Pentru tabloul 4 5 6 7 1 2 3 și x = 2: mij = 4, v[4] = 7; jumătatea stângă 4 5 6 7 este sortată, dar 2 nu este în ea, deci căutăm în dreapta; la pasul următor găsim 2 pe poziția 6.
#include <iostream>
using namespace std;
int v[100001];
int cautaRotit(int st, int dr, int x) {
if (st > dr) {
return 0;
}
int mij = (st + dr) / 2;
if (v[mij] == x) {
return mij;
}
if (v[st] <= v[mij]) {
if (x >= v[st] && x < v[mij]) {
return cautaRotit(st, mij - 1, x);
} else {
return cautaRotit(mij + 1, dr, x);
}
} else {
if (x > v[mij] && x <= v[dr]) {
return cautaRotit(mij + 1, dr, x);
} else {
return cautaRotit(st, mij - 1, x);
}
}
}
int main() {
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
cout << cautaRotit(1, n, x) << endl;
return 0;
}
Ce învățăm: testul v[st] <= v[mij] detectează jumătatea sortată normal. Comparațiile x >= v[st] && x < v[mij] decid în care jumătate continuă căutarea, păstrând complexitatea logaritmică.
v[i] > v[j]), deci egalitățile nu se numără; totodată numărul de inversiuni poate depăși int, așa că rezultatul se declară long long.Aprofundare
De ce funcționează numărarea inversiunilor prin interclasare? La interclasare, fiecare jumătate este deja sortată. Când elementul v[j] din dreapta este mai mic decât v[i] din stânga, atunci el este mai mic decât toate elementele de la v[i] până la v[mij] (pentru că stânga e sortată), deci formează exact mij - i + 1 inversiuni. Numărarea „în bloc" transformă algoritmul pătratic într-unul O(n log n).
Elemente egale: la comparația cu <=, elementele egale nu formează inversiuni (perechea (2, 2) nu este inversată), deci se copiază din stânga. Dacă s-ar folosi < strict, egalitățile ar fi numărate greșit drept inversiuni; verifică întotdeauna semnul comparației.
Tablou rotit fără elemente distincte: dacă tabloul rotit conține valori egale, testul v[st] <= v[mij] poate fi ambiguu (ambele jumătăți par sortate). Cazul cu elemente distincte este cel cerut de obicei la bacalaureat; pentru valori cu duplicate, algoritmul trebuie rafinat prin verificarea ambelor jumătăți.
Cazuri particulare la tabloul rotit: dacă vectorul nu a fost rotit deloc (rotire cu 0 poziții), algoritmul se comportă ca o căutare binară obișnuită. Dacă x este mai mic decât toate elementele din partea „mare" a tabloului, căutarea trece corect în partea „mică", de la începutul original al vectorului.
Exemplu din viața reală: un operator de date primește lista clasamentului unui concurs, dar ultimele poziții au fost aduse în față din greșeală (tăiere și mutare). Numărarea inversiunilor îi spune cât de „amestecată" este lista, iar căutarea binară rotită îi permite să găsească rapid poziția unui concurent, fără a reordona lista. Ambele tehnici rezolvă situații reale în care datele au suferit o transformare simplă.
Exercițiu de completare
Completează enunțul despre inversiuni:
O ______ este o pereche de poziții (i, j) cu i < j și v[i] ______ v[j]. Numărul maxim de inversiuni este n·(n-1)/______. Le numărăm eficient în timpul ______, adăugând mij - i + ______ inversiuni.
Bancă de cuvinte:
Exercițiu de completare: căutarea rotită
Completează descrierea căutării într-un tablou rotit:
Un tablou sortat și ______ are două jumătăți sortate separat. La fiecare pas testăm dacă v[st] <= ______. Dacă da, jumătatea stângă este sortată; altfel este sortată cea ______. Cazul de bază, când intervalul s-a golit (st > ______), înseamnă că elementul nu există, și funcția returnează ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - probleme avansate D&I:
1. Numărul de inversiuni ale vectorului 3 1 2 este:
2. Când copiem elementul v[j] din jumătatea dreaptă, inversiunile adăugate sunt:
3. Complexitatea căutării într-un tablou sortat și rotit este:
PbInfo - Inversiuni (numărare eficientă)
Enunț:
Cerință: Se citește n și apoi n numere naturale. Să se afișeze numărul de inversiuni ale vectorului, adică numărul de perechi (i, j) cu i < j și v[i] > v[j].
Date de intrare:
Programul citește de la tastatură numărul n, apoi cele n elemente ale vectorului.
Date de ieșire:
Programul va afișa pe ecran numărul de inversiuni.
Restricții și precizări:
1 ≤ n ≤ 100000; elementele vectorului sunt numere naturale mai mici decât 1000000000; rezultatul poate depăși valoarea maximă a tipului int, deci se folosește long long.
Exemplu:
Intrare:
5 5 4 3 2 1
Ieșire:
10
Cum gândim soluția:
- Modificăm interclasarea: când copiem v[j] din dreapta, adăugăm mij - i + 1 la contor
- Funcțiile interclaseaza și numaraInversiuni se definesc înainte de main()
- Afișăm contorul ca long long
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int v[100001], temp[100001];
long long inversiuni;
void interclaseaza(int st, int mij, int dr) {
int i = st, j = mij + 1, k = st;
while (i <= mij && j <= dr) {
if (v[i] <= v[j]) {
temp[k++] = v[i++];
} else {
temp[k++] = v[j++];
inversiuni += mij - i + 1;
}
}
while (i <= mij) {
temp[k++] = v[i++];
}
while (j <= dr) {
temp[k++] = v[j++];
}
for (int p = st; p <= dr; p++) {
v[p] = temp[p];
}
}
void numaraInversiuni(int st, int dr) {
if (st < dr) {
int mij = (st + dr) / 2;
numaraInversiuni(st, mij);
numaraInversiuni(mij + 1, dr);
interclaseaza(st, mij, dr);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
inversiuni = 0;
numaraInversiuni(1, n);
cout << inversiuni << endl;
return 0;
}
Ce învățăm: pentru 5 4 3 2 1, fiecare element formează inversiuni cu toate cele din dreapta: 4 + 3 + 2 + 1 = 10. Algoritmul rămâne O(n log n), pentru că numărarea se face în timpul interclasării.
PbInfo - Căutare în tablou rotit
Enunț:
Cerință: Se dă un tablou sortat crescător, rotit (obținut prin mutarea primelor k elemente la sfârșit) și un număr x. Să se afișeze poziția pe care se află x, sau 0 dacă x nu apare.
Date de intrare:
Programul citește n, x, apoi cele n elemente distincte ale tabloului rotit.
Date de ieșire:
Programul va afișa poziția lui x (între 1 și n) sau 0 dacă x nu există.
Restricții și precizări:
1 ≤ n ≤ 100000; elementele sunt distincte; căutarea trebuie făcută în O(log n), cu metoda Divide et impera.
Exemplu:
Intrare:
7 2 4 5 6 7 1 2 3
Ieșire:
6
Cum gândim soluția:
- Cazul de bază: st > dr, returnăm 0
- Testăm v[st] <= v[mij] pentru a detecta jumătatea sortată
- Decidem jumătatea de continuare după poziția lui x față de interval
- Afișăm poziția găsită sau 0
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int v[100001];
int cautaRotit(int st, int dr, int x) {
if (st > dr) {
return 0;
}
int mij = (st + dr) / 2;
if (v[mij] == x) {
return mij;
}
if (v[st] <= v[mij]) {
if (x >= v[st] && x < v[mij]) {
return cautaRotit(st, mij - 1, x);
} else {
return cautaRotit(mij + 1, dr, x);
}
} else {
if (x > v[mij] && x <= v[dr]) {
return cautaRotit(mij + 1, dr, x);
} else {
return cautaRotit(st, mij - 1, x);
}
}
}
int main() {
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
cout << cautaRotit(1, n, x) << endl;
return 0;
}
Ce învățăm: pentru 4 5 6 7 1 2 3 și x = 2, algoritmul renunță la jumătatea stângă la primul pas și găsește poziția 6. Fiecare pas înjumătățește intervalul, deci sunt necesare doar O(log n) comparații.
Exercițiul Practic: aplicații avansate Divide et impera
Sarcini de lucru
Rezolvă sarcinile de mai jos pentru a consolida tehnicile avansate de tip Divide et impera
Sarcina 1: Inversiunile unui vector aproape sortat
Cerință: Scrie un program C++ care citește n și n numere și afișează numărul de inversiuni, folosind interclasarea modificată. Testează pe un vector aproape sortat (de exemplu 1 2 4 3 5) și verifică mental rezultatul.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int v[100001], temp[100001];
long long inversiuni;
void interclaseaza(int st, int mij, int dr) {
int i = st, j = mij + 1, k = st;
while (i <= mij && j <= dr) {
if (v[i] <= v[j]) {
temp[k++] = v[i++];
} else {
temp[k++] = v[j++];
inversiuni += mij - i + 1;
}
}
while (i <= mij) {
temp[k++] = v[i++];
}
while (j <= dr) {
temp[k++] = v[j++];
}
for (int p = st; p <= dr; p++) {
v[p] = temp[p];
}
}
void numaraInversiuni(int st, int dr) {
if (st < dr) {
int mij = (st + dr) / 2;
numaraInversiuni(st, mij);
numaraInversiuni(mij + 1, dr);
interclaseaza(st, mij, dr);
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
inversiuni = 0;
numaraInversiuni(1, n);
cout << inversiuni << endl;
return 0;
}
Verifică: pentru 1 2 4 3 5 există o singură inversiune, perechea (4, 3). Pentru 5 4 3 2 1, rezultatul este 10. Vectorii aproape sortați au puține inversiuni, iar algoritmul le numără corect în timpul interclasării.
Sarcina 2: Căutare rotită cu poziție validată
Cerință: Scrie un program C++ care citește n, x și un tablou sortat rotit cu elemente distincte și afișează poziția lui x sau 0. Testează și cazurile: x mai mic decât toate elementele și x mai mare decât toate elementele.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int v[100001];
int cautaRotit(int st, int dr, int x) {
if (st > dr) {
return 0;
}
int mij = (st + dr) / 2;
if (v[mij] == x) {
return mij;
}
if (v[st] <= v[mij]) {
if (x >= v[st] && x < v[mij]) {
return cautaRotit(st, mij - 1, x);
} else {
return cautaRotit(mij + 1, dr, x);
}
} else {
if (x > v[mij] && x <= v[dr]) {
return cautaRotit(mij + 1, dr, x);
} else {
return cautaRotit(st, mij - 1, x);
}
}
}
int main() {
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
cout << cautaRotit(1, n, x) << endl;
return 0;
}
Verifică: pentru 4 5 6 7 1 2 3 și x = 0 (mai mic decât toate) rezultatul este 0; pentru x = 7, rezultatul este 4. Ambele cazuri exercită ambele ramuri ale testului de jumătate sortată.
Scrie pe caiet - Probleme avansate Divide et impera
Titlul lecției
- Ora 10: Probleme avansate Divide et impera
Definiția lecției
Lecția prezintă două probleme avansate de tip Divide et impera. O inversiune este o pereche de poziții (i, j) cu i < j și v[i] > v[j]; numărul de inversiuni măsoară cât de departe este vectorul de la ordonarea crescătoare. Numărarea se face printr-o interclasare modificată: la copierea unui element din jumătatea dreaptă se adaugă contorului mij - i + 1 (câte elemente mai rămân în jumătatea stângă), obținându-se O(n log n). Căutarea într-un tablou sortat și rotit se bazează pe testul v[st] <= v[mij], care arată care jumătate este sortată, apoi se continuă recursiv în jumătatea potrivită, în O(log n). Contorul de inversiuni se declară long long, iar cazul de bază al căutării este st > dr (elementul lipsește).
Definiții esențiale
- Inversiune: perechea de poziții (i, j) cu i < j și v[i] > v[j]; numărul de inversiuni măsoară cât de „răsturnat" este un vector.
- Numărarea prin interclasare: când copiem v[j] din jumătatea dreaptă, adăugăm mij - i + 1 inversiuni (elementele rămase în stânga), în O(n log n).
- Tablou sortat și rotit: tablou sortat crescător tăiat într-un punct, cu primele k elemente mutate la sfârșit; cele două jumătăți sunt sortate separat.
- Testul de jumătate sortată: dacă v[st] <= v[mij], jumătatea stângă este sortată; altfel este sortată cea dreaptă.
Algoritmul cheie - pseudocod
- Numărare inversiuni: interclasare modificată cu
inversiuni += mij - i + 1la copierea din dreapta. - Căutare rotită: caz de bază
st > dr→ 0; testv[st] <= v[mij]; continuare în jumătatea potrivită.
Algoritmul cheie - cod C++
- Interclasare: compară cu
<=(egalitățile nu sunt inversiuni), contorlong long. - Căutare: funcție recursivă
cautaRotit(st, dr, x)cu patru ramuri de decizie. - Ambele funcții se definesc înainte de
main(), cu tablouri globale.
Greșeli comune de evitat
- Folosirea lui
<în loc de<=la interclasare: egalitățile devin inversiuni false. - Contor
intpentru inversiuni: pentru n = 100000, rezultatul depășește 2 miliarde. - La căutarea rotită, folosirea unei căutări binare obișnuite: tabloul nu este sortat global.
- Uitarea cazului de bază
st > drla căutare: recursivitate fără oprire.
Sfaturi practice și trucuri
- Pentru a verifica numărul de inversiuni, scrie mai întâi soluția pătratică pe un vector mic și compară rezultatele.
- La căutarea rotită, testează vectorul nerotit (rotire cu 0 poziții): trebuie să se comporte ca o căutare binară.
- Desenează interclasarea pe 4 elemente și urmărește fiecare adunare la contor.
- La oral, justifică numărarea „în bloc" spunând: jumătatea stângă e sortată, deci toate elementele rămase sunt mai mari decât v[j].
Exemplu practic
Un profesor vrea să vadă cât de aproape de ordinea alfabetică este lista clasei: numără perechile de elevi așezați „întors" (un elev cu numele mai mare înaintea unuia cu numele mai mic). Același număr se obține în O(n log n) adăugând în interclasare fragmentul de mai jos, care contorizează inversiunile la copierea din jumătatea dreaptă:
if (v[i] <= v[j]) {
temp[k++] = v[i++];
} else {
inversiuni += mij - i + 1;
temp[k++] = v[j++];
}