ASD Ćwiczenia 2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Rytter (dyskusja | edycje)
830 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 10 wersji utworzonych przez 5 użytkowników)
Linia 1: Linia 1:
<font color=darkred> ----------------------------------------------------------------------
=='''Zadanie 1''' ==


'''Zadanie 1''' </font>
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).


Udowodnij, że algorytm Sklejanie-Par jest poprawny. Co by było, gdybyśmy w jednym kroku sklajali dwa lub trzy elementy, koszt
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
sklejenia suma wag.
Rozwiązanie
 
<div class="mw-collapsible-content" style="display:none">
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 może być mniejsza: musi być taka, żeby w każdej następnej iteracji sklejać dokładnie k.
</div>
</div>
 
=='''Zadanie 2''' ==
 
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 10: Linia 21:


<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
Dodatkowo musimy sprytnie dorzucić trzy monety.
  </div>
  </div>
</div>
</div>


<font color=darkred> ----------------------------------------------------------------------


'''Zadanie 2''' </font>
==''Zadanie 3'' ==


Opisz algorytm na znajdowanie fałszywej monety wynikający z rekurencyjnego wzoru <math> a_n=3\cdot a_{n-1}+3 </math>
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">
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 24: Linia 50:


<div class="mw-collapsible-content" style="display:none">
<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>
</div>
</div>


 


<font color=darkred> ----------------------------------------------------------------------
=='''Zadanie 5''' ==
 
'''Zadanie 4''' </font>


Zmodyfikuj algorytm Sortowanie-Kolejkowe tak aby w czasie O(n log n) liczył liczbę inwersji w permutacji.  
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 39: Linia 67:
<div class="mw-collapsible-content" style="display:none">
<div class="mw-collapsible-content" style="display:none">
Skorzystaj z algorytmu
Skorzystaj z algorytmu
liczącego liczbę inwersji mięðzy dwoam posortowanymi tablicami.
wyznaczającego liczbę inwersji między dwiema posortowanymi tablicami.


  </div>
  </div>
Linia 45: Linia 73:




<font color=darkred> ----------------------------------------------------------------------
 
 
'''Zadanie 4''' </font>


=='''Zadanie 6''' ==


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 55: Linia 83:


<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.
Potraktujmy ciąg elementów bezpośrednio wypisywanych z wejścia na wyjście jako
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>

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 an=3⋅an−1+3.

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

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=ASD_Ćwiczenia_2&oldid=81218”