ASD Ćwiczenia 2: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniam |
|||
| 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
