1
Algorytmy i struktury danych
wykład 2
Algorytmy rekurencyjne
1
Algorytmy i struktury danych
wykład 2
Algorytmy rekurencyjne
2/41
Definicja i cechy algorytmu
rekurencyjnego
algorytm, który odwołuje się do samego siebie
(funkcja/procedura wywołuje siebie w czasie
wykonywania)
duży problem zostaje rozłożony na tzw. problem
elementarny (który umiemy rozwiązać) i problem o
mniejszym stopniu komplikacji niż problem wyjściowy
podejście rekurencyjne jest zgodne z podejściem
człowieka do rozwiązania wielu problemów
zakończenie algorytmu jest precyzyjnie określone
3/41
Definicja algorytmu
rekurencyjnego
start
procedura rekurencyjna
warunek
jeżeli tak → instrukcje
jeżeli nie → procedura rekurencyjna
koniec procedury
wywołanie procedury rekurencyjnej
koniec
4/41
Przykład klasyczny czyli silnia
zadanie → obliczenie wartości n!
definicja matematyczna silni →
0! = 1
n! = n
∙
(n-1)!
n jest liczbą naturalną, n ≥ 1
5/41
Funkcja obliczająca wyrażenie n!
– algorytmy iteracyjne
int n;
cout<<„podaj n: ”;
cin>>n;
int silnia=1;
for(int i=1;i<=n;i++)
{
silnia=silnia*i;
}
cout<<"\n" <<n <<"!="
<<silnia<<endl;
int silnia=1;
int i=1;
while(i<=n)
{
silnia=silnia*i;
i++;
}
cout<<"\n" <<n <<"!="
<<silnia<<endl;
6/41
Analiza funkcji silnia –
algorytm rekurencyjny
problem zostaje rozłożony na dwa: elementarny (jeżeli
n=0) oraz (jeżeli n>0) problem podobny jak wyjściowy,
ale o mniejszym stopniu trudności → (n-1)! zamiast n!
koniec algorytmu następuje, gdy funkcja zagłębi się w
sobie tyle razy, że w końcu obliczy wartość elementarną
silnia
wyniki cząstkowe nie mogą zostać obliczone w chwili
wywołania kolejnego egzemplarza
w każdym kroku funkcja czeka na wynik następnego kroku
i obliczenie wartości jest wstrzymywane
7/41
Analiza funkcji silnia dla n=4
n=0 ? → nie
oblicz
4*3!
n=0 ? → nie
3*2!
n=0 ? → nie
2*1!
n=0 ? → nie
1*0!
n=0 ? → tak
1
8/41
Funkcja obliczająca wyrażenie n! –
algorytm rekurencyjny
int fun_silnia(int n)
{
int silnia;
if(n==0) silnia=1;
else silnia=n*fun_silnia(n-1);
return silnia;
}
main()
{
int n;
cout<<"podaj n: "; cin>>n;
cout<<"\n" <<n <<"! = " <<fun_silnia(n);
return 0;
}
wewnętrzne
wywołanie funkcji
silnia
koniec funkcji silnia
9/41
Obliczenie wyrażenia 4!
10/41
Obciążenie pamięci
4*3!
4*3!
4*3!
4*3!
4*3!
4*3!
4*3!
3*2!
3*2!
3*2!
3*2!
3*2!
2*1!
2*1!
2*1!
1*0!
Algorytmy rekurencyjne określa się często mianem „pamięciożernych”,
ponieważ poszczególne obliczenia cząstkowe są wstrzymywane aż do
obliczenia tzw. zadania elementarnego. Dopiero wówczas realizowane
są poszczególne, wstrzymane wcześniej, zadania cząstkowe i
zwalniana jest zarezerwowana pamięć.
11/41
Ciąg Fibonacciego - definicja
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) dla n ≥ 2
Pierwsze wyrazy: 0, 1, 1, 2, 3, 5, 8, 13
12/41
Schemat obliczania wyrazów
ciągu Fibonacciego
fib(4)
fib(3)
fib(2)
fib(2)
fib(1)
fib(1)
fib(0)
fib(1)
fib(0)
fib(1)
fib(2)
→ obliczenia powtarzane
→ operacje elementarne
13/41
Ciąg Fibonacciego - program
int fibonacci(int n)
{
int fib;
if(n==0) fib=0;
else if (n==1) fib=1;
else fib=fibonacci(n-1)+fibonacci(n-2);
return fib;
}
main()
{
int n;
cout<<"podaj n: "; cin>>n;
cout<<"\nfib("<<n<<") = " <<fibonacci(n);
return 0;
}
14/41
Schemat obliczania wyrazów
ciągu Fibonacciego
pewne części obliczeń powtarzają się wielokrotnie
program „nie zauważa”, że pewne operacje
obliczenia już wykonywał i nie korzysta z ich
wyników
optymalne wykorzystanie algorytmu →
programowanie dynamiczne, utworzenie
specjalnych tablic, przechowujących wyniki
pośrednie, które można w każdej chwili
wykorzystać
15/41
Cechy algorytmu
wyszukiwania
określone zakończenie algorytmu →
indeks left>right, lub element zostanie
wyszukany
duży problem rozłożony na sumę
problemu elementarnego oraz problemu
podobnego ale o niższym stopniu
trudności
16/41
Algorytm wyszukiwania
int tab1[8];
void szukaj(int t[]; int left, int right, int );
{
if (left>right) cout<<„nic nie wyszukano”;
else
if (tab[left]==wart)
cout<<„wartosc=”<<wart<<„ na pozycji: ”<<left;
else szukaj(tab, left+1, right, wartosc);
}
main()
{
for(int i=0;i<8;i++)
{ tab1[i]=i*10+10; cout<<tab1[i]; }
wartosc=50; szukaj(tab1,0,7,wartosc);
}
17/41
Błędy popełniane przy używaniu
algorytmów rekurencyjnych
niewłaściwie sformułowany warunek
końca
niepoprawne rozłożenie problemu
18/41
Przyczyny zawieszania się
programów
nielegalne użycie zasobów
pętla nieskończona
brak pamięci
nieprawidłowe lub nieprecyzyjne
określenie warunków zatrzymania
algorytmu
błąd w algorytmie powodujący zbyt
wolną pracę algorytmu
19/41
Niekorzystne cechy algorytmów
rekurencyjnych
brak możliwości obliczenia liczby
zagłębień w siebie algorytmu → brak
możliwości przewidywania czasu pracy
algorytmu
możliwość skonstruowania algorytmu o
nieskończonej liczbie wywołań
20/41
Przykład algorytmu o
nieskończonej liczbie operacji
int sprawdz(int liczba)
{
if(liczba==1) return 1;
else
{
if(liczba % 2)==0
return liczba*sprawdz(liczba-2);
else return liczba*sprawdz(liczba-1);
}
}
main()
{
sprawdz(6);...
}
operacja „liczba % 2” sprawia, że program
nigdy nie osiągnie wartości 1, która kończy
jego działanie!
21/41
Program dobry, wykonania
brak
int policz(int n1, int n2)
{
if (n1==0) return 1;
else
return policz(n1-1,policz(n1-n2,n2))
}
main()
{
policz(1,0);
...
}
parametry funkcji rekurencyjnej obliczane s
ą
jako pierwsze, potem wywo
ływana jest
funkcja, program próbuje obliczy
ć n2
(niepotrzebnie) i si
ę zapętla!
(
źródło – P. Wróblewski)
22/41
Kiedy należy unikać rekurencji?
jeżeli można algorytm rekurencyjny
zastąpić iteracyjnym
jeżeli algorytm może dawać
niepoprawne wyniki dla pewnych
zmiennych
23/41
Przykłady zastosowania
algorytmów rekurencyjnych
sortowanie (quicksort)
wyznaczanie pozycji wartości w tablicy
grafika
problem trwałego małżeństwa
(optymalizacja)
wieże Hanoi
24/41
Problem wież Hanoi - opis
„wieża” składa się z n krążków, o malejących
średnicach, ułożonych jeden na drugim na słupku, przy
czym krążek z największą średnicą jest na dole
należy przełożyć krążki z jednego słupka (źródłowego,
S1) na drugi słupek (docelowy, S2), wykorzystując
tylko jeden słupek pomocniczy (Sp) oraz nie
dopuszczając do sytuacji, aby na krążek o mniejszej
średnicy został nałożony krążek o większej średnicy
25/41
Problem wież Hanoi - schemat
S1
S2
Sp
S1
S2
Sp
26/41
Problem wież Hanoi – przykład
dla n=3
1
2
3
4
5
7
6
8
S1
S2
Sp
27/41
Problem wież Hanoi – analiza
jeżeli dany jest jeden krążek, to zadanie polega na
przeniesieniu go ze słupka S1 na słupek docelowy
S2 (zadanie elementarne)
jeżeli danych jest n≥2 krążków to zadanie
rozkładamy na zadania cząstkowe przeniesienia n-
1 krążków
przenosimy zgodnie z zasadami n-1 krążków w S1 na Sp
przenosimy jeden krążek z S1 na S2
przenosimy zgodnie z zasadami n-1 krążków z Sp na S2
liczba operacji przenosin krążków: 2
n
-1
28/41
Problem wież Hanoi – program
void hanoi(int n, int a, int b, int c)
{
if(n==1) cout<<"\nprzesu
ń krążek1 z "<<a<<" na "<<b;
else
{
hanoi(n-1,a,0,b);
cout<<"\nprzesu
ń krążek"<<n<<" z "<<a<<" na "<<b;
hanoi(n-1,3-a-b,b,a);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"1-p. pocz
ątkowy, 2-p. docelowy, 0-p. dodatkowy";
cout<<"ile kr
ążków przenie
ść? "; int ile_kr; cin>>ile_kr;
hanoi(ile_kr,1,2,0);
return 0;
}
29/41
Algorytmy z powrotami
zadania rozwiązywane są metodą „prób i
błędów”
zadania dzielone są na podzadania
rozwiązanie problemu realizowane jest
na drodze stopniowego rozbudowywania
i przeglądania drzewa podzadań
30/41
Przykłady zastosowań algorytmów
rekurencyjnych z powrotami
ruchy skoczka na szachownicy
problem 8 nieszachujących się hetmanów
szukanie drogi wyjścia z labiryntu
31/41
Problem 8 hetmanów
zadanie: ustawienie na
szachownicy 8 hetmanów
w ten sposób, aby żaden
z nich nie szachował
innego
H
H
H
H
H
H
H
H
32/41
Problem 8 hetmanów –
założenia do programu
hetman szachuje figury będące w tej samej kolumnie,
wierszu oraz na dwóch przekątnych (reguły gry)
każda kolumna może zawierać tylko jednego hetmana
problem sprowadza się do wyznaczenia pozycji j z
zakresu 0..7 dla i-tego hetmana (w i-tej kolumnie)
w miejsce naturalnej reprezentacji szachownicy w
postaci macierzy kwadratowej wprowadza się 4 tablice
określające:
pozycję hetmana w i-tej kolumnie: int k[8]
brak hetmana w j-tym wierszu: bool w[8]
brak hetmana na k-tej przekątnej o kier. ld->pg: bool p1[15]
brak hetmana na k-tej przekątnej o kier. lg->pd: bool p2[15]
33/41
Problem 8 hetmanów –
reprezentacja operacji
ustawienie hetmana:
k[i]=j; w[j]=false;
p1[i+j]=false;
p2[i-j+7]=false;
pozycja dopuszczalna:
w[j]=true;
p1[i+j]=true;
p2[i-j+7]=true;
usuwanie hetmana:
w[j]=true;
p1[i+j]=true;
p2[i-j+7]=true;
H
p1[0] p1[1]
p1[8]
p1[14]
p2[0]
p2[1]
p2[5]
p2[14]
i
j
34/41
Problem 8 hetmanów –
rozwiązania
istnieją 92 rozwiązania
12 spośród nich jest różnych, reszta
wynika z symetrii szachownicy
35/41
Problem 8 hetmanów -
algorytm
void ustaw(int i)
{
for(int j=0;j<8;j++)
if(w[j]==true && p1[i+j]==true && p2[i-j+7]==true)
{
k[i]=j;
w[j]=false; p1[i+j]=false; p2[i-j+7]=false;
if(i<7) ustaw(i+1);
else wypisz();
w[j]=true; p1[i+j]=true; p2[i-j+7]=true;
}
}
main()
{
ustaw(0); ...
}
36/41
Problem skoczka szachowego
- opis
należy odwiedzić wszystkie pola
kwadratowej planszy o zadanym
wymiarze
poruszamy się ruchem konika
szachowego
założenie: każde pole odwiedzamy tylko
raz
37/41
Problem skoczka szachowego
- algorytm
zadanie odwiedzenia wszystkich pól
można podzielić na dwa problemy:
wykonania kolejnego ruchu
lub wykazanie, że kolejny ruch nie jest
możliwy do wykonania
38/41
Problem skoczka szachowego
– przykład rozwiązania
5
16
23
10
3
22
11
4
15
24
17
6
19
2
9
12
21
8
25
14
7
18
13
20
1
39/41
Problem skoczka szachowego
– reprezentacja programowa
plansza jest reprezentowana przez tablicę
kwadratową:
int plansza[n][n];
pole jeszcze nie odwiedzone:
plansza[x][y] = 0;
pole już odwiedzone w i-tym ruchu:
plansza[x][y] = i;
liczba ruchów:
1
≤ i ≤ n
2
40/41
Problem skoczka szachowego
- procedura
procedure próba_następnego_ruchu;
pozycja_początkowa
repeat następny_możliwy_ruch_z_listy_ruchów
if dozwolony then zapisz_ruch
if są_jeszcze_wolne_pola then
próba_następnego_ruchu
if nieudany then
skasuj ostatni_ruch
until ruch_udany lub nie_ma_następnego_możliwego
41
Dziękuję za uwagę