ASD Ćwiczenia 1: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniam (→''Zadanie 4'') |
|||
| 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
