ASD Ćwiczenia 2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Udowodnij, że algorytm Sklejanie-Par jest poprawny. Co by było, gdybyśmy w jednym kroku sklejali co najwyżej k elementów? (Kosztem pojedynczego sklejenia jest w dalszym ciągu suma wag).

Rozwiązanie

Zadanie 2

Opisz algorytm znajdowania fałszywej monety wynikający z rekurencyjnego wzoru .

Rozwiązanie


Zadanie 3

Udowodnij, że algorytm Permutacja-Wagowa jest poprawny.

Rozwiązanie

Zadanie 4

Przypuśćmy, że mamy wage szalkową i odważniki będące potęgami trójki, dla każdej potęgi dokładnie jeden odważnik. Jak powinniśmy rozmieścić odważniki na wadze, aby doładnie zważyć przedmiot o zadanej wadze x?

Rozwiązanie


Zadanie 5

Zmodyfikuj algorytm Sortowanie-Kolejkowe tak, aby w czasie O(n log n) wyznaczał liczbę inwersji w permutacji.

Rozwiązanie



Zadanie 6

Jak wyznaczyć liczbę kolejkową w czasie liniowym?

Rozwiązanie