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

02.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

Teraz przedstawimy kilka przykładów ilustrujących zastosowanie metody włączeń i wyłączeń.

Przykłady

Rozważmy następujący problem: chcemy znaleźć ilość wszystkich liczb naturalnych mniejszych lub równych 10000, które są podzielne przez 6, 15 lub 20. Łatwo policzyć ile w tym przedziale jest liczb podzielnych przez 6. Jest ich $  \left\lfloor \dfrac{10000}{6} \right\rfloor $. Łatwo też policzyć ile jest liczb w tym przedziale które są zarówno podzielne przez 6 jak i przez 15. Jest ich $  \left\lfloor \dfrac{10000}{NWW(6, 15)} \right\rfloor $. Jednak policzenie ile jest liczb, które są podzielne przez 6 lub przez 15... już takie łatwe nie jest.

Spróbujmy policzyć ten problem z metody włączeń i wyłączeń. Oznaczmy przez $ p_n $ zbiór liczb z naszego przedziału podzielne przez $ n $. Wtedy:

$ |p_6 \cup p_{15} \cup p_{20}| = |p_6| + |p_{15}| + |p_{20}| - |p_{NWW(6, 15)}| $

$ - |p_{NWW(6, 20)}| - |p_{NWW(15, 20)}| + |p_{NWW(6, 15, 20)}| =  $

$ = |p_6| + |p_{15}| + |p_{20}| - |p_{NWW(30)}| - |p_{NWW(60)}| - |p_{NWW(60)}| + |p_{NWW(60)}| = $

$ = |p_6| + |p_{15}| + |p_{20}| - |p_{NWW(30)}| - |p_{NWW(60)}| = $

$ = \left\lfloor \dfrac{10000}{6} \right\rfloor + \left\lfloor \dfrac{10000}{15} \right\rfloor + \left\lfloor \dfrac{10000}{20} \right\rfloor - \left\lfloor \dfrac{10000}{30} \right\rfloor - \left\lfloor \dfrac{10000}{60} \right\rfloor = $

$ = 1666 + 666 + 500 - 333 - 166 = 2333 $

Kolejnym zadaniem jakim się zajmiemy jest policzenie objętości bryły powstałej przez sklejenie kilku prostopadłościanów.

Mamy dane dziesięć prostopadłościanów o krawędziach równoległych do odpowiednich osi układu współrzędnych. Prostopadłościan jest dany za pomocą współrzędnych dolnego, lewego, przedniego rogu $ (x_1, y_1, z_1) $ i górnego, prawego, tylniego rogu $ (x_2, y_2, z_2) $. Istnieje prosty wzór na objętość takiego prostopadłościanu.

Jednak suma dwóch (albo dziesięciu) prostopadłościanów może być bryła mniej regularną i znalezienie wzoru na jego objętość może być rzeczą niebanalną. Jednak przecięcie dwóch prostopadłościanów (jeśli jest niepuste) jest również prostopadłościanem. Powiem więcej - znalezienie współrzędnych wierzchołków przecięcia jest stosunkowo prostym zadaniem. Zostawimy to jako ćwiczenie.

Złożoność i implementacja

Sporą wadą metody jest złożoność. Gdy chcemy policzyć sumę n zbiorów: $ |A_1 \cup A_2 \cup \ldots \cup A_n| $ potrzebujemy policzyć aż $ O(2^n) $ różnych przecięć. Gdy $ n = 20 $ mamy 1048575 podzbiorów - czyli mniej więcej tyle ile jesteśmy w stanie w limicie czasowym przetworzyć. Na przykład dla $ n = 30 $ mamy już ponad miliard różnych przecięć. Jest to zdecydowanie za dużo.

Zastanówmy się teraz jaka jest różnica między algorytmem wykonującym $ 2^n \times n $ operacji, a algorytmem wykonującym $ 2^n \times n^2 $ operacji. Z jednej strony może się wydawać, że niewielka bo $ 2^n $ jest na tyle duże, że czynnik $ n^2 $ wydaje się pomijalny dla odpowiednio dużych $ n $. Nic bardziej mylnego - zauważmy, że dla $ n = 20 $ drugi algorytm działa 20 razy wolniej niż pierwszy. To może zaważyć na zmieszczeniu się bądź nie w limicie czasowym na konkursie. Pisząc algorytmy działające w czasie wykładniczym należy zwracać uwagę na współczynniki przy $ 2^n $.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com