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

/• 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.

Wyszukiwarka

Podobne podstrony:
Kopia DSC00540 Kierunek: informatyko, studia stacjonarne I stopnia Wstęp do algorytm izacji, sem.ll
lista2 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I sto
lista 6 (2) ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I st
20855 lista 7 ALGORYTMY I STRUKTURY DANYCH - ćwiczenia II rok INFORMATYKA studia stacjonarne I stopn
dr inz. Jarosław Forenc 10/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inz. Jarosław Forenc 11/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inz. Jarosław Forenc 12/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inz. Jarosław Forenc 13/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inż. Jarosław Forenc 14/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inż. Jarosław Forenc 15/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inż. Jarosław Forenc 16/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki 2011/2012, Pracownia nr 1 dr i
dr inż. Jarosław Forenc 18/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inż. Jarosław Forenc 19/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki 2011/2012, Pracownia nr 1Da
dr inż. Jarosław Forenc 20/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki
dr inz. Jarosław Forenc 3/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki 2
dr inż. Jarosław Forenc 4/39 Technologia informacyjna, studia stacjonarne I stopnia Rok akademicki 2

więcej podobnych podstron