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ą an. Oszacuj koszt czasowy i głębokość rekursji.
1
n = 0
an = ( a 2 n
) / 2
n parzyste
2 n / 2
a * ( a )
n nieparzyste
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:
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
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.
Czy potrafisz znaleźć funkcję, której wartością dla danego n jest liczba poziomów drzewa wywołań rekurencyjnych sortowania przez scalenie ciągu n-elementowego?