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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
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
 
pojedynczego sklejenia jest w dalszym ciągu suma wag.
 
pojedynczego sklejenia jest w dalszym ciągu suma wag.
  
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>

Wersja z 09:56, 30 wrz 2006

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

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