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.
