7. Kolokwium - [2000]

200-06-07, 12:00

Sprawdzian z Analizy Algorytmów Grupa B Zadanie 1 Kolejką nazywamy struktur; danych przechowującą zmienną liczbę elementów z dwiema metodami dostępu: „wstaw element do kolejki” (PLT) i „pobierz element z kolejki"" (GET). Element najdawniej wstawiony do kolejki jest jako pierwszy zdejmowany (FIFO, first-m, first-out). Stos różni się kolejki tym, że zawsze pobierany jest element „najnowszy", tzn. ostatnio odłożony na nos (LIFO, last-in, first-out). Załóżmy, że dana jest implementacja kolejki (np. klasa) z operacjom PUT i GET, każda realizowana w jednostkowym czasie dla jednego elementu. W jaki sposób można zaimplementować stos LIFO korzystając z dwóch kolejek ? Przedstawić propozycje procedur „odlóż_na_stos(element)” i „pobierz_ze_stosu(element) tna „wysokim poziomic abstrakcji”. Jaka jest złożoność odłożenia na taki stos ciągu n elementów, a następnie pobrania z niej wszystkich n elementów? Jako dominujące przyjąć wywołania metod PUT i GET. Zadanie 2 Poniższa procedura rysuje pewną figurę korzystając z biblioteki graficznej udostępniającej funkcje Forwd, TurnLeft i TurnRigh. Wyznaczyć liczbę wywołań tych funkcji w zależności od parametru n. procedure rysuj (n: integer); begin if n-1 then Forwd(l) else rysuj(n-1) ; TurnLeft(60) rysuj(n-1) ; TurnRight(120); rysuj(n-1) ; TurnLeft.(60) ; rysuj(n-1) endif; end;

Zadanie 3 Rozwiązać równanie rekurencyjne, tzn. Wyznaczyć T(n) jako funkcję n:

,n = 0 3 T(n)=  n 4T (n − 1) + 2 , n > 0