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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
(Nie pokazano 4 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
 
=='''Zadanie 1''' ==
 
=='''Zadanie 1''' ==
  
Udowodnij, że algorytm Sklejanie-Par jest poprawny. Co by było, gdybyśmy w jednym kroku sklejali co najwyżej k elemnów, kosztem
+
Udowodnij, że algorytm Sklejanie-Par jest poprawny. Co by było, gdybyśmy w jednym kroku sklejali co najwyżej k elementów? (Kosztem
pojedyńczego sklejenia jest w dalszym ciągu suma wag.
+
pojedynczego sklejenia jest w dalszym ciągu suma wag).
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 8: Linia 8:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Postępujemy podobnie jak poprzednio, za każdym razem wybieramy do sklejenia k najmniejszych elemenów, z tym że w pierwszej
+
Postępujemy podobnie jak poprzednio, za każdym razem wybieramy do sklejenia k najmniejszych elemenów z tym, że w pierwszej
 
iteracji liczba elementów może być mniejsza: musi być taka, żeby w każdej następnej iteracji sklejać dokładnie k.
 
iteracji liczba elementów może być mniejsza: musi być taka, żeby w każdej następnej iteracji sklejać dokładnie k.
 
  </div>
 
  </div>
 
</div>
 
</div>
 
 
 
  
 
=='''Zadanie 2''' ==
 
=='''Zadanie 2''' ==
Linia 29: Linia 27:
  
  
 
+
==''Zadanie 3'' ==
 +
 
 +
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 5''' ==
  
 
Zmodyfikuj algorytm Sortowanie-Kolejkowe tak, aby w czasie O(n log n) wyznaczał liczbę inwersji w permutacji.  
 
Zmodyfikuj algorytm Sortowanie-Kolejkowe tak, aby w czasie O(n log n) wyznaczał liczbę inwersji w permutacji.  
Linia 47: Linia 75:
 
    
 
    
  
=='''Zadanie 4''' ==
+
=='''Zadanie 6''' ==
  
 
Jak wyznaczyć liczbę kolejkową w czasie liniowym?
 
Jak wyznaczyć liczbę kolejkową w czasie liniowym?

Aktualna wersja na dzień 12:00, 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 3

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 5

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

Rozwiązanie



Zadanie 6

Jak wyznaczyć liczbę kolejkową w czasie liniowym?

Rozwiązanie