ASD Ćwiczenia 2: Różnice pomiędzy wersjami
Nie podano opisu zmian |
m Zastępowanie tekstu – „<math> ” na „<math>” |
||
| (Nie pokazano 2 wersji utworzonych przez 2 użytkowników) | |||
| Linia 15: | Linia 15: | ||
=='''Zadanie 2''' == | =='''Zadanie 2''' == | ||
Opisz algorytm znajdowania 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 27: | Linia 27: | ||
==''Zadanie | ==''Zadanie 3'' == | ||
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny. | Udowodnij, że algorytm Permutacja-Wagowa jest poprawny. | ||
| Linia 59: | Linia 59: | ||
=='''Zadanie | =='''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 | =='''Zadanie 6''' == | ||
Jak wyznaczyć liczbę kolejkową w czasie liniowym? | Jak wyznaczyć liczbę kolejkową w czasie liniowym? | ||
Aktualna wersja na dzień 10:36, 5 wrz 2023
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
