Zasada włączeń i wyłączeń

02.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

Teraz postarajmy się zaimplementować ogólną metodę włączeń i wyłączeń. Powiedzmy, że mamy zaimplementowaną funkcję $ intersection $, która jako argumenty potrzebuje tablicę wartości logicznych $ A $ oraz jej długość $ N $. Liczy ona ilość elementów dla przecięcia pewnych zbiorów. Mówiąc konkretniej to bierze on zbiór $ i $-ty jeśli wartość tablicy $ A\left[i-1 \right] $ jest ustawiona na prawdę. Czyli na przykład $ intersection\left(\left[0, 1, 1, 0, 1\right], 5\right) $ wyznacza ilość elementów w zbiorze $ A_2 \cap A_3 \cap A_5 $.

Oznaczmy na chwilę prawdę jako jeden, a fałsz jako zero. Tablicę A będziemy "zwiększać o 1" tak jakgdyby była ona licznikiem binarnym. To znaczy, że dla $ N = 3 $ będzie ona przyjmowała następujące wartości:

A = [1, 0 ,0];
A = [0, 1, 0];
A = [1, 1, 0];
A = [0, 0, 1];
A = [1, 0, 1];
A = [0, 1, 1];
A = [1, 1, 1];

Czytając te cyfry od prawej do lewej otrzymujemy kolejne liczby naturalne w systemie dwójkowym. $ (001)_2 = 1 $, $ (010)_2 = 2 $, $ (011)_2 = 3 $ i tak dalej.

W naszym rozwiązaniu pojawiają się ponadto zmienna answer oraz sign. Każdy kto zna dobrze angielski od razu zgadnie, że w zmiennej answer będziemy trzymali obliczoną odpowiedź, a w zmiennej sign znak $ \pm $ w zależności od tego czy ilość elementów danego przecięcia będziemy chcieli dodać czy odjąć.

int sum(int N)
{
  int answer = 0;
  int sign = 1;
  bool *A = new bool[N+1];

  A[0] = true;
  for (int i = 1; i <= N; i++)
    A[i] = false;

  while (A[N] == 0)
  {
    answer += sign * intersection(A, N);

    int j = 0;
    while (A[j])
    {
      A[j] = false;
      sign = -sign;
      j++;
    }
    A[j] = true;
    sign = -sign;
  }

  return answer;
}

Po deklaracji zmiennych, ustawiamy wartości początkowe tablicy $ A $. Następnie w pętli najpierw aktualizujemy wynik, a następnie zwiększamy licznik tablicy $ A $. Robimy to w ten sposób, że zerujemy od lewej wszystkie $ 1 $, aż natrafimy na pierwsze $ 0 $ z lewej. Następnie to $ 0 $ zamieniamy na $ 1 $. Zmieniamy znak za każdym razem gdy zmieniamy jakąś jedynkę na zero lub zero na jedynkę.

Wyjaśnienia może wymagać jeszcze fakt, że tablica $ A $ ma o jeden element więcej niż potrzeba. Jest tak tylko na użytek tej funkcji. Funkcja intersection widzi już tą tablicę w "zwykłej" wielkości, dzięki zmiennej N. Już wyjaśniam czemu służy dodatkowa komórka. Gdy $ N = 3 $ ostatnie przecięcie jakie sprawdzamy jest określone w tablicy jako $ \left[1, 1, 1, 0]\right $. Ostatnie zero jest właśnie tą dodaną komórką. Jak teraz będziemy próbowali zwiększyć o $ 1 $ taki licznik otrzymamy $ \left[0, 0, 0, 1\right] $. Dzięki temu mamły prosty warunek końca pętli while. Działamy w pętli tak długo jak długo dodatkowa komórka jest ustawiona na zero.

Zadania

Do implementacji pozostają zadania przedstawione w treści artykułu. Implementacja ich powinna być ciekawym problemem samym w sobie. Zapraszam na następną stronę wszystkich chcących się zmierzyć z zadaniami!

3.25
Twoja ocena: Brak Ocena: 3.3 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com