21 września 2008

Metoda włączeń i wyłączeń cz II.

Przedstawię dwa proste zadania, które można rozwiązać za pomocą metody włączeń i wyłączeń.

Mamy danych 10 prostopadłościanów ortogonalnych (to znaczy takich, których krawędzie są równoległe do osi układów współrzędnych). Prostopadłościany te mogą na siebie nachodzić. Pytamy o sumę objętości tych prostopadłościanów.
Prostopadłościan ortogonalny może być zapisany za pomocą pary punktów: lewego, dolnego, "bliższego" (nam) oraz prawego, górnego, "dalszego". Powiedzmy, że pewien prostopadłościan jest określony za pomocą pary: (a1, a2, a3) oraz (b1, b2, b3). Jego objętość można wyrazić wzorem: (b1-a1)(b2-a2)(b3-a3).
Bardzo łatwo także wyznaczyć przecięcie dwóch prostopadłościanów, które także jest prostopadłościanem. Jeśli pierwszy z prostopadłościanów to (a1, a2, a3) oraz (b1, b2, b3), a drugi: (c1, c2, c3) oraz (d1, d2, d3) to prostopadłościan, który jest ich przecięciem to: (max{a1, c1}, max{a2, c2}, max{a3, c3}) oraz (min{b1,d1}, min{b2,d2}, min{b3,d3}).
Tak jak nauczyliśmy się w poprzedniej części - możemy teraz obliczyć sumę objętości prostopadłościanów na podstawię ich przecięć.

Drugie zadanie jest następujące. Mamy dany zbiór S = {1, 2, 3, ..., 109}. Pytamy ile jest liczb w tym zbiorze, które są podzielne przez 9, 11 lub 15?
Oznaczmy przez Dk zbiór tych wszystkich liczb należących do S, które są podzielne przez k. Nie trudno zauważyć, że |Dk| = 109 / k. Przy czym dzielenie tutaj rozumiemy jako dzielenie całkowitoliczbowe.
Tak samo łatwo można policzyć przecięcie dwóch zbiorów. Wystarczy tylko zauważyć, że:
Gdzie lcm(k, l) oznacza najmniejszą wspólną wielokrotność liczb k oraz l.
Zgodnie z opisaną w poprzedniej części metodą włączeń i wyłączeń możemy obliczyć sumę zdefiniowanych wzorów.

Dobrym ćwiczeniem będzie dla każdego implementacja powyższych algorytmów. Nie powinno to nikomu sprawić większych problemów, ale warto się oswoić z tą techniką.

Brak komentarzy: