ASD Ćwiczenia 1: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
mNie podano opisu zmian |
|||
| Linia 1: | Linia 1: | ||
==''Zadanie 1'' == | ==''Zadanie 1'' == | ||
Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny | Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
| Linia 9: | Linia 9: | ||
Dla każdego nowego niezerowego elementu x, który jest aktualnie na pozycji j-tej, jeśli wstawiamy x na pozycję i-tą, | 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 | 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 y jest na pewnej pozycji mniejszej od j. | 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. | ||
</div> | </div> | ||
</div> | </div> | ||
| Linia 15: | Linia 15: | ||
==''Zadanie 2'' == | ==''Zadanie 2'' == | ||
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny | Udowodnij, że algorytm Permutacja-Wagowa jest poprawny. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
Rozwiązanie | Rozwiązanie | ||
| Linia 31: | Linia 31: | ||
==''Zadanie 3'' == | ==''Zadanie 3'' == | ||
Udowodnij, że algorytm Proste-Pakowanie jest poprawny | Udowodnij, że algorytm Proste-Pakowanie jest poprawny. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
| Linia 49: | Linia 49: | ||
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 powinniśmy 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? | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
Wersja z 20:57, 3 gru 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
