ASD Ćwiczenia 2: Różnice pomiędzy wersjami
Nie podano opisu zmian |
m Zastępowanie tekstu – „<math> ” na „<math>” |
||
| (Nie pokazano 4 wersji utworzonych przez 3 użytkowników) | |||
| Linia 1: | Linia 1: | ||
=='''Zadanie 1''' == | =='''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 | 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. | pojedynczego sklejenia jest w dalszym ciągu suma wag). | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
| 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 3'' == | |||
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny. | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
Rozwiązanie | |||
<div class="mw-collapsible-content" style="display:none"> | |||
W każdym momencie na wadze jest w sumie pewien spójny przedział ciągu wejściowego, | |||
na jednej (lewej lub prawej) szalce są elementy z pozycji parzystych, na drugiej z pozycji nieparzystych. | |||
</div> | |||
</div> | |||
==''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? | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
Rozwiązanie | |||
<div class="mw-collapsible-content" style="display:none"> | |||
Dodajemy minimalną liczbę y>=x, której rozwinięciem w systemie trójkowym są same jedynki, | |||
tworzymy liczbę z = x+y, rozwijamy z w systemie trójkowym, a potem odejmujemy od każdej | |||
cyfry jedynkę. Jeśli mamy -1, to odpowiedni odważnik kładziemy na szalce razem z danym przedmiotem, | |||
jeśli +1, to na drugiej szalce, a jeśli zero - ignorujemy. | |||
</div> | |||
</div> | |||
=='''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 45: | 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
