Dwa dodatkowe zadania o wadze szalkowej

Waga czwórkowa

Zupełnie innym problemem jest obliczenie minimalnej liczby odważników potrzebnych do zważenia na wadze szalkowej przedmiotu o wadze \( n \).

Zakładamy, że mamy tylko odważniki o wagach będących potęgami czwórki.

W tym przypadku algorytm opiera się na obserwacji, że na lewo w ciągu generuje się co janwyżej przeniesienie jednej jedynki (reprezentującej następną wartść czwórki).

Algorytm korzysta istotnie z reprezentacji czwórkowej liczby \( n \). Niech

\( repr(n)\ =\ [n_0,n_1,n_2,\ldots,n_k] \)

oznacza reprezentację czwórkową liczby \( n \)

Cały algorytm nieformalnie wygląda następująco:

Algorytm WagaCzwórkowa

\( x_0 = 0 \), \( y_0 = 1 \)
for \( i:=0 \) to \( k-1 \) do \[ \begin{array}{rcl} n_{i+1} = 0 & \Longrightarrow & (x_{i+1}, y_{i+1}):= (x_i, x_i+1) \\ n_{i+1} = 1 & \Longrightarrow & (x_{i+1}, y_{i+1}):= (x_i+1, \min(x_i+2, y_i+2)) \\ n_{i+1} = 2 & \Longrightarrow & (x_{i+1}, y_{i+1}):= (\min(x_i+2, y_i+2), y_i+1) \\ n_{i+1} = 3 & \Longrightarrow & (x_{i+1}, y_{i+1}):= (y_i+1, y_i) \end{array} \] \( wynik\:=\ x_k \)

Pozostawiamy jako ćwiczenie modyfikację (rozszerzeie) algorytmu tak aby obliczał on liczbę możliwych ważeń używających minimalnej liczby odważników.

Permutacje wagowe

Przedstawimy jeszcze jeden problem związany z wagą. Rozważmy wagę szalkową, na której początkowo obie szalki są puste. Mamy do dyspozycji odważniki o numerach \( 1,2,\ldots,n \). Waga i-tego odważnika wynosi \( a_i \) i wagi są parami różne. Dla danej permutacji \( \Pi \) numerów odważników będziemy je wkładać na wagę zgodnie z permutacją. Kładziemy kolejno odważniki w kolejności \( \Pi \) na lewą lub prawa szalkę, raz położony odważnik nie zmienia już nigdy swego położenia na szalce (wybór szalki jest niedeterministyczny). Otrzymujemy ciąg wyników ważenia: +1, gdy lewa szalka przeważa, a -1 w przeciwnym wypadku. Ciąg ten oznaczamy przez Input. Mówimy, że permutacja \( \Pi \) jest zgodna z ciągiem wyników ważeń, danych tablicą Input. Zajmiemy się problemem: dany jest na wejściu ciąg Input wyników ważeń i mamy znaleźć jakąkolwiek permutację \( \Pi \) zgodną z ciągiem Input. Takich permutacji może być wiele. Zauważmy, że liczba permutacji wynosi n!, a liczba ciągów wyników ważeń wynosi \( 2^n \), co jest liczbą znacznie mniejszą.
Następujący algorytm znajduje pewną permutację zgodną Input. Zakładamy, że

\( a_1 < a_2 < a_3 < \ldots a_n. \)

Algorytm Permutacja-Wagowa

  p:=1; q:=n;  
  for  i:=n  downto  1  do 
     if (i > 1)  and (Input[i-1] <>  Input [i])  then 
       Wynik[i]:= q; q:=q-1;  
     else  
        Wynik[i]:= p; p:=p+1

Jeśli \( Input \) = [+1,+1,+1,-1,-1,-1,+1,+1,-1], to \( Wynik \) = [6, 5, 4, 7, 3, 2, 8, 1, 9]. Ciąg \( Input \) jest zrealizowany przez następujący ciąg wyborów wkładania kolejnego odważnika:

L P L P P L L P P,

gdzie L oznacza połóż na lewą szalkę, P na prawą.

Nie jest jasne, jak policzyć efektywnie liczbę wszystkich permutacji zgodnych z danym ciągiem wyników, albo znaleźć jakąś szczególną permutację, np. leksykograficznie pierwszą lub ostatnią. Co stanie się, jeśli tablica \( Input \) zawiera również zera (wagi szalek są równe)? Wtedy nie każdy ciąg \( Input \) jest realizowalny. Jak to można efektywnie sprawdzać?

Informatyka MIMUW