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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 2: Linia 2:
  
 
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 elemnó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 12: Linia 12:
 
  </div>
 
  </div>
 
</div>
 
</div>
 
 
 
  
 
=='''Zadanie 2''' ==
 
=='''Zadanie 2''' ==

Wersja z 12:14, 28 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 elemnó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