Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.
Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.
Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.
Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.
Meniu shortcuturi | ? |
Căutare probleme sau utilizatori | / |
Navigare printre rezultatele căutării | ↑, ↓ |
Meniu de contact și feedback | CTRL + Shift + F |
Ieșire din meniuri | Esc |
Setări editor | CTRL + Shift + S |
Schimbare stil editor | CTRL + Shift + E |
Șabloane de cod | CTRL + Shift + 1/2/3 |
Golire editor | CTRL + Shift + 4 |
Vedem că există multe probleme care se pot rezolva prin împărțirea lor în subprobleme mai mici și mai ușor de rezolvat (care la rândul lor se pot împărți în probleme și mai mici și tot așa, până când ajungem la probleme foarte ușoare care se pot rezolva pe loc). Iată un tip de cerință:
Se dă un șir de
n
numere naturale. Se cere calcularea sumei tuturor numerelor.
Putem să împărțim problema în a calcula suma primelor n / 2
valori, la care adunăm suma ultimelor n / 2
valori. După aceea, fiecare secvență o putem împărți la rândul ei în alte două secvențe mai mici, până când ajungem la secvențe de lungime 1
, în care suma este chiar valoarea respectivă (mai jos găsim un exemplu vizual).
Aceste tipuri de probleme se pot rezolva folosind metoda Divide et Impera.
Divide et Impera este o metodă de programare recursivă ce constă în principiul următor:
Trebuie menționat faptul că subproblemele:
Atunci când ajungem la o (sub)problemă indivizibilă (fie că este foarte ușor de găsit răspunsul pe loc, sau că pur și simplu nu mai putem să dividem problema mai mult), atunci ne aflăm la o așa-numită problemă elementară, care se rezolvă într-un alt mod, de regulă brut.
Să luăm exemplul de mai devreme: suma numerelor unui șir. Reformulăm un pic problema:
Se dă un șir de
n
numere naturale. Să se calculeze suma numerelor cu indicii între1
șin
.
Reformulând astfel problema, ne este mai ușor să găsim o rezolvare Divide et Impera.
Avem șirul inițial, pe care îl vom descompune în două jumătăți. Fiecare jumătate o vom descompune la rândul ei în alte două jumătăți și tot așa, până când ajungem să avem secvențe de lungime 1
, unde pur și simplu returnăm elementul curent, întrucât nu mai putem să împărțim în secvențe mai mici.
Pentru problema curentă, după calcularea rezultatelor din subprobleme, le vom aduna în acest caz pentru a forma rezultatul problemei curente (întrucât trebuie să calculăm suma numerelor).
Să vedem un exemplu vizual:
Pentru a calcula suma elementelor din vectorul (22, 2, 15, 44, 41, 7, 29, 49, 31, 24)
, îl împărțim în două secvențe (prima și a doua jumătate), pe care le despărțim la rândul lor în alte două secvențe și așa mai departe, până când ajungem la secvențe de numere individuale, pe care le procesăm direct.
Observație: Nu trebuie neapărat să împărțim în două subprobleme. Am putea să împărțim șirul în 3
, 4
, …, însă din punct de vedere al eficienței nu suntem mai avantajați cu mult, iar împărțirea în mai multe subprobleme devine impractică la un moment dat.
Totuși, există situații când este mai util să împărțim în mai mult de două subprobleme. Spre exemplu, într-o matrice căruia vrem să îi aflăm suma elementelor, poate fi practic să împărțim în 4
zone.
Un program de tip Divide et Impera este recursiv. Astfel, de regulă, avem următoarea structură:
┌ rezolvă(pb)
│ ┌ dacă pb este problemă elementară
│ │ raspuns = rezolvareDirectă(pb)
│ ├ altfel
│ │ subPb1, subPb2 ← descompune(pb)
│ │ raspuns1 ← rezolvă(subPb1)
│ │ raspuns2 ← rezolvă(subPb2)
│ │ raspuns ← combinăRezulate(raspuns1, raspuns2)
│ └■
│ returnează raspuns
└■
Rezolvăm problema propusă la începutul lecției. Vom folosi doi indici, st
și dr
, care marchează secvența curentă a problemei. Problema în sine se rezolvă apelând funcția cu indicii st = 1
și dr = n
, iar de aici împărțim recursiv problema în jumătăți, luând la final suma fiecărei jumătăți.
Problema elementară apare atunci când st = dr
, adică atunci când avem un singur element. În acest caz, returnăm pur și simplu elementul de pe poziția dată.
#include <iostream>
using namespace std;
int sumaDivImp(int a[], int st, int dr) {
//Explicații: infoas.ro
if(st == dr) { //Problemă elementară
return a[st];
}
int mij = (st + dr) / 2;
int suma1 = sumaDivImp(a, st, mij); //Subproblema 1
int suma2 = sumaDivImp(a, mij + 1, dr); //Subproblema 2
return suma1 + suma2; //Rezolvarea problemei
}
int main()
{
//Declarăm și citim șirul în ordinea: lungimea șirului, elementele șirului
int a[100], n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
cout << "Suma numerelor sirului este " << sumaDivImp(a, 1, n);
return 0;
}
Similar ca mai devreme, putem să calculăm maximul (sau minimul) dintre elementele unui vector. De menționat este faptul că, spre deosebire de suma elementelor, pentru a calcula maximul nu este nicio problemă dacă se suprapun anumite subprobleme (în afară de faptul că ar încetini programul), pentru că maximul rămâne tot același chiar dacă verificăm de mai multe ori același element.
#include <iostream>
using namespace std;
int maxDivImp(int a[], int st, int dr) {
//Explicații: infoas.ro
if(st == dr) { //Problemă elementară
return a[st];
}
int mij = (st + dr) / 2;
int max1 = maxDivImp(a, st, mij); //Subproblema 1
int max2 = maxDivImp(a, mij + 1, dr); //Subproblema 2
if(max1 > max2) return max1;
return max2;
}
int main()
{
//Declarăm și citim șirul în ordinea: lungimea șirului, elementele șirului
int a[100], n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
cout << "Maximul numerelor sirului este " << maxDivImp(a, 1, n);
return 0;
}
# | Problemă | Dificultate | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
703. | Toate egale Divide et Impera | Medie (4 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
704. | Cmmdc sir Divide et Impera | Medie (4 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
694. | Suma sirului Divide et Impera | Ușoară (2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
701. | Maximul sirului Divide et Impera | Ușoară (2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
699. | Numarare palindrom Divide et Impera | Medie (4 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse. |
# | Problemă | Dificultate | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Vom adăuga probleme cât de curând! |