Studia Licencjackie / InŜynierskie
Algorytmy i struktury danych
Lista zadań nr 3
1.
W oparciu o następującą zaleŜność napisz funkcję rekurencyjną wyznaczającą a
n
. Oszacuj
koszt czasowy i głębokość rekursji.
e
nieparzyst
n
parzyste
n
n
a
a
a
a
n
n
n
0
)
(
*
)
(
1
2
/
2
2
/
2
=
=
Uwaga: głębokość rekursji to największa liczba jednocześnie uruchomionych instancji
funkcji (inaczej, długość najdłuŜszej ścieŜki w drzewie wywołań rekurencyjnych).
2.
Przedstaw drzewo wywołań rekurencyjnej funkcji rekurencyjnej
newton
dla
argumentów n=6 i m=3. Odpowiedz na pytanie: ile razy podczas obliczania
newton(10,5)
zostanie wywołana funkcja
newton
dla n równego m lub m równego
zero (chodzi o łączną liczbę takich wywołań).
3.
Napisz funkcję
fibonacci(k,l)
, która jako wartość zwraca najmniejszą wartość p
taką, Ŝe p-ta liczba Fibonacciego przy dzieleniu przez k daje resztę l.
Uwaga: zadbaj o to, Ŝeby funkcja zwracała poprawny wynik nawet wówczas, gdy p-ta
liczba Fibonacciego przekracza zakres liczb całkowitych reprezentowanych przez
całkowitoliczbowe typy danych dostępne w kompilatorach.
4.
RozwaŜmy następujący algorytm wyznaczania najmniejszej liczby w ciągu n-
elementowym: Jeśli n=1 to minimum jest równe jedynemu elementowi ciągu.
W przeciwnym razie dzielimy ciąg na dwa ciągi (prawie) równej długości, wyznaczamy
minima tych dwóch ciągów m
1
i m
2
a następnie wybieramy mniejszą z liczb m
1
, m
2
.
Napisz funkcję rekurencyjną realizującą ten algorytm. Jaki jest czas działania Twojej
funkcji, porównaj go z czasem działania metody iteracyjnej.
5.
Niech funkcja T określona na liczbach naturalnych będzie zadana następującym wzorem:
a.
Napisz rekurencyjną funkcję fTrec(int n, int m) obliczającą wartość funkcji T dla
argumentów n i m. Narysuj drzewo wywołań dla fTrec(2,3) i podaj wartość
T(2,3).
b.
Napisz nierekurencyjną funkcję fTiter(int n, int m) obliczającą wartość funkcji T
dla argumentów n i m, działającą w czasie proporcjonalnym do n
⋅
m.
c.
Napisz nierekurencyjną funkcję fTiter(int n, int m) obliczającą wartość funkcji T
dla argumentów n i m, działającą w czasie proporcjonalnym do n
⋅
m i
wykorzystującą pamięć o rozmiarze proporcjonalnym do n.
6.
Sortujemy przez scalanie ciąg złoŜony z 10 elementów. Przedstaw:
a.
drzewo wywołań rekurencyjnych,
b.
parametry wywołań funkcji scalającej.
7.
Sortujemy przez scalanie ciągi złoŜone z 10, 100, 1000, 10 000 elementów. Dla kaŜdej z
tych wartości ustal, ile poziomów mieć będzie drzewo wywołań rekurencyjnych.
T(n,0) = n dla n
≥
0
T(0,m) = n dla m
≥
0
T(n,m)= T(n-1,m)+T(n,m-1) dla n>0 i
