1 

Wykład 3 

Metoda „dziel i zwyciężaj” 

2 

Wprowadzenie 



Technika konstrukcji algorytmów

 

dziel i zwyciężaj. 

 

  

przykładowe problemy: 

– Wypełnianie planszy 

– Poszukiwanie (binarne) 

– Sortowanie (sortowanie przez łączenie - merge sort). 

3 

Wypełnianie planszy 

Zadanie: dysponując klockami 

oraz planszą 2

n

x2

n

 z 

brakującym polem: 

Wypełnić plansze w 

całości: 

4 

Wypełnianie planszy: przypadki trywialne (n = 1) 

 Przypadek trywialny (n = 1): 

wypełniamy plansze jednym klockiem: 



Idea dla rozwiązania problemu – doprowadzić 

rozmiar zadania do przypadku trywialnego, który 

umiemy rozwiązać 

5 

Wypełnianie planszy : podział zadania 



Oryginalną planszę dzielimy na 4 części 



Dostajemy problemy o rozmiarze 2

n-1

x2

n-1

 



Ale: trzy z nich nie są podobne do 

oryginalnego (plansze nie mają brakującego 

pola)!  

6 

Wypełnianie planszy : podział zadania 



pomysł: umieszczamy jeden klocek w środku planszy i dokonujemy 

podziału na 4 części 



Teraz otrzymujemy 4 plansze o rozmiarach 2

n-1

x2

n-1

. 



Każda z planszy ma brakujące pole

 

7 

Wypełnianie planszy : algorytm 

INPUT: n  

– plansza 2

n

x2

n

, L 

– pozycja brakującego pola.  

OUTPUT: 

wypełniona plansza

 

 
Tile(n, L) 
   if n = 1 then 
      

przypadek trywialny 

      wypełnij jednym klockiem 
      return 
   umieść jeden klocek w środku planszy   
  podziel planszę na 4 równe części 
  Niech L1, L2, L3, L4 oznaczają pozycje 4 brakujących pól 
   Tile(n-1, L1) 
   Tile(n-1, L2)  
   Tile(n-1, L3)  
   Tile(n-1, L4)  
 

8 

Dziel i zwyciężaj 



Metoda konstrukcji algorytmów „Dziel i zwyciężaj” : 

– Jeśli problem jest na tyle mały, że umiesz go rozwiązać  - zrób to. Jeśli nie 

to: 

• Podział: Podziel problem na dwa lub więcej rozdzielnych 

podproblemów 

• Rozwiązanie: Wykorzystaj metodę rekurencyjnie dla rozwiązania tych 

podproblemów 

• Łączenie: połącz rozwiązania podproblemów tak, aby rozwiązać 

oryginalny problem 

9 

Wypełnianie planszy : Dziel i zwyciężaj 



Wypełnianie jest przykładem algorytmu „dziel i zwyciężaj” : 

– w wypadku trywialnym (2x2) – po prostu wypełniamy planszę, lub: 

– Dzielimy planszę na 4 mniejsze części (wprowadzając wypełnione miejsce 

w rogu, przez umieszczenie centralnie jednego klocka) 

– Rozwiązujemy problem rekursywnie stosując tą samą metodę 

– Łączymy części umieszczając klocek w środku planszy 

10 



Odnaleźć 

liczbę w posortowanej tablicy: 

– Przypadek trywialny – tablica jest jednoelementowa 

– Albo dzielimy tablice na dwie równe części i rozwiązujemy zadanie 

osobno dla każdej z

 nich 

 
 

Poszukiwanie binarne 

INPUT: A[1..n] 

– posortowana niemalejąco tablica liczb, s – liczba.  

OUTPUT: indeks j 

taki, że A[j] = s. NIL, jeśli 

"

j (1



j



n): A[j] 

 

s 

 

Binary-search(A, p, r, s): 
   if p = r then  
      if A[p] = s then return p 
      else return NIL  

 

   q



(p+r)/2



 

   ret 



 Binary-search(A, p, q, s) 

   if ret = NIL then  
      return Binary-search(A, q+1, r, s) 
   else return ret       

11 

Rekurencja 



Czas działania algorytmu z odwołaniami rekursywnymi można opisać poprzez 
rekurencję 



Równanie/nierówność opisująca funkcję poprzez jej wartości dla mniejszego 

argumentu 

 

 

Przykład: poszukiwanie binarne 

 

 

 

 

 

 

Po rozwiązaniu daje to złożoność O(n)! – taką samą jak dla metody naiwnej 

(1)

  if 

1

( )

2 ( / 2)

(1)   if 

1

n

T n

T n

n







 

 





12 

Poszukiwanie binarne (poprawione) 

INPUT: A[1..n] 

– posortowana niemalejąco tablica liczb, s – liczba.  

OUTPUT: indeks j 

taki, że A[j] = s. NIL, jeśli 

"

j (1

≤j≤n): A[j] ≠s  

 
Binary-search(A, p, r, s): 
   if p = r then  
      if A[p] = s then return p 
      else return NIL  

 

   q



(p+r)/2



 

   if A[q] 



 s then return Binary-search(A, p, q, s) 

   else return Binary-search(A, q+1, r, s) 



T(n) = 



(n) – nie lepiej niż dla metody siłowej! 



Poprawa: rozwiązywać zadanie tylko dla jednej połowy tablicy 

 

13 

Czas działania metody 

T(n) = 



(lg n) ! 

(1)

  if 

1

( )

( / 2)

(1)   if 

