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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 1: Linia 1:
 
 
=='''Zadanie 1''' ==
 
=='''Zadanie 1''' ==
  
Linia 9: Linia 8:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Postępujemy podobnie jak poprzednio, za kżdym rzem 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 moe 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>
Linia 18: Linia 17:
 
=='''Zadanie 2''' ==
 
=='''Zadanie 2''' ==
  
Opisz algorytm na znajdowanie fałszywej monety wynikający z rekurencyjnego wzoru <math> a_n=3\cdot a_{n-1}+3 </math>
+
Opisz algorytm znajdowania fałszywej monety wynikający z rekurencyjnego wzoru <math> a_n=3\cdot a_{n-1}+3 </math>.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 25: Linia 24:
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
Algorytm najpierw rekurencyjnie korzysta z algorytmu dla n-1 grupując monety w paczki po trzy. Do tych paczek stosujemy algorytm dla n-1
 
Algorytm najpierw rekurencyjnie korzysta z algorytmu dla n-1 grupując monety w paczki po trzy. Do tych paczek stosujemy algorytm dla n-1
Dodatkowo musimy sprytnie dożucić trzy monety.
+
Dodatkowo musimy sprytnie dorzucić trzy monety.
 
  </div>
 
  </div>
 
</div>
 
</div>
Linia 34: Linia 33:
 
=='''Zadanie 3''' ==
 
=='''Zadanie 3''' ==
  
Zmodyfikuj algorytm Sortowanie-Kolejkowe tak aby w czasie O(n log n) liczył liczbę inwersji w permutacji.  
+
Zmodyfikuj algorytm Sortowanie-Kolejkowe tak, aby w czasie O(n log n) wyznaczał liczbę inwersji w permutacji.  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
Rozwiązanie
 
Rozwiązanie
Linia 40: Linia 39:
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
Skorzystaj z algorytmu
 
Skorzystaj z algorytmu
liczącego liczbę inwersji mięðzy dwoma posortowanymi tablicami.
+
wyznaczającego liczbę inwersji między dwiema posortowanymi tablicami.
  
 
  </div>
 
  </div>
Linia 50: Linia 49:
 
=='''Zadanie 4''' ==
 
=='''Zadanie 4''' ==
  
Jak policzyć liczbę kolejkową w czasie liniowym.
+
Jak wyznaczyć liczbę kolejkową w czasie liniowym?
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 57: Linia 56:
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
Wynikiem jest k-1, gdzie k jest wynikiem algorytmu Najdłuższy-Malejący.  
 
Wynikiem jest k-1, gdzie k jest wynikiem algorytmu Najdłuższy-Malejący.  
Potraktujmy ciąg elementów bezposrednio wyoisywanych z wejścia na wyjści jako
+
Potraktujmy ciąg elementów bezpośrednio wypisywanych z wejścia na wyjście jako
dodatkową kolejkę. Wtedy kolejki odpowiadaja ciągom elemenów wpisywanych kolejno do tablicy na  
+
dodatkową kolejkę. Wtedy kolejki odpowiadają ciągom elementów wpisywanych kolejno do tablicy na  
określona pozycje w algorytmie Najdłuższy-Malejący.
+
określoną pozycję w algorytmie Najdłuższy-Malejący.
 
  </div>
 
  </div>
 
</div>
 
</div>

Wersja z 12:16, 25 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 pojedyńczego 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