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 elemnów, kosztem pojedyńczego sklejenia jest w dalszym ciągu suma wag.

Rozwiązanie


Zadanie 2

Opisz algorytm na znajdowanie fałszywej monety wynikający z rekurencyjnego wzoru

Rozwiązanie



Zadanie 3

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

Rozwiązanie



Zadanie 4

Jak policzyć liczbę kolejkową w czasie liniowym.

Rozwiązanie