ASD Ćwiczenia 1: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
<font color=darkred> ---------------------------------------------------------------------- | <font color=darkred> ---------------------------------------------------------------------- | ||
==''Zadanie 1''' == | |||
Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny | Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny | ||
| Linia 10: | Linia 9: | ||
<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ą | |||
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 | |||
</div> | </div> | ||
</div> | </div> | ||
==''Zadanie 2''' == | |||
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny | Udowodnij, że algorytm Permutacja-Wagowa jest poprawny | ||
| Linia 24: | Linia 25: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
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. | |||
</div> | </div> | ||
</div> | </div> | ||
==''Zadanie 3''' == | |||
Udowodnij, że algorytm Proste-Pakowanie jest poprawny | Udowodnij, że algorytm Proste-Pakowanie jest poprawny | ||
| Linia 39: | Linia 42: | ||
<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 | |||
z maksymalnym z którym się mieści do tego samego pudełka | |||
</div> | </div> | ||
</div> | </div> | ||
==''Zadanie 4''' == | |||
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 | dokładnie jeden odważnik. Jak rozmieścić odważniki na wadze aby doładnie zważyć przedmiot o | ||
zadanej wadze x. | zadanej wadze x. | ||
| Linia 56: | Linia 60: | ||
<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, | |||
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. | |||
</div> | </div> | ||
</div> | </div> | ||
[[Grafika:Example.jpg]] | |||
Wersja z 11:08, 11 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 rozmieścić odważniki na wadze aby doładnie zważyć przedmiot o zadanej wadze x.
Rozwiązanie
