ASD Ćwiczenia 1

Zadanie 1'

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

Rozwiązanie

Dla każdego nowego niezerowego elementu, jeśli wstawiamy go na pozycję i-tą to w tym momencie na pozycji (i-1)-szej jest jego poprzednik w najdłuższym ciągu malejącym kończącym się na tym elemencie

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 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 druguej szalce, a jeśli zero to ignorujemy.