10 2018 Lectia22

From Algopedia
Jump to navigationJump to search

Metoda Divide et impera

Achizitii anterioare Pentru a parcurge aceasta lectie trebuie sa stiti:

  • Tablouri unidimensionale ( vectori )
  • Subprograme definite de utilizator
  • Recursivitate. Principiul recursivitatii ( ce se intampla la un nivel, se intampla la orice nivel, avand grija sa asiguram oprirea lantului recursiv)

Utilizare

  • Cautare binara - analogie cu cautarea unui cuvant intr-un dictionar
  • Sortari rapide (QuickSort,MergeSort, Stitistici de ordine) -analogie cu impartirea merelor in 2 gramezi in functie de un mar etalon
  • Un alt domeniu de utilizare a tehnicii divide et impera este programarea paralelă pe mai multe procesoare, sub-problemele fiind executate pe mașini diferite.

Introducere

Expresia “Divide et Impera” provine din limba latina si reprezinta unul dintre principiile de guvernare ale imparatului roman Iulius Caesar. In traducere inseamna „dezbina si stapaneste”. El a ajuns la concluzia ca o masa de oameni poate fi mai usor stapanita, atunci cand este dezbinata! In informatica metoda Divide et Impera reprezinta o metoda de programare ce se bazeaza pe acelasi principiu. Aceasta presupune 3 etape de rezolvare:

  1. DIVIDE problema data se descompune in 2 sau mai multe subprobleme, de acelasi tip cu problema initiala, dar de dimensiuni mai mici, independente ( subproblemele nu se suprapun ).
  2. STAPANESTE Se rezolvata subproblemele. Subproblemele se rezolva direct daca dimensiunea lor permite acest lucru (probleme elementare) sau, fiind de acelasi tip, se rezolva in mod recursiv, in acelasi mod precum problema initiala (se descompun in continuare similar cu problema de baza. Procesul de descompunere continua pana cand s-au obtinut numai probleme elementare).
  3. COMBINA Se combina solutiile subproblemelor pentru a obtine solutia problemelor initiale.

Modelul metodei

Cel mai potrivit model pentru explicarea metodei il constituie prelucrarea unui vector (sir) de forma fara: (x0,x1,…,xn-1). Aplicarea metodei consta in impartirea sirului dat in doua subsiruri (x0,…xm), (xm+1,…,xn-1) si prelucrarea fiecaruia dintre ele. Astfel, am descompus problema in doua subprobleme de acelasi tip. In continuare, pentru fiecare dintre subsirurile obtinute sunt posibile doua situatii:

  • Se poate prelucra direct;
  • Nu poate fi prelucrat direct, caz in care subsirul trebuie descompus in acelasi fel. Lantul de descompuneri va continua pana cand obtinem numai subsiruri prelucrabile direct. Putin mai general, putem modela procedeul considerand ca la fiecare pas al algoritmului va fi analizat un subsir de forma (xp,…xq), care contine elementele sirului situate intre indicii p si q. Presupunem ca oricare ar fi p,q∈{0,1,…n-1}, exista m∈{p,…,q} asa incat prelucrarea subsirului {xp,…,xq} sa se faca prelucrand subsirurile (xp,…,xm) si (xm+1,…,xq). Este natural sa consideram ca prelucrarea subsirului (xp,…xq) se face printr-o functie recursiva, notata generic Div_Imp (int p, int q). O structura posibila a acesteia ar fi:
  • Daca subsirul (xp,…xq) poate fi prelucrat direct, atunci il prelucram;

In caz contrar:

  • Impartim subsirul (xp,…xq) in alte 2 subsiruri: (xp,…xm) si (xm+1,…xq)
  • Prelucram subsirurile obtinute: intrucat subsirul(xp,…xm) trebuie descompus mai departe in aceeasi maniera, rezulta ca prelucrarea acestuia se va face printr-un auto-apel recursiv de forma Div_Imp (p,m); analog, sirul (xm+1,…xq) se va prelucra prin auto-apelul Div_Imp (m+1,q)

Observatii:

  • De obicei elementul xm care determina partitionarea subsirului (xp,…xq), este cel aflat pe pozitia de mijloc: m=(p+q)/2(“parte intreaga din (p+q)/2”).

