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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
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 to ignorujemy.
+
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