Se poate trece la capitolul următor cu tasta ► și se poate reveni la un capitol precedent cu tasta ◄

Determinarea maximului unui șir prin Divide et Impera


<

C
a
p
i
t
o
l
u
l

a
n
t
e
r
i
o
r

<

1. Program

Determinarea valorii maxime a unui șir prin Divide et Impera în Pascal

2. Algoritm

Pentru șirul: (1, 4, 8, 3) algoritmul va împărți șirul în două jumătăți. Va încerca să găsească maximului șirului (1, 4) și apoi al șirului (8 și 3). Pentru a înțelege mai bine recursivitatea prezentă aici trebuie să urmărim codul:

Nivelul 1:

Funcția este apelată cu parametri i=1 și j=4. i este diferit de j. Ok, atunci a ia valoarea max(1 și 1+4 div 2), adică max(1, 2).

În acest moment execuția funcției este oprită fiindcă aceeași funcție este apelată a doua oară. Programul reține locul unde am rămas în primul apel al funcției și coboară la nivelul al doilea.

Nivelul 2:

Aici avem i=1 și j=2. Evident valorile sunt diferite. Aici a ia valoarea max(1, 1). Din nou ține minte unde am rămas și funcția se apelează a treia oară.

Nivelul 3:

Și aici ne vom lovi de situația când i=j și întoarcem valoarea curentă. Elementul de pe prima poziție este numărul 1.

Revenim la nivelul 2:

Așadar a ia valoarea 1. Apoi trecem la următoarea linie. b ia valoarea max(2, 2). Se apelează din nou funcția max și, cum i=j, ea va întoarce valoarea 4, numărul de pe poziția 2.

Aici vom avea de făcut o comparație, care este mai mare dintre 1 și 4? Păi 4. Și...

Revenim la nivelul 1

În acest moment a are valoarea 4. Continuăm cu b repetând procesul pentru max(3, 4). Deja de aici putem intui comparația finală, dintre 8 și 3. Evident b va lua valoarea 8, ca apoi să comparăm pe a (cu valoarea 4) cu b (care are valoarea 8). Și max va da răspunsul corect: 8 este valoarea maximă a acestui șir de test.

3. Avantaje și dezavantaje

Divide et impera are rolul de a reduce o problemă complexă la forma ei cea mai simplă. Ce este mai ușor decât suma unui șir cu un singur element? Ce este mai ușor decât a compara două numere?

Algoritmul necesită schimbarea felului cum privim o problemă. Un șir nu mai este văzut ca o linie: 4, 3, 7, 10, 6, 9, ci devine o problemă în spațiu bidimensional, introducând nivelele ca o nouă dimensiune. Pe primul nivel avem problema unui șir cu 6 elemente, dar pe nivelul doi avem două instanțe ale aceleiași probleme unde fiecare are doar 3 elemente.

Pe nivelul 3 avem deja aceeași problemă dar trebuie să facem comparație doar între două numere, iar pe nivelul 4 nici măcar nu mai avem 2 numere, aici trebuie să găsim valoarea maximă a unui șir cu un singur element.

Vizual ar arăta cam așa:

Nivel 1 Nivel 2  Nivel 3 Nivel 4 Nivel 3 Nivel 2 Nivel 1
    7 - (7)    
      4      
       3      
    4, 3   4    
  4, 3, 7       7  
4, 3, 7, 10, 6, 9           10
  10, 6, 9       10  
    10, 6    10    
      10      
      6      
    9  - (9)    

 Dezavantajul este însăși metoda, necesită o altfel de gândire asupra unei probleme care poate fi rezolvată mai simplu. Pe de altă parte nu poți apela aceeași funcție la nesfârșit. Fiecare apel consecutiv consumă memorie RAM. Ce se întâmplă dacă nu avem o condiție de ieșire? Funcția se va tot reapela până când:

Algoritm incorect divide et impera în Pascal

Eliminând condiția de ieșire, atunci când șirul are un singur element, am condamnat funcția noastră să se tot reapeleze. Și la un moment dat nu va mai exista memorie disponibilă pentru a realiza un nou apel.

Dar la ce ajută? E vorba de posibilitatea paralelizării, un obicei întâlnit la tot pasul în lumea actuală. Împărțind problema în două, obținem aceeași problemă de două ori, cu date total diferite. Gândește-te că valorile a și b ar putea fi calculate simultan. Nu trebuie să aștepți să afli maximul dintre 8 și 3 pentru a afla maximul dintre 7 și 2 (pentru șirul 8, 3, 7, 2 desigur).

În combinație cu fire de execuție, un algoritm divide et impera ar putea, de pildă, înjumătății timpul de execuție cu doar două fire lucrând în paralel. Dar cu 4? Sau cu 16?


>

C
a
p
i
t
o
l
u
l

u
r
m
ă
t
o
r

>

Ți-a fost de ajutor ce am scris aici?
Hei, mersi de răspuns.