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 elementów? (Kosztem pojedynczego sklejenia jest w dalszym ciągu suma wag).

Rozwiązanie

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

Zadanie 2

Opisz algorytm znajdowania 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 dorzucić trzy monety.

Zadanie 2

Udowodnij, że algorytm Permutacja-Wagowa jest poprawny.

Rozwiązanie

W każdym momencie na wadze jest w sumie pewien spójny przedział ciągu wejściowego, na jednej (lewej lub prawej) szalce są elementy z pozycji parzystych, na drugiej z pozycji nieparzystych.

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

Dodajemy minimalną liczbę y>=x, której rozwinięciem w systemie trójkowym są same jedynki, tworzymy liczbę z = x+y, rozwijamy z w systemie trójkowym, a potem odejmujemy od każdej cyfry jedynkę. Jeśli mamy -1, to odpowiedni odważnik kładziemy na szalce razem z danym przedmiotem, jeśli +1, to na drugiej szalce, a jeśli zero - ignorujemy.

Zadanie 3

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

Rozwiązanie

Skorzystaj z algorytmu wyznaczającego liczbę inwersji między dwiema posortowanymi tablicami.

Zadanie 4

Jak wyznaczyć 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 bezpośrednio wypisywanych z wejścia na wyjście jako dodatkową kolejkę. Wtedy kolejki odpowiadają ciągom elementów wpisywanych kolejno do tablicy na określoną pozycję w algorytmie Najdłuższy-Malejący.