Metody -
algorytmy
rekurencyjn
e i
biblioteka
metod
Metody -
algorytmy
rekurencyjn
e i
biblioteka
metod
Przegląd zagadnień
Pojęcie rekurencji
Przykład - Wieże Hanoi
Nadużywanie rekurencji
Algorytmy z powrotami
Demo: utworzenie biblioteki funkcji
Podsumowanie
Pytania sprawdzające
Laboratorium
Pojęcie rekurencji
Zdolność metody (funkcji) do wywołania samej
siebie
Typy rekurencji
rekurencja bezpośrednia
rekurencja pośrednia
Metoda dziel i zwyciężaj
Metoda iteracyjna
Metoda rekurencyjna
static ulong Silnia(uint n){
ulong iloczyn = 1;
for(uint i=2;i<=n;i++)
iloczyn *= i;
return iloczyn;
}
static ulong Silnia(uint n){
if(n == 0 || n == 1)
return 1;
return n * Silnia(n-1);
}
Przykład - Wieże Hanoi
w każdym kroku można przenieść dokładnie jeden krążek
krążek nie może być nigdy nałożony na krążek o
mniejszej średnicy
Mamy trzy pręty i n krążków o różnych średnicach,
które są nanizane są na pierwszy pręt w porządku
malejących średnic tworząc wieżę. Chcemy przenieść
krążki z pierwszego pręta na drugi, przy pomocy pręta
trzeciego stosując następujące zasady:
static void Hanoi(uint n, string zrodlo,string cel, string tmp)
{
if (n == 1)
Console.WriteLine("Przeniś z prętu {0} na pręt {1}.",
zrodlo, cel);
else{
Hanoi(n - 1, zrodlo, tmp, cel);
Console.WriteLine("Przeniś z prętu {0} na pręt {1}.",
zrodlo, cel);
Hanoi(n - 1, tmp, cel, zrodlo);
}
}
Nadużywanie rekurencji
static ulong Fib(ushort n){
if(n<2)
return n;
return Fib(n-1)+Fib(n-2);
}
Unikajmy rekurencji, jeżeli istnieje
oczywiste rozwiązanie iteracyjne!!!
Ciąg Fibonacciego:
2
)
2
(
)
1
(
2
)
(
n
dla
n
Fib
n
Fib
n
dla
n
n
Fib
Fib(
5
)
Fib(
4
)
Fib(
3
)
Fib(
3
)
Fib(
2
)
Fib(
2
)
Fib(
1
)
Fib(
2
)
Fib(
1
)
Fib(
1
)
Fib(
0
)
Fib(
1
)
Fib(
0
)
Fib(
1
)
Fib(
0
)
1
1
0
1
0
1
Algorytmy z powrotami
Star
t
Metoda Sprawdz
we: krok - opis aktualnego
stanu
Wybierz następny, dopuszczalny, nieodwiedzony stan (ruch)
dostępny z bieżącej pozycji - krok, oznacz go jako krok2.
Oznacz stan krok2 jako odwiedzony
Czy osiągnięto
cel
Sprawdz(krok2);
N
Czy istnieje następny, dopuszczalny,
nieodwiedzony
stan dostępny z bieżącej pozycji
N
Stop
osiognietoCel=true;
T
osiognietoCel==
true
Oznacz stan krok2 jako nieodwiedzony
Stop
T
T
N
osignietoCel - pomocnicza
zmienne współdzielona
osiognietoCel=false;
Demo: utworzenie biblioteki
funkcji
Szablon projektu
Class Library
Korzystanie z bibliotki
w oknie Solution Explorer z menu
kontekstowego związanego z projektem
w którym chcemy skorzystać z biblioteki
wybrać Add Reference...
Podsumowanie
Pojęcie rekurencji
Przykład - Wieże Hanoi
Nadużywanie rekurencji
Algorytmy z powrotami
Demo: utworzenie biblioteki funkcji
Podsumowanie
Pytania sprawdzające
Laboratorium
Pytania sprawdzające
Co to jest rekurencja?
Na czym polega strategia "dziel i
rządź"?
Na czym polega programowanie
dynamiczne?
Laboratorium
Ćwiczenie 1:
Sortowanie szybkie - quick
sort
Ćwiczenie 2:
Problem ośmiu hetmanów