51586 IMG�62

Kierunek: informatyka, studia dzienne magisterskie Algoiylmy i simki wy lUmych, nem. 11_

A

Algorytmy i struktury danych

—.__

Imię i nazwisko

2.    Skorzystaj z metody rekurencji uniwersalnej i podaj dokładne asymptotyczne oszacowanie dla następu jących rek urcncj i;

(a)    T(n) ~ 4T(n/2) + n

(b)    T(n) “ 4T(n/2) + n²

(c)    T(n) ~ 4T(n/2) + feP

3.    Opisz zadanie realizowane przez funkcje f2 i co otrzymamy w wyniku jej wykonania ? Określ klasę złożoności funkcji (algorytmu) 12.

m (L + R) div 2; if tab Im] ■ x then £2 ; as m else begin

if x < tab[m] then

f2 : = £2 (tab, x, L, m-1) else

f2 : ss f2(tab, x, m+1, R) ;

end;

prgram Tj

const tab: array(0..9] o£ integer ■

(1,2,3,4,5,6,7,8,9,10)-;

var m, n: Integer;

function f2(tab: array of integer; x, L,

R; integer): integer;

var

end;

end;

begin X : = 7;

x :s f2(tab, x, 0, 9); end.

xn: integer; begin

if Ł i R then

if tab[L] = x then f2 : = L else

f2 ;= -1

else

begin

4. Dla poniższego ważonego grafu nicskicrowancgo wyznaczyć minimalne drzewo rozpinające (MST) posługując się algorytmem Kruskala.

5.    Załóżmy, żc wraz z partnerem grasz w zgadywanie liczby naturalnej z przedziału [1,2048]. Partner wybiera dowolna liczbę z tego przedziału, a Ty próbujesz ją zgadnąć. Partner może jedynie odpowiadać: tak, za mała, raduża. Jaką przyjmiesz strategię odgadywania liczby, by ją znaleźć w możliwie najmniejszej liczbie prób? Ile tych prób musisz wykonać, jeśli Partner wybrał liczbę 117?.

6.    Dana jest następująca funkcja rekurencyjna:

function GCD (i, j: integer) : integer;

{ Funkcja zwraca największy wspólny dzielnik itwóch licz całkowitych i oraz jf begin

if i mad j - 0 then GCD ;=j else

GCD /= GCD (j, i modj); end; { GCD }

Pokaż, jak wygląda drzewo wywołań funkcji GCD, gdy wywołamy ją następująco: GCD (21. V)