ASD Ćwiczenia 2

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

Postępujemy podobnie jak poprzednio, za kżdym rzem wybieramy do sklejenia k najmniejszych elemenów, z tym że w pierwszej iteracji liczba elementów moe być mniejsza, musi być taka żeby w każdej następnej iteracji sklejać dokładnie k.

Zadanie 2

Opisz algorytm na znajdowanie fałszywej monety wynikający z rekurencyjnego wzoru $a_{n}=3\cdot a_{n-1}+3$

Rozwiązanie

Algorytm najpierw rekurencyjnie korzysta z algorytmu dla n-1 grupując monety w paczki po trzy. Do tych paczek stosujemy algorytm dla n-1 Dodatkowo musimy sprytnie dożucić trzy monety.

Zadanie 3

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

Rozwiązanie

Skorzystaj z algorytmu liczącego liczbę inwersji mięðzy dwoma posortowanymi tablicami.

Zadanie 4

Jak policzyć liczbę kolejkową w czasie liniowym.

Rozwiązanie

Wynikiem jest k-1, gdzie k jest wynikiem algorytmu Najdłuższy-Malejący. Potraktujmy ciąg elementów bezposrednio wyoisywanych z wejścia na wyjści jako dodatkową kolejkę. Wtedy kolejki odpowiadaja ciągom elemenów wpisywanych kolejno do tablicy na określona pozycje w algorytmie Najdłuższy-Malejący.