ASD Ćwiczenia 2: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
mNie podano opisu zmian |
||
| 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 | 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 | 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 | 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 | 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) | 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 | ||
wyznaczającego liczbę inwersji między dwiema posortowanymi tablicami. | |||
</div> | </div> | ||
| Linia 50: | Linia 49: | ||
=='''Zadanie 4''' == | =='''Zadanie 4''' == | ||
Jak | 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 | Potraktujmy ciąg elementów bezpośrednio wypisywanych z wejścia na wyjście jako | ||
dodatkową kolejkę. Wtedy kolejki | dodatkową kolejkę. Wtedy kolejki odpowiadają ciągom elementów wpisywanych kolejno do tablicy na | ||
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
