przykladowy egzam3

A

Algorytmy i struktury danvch

Imię i nazwisko    Przedmiot Rok Grupa

/

/

/■

Dane jest jednorodne, liniowe równanie rckurcncyjne: a* = ^_an-i -'■12a_n_j, 3i ” 10. a₀ - 1

Znajdź rozwiązanie tego równania.

Przypomnij sobie „ręczny” algorytm przekształcania liczby dziesiętnej na odpowiadającajej postać binarną Korzystając z dowolnego graficznego sposobu opisu algoryrmów (jakie to są opisy - wymień jc) przedstaw algorytm przekształcający podaną z klawiatury liczbę naturalną na odpowiadającą jej postać binarną i wyprowadzający uzyskany wynik na ekran monitora. Oszacuj złożoność asymptotyczną typu 0(.) uzyskanego algorytmu.

Załóżmy, ze 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, za duża. Jaką przyjmiesz strategię odgadywania liczby, by ją znaleźć w możliwie najmniejszej liczbie prób⁷ He tych prób musisz wykonać, jeśli partner wybrał liczbę 117?

X- 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(.).

JL

s = 0

n = 0

czytaj: x

s = s +• x ' n = n ♦ 1 '

X

wy: s/n

J

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

6. Udowodnij, że

( (x > 0) a (y ■*--2) } _v

if (x>3)'

begin

x«—x - 3;    '<

Y«-y ⁺ 4; end else beęin

X4—x + 4; y«—2*y + 4; end

{ (x > 0) v. (y > 0) ) —