ASD Ćwiczenia 1: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
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