Page 4 - Informatyka na czasie. Podejście zachłanne w rozwiązywaniu problemów. Podręcznik klasa 3
P. 4

Rozdział 1. Algorytmika i programowanie w języku C++

                                4.2. Kolorowanie mapy metodą zachłanną

                                Podejście zachłanne ma zastosowanie nie tylko w algorytmach liczbo-
             Warto wiedzieć
           W 1853 r. postawiono   wych. Dzięki niemu można np. próbować ustalić, ile minimum kolorów
           hipotezę, że cztery kolory   wystarczy do wypełnienia mapy w taki sposób, aby dwa sąsiednie obsza-
           zawsze wystarczą do   ry, np. państwa lub województwa (jak na rys. 4.2), miały różne kolory.
           pokolorowania każdej
           płaskiej mapy. Dowód
           sformułowano dopiero
           w 1976 r. Dzięki pracy
           matematyków problem
           udało się zredukować do
           jedynie 1936 układów
           państw na mapie. Dalsze
           obliczenia przeprowadził już
           komputer. Dotąd nikomu
           nie udało się udowodnić
           tego twierdzenia bez użycia
           komputera.




                                Rys. 4.2. Mapa Polski z podziałem na województwa


             Warto wiedzieć      Ćwiczenie 2
           Mapę można pokolorować
           trzema kolorami wtedy   W pliku, który otrzymasz od nauczyciela (np. mapa.png), znajduje się
           i tylko wtedy, gdy     mapa konturowa Polski z podziałem na województwa. Pokoloruj ją, ko-
           każdy obszar na mapie   rzystając z możliwie najmniejszej liczby kolorów tak, aby dwa sąsiednie
           (np. województwo) ma
           parzystą liczbę sąsiadów.  województwa miały różne barwy.
              Problem kolorowania   Problem kolorowania mapy, zwany też problemem ubogiego karto-
                         mapy   grafa, sformułowano w połowie XIX w. Ówczesna technika drukarska
                                pozwalała już na drukowanie barwnych map, w szczególności map
                                politycznych. Liczbę użytych kolorów starano się jednak jak najbardziej
                                ograniczyć, by zmniejszyć koszty konstrukcji maszyny drukarskiej.
                                  Okazuje się, że do pokolorowania każdej płaskiej mapy wystarczą
                                cztery kolory. Nie jest jednak znany algorytm takiego optymalnego
                                kolorowania. Podejście zachłanne dla niektórych map daje tylko rozwią-
                                zanie przybliżone: spełniony jest warunek różnych barw dla sąsiednich
                                obszarów, ale w sumie wykorzystuje się np. pięć barw.

                                4.3. Wydawanie reszty metodą zachłanną

                                Wyobraź sobie, że podczas zakupów otrzymujesz przy kasie resztę 8 zł
                                i 45 gr wydaną wyłącznie monetami o wartości 1 zł oraz 5 gr. Łącznie
                                to 17 monet. Gdyby w ten sposób wydawano resztę w sklepach, trudno
                                byłoby ją zmieścić w portfelu, a w kasie mogłoby zabraknąć monet.
                                Dlatego dąży się do tego, aby liczba monet była możliwie jak najmniejsza.
           Problem wydawania reszty  Jest to tak zwany problem wydawania reszty.

           64
   1   2   3   4   5   6   7   8   9