Contact și feedback

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.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Divide et Impera (metodă de programare C++)

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).

Untitled

Aceste tipuri de probleme se pot rezolva folosind metoda Divide et Impera.

Ce este Divide et Impera?

Divide et Impera este o metodă de programare recursivă ce constă în principiul următor:

  • descompunem problema curentă în două sau mai multe subprobleme (de același tip ca problema inițială, însă mai mici sau mai ușoare);
  • fiecare subproblemă se rezolvă separat (se pot descompune la rândul lor în alte subprobleme și mai ușoare);
  • se combină rezultatele fiecărei subprobleme, pentru a forma soluția problemei inițiale.

Trebuie menționat faptul că subproblemele:

  • trebuie să fie de același tip ca problema inițială;
  • trebuie să fie mai simple;
  • trebuie să fie independente unele de altele, pentru a nu risca suprapunerea rezultatelor.

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.

Exemplu: suma numerelor unui vector folosind Divide et Impera

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 între 1 și n.

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).

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Să vedem un exemplu vizual:

Untitled

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.

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Structura unui program de tip Divide et Impera

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
└■

Suma elementelor unui vector folosind Divide et Impera în C++

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.

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

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;
}

Maximul unui vector folosind Divide et Impera în C++

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.

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

#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;
}

Probleme propuse

Probleme diverse cu Divide et Impera

# 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.

Probleme de sortare folosind Divide et Impera

# Problemă Dificultate
771. La furat de corcoduse Grea (8 )

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Bibliografie sau alte resurse

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Interschimbarea a două variabile în C++ (3 metode)Verificare dacă șir de caractere este palindrom în C++Verificare dacă un număr este palindrom în C++Maximul și minimul a două valori în C++Tipul struct în C++. Ce sunt structurile de date neomogeneVerifică dacă un număr este par sau impar fără modulo în C++Numărul de divizori al unui număr în C++Maximul și minimul unui vector în C++Numărul combinărilor în C++ (formula combinărilor)Vectorii în C++: declarare și parcurgereVectorii în C++: citire și afișareAflarea sumei primelor N sume GaussCodul ASCII (tabel complet)Citirea și afișarea matricelor în C++Ce este o funcție void în C++?Cel mai frecvent element dintr-un șir în C++Generarea șirului Fibonacci generalizat în C++Instrucțiunea while (structuri repetitive)Verifică dacă trei puncte sunt coliniare C++Șiruri de caractere în C++. Tot ce trebuie să știiTutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Funcții predefinite în C++ (matematice, șiruri de caractere)Transformarea unui număr din baza 10 în baza 2 în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Distanța dintre două puncte în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiCopiuțe: Cifrele unui numărCel mai mic număr cu suma cifrelor N în C++Al N-lea termen dintr-o progresie aritmeticăCMMMC a două numere în C++ (cel mai mic multiplu comun)Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortCiurul lui Eratostene în C++Comentarii în C++Maximul și minimul a trei valori în C++Calculul combinărilor de n luate câte k (nCk) în C++Cel mai semnificativ bit în C++Numărul de cifre ale factorialului unui numărCel mai puțin semnificativ bit în C++Numărul minim de peroane pentru o gară în C++Divide et Impera (metodă de programare C++)Indicatorul lui Euler în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleVerificare număr prim în C++ (Clasa a IX-a)Instrucțiunea break (structuri repetitive)Suma 1 + 2 + 3 + ... + N în C++Maximul și minimul a n valori în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Oglinditul recursiv al unui număr în C++Cum să calculezi instant 2 la puterea N în C++Do while vs while în C++ - Care e diferența?Afișarea elementelor unui vector recursiv în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorCifra maximă și minimă a unui număr în C++Mediana unui șir de valori în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Vectori de frecvență (de apariții) în C++Instrucțiunea for (structuri repetitive)Numărul aranjamentelor în C++ (formula aranjamentelor)Cifra de control a unui numărInstrucțiunea continue (structuri repetitive)Transformarea unei litere mici în literă mare în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicValoarea absolută (modulul) unui număr în C++Al N-lea termen Fibonacci în C++Instrucțiunea de decizie în C++: if, else, switch, caseDe ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Pointer în C++. Variabile de tipul char * (char steluță)Combinatorică în C++: permutări, aranjamente, combinări și alteleCifra maximă a unui număr recursiv în C++Verifică dacă o literă este mică sau mare în C++Ce înseamnă variabilă globală și locală în C++?Structuri repetitive (while, do while, for, etc)Suma numerelor naturale dintr-un interval dat în C++Cum să citești și să afișezi în fișiere în C++Complexitatea unui algoritm (timp și spațiu) în C++Prima cifră a unui număr în C++Verifică dacă un număr dat este o putere de 2 în C++Verifică dacă un caracter este cifră în C++Factorialul unui număr în C++Matrice pătratice în C++. Diagonala principală și secundarăTransformarea unei litere mari în literă mică în C++Citește un șir de caractere cu spații în C++Operații cu numere mari în C++ - Toate funcțiile explicateInversarea unui șir de caractere în C++Verifică dacă un număr aparține șirului Fibonacci în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Funcții în C++. Ce sunt subprogrameleNumărul de divizori primi ai unui număr în C++Tipuri de date în C++: numere întregi, reale, caractere și alteleNumere triunghiulare. Verificarea unui număr triunghiularInversarea unui vector în C++Suma divizorilor unui număr în C++Rădăcina cubică a unui număr în C++ (cube root)Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Recursivitate în C++Câte numere naturale sunt într-un interval dat? (C++)Verifică dacă o literă este vocală în C++Căutare binară în C++Interclasarea a doi vectori în C++Numărul permutărilor în C++ (formula permutărilor)CMMDC recursiv a două numere naturale în C++Afișarea divizorilor primi ai unui număr în C++Cea mai lungă secvență de elemente crescătoare în C++Oglinditul unui număr în C++Bordarea unei matrice în C++Cum să afișezi partea întreagă a unui număr real în C++Radicalul unui număr în C++ (rădăcina pătrată)Verificarea unui an bisect în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăAflă secolul unui an citit de la tastatură în C++Aria unui triunghi folosind coordonatele acestora în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Aria și circumferința unui cerc în C++Transformarea unui număr din baza 2 în baza 10 în C++Verifică dacă un caracter este literă în C++Ce înseamnă endl în C++?Al N-lea termen dintr-o progresie geometricăCifrele unui număr. Prelucrarea cifrelor unui număr în C++Șirul lui Fibonacci în C++Ce este o variabilă unsigned în C++?Instrucțiunea do while (structuri repetitive)Suma elementelor unui vector recursiv în C++Numărul de apariții al unui număr într-un vector în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont