Krowa, las i eksploracja terenu

17.11.2009 - Marcin Bieńkowski
TrudnośćTrudnośćTrudność

Łata na łacie

Tu mała dygresja: informatycy, jak i wszystkie umysły ścisłe uwielbiają: a) łatanie złych rozwiązań zamiast pisania ich od początku, b) redukcje. Do tego stopnia, że często wpadają w pułapki jak w opisana niżej historia (z długaśną brodą) o czajniku.

Mamy pusty czajnik czajnik, chcemy zagotować wodę. Co zrobić? Należy oczywiście: 1. nalać wodę, 2. włączyć czajnik, 3. czekać. A co zrobić jeśli mamy pełny czajnik i chcemy zagotować wodę? To proste — odpowie prawdziwy (i leniwy) informatyk — wylewamy z niego wodę i w ten sposób doprowadzamy sytuację do stanu, który potrafimy rozwiązać.

Zastanówmy się zatem, czy przez ,,łatanie'' algorytmu Go-And-Eat i dodanie punktu 4 nie postąpiliśmy przypadkiem jak prawdziwi informatycy (a nie chcielibyśmy tego robić, bo po co męczyć steraną życiem i mocno już wygłodniałą krowę). Zobaczmy, jak wygląda droga, po której teraz chodzi krowa.

Może nie jest oczywiste, co można tutaj poprawić. Ale... pamiętacie, że to w którą stronę krowa zaczyna wykonywanie algorytmu Go-And-Eat nie ma znaczenia? W takim razie narysujmy drogę krowy która nieparzyste wykonania algorytmu Go-And-Eat zaczyna w stronę lewą a parzyste w prawą.

Bez sensu, prawda? Krowa idzie w jedną stronę $ 2^j $ metrów, tylko po to żeby wrócić do punktu wyjścia i pójść w tę samą stronę $ 2^{j+1} $ metrów! Wyrzućmy zatem nadmiarowe spacery (zaznaczone na czerwono na rysunku powyżej). Zmodyfikowany algorytm prezentuje się następująco:

Algorytm Smart-Cow
1. Kierunek zwiedzania := lewo
2. D := 1
3. Dopóki nie znaleźliśmy wejścia na pastwisko, powtarzajmy:
   a. Przejdź D metrów w kierunku zwiedzania i wróć punktu startowego
   b. D := D * 2
   c. Obróć kierunek zwiedzania

Spróbujmy teraz przeanalizować, jaki dystans pokona krowa w najgorszym przypadku.Weźmy takie naturalne j, że zachodzi $ 2^j < X \leq 2^{j+1} $. Oznacza to, że pierwsze j wykonań pętli w punkcie 3 powyższego algorytmu (z wartościami $ D \leq 2^j $) nie spowoduje znalezienia pastwiska. Droga w metrach przebyta przez krowę do tego momentu wynosi


\begin{align*} K 
 & = (1+1) + (2+2) + (4+4) + (8+8) + ... + (2^{j-1}+2^{j-1}) + (2^j +2^j) \\
 & = 2 \cdot (1+2+4+8+....+2^{j-1}+2^j) \\
 & = 2 \cdot (2^{j+1} - 1) \\
 & < 4 \cdot 2^j \enspace.
\end{align*}

Nazwijmy ten punkt krytycznym, przyda się on w dalszej części artykułu. Następnie krowa chce iść $ 2^{j+1} $ metrów w jakimś kierunku. Oczywiście ma pecha i idzie kierunku przeciwnym do wejścia na pastwisko.Ten skok w niewłaściwy bok (wraz z powrotem) kosztuje ją kolejne $ 2^{j+1} + 2^{j+1}
= 4 \cdot 2^j $ metrów. Następnie krowa zamierza iść $ 2^{j+2} $ metrów, ale już po X metrach napotyka pastwisko. Sumarycznie jej całkowita droga to co najwyżej


\begin{equation*}
K + 4 \cdot 2^j + X < 8 \cdot 2^j + X < 8 \cdot X + X = 9 X \enspace.
\end{equation*}

5
Twoja ocena: Brak Ocena: 5 (14 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com