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

Wersja z 12:20, 25 sie 2006

----------------------------------------------------------------------

Zadanie 1

Udowodnij, że algorytm Sklejanie-Par jest poprawny. Co by było, gdybyśmy w jednym kroku sklajali dwa lub trzy elementy, koszt sklejenia suma wag.

Rozwiązanie

----------------------------------------------------------------------

Zadanie 2

Opisz algorytm na znajdowanie fałszywej monety wynikający z rekurencyjnego wzoru $a_{n} = 3 \cdot a_{n - 1} + 3$

Rozwiązanie

----------------------------------------------------------------------

Zadanie 4

Zmodyfikuj algorytm Sortowanie-Kolejkowe tak aby w czasie O(n log n) liczył liczbę inwersji w permutacji.

Rozwiązanie

----------------------------------------------------------------------

Zadanie 4

Rozwiązanie

@@ Linia 33: / Linia 33: @@
 '''Zadanie 4''' </font>
-Przypuśćmy, że mamy wage szalkową i odważniki będące potęgami trójki, dla każdej potęgi
+Zmodyfikuj algorytm Sortowanie-Kolejkowe tak aby w czasie O(n log n) liczył liczbę inwersji w permutacji.
-dokładnie jeden odważnik. Jak rozmie"sci"c odwa'zniki na wadze aby dok'ladnie zwa'ry'c przedmiot o
-zadanej wadze x.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed">
 Rozwiązanie
 <div class="mw-collapsible-content" style="display:none">
-????????????.
+Skorzystaj z algorytmu
+liczącego liczbę inwersji mięðzy dwoam posortowanymi tablicami.
   </div>
 </div>
@@ Linia 50: / Linia 49: @@
 '''Zadanie 4''' </font>
-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 rozmie"sci"c odwa'zniki na wadze aby dok'ladnie zwa'ry'c przedmiot o
-zadanej wadze x.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed">