1. Klasówka 2000/01#
Zadanie 1#
Zaproponuj algorytm, który w miejscu i w czasie \(O(n \log(k + 1))\) wyznaczy liczbę \(k\), różnych elementów w tablicy \(a\)?
Wskazówka: Rozważ dwa przypadki:
\(k \leq n^{\frac{1}{2}}\)
\(k > n^{\frac{1}{2}}\)
Załóżmy, że elementy w \(a\) należą do zbioru \(\{1, 2, \cdots, k\}\), gdzie \(1 \leq k \leq n\). Zaprojektuj algorytm, który posortuje \(a\) w miejscu i w czasie \(O(n \log (k + 1))\)
Zaprojektuj algorytm, który w miejscu i w czasie \(O(n \log (k + 1))\) posortuje tablicę \(a\), gdzie \(k\) jest liczbą różnych elementów w \(a\).
Wskazówka: skorzystaj z poprzednich punktów.
Zadanie 2#
Reprezentacją Fibonacciego liczby całkowitej \(n > 0\) nazywamy ciąg zero-jedynkowy \(a_1\), \(a_2\), \(\cdots\), \(a_k\) taki, że:
\(n = \sum\limits_{i=1}^k a_i * F_i\) gdzie \(F_i\) jest \(i\)-tą liczbą Fibonacciego (tutaj przyjmujemy, że \(F_1=1\), \(F_2=2\));
\(a_k = 1\);
w ciągu \((a_i)\) nie ma dwóch kolejnych jedynek.
Licznikiem Fibonacciego nazywamy tablicę \(LF[1..\inf]\) zainicjowaną zerami, której kolejne elementy (do ostatniej jedynki włącznie) są reprezentacją Fibonacciego pewnej liczby naturalnej. Zaprojektuj operacje dodawania 1 do licznika \(LF\). Zbadaj jej koszt pesymistyczny i zamortyzowany. Za jednostkę kosztu przyjmijmy koszt zmiany \(1\) bitu na przeciwny. Przeprowadź analizę kosztu zamortyzowanego metodami:
księgowania;
potencjału;
Zadanie 3#
Jaki jest czas działania \(QuickSortu\) dla ciągu składającego się z \(k\) zer i \((n - k)\) jedynek \((0 \leq k \leq n)\)? (Bierzemy pod uwagę wersję procedury podziału omawianą na wykładzie.). Odpowiedź uzasadnij.