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

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?