w3

Wypełnianie planszy

Zadanie: dysponując klockami

oraz planszą
2

brakującym
polem:

Wypełnić plansze
w całości:

Wypełnianie planszy : podział zadania

 Oryginalną planszę dzielimy na 4 części



Dostajemy problemy o rozmiarze 2

n-1



Ale: trzy z nich nie są podobne do
oryginalnego (plansze nie mają
brakującego pola)!

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



Każda z planszy ma brakujące pole

Wypełnianie planszy : algorytm

INPUT: n – plansza 2

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

INPUT: n – plansza 2

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

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

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

 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

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

(1)

( )

2 ( / 2)

(1) if

T n









 





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)

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

 T(n) = (n) – nie lepiej niż dla metody siłowej!
 Poprawa: rozwiązywać zadanie tylko dla jednej połowy tablicy

Czas działania metody

T(n) = (lg n) !

(1)

( )

( / 2)

(1) if

T n









 





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

i S

. (tj. S

zawiera

pierwsze n/2elementów, a S

kolejne n/2).

 Zwyciężaj: posortuj sekwencje S

i S

stosując Merge Sort.

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

w sekwencję S zachowaniem porządku

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

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ń

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)

( )

2 ( /2)

( ) if

T n









 





)

(

)

(





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

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

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.

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

M(n)

Ilość kroków

 Rozwijając tę zależność dostajemy

M(n)

= 2M(n-1) + 1

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

M(n-2) + 1+2

= 2

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

= 2

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

=…

 Po k krokach

M(n) = 2

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

+ … + 2

n-k-1

 Dla k = n-1

M(n)

= 2

n-1

M(1) + 1+2 + 2

+ … + 2

n-2

= 1 + 2 + … + 2

n-1

= 2

-1

Document Outline