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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 27: Linia 27:
  
  
==''Zadanie 2'' ==  
+
==''Zadanie 3'' ==  
  
 
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny.
 
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny.
Linia 59: Linia 59:
 
    
 
    
  
=='''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 75: 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