Astfel, subsirurile obtinute vor avea dimensiuni apropiate si in consecinta subproblemele determinate de catre aceste subsiruri vor fi apropiate din punct de vedere al complexitatii.

  • In procesul de descompunere, subsirurile pot fi alese si altfel: de exemplu, (xp,…xm-1) si (xm+1,…xq), adica elementul de referinta xm nu a fost inclus in nici unul dintre subsiruri;
  • In general, un subsir poate fi prelucrat direct daca nu are nici un element sau contine un singur element.

Complexitatea algoritmului este dată de formula: unde D(n), S(n) şi C(n) reprezintă complexitățile celor 3 pași descriși mai sus: divide, stăpânește, respectiv combină

T(n) = D(n)+S(n)+C(n), unde D(n)=O(1), S(n)=2∗T(n/2) și C(n)=O(n), rezulta 
T(n) = 2∗T(n/2)+O(n).

Vom ajunge la complexitatea:

T(n) = O(n∗log(n)) 

Maximul dintr-un vector

Enunt: Se consideră un șir cu n elemente, numere naturale. Folosind metoda Divide et Impera, determinați cel mai mare element din acest șir.

Descrierea solutiei: Impartim problema in 2 subprobleme de complexitate similara. Vom mparti intervalul de cautare in 2 subintervale, rezultand astfel 2 subprobleme, similare problemei intiale, dar de complexitate mai mica. Vom continua impartirea acestora in alte subintervale pana vor rezulta intervale cu un singur elemenent. Aceste probleme elementare le putem rezolva direct, intrerupand lantul recursiv. Putem defini deci functia vmax astfel:

vmax(i, j) = v[i], daca i = j
           = max(vmax(i,m), vmax(m+1, j)), daca i<j
            
  • dacă i = j, valoarea maxima va fi v[i];
  • în caz contrar, se imparte vectorul în doi subvectori . Se calculează mijlocul m al intervalului [i, j]: m = (i+j) / 2. Primul subvector va conține componentele de la i la m, al doilea va conține componentele de la (m+1) la j; se rezolvă subproblemele (aflându-se astfel maximul pentru fiecare din subvectori), iar soluția curentă va fi dată de valoarea maximă dintre rezultatele celor două subprobleme.

Implementare

#include <iostream>
using namespace std;
int v[1000], n;

int max( int i, int j ) {
  int a, b, m;
  if ( i == j )
    return v[i];

  m = ( i + j ) / 2;
  a = max( i, m );
  b = max( m + 1, j );
  if  ( a > b )
    return a;
  else
    return b;
}

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

Cmmdc

cmmdc3 Enunt:Se dă un sir cu n elemente, numere naturale nenule. Folosind metoda Divide et Impera, determinaţi cel mai mare divizor comun al elementelor acestui șir.

#include <iostream>

using namespace std;

int cmmdc( int a, int b ){
  int r;
  while( b > 0 ){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

int n,v[1001];

int f( int st, int dr ){
  if( st == dr )
    return v[st];
  int mij = ( st + dr ) / 2;
  int s1 = f( st, mij );
  int s2 = f( mij + 1, dr );
  return cmmdc( s1, s2 );
}

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

Suma elementelor pare dintr-o matrice

Se consideră o matrice cu m linii și n coloane, numere naturale. Folosind metoda Divide et Impera, determinați suma numerelor pare din matrice.

#include <iostream>

using namespace std;

int a[101][101], m, n;
long long sum( int i1, int j1, int i2, int j2 ){
    // problema elementara - matrice fara nici un element
    if ( i2 < i1 || j2 < j1 )
      return 0;
    // problema elementara - matrice cu un singur element
    if ( i1 == i2 && j1 == j2 )
      if ( a[i1][j1] % 2 == 0 )
        return a[i1][j1];
      else
        return 0;
    long long s = 0;
    // problema neelementara - impart matricea in 4 submatrici
    int imij = ( i1 + i2 ) / 2;
    int jmij = ( j1 + j2 ) / 2;
    int s1 = sum( i1, j1, imij, jmij );     // rezolv subproblemele
    int s2 = sum( i1, jmij + 1, imij, j2 );
    int s3 = sum( imij + 1, j1, i2, jmij );
    int s4 = sum(imij + 1, jmij + 1, i2, j2 );
    return s1 + s2 + s3 + s4;           // combin rezultatul subproblemelor pentru a obtine sol problemei initiale
}

int main(){
  cin >> n >> m;
  for ( int i = 0; i< n; i++ )
    for ( int j = 0; j < m; j++ )
      cin >> a[i][j];
  cout<<sum( 0, 0, n - 1, m - 1);
  return 0;
}