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?