aa (4)

aa (4)



1 (pki. 3) Sformułować algorytm przekształcający podaną z klawiatury liczbę naturalna (wprowadzaną jako ciąg cyfr dziesiętnych, począwszy od najbardziej znaczącej) na odpowiadającą jej postać binarna i wyprowadzający uzyskany wynik na ekran monitora (w kolejności od najbardziej do najmniej znaczącego bitu). Przyjąć, ze po ostatniej cyfrze dziesiętnej będzie naciskany klawisz „ENTKR". Oszacować złożoność asymptotyczną typu Ó(.) zarówno w stosunku Jo czasu wykonywania obliczeń, juk i niezbędnych do rozwiązania problemu zasobów pamięciowych. Rozmiar danych wejściowych scharakteryzowany jest przez wielkość liczby przekształcanej n (rozumianej jako wielkość ^'Hstrakcyjra, niezależna od sposobu jej prezentacji).

2. (pki. 2) Na ry s. (a) pokazany jest graf z w agami, a na rysunkach (b) i (c) pokazane są dwa różne sposoby oznaczenia etykietami jego krawędzi za pomocą liter a. b.....n w kolejności rosnących wag.

(a)    Zastosuj algorytm Kruskala do grafu o krawędziach uporządkowanych tak jak na rys. (b). Narysuj otrzymane minimalne drzewo spinające i podaj jego wagę.

(b)    Powtórz zadanie (a), kiedy krawędzie są uporządkowane tak, jak na rysunku (c).




3. (pkt 2) Do rozwiązania pewnego zadania algorytmicznego zaproponowano cztery różne algorytmy należące do następujących klas złożoności:

f,(n) = Ofn^2) fr(n) - O In™) fi(n) = Odgjn^11)

, f«(n) = 0(2")

•'i. (pkt. 2) Stosując metodę pierwiastków charakterystycznych rozwiązać równanie rekurcncyjnc:

= -at*., +J.2ar.-?/    *■. = 10, ac = 1

5. (pkt. 3) Załóż, żc dla dyskretnego problemu plecakowego przyjęto następujące dane: n = 5 (liczba elementów do upakowania), W - 9 (maksymalny udźwig plecaka), elementy (waga. wartość): (23). (3,4). (4.5), (5,6), (6, 7).


Wyszukiwarka

Podobne podstrony:
82a08493da4755degen I (pkt. 3) Sformułować algorytm przekształcający podaną z klawiatury liczbę natu
egzamin2009 1 * . . L (pkt. 3) Sformułować algorytm przekształcający podaną z klawiatury liczbę natu
str2W13/14 W celu obliczenia wyniku należy sformułować algorytm numeryczny (metodę) polegająca na
KlAiR_Ul 1 Potrafi sformułować algorytm. posłużyć się językami Matlab i Simulink do opracowania
K_U14 potrafi sformułować algorytm, posługuje się wybranymi językami programowania oraz odpowiednimi
DSC00944 3 Nr indeksu; Teoretyczne podstawy informatyki - egzamin Nazwisko i imię: Zadanie l._ Przek
Zadanie 2. Analiza algorytmu Przeanalizuj podaną funkcję pisz.Specyfikacja: Dane: s - napis n - licz
algorytmu przekształceń. Niektóre tematy ilustrowane są kolorowymi animacjami, które zdecydowanie
img087 7.1. Podstawowe sformułowanie metody funkcji potencjalnych 87 Rys. 7.2. Funkcja przynależnośc
IMG70 L Napisz program realizujący: l .Wczytanie z klawiatury "w*k" liczb (typu Inte
IMG74 pjO VL Napisz program realizujący: 1 .Wczytanie z klawiatury "w*k" liczb (typu Inte
IMG77 V. Napisz program realizujący: 1 .Wczytanie z klawiatury "w*k" liczb (typu Integer)
IMG78 XI. Napisz program realizujący: 1. Wczytanie z klawiatury "w*k" liczb (typu Re

więcej podobnych podstron