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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 27: Linia 27:
  
  
 
+
==''Zadanie 2'' ==
 +
 
 +
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
 +
 
 +
<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>
 +
 
 +
==''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?
 +
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
 +
 
 +
<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 drugiej szalce, a jeśli zero - ignorujemy.
 +
</div>
 +
</div>
 +
 
 +
 
  
 
=='''Zadanie 3''' ==
 
=='''Zadanie 3''' ==

Wersja z 11:59, 15 cze 2007

Zadanie 1

Udowodnij, że algorytm Sklejanie-Par jest poprawny. Co by było, gdybyśmy w jednym kroku sklejali co najwyżej k elementów? (Kosztem pojedynczego sklejenia jest w dalszym ciągu suma wag).

Rozwiązanie

Zadanie 2

Opisz algorytm znajdowania fałszywej monety wynikający z rekurencyjnego wzoru .

Rozwiązanie


Zadanie 2

Udowodnij, że algorytm Permutacja-Wagowa 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


Zadanie 3

Zmodyfikuj algorytm Sortowanie-Kolejkowe tak, aby w czasie O(n log n) wyznaczał liczbę inwersji w permutacji.

Rozwiązanie



Zadanie 4

Jak wyznaczyć liczbę kolejkową w czasie liniowym?

Rozwiązanie