1

n

T n

T n

n







 

 





14 

 
Sortowanie przez łączenie (merge sort) 

 Podziel: 

Jeśli S posiada przynajmniej dwa elementy (1 lub 0 elementów – 

przypadek trywialny), podziel S 

na dwie równe (z dokładnością do 1 

elementu) części S

1

 i S

2

. (tj. S

1

 zawiera pierwsze 



n/2

  

elementów, a S

2

 

kolejne 



n/2



). 



Zwyciężaj: posortuj sekwencje S

1

 i S

2

 

stosując Merge Sort. 



Połącz: Połącz elementy z dwóch posortowanych sekwencji S

1

 i S

2

 w 

sekwencję S zachowaniem porządku 

15 

Algorytm 

– Merge Sort   

Merge-Sort(A, p, r) 
   if p < r then 
      q

 

(p+r)/2



 

      Merge-Sort(A, p, q) 
      Merge-Sort(A, q+1, r) 
      Merge(A, p, q, r) 

Merge(A, p, q, r) 
   wybieramy mniejszy z dwóch elementów na początku 
sekwencji A[p..q] oraz A[q+1..r] i wkładamy go do 
sekwencji wynikowej, przestawiamy odpowiedni znacznik. 
Powtarzamy to aż do wyczerpania się elementów. 
Rezultat kopiujemy do A[p..r].  

16 

Sortowanie przez łączenie - 1 

17 

Sortowanie przez łączenie - 2 

18 

Sortowanie przez łączenie - 3 

19 

Sortowanie przez łączenie - 4 

20 

Sortowanie przez łączenie - 5 

21 

Sortowanie przez łączenie - 6 

22 

Sortowanie przez łączenie - 7 

23 

Sortowanie przez łączenie - 8 

24 

Sortowanie przez łączenie - 9 

25 

Sortowanie przez łączenie - 10 

26 

Sortowanie przez łączenie - 11 

27 

Sortowanie przez łączenie - 12 

28 

Sortowanie przez łączenie - 13 

29 

Sortowanie przez łączenie - 14 

30 

Sortowanie przez łączenie - 15 

31 

Sortowanie przez łączenie - 16 

32 

Sortowanie przez łączenie - 17 

33 

Sortowanie przez łączenie - 18 

34 

Sortowanie przez łączenie - 19 

35 

Sortowanie przez łączenie - 20 

36 

Sortowanie przez łączenie - 21 

37 

Sortowanie przez łączenie - 22 

38 

Sortowanie przez łączenie – podsumowanie  

 Sortowanie n liczb 

– jeśli n=1 – trywialne  

– rekursywnie sortujemy 2 ciągi 



n/2



 i 



n/2



 liczb 

– łączymy dwa ciągi w czasie 



(n) 

 Strategia  

– Podział problemu na mniejsze, ale 

analogiczne podproblemy 

– Rekursywne rozwiązywanie 

podproblemów 

– Łączenie otrzymanych rozwiązań 

39 

Sortowanie przez łączenie – czas działania 



Czas działania algorytmu może być 
reprezentowany przez następującą 
zależność rekurencyjną: 

 

 

 

 

 



Po rozwiązaniu dostajemy: 

(1)

  if 

1

( )

2 ( / 2)

( )   if 

1

n

T n

T n

n

n







 

 





)

lg

(

)

(

n

n

n

T





40 

Wieże Hanoi 



Mamy 3 wieże oraz stos 64 dysków o zmniejszających się średnicach 
umieszczonych na pierwszej wieży 



Potrzebujemy przenieść wszystkie dyski na inną wieżę 



Zabronione jest położenie dysku  większego na mniejszym 



W każdym kroku wolno mam przenieść tylko jeden dysk 

41 

Wieże Hanoi 

42 

Rozwiązanie rekursywne 

43 

Algorytm rekursywny 

INPUT: n  

– ilość dysków , a, b, c – wieże, wieża a zawiera wszystkie dyski.  

OUTPUT: a, b, c 

– wieże, wieża b zawiera wszystkie dyski 

 
Hanoi(n, a, b, c) 
      if  n = 1 then 
          Move(a,b); 
      else 
          Hanoi(n-1,a,c,b); 
          Move(a,b); 
          Hanoi(n-1,c,b,a); 
 

Poprawność algorytmu łatwo pokazać przez indukcję względem n. 

44 

Ilość kroków 

 



Ilość kroków M(n) potrzebnych do 
rozwiązania problemu dla n  dysków 
spełnia zależność rekurencyjną 

M(1) = 1 

M(n) = 2M(n-1) + 1 

 

n 

M(n) 

1 

1 

2 

3 

3 

7 

4 

15 

5 

31 

45 

Ilość kroków 



Rozwijając tę zależność dostajemy 

 

    M(n)   = 2M(n-1) + 1 

       

= 2*[2*M(n-2)+1] + 1 = 2

2 

*

 

M(n-2) + 1+2 

       

= 2

2 

* [2*M(n-3)+1]  + 1 + 2 

       

= 2

3 

*

 

M(n-3) + 1+2 + 2

2 

=… 

 Po k krokach 
 

M(n) = 2

k 

*

 

M(n-k) + 1+2 + 2

2 

+ … + 2

n-k-1 

 

 Dla k = n-1 
 

M(n)  = 2

n-1 

*

 

M(1) + 1+2 + 2

2 

+ … + 2

n-2 

 

 

= 1 + 2 + … + 2

n-1 

= 2

n

-1