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 że y jest na 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.
