ASD Ćwiczenia 1: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 7: | Linia 7: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Dla każdego nowego niezerowego elementu, jeśli wstawiamy go na pozycję i-tą | 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 | 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 | kończącym się na tym elemencie | ||
| Linia 40: | Linia 40: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
W każdym optymalnym pakowaniu można je tak zmienić że najmniejszy element będzie razem | 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 | z maksymalnym, z którym się mieści do tego samego pudełka | ||
</div> | </div> | ||
</div> | </div> | ||
| Linia 51: | Linia 51: | ||
Przypuśćmy, że mamy wage szalkową i odważniki będące potęgami trójki, dla każdej potęgi | 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 | dokładnie jeden odważnik. Jak powinniśmy rozmieścić odważniki na wadze, aby doładnie zważyć przedmiot o | ||
zadanej wadze x. | zadanej wadze x. | ||
| Linia 59: | Linia 59: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Dodajemy minimalną liczbę y>=x, której rozwinięciem w systemie trójkowym są same jedynki, | 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 | 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, | 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 | jeśli +1, to na drugiej szalce, a jeśli zero - ignorujemy. | ||
</div> | </div> | ||
</div> | </div> | ||
Wersja z 09:14, 30 wrz 2006
Zadanie 1
Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny
Rozwiązanie
Zadanie 2
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny
Rozwiązanie
Zadanie 3
Udowodnij, że algorytm Proste-Pakowanie jest poprawny
Rozwiązanie
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
