2008-10-14
Rekurencja
Wykład 02.
Algorytmy i struktury danych
Rok akademicki: 2008/09
Rekurencja
• Rekurencyjny sposób zapisu kodu programu - z poziomu podprogramu wywoływany jest ten sam podprogram.
2
1
2008-10-14
Przykład (1)
public class Rekurencja01 {
static void f() {
System.out.println("Poczatek"); f();
System.out.println("Koniec");
}
public static void main(String [] args) {
f();
}
}
3
Przykład (2)
main()
Początek
Początek
Początek
Początek
{
f(x)
f(x)
f(x)
f(x)
i.t.d.
f()
Koniec
Koniec
Koniec
Koniec
}
4
2
2008-10-14
Przykład (3)
Efekt uruchomienia programu:
Poczatek
Poczatek
Poczatek
....
Poczatek
Exception in thread "main"
java.lang.StackOverflowError
5
Warunek stopu
• Wywołania rekurencyjne muszą się zakończyć (w podprogramie musi zostać zdefiniowany warunek zatrzymania się algorytmu /warunek stopu/).
6
3
2008-10-14
Przykład (1)
public class Rekurencja02 {
static int licznik = 0;
static void f() {
licznik++;
System.out.println("Poczatek"); if (licznik <=5) f();
System.out.println("Koniec");
}
public static void main(String [] args)
{
f();
}
}
7
Przykład (2)
licznik = 1
licznik = 2
licznik = 3
licznik = 4
licznik = 5
main()
licznik = 6
{
Początek
Początek
Początek
Początek
Początek
Początek
f()
f(x)
f(x)
f(x)
f(x)
f(x)
}
Koniec
Koniec
Koniec
Koniec
Koniec
Koniec
8
4
2008-10-14
Przykład (3)
Efekt uruchomienia programu:
Poczatek
Poczatek
Poczatek
Poczatek
Poczatek
Poczatek
Koniec
Koniec
Koniec
Koniec
Koniec
Koniec
9
Rekurencyjne obliczanie silni (1)
public class Rekurencja03 {
static int silnia(int n) {
int pomoc;
System.out.println("Wywolanie: silnia(" + n + ")"); if ((n == 0) || (n == 1)) pomoc = 1;
else pomoc = n * silnia(n-1);
System.out.println("Zwrocenie wyniku: " + n + "! = " + pomoc); return pomoc;
}
public static void main(String [] args) {
System.out.println("4! = " + silnia(4));
}
}
10
5
2008-10-14
Rekurencyjne obliczanie silni (2)
11
Rekurencja może być kosztowna ...
public class Rekurencja04 {
static int licznik = 0;
static int fib(int n)
//obliczanie n-tej liczby Fibonacciego
{
licznik++;
if (n == 0) return 0;
else
if (n == 1) return 1;
else return fib(n-1) + fib(n-2);
}
public static void main(String [] args) {
System.out.println("5-ta liczba Fibonacciego to: " + fib(5)); System.out.println("Liczba wywolan funkcji:" + licznik);
}
}
12
6
2008-10-14
Efekt działania:
5-ta liczba Fibonacciego to: 5
Liczba wywolan funkcji: 15
13
Sposób wyznaczania liczb Fibonacciego
Jeśli istnieje oczywiste rozwiązanie iteracyjne, to należy je wybrać.
14
7
2008-10-14
Sterowanie kolejnością wykonywania działań (1) public class Rekurencja05 {
static void sekwencja(int n) {
System.out.print(n + " ");
if (n > 0) sekwencja(n-1);
}
public static void main(String [] args) {
sekwencja(5);
System.out.println();
}
}
Efekt działania programu:
5 4 3 2 1 0
15
Sterowanie kolejnością wykonywania działań (2) public class Rekurencja06 {
static void sekwencja(int n) {
if (n > 0) sekwencja(n-1);
System.out.print(n + " ");
}
public static void main(String [] args) {
sekwencja(5);
System.out.println();
}
}
Efekt działania programu
0 1 2 3 4 5
16
8
2008-10-14
Wieże Hanoi
public class Rekurencja08 {
static void przesun(int ile, char wiezaZrodlowa, char wiezaDocelowa, char wiezaPomocnicza)
{
if (ile == 1)
System.out.println(wiezaZrodlowa + " => " + wiezaDocelowa); else
{
przesun(ile-1,wiezaZrodlowa,wiezaPomocnicza, wiezaDocelowa);
System.out.println(wiezaZrodlowa + " => " +
wiezaDocelowa);
przesun(ile-1,wiezaPomocnicza,wiezaDocelowa, wiezaZrodlowa);
}
}
17
Złożoność algorytmu: Wieże Hanoi (1)
• Analizowana jest liczba przesunięć potrzebna do rozwiązania zadania z n krążkami (liczbę przesunięć oznaczymy przez P(n))
• gdy n = 1 to P(1) = 1
• gdy n > 1 to P(n) = 2 * P(n – 1) + 1
18
9
2008-10-14
Złożoność algorytmu: Wieże Hanoi (2)
Liczba
Poziom
przesunięć
0
P(n)
1
P(n-1)
1
P(n-1)
1
2
P(n-2)
1
P(n-2)
P(n-2)
1
P(n-2)
2
3
P(n-3)
1
P(n-3)
P(n-3)
1
P(n-3)
P(n-3)
1
P(n-3)
P(n-3)
1
P(n-3)
4
19
Złożoność algorytmu: Wieże Hanoi (3)
• P(n) = P1 + P2 + P3 + ... + Pn = 2n – 1
• W powyższym wzorze zastosowany został wzór na sumę n pierwszych elementów ciągu geometrycznego (o elementach b , b , ..., bn i ilorazie q)
1
2
• S = b * (qn – 1) / (q – 1)
n
1
20
10
2008-10-14
Inwersja elementów w wektorze (1)
public class Rekurencja07 {
static void wyswietlWektor(int [] w) {
for(int i = 0; i < w.length; i++)
System.out.print(w[i] + " ");
System.out.println();
}
21
Inwersja elementów w wektorze (2)
static void inwersja(int poczatek, int koniec, int [] w)
{
if (poczatek < koniec) {
int pomoc = w[poczatek];
w[poczatek] = w[koniec];
w[koniec] = pomoc;
inwersja(poczatek+1,koniec-1,w);
}
}
22
11
2008-10-14
Inwersja elementów w wektorze (3)
public static void main(String [] args)
{
int [] tab = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; wyswietlWektor(tab);
inwersja(0,tab.length-1,tab);
wyswietlWektor(tab);
}
}
Efekt działania programu:
1 2 3 4 5 6 7 8 9 10 11
11 10 9 8 7 6 5 4 3 2 1
23
Sortowanie szybkie (1)
• Hoare, 1960
void quickSort(int tab[], int first, int last)
• wybierz jedną z wartości znajdujących się w wektorze (w poniższym algorytmie wybierana jest wartość znajdująca się na pozycji o numerze first)
• dokonaj przemieszczenia elementów w wektorze, tak aby uzyskać:
elementy < x | x | elementy >= x
• za pomocą tej samej procedury uporządkuj część wektora znajdującą się na lewo od wartości „x” oraz część znajdującą się na prawo od wartości „x”.
• średnia złożoność obliczeniowa: O(n * log(n))
• pesymistyczna złożoność obliczeniowa O(n2) 24
12
2008-10-14
Sortowanie szybkie (2)
public class QuickSort
{
public static void swap (int tab[], int x, int y) {
int temp = tab[x];
tab[x] = tab[y];
tab[y] = temp;
}
25
Sortowanie szybkie (3)
public static int partition(int tab[], int first, int last) {
int pivot = tab[first];
int up = first;
int down = last;
do {
while ((up < last) && (pivot >= tab[up])) up++; while (pivot < tab[down]) down--;
if (up < down) swap(tab,up,down);
} while (up < down);
swap(tab,first,down);
return down;
}
26
13
2008-10-14
Sortowanie szybkie (4)
public static void quickSort(int tab[], int first, int last) {
if (first >= last) return;
int pivot = partition(tab, first, last);
quickSort(tab, first, pivot-1);
quickSort(tab, pivot+1, last);
}
27
Sortowanie szybkie (5)
public static void main(String argv[]) {
int n = 10;
int tab[] = new int[n];
for (int i=0 ; i < n; i++)
tab[i] = (int) (100 * Math.random());
quickSort(tab, 0, n-1);
for (int i=0 ; i < n; i++)
System.out.print(tab[i] + " "); System.out.println();
}
}
28
14
2008-10-14
Sortowanie przez łączenie – Mergesort (1)
• sort(int poczatek, int koniec, int [] w),
• podziel wektory na dwie połowy,
• posortuj każdą z nich (za pomocą tej samej metody, o ile ich długość > 1),
• połącz posortowane części w całość,
• złożoność obliczeniowa: O(n * log(n)).
29
Sortowanie przez łączenie – Mergesort (2) public class MergeSort
{
static void wyswietlWektor(int [] w)
{
for(int i = 0; i < w.length; i++)
System.out.print(w[i] + " ");
System.out.println();
}
30
15
2008-10-14
Sortowanie przez łączenie – Mergesort (3) static void sort(int poczatek, int koniec, int [] w)
{
if (poczatek >= koniec)
return;
int srodek = (poczatek + koniec) / 2;
sort(poczatek, srodek, w);
sort(srodek+1, koniec, w);
scal(poczatek, srodek, koniec, w);
}
31
Sortowanie przez łączenie – Mergesort (3) static void scal(int poczatek, int srodek, int koniec, int [] w) {
int pocz1 = poczatek;
int kon1 = srodek;
int pocz2 = srodek + 1;
int kon2 = koniec;
while ((pocz1 <= kon1) && (pocz2 <= kon2))
{
if (w[pocz1] < w[pocz2]) pocz1++;
else {
int pomoc = w[pocz2];
for (int i = pocz2 - 1; i >= pocz1; i--) w[i+1] = w[i];
w[pocz1] = pomoc;
pocz1++;
kon1++;
pocz2++;
}
}
}
32
16
2008-10-14
Sortowanie przez łączenie – Mergesort (4) public static void main(String [] args)
{
int [] tab = {1, 5, 3, 7, 7, 9, 2, 3, 2, 2, 3}; wyswietlWektor(tab);
sort(0,tab.length-1,tab);
wyswietlWektor(tab);
}
}
Wynik działania programu
1 5 3 7 7 9 2 3 2 2 3
1 2 2 2 3 3 3 5 7 7 9
33
17