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

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

Rozwiązanie



Zadanie 4

Jak wyznaczyć liczbę kolejkową w czasie liniowym?

Rozwiązanie