ASD Ćwiczenia 1: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| 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 pewnej pozycji mniejszej od j. | 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. | ||
</div> | </div> | ||
</div> | </div> | ||
Wersja z 10:20, 2 paź 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
