ASD Ćwiczenia 1

Zadanie 1

Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny

Rozwiązanie

Dla każdego nowego niezerowego elementu x, który jest aktualnie na pozycji j-tej, jeśli wstawiamy x na pozycję i-tą, to w tym momencie na pozycji (i-1)-szej jest pewien jego poprzednik y w najdłuższym ciągu malejącym kończącym się na pozycji j-tej. To znaczy w szczególności, że y>x, oraz y jest pewnej pozycji mniejszej od j.

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 3

Udowodnij, że algorytm Proste-Pakowanie jest poprawny

Rozwiązanie

W każdym optymalnym pakowaniu można je tak zmienić, że najmniejszy element będzie razem z maksymalnym, z którym się mieści do tego samego pudełka

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.