ASD Ćwiczenia 2: Różnice pomiędzy wersjami
m Zastępowanie tekstu – „ </math>” na „</math>” |
m Zastępowanie tekstu – „<math> ” na „<math>” |
||
| 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"> | ||
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
