kolejki dwumianowe, kopce Fibonacciego
Ćwiczenia 7: kolejki priorytetowe, koszt zamortyzowany - część 2
pon., 11/15/2010 - 15:27 — diksZadanie 1 (symulacja kolejki dwoma stosami)
Opracuj sposób implementacji kolejki typu FIFO z pomocą dwóch stosów w taki sposób, żeby zamortyzowany koszt operacji stosowych był stały. Dokonaj analizy kosztu metodami księgowania i funkcji potencjału.
Zadanie 2 (stos w tablicy dynamicznej)
Reprezentujemy stos w dynamicznej tablicy \(S[1..n]\), gdzie \(n = 2^m\), dla pewnego całkowitego \(m \ge 0 \). Poszczególne operacje implementujemy następująco:
