Kopia DSC00540

Kierunek: informatyko, studia stacjonarne I stopnia

Wstęp do algorytm izacji, sem.ll    __    .    ■■

4j Rozwiązać równanie rekurencyjne:

(a)    a, = 23b.i ⁺3a*^ z warunkami początkowymi Bo = 1, aj = 1;

(b)    a. “ a», +2a^ z warunkami początkowymi ao = 2, a, = 2

5. Dany jest algorytm dzielenia:

/*Dane: liczby całkowita    i n>0>

Wyniki: liczby całkowi te q i r takie, ta q*» + * ■ a oraz 0 £ r < n) */

<

q - 0 r - »

/» q*n ł x ■ a oraz r2G */ whila (r 2 a) {

« ■ « t ■ r - n >

}

Pokaż, że stwierdzenie q*n + r = m oraz rH) jest niezmiennikiem pętli.

14-06-07 15.Z4

Skorzystaj z twierdzenia o rekurcncji uniwersalnej i podaj dokładne asymptotyczne oszacowanie dla następujących rekurencji;

(a) T(n) - 4T(n/2) + n;

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

Zapisz przedstawiony w postaci schematu blokowego algorytm w odpowiadającej mu postaci pscudokodu, (I) z wykorzystaniem iteracji ograniczonej, (2) z wykorzystaniem iteracji nieograniczonej. Czy jest to możliwe w obu przypadkach? Odpowiedź uzasadnij. Co realizuje algorytm? Podaj jego złożoność asymptotyczną O(-).

8. Podaj przykład zbioru nominałów monet fikcyjnej waluty prime, dla której zachłanny algorytm wydawania reszty nie zawsze wydaje resztę w postaci najmniejszej liczby monet.