Kopia DSC00539

KJenmelc informatyka, studia stacjonarne l stopnia wstęp do algorytm izucji, sem. //

Rozwiązać równanie rekurcncyjne

(a)    a, " 2a».i *3^ z warunkami początkowymi a> - 1. ar - I;

(b)    a, “ ą,., -2a»_; z warunkami początkowy mi ao “ 2. a₍ = 2

5.

Dany jest algorytm dzielenia:

/'Dana: liczby calkomta a20 1 n>0) Wyniki: liczby całkowita q i r talua,

I

q • 0 r - *

że q*n + r

oraz 0 £ r < n) */

/• qt_n + r « ■ oraz riO */ wbiło (r 2 a) {

<ł ■ q

r « r - n

i

>

Pokaż, że stwierdzenie «/*n + r - m ar ar r^O jest niezmiennikiem pętli.

/6.'j Skorzystaj z twierdzenia o rekurencji 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 pseudokodu. (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ą 0(.).

S. 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.