ASD e 02 2005 1

Egzamin ASD

Studia dzienne, 7go lutego 2005

Nazwisko............................................. Nr studenta............Nr grupy.........

Zadanie l(lOpunktów) Wyobraźmy sobie "nieskończona" strukturę danych S przechowująca liczby całkowite. Jest ona wyposażona w operację get(i), gdzie i może być dowolnie dużą liczbą naturalną; operacja S.get(i) zwraca liczbę całkowitą przechowywaną w strukturze S "pod indeksem" i, przy czym:

1)    pod każdym indeksem znajduje się dokładnie jedna liczba całkowita.

2)    przechowywane liczby są posortowane rosnąco, tzn. jeśli i < j, to S.get(i)<S.get(j),

3)    pierwsza liczba w strukturze (tzn. S.get(O)) jest ujemna.

4)    operacja S.get(i) ma koszt 0(1) dla dowolnego naturalnego i.

Opis zadania: Przy powyższych założeniach opracuj algorytm find(), możliwie najszybszy(asymptotycznie), który odnajduje najniższy indeks w strukturze S, pod którym znajduje się liczba dodatnia (tzn. minimalne i, takie że get(i)>0). Jedynym środkiem do sprawdzania zawartości pod indeksem i jest operacja S.get(i).

Polecenia:

(a)    Podaj możliwie krótki opis algorytmu find().

(b)    Napisz pseudokod algorytmu find().

(c)    Oszacuj złożoność czasową algorytmu, przy czym dokładnie opisz składniki złożoności, jeśli algorytm składa się z kilku faz. Nie zapomnij precyzyjnie określić co stanowi argument funkcji złożoności (czyli co jest parametrem, od którego zależy złożoność)

Przykład:

S: get(O) = -3, get(l ) = -1, get(2) = 0, get(3) = 3, get(4) = 10,... algorytm S.find(), powinien zwrócić liczbę 3.