ASD k1 11 2005 4

Zadanie 4a Niech V będzie obustronnie nieskończonym wektorem liczb naturalnych, indeksowanym liczbami z zakresu od -oo, ...,-1,0, 1, oo. Zakładamy, że:

-V[0] = 0,

- istnieje dokładnie jedna liczba całkowita n taka, że V[n] mod 2 = 1 oraz dla każdej liczby naturalnej i różnej od n zachodzi V[i] mod 2 = 0.

Dodatkowo zdefiniowano „działającą w miejscu" funkcję

int SUM(int V[], int 1, int r),

która w czasie 0(1) wyznacza sumę kolejnych elementów wektora wejściowego V od elementu o indeksie 1 do elementu o indeksie r włącznie. Zaprojektuj możliwie efektywną funkcję

int FIND(int V[]>,

która wyznaczy indeks n wektora V taki, że V[n| mod 2=1.

Polecenia:

a)    Podaj krótki słowny opis rozwiązania.

b)    Podaj pseudokod funkcji FIND()-

c)    Oszacuj złożoność czasową i pamięciową rozwiązania. Przyjmij, że operacją dominującą jest ewaluacja (obliczenie wartości) funkcji SUM().

d)    Czy złożoność twojego rozwiązania zmieni się istotnie, gdy elementy wektora wejściowego V indeksowane liczbami od -oo, ..., -1 będą uporządkowane w kolejności nierosnącej oraz gdy elementy indeksowane liczbami od 1, ..., oo będą uporządkowane w kolejności niemalejącej? Odpowiedź uzasadnij.

Wyszukiwarka

Podobne podstrony:
ASD k1 11 2005 2 Zadanie 2a. Dany jest n elementowy ciąg a[l a[n]. Rozważmy następujący algorytm A:
ASD k1 11 2005 3 Zadanie 3a W pewnej firmie znajdują się 4 działy, w każdym z nich pracuje m pracow
ASD k1 11 2005 1 SPRAWDZIAN Nr 1 ASD IIrok18 listopad
6b (2) 11. 11. < h-V? Niech f będzie funkcją odwzorowującą zbiór liczb rzeczywistych R w R. f(.).
8b (2) 11.    Niech f będzie funkcją odwzorowującą zbiór liczb rzeczywistych R w R. f
6 (28) 101 Zadania MB. Niech/będzie dwukrotnie różniczkował na na %a, b},f(a) < 0 ,f(b) > 0 J
Zadanie 7Zadanie 7 Niech f (x, y) będzie w pewnym języku zdefiniowana jako { if y>0 then x + &quo
EgzMAD2002popr? 11. Niech f będzie funkcją odwzorowującą zbiór liczb rzeczywistych R w R, f(x) = x +
EgzMAD2002popr? 11. Niech f będzie funkcją odwzorowującą zbiór liczb rzeczywistych R w R, f(x) - x -
8 (17) 143 Zadania 14. Niech/ będzie ciągłą funkcją rzeczywistą określoną na R mającą własności: 0

więcej podobnych podstron