Wstęp do programowania/Wstęp do algorytmów/Ćwiczenia

Zadanie 1

Podaj algorytm wyliczający część wspólną dwu zadanych prostokątów o bokach równoległych do osi układu współrzędnych.

Analiza specyfikacji

• Czy specyfikacja podana w zadaniu jest wystarczająca do zapisania algorytmu ?

Odpowiedź

Nie, nie wiadomo co to znaczy zadane, nie wiadomo czy prostokąty są domknięte (z brzegiem), nie wiadomo co zlecający wykonanie zadania rozumiał przez wyliczanie.

• Co może być częścią wspólną ?

Odpowiedź

Jeśli prostokąty są z brzegiem to prostokąt o bokach równoległych do osi układu, odcinek pionowy lub poziomy, punkt, zbiór pusty; wszystkie te przypadki możemy traktować jako szczególne rodzaje pierwszego przypadku.

• Jaka może być postać danych ?

Odpowiedź

Można rozważać kilka różnych postaci:

1. współrzędne dwu przeciwległych wierzchołków,
2. współrzędne lewego-górnego wierzchołka i prawego-dolnego,
3. współrzędne lewego-górnego wierzchołka i długości boków,
4. współrzędne środka, długość przekątnych i kąt nachylenia przekątnej łączącej lewy-górny wierzchołek z prawym-dolnym,
5. współrzędne lewego-górnego wierzchołka, pole prostokąta i stosunek długości boków,
6. współrzędne wszystkich czterech wierzchołków (od lewego-górnego w kolejności zgodnej z ruchem wskazówek zegara).
7. obszar zaznaczony przez użytkownika myszką na ekranie.

Każda z tych reprezentacji danych spełnia swoje zadanie i w konkretnym zastosowaniu może być tą, którą należy wybrać (bo np. nasz algorytm jest częścią większego systemu, który jej właśnie używa). Naszym zadaniem jako projektantów/analityków jest przeanalizowanie różnych możliwości, zaproponowanie zlecającemu rozwiązań, które uważamy za najlepsze, ale ostateczna decyzja należy do zlecającego, to my musimy się dostosować.

Reprezentacja 7 i tak sprowadzi się do jednej z pozostałych. Reprezentacja 6 jest nadmiarowa. Taka sytuacja ma swoje wady (koszt pamięciowy) i zalety (można łatwiej się zorientować, że dane nie są poprawne i nie trzeba wyliczać danych które są już podane, co może być kosztowne czasowo). Reprezentacje 3,4,5 są poprawne, w zależności od tego co chcemy robić z wynikiem naszych obliczeń mogą się okazać warte wybrania.

Reprezentacje 2 i 1 wydają się równoważne, dopiero przy wyborze reprezentacji wyniku okaże się, że różnica między nimi w tym akurat zadaniu jest bardzo istotna.

• Jaka może być postać wyniku ?

Odpowiedź

Skoro możemy traktować każdy możliwy wynik jako (być może zdegenerowany) prostokąt o bokach równoległych do osi układu, to byłoby dobrze użyć tu tej samej reprezentacji co dla danych (nam jako piszącym będzie łatwiej, a przede wszystkim jest to lepsze dla użytkownika, który będzie mógł zastosować nasz algorytm do wyników przez ten algorytm policzonych). I tu okazuje się wyższość reprezentacji 2, która pozwala reprezentować także pusty prostokąt, w przeciwieństwie do reprezentacji 1. (Reprezetacje 3-6 też są dobre, moglibyśmy także np. rysować wynik na ekranie.)

Znajdowanie algorytmu

Gdy zaczniemy analizować możliwe wzajemne położenia prostokątów okaże się, że przypadków jest co najmniej kilkanaście. rysunek

Wskazówka 1

Zauważ, że wynikowy prostokąt jest iloczynem kartezjańskim dwóch odcinków. Tego, który jest częścią wspólną rzutów obu prostokątów na oś X i tego, który jest częścią wspólną rzutów obu prostokątów na oś Y. W ten sposób zadanie dwuwymiarowe zostaje zredukowane do dwóch zadań jednowymiarowych.

Wskazówka 2

Dane są dwa odcinki na prostej. Zastanów się jaka może być wartość lewego końca części wspólnej tych odcinków.

Rozwiązanie

Załóżmy, że mamy operacje min i max. Przyjmijmy oznaczenia:

A, B, W - prostokąty dane i wynikowy (odpowiednio)
x1,x2,y1,y2 - współrzędne lewego-górnego, i prawego-dolnego wierzchołka (odpowiednio)
P.x1 - notacja kropkowa do odwoływania się do współrzędnych

Cały algorytm to cztery linijki:

W.x1 = max(A.x1, B,x1)
W.y1 = min(A.y1, B.y1)
W.x2 = min(A.x2, B.x2)
W.y2 = max(A.y2, B.y2)

(współrzędne y-owe rosną w górę, tak jak w matematyce, a nie w dól jak na ekranie komputera).

Testowanie

Mając algorytm/program powinniśmy go przetestować, czyli sprawdzić jakie daje wyniki dla przykładowych danych. Warto testować z jednej strony przypadki typowe, z drugiej zaś szczególne przypadki graniczne (np. prostokąty dotykające się jednym rogiem lub jeden prostokąt zawarty w drugim). Testowanie jest ważne i trzeba je robić, mimo że, w przypadku gdy nie wykryje błędów, nic nie daje (nawet nie mamy pewności, że dla przetestowanych danych zawsze dostaniemy poprawny wynik, bo np. mamy niezainicjalizowane zmienne).

Dowód poprawności

Skoro testowanie nie daje pewności, że mamy dobry program to potrzebujemy innego narzędzia, które pozwoli nam spać spokojnie - możemy (przynajmniej teoretycznie) dowieść formalnie poprawność programu. Powinniśmy ustalić co jest formalną specyfikacją naszego zadania (W = A ∩ B) i zrobić formalny dowód, że dla każdego punktu p zdanie p ε A ∩ B jest równoważne temu, że p ε W. Teraz już możemy spać spokojnie - nasz algorytm jest poprawny (o ile nie pomylilismy się w dowodzie)!

Dowód

Najpierw zauważmy, że

p ε A ∩ B   wtedy i tylko wtedy    p.x ε rzutX(A) ∩ rzutX(B) i p.y ε rzutY(A) ∩ rzutY(B) 
   p ε W    wtedy i tylko wtedy               p.x ε rzutX(W) i p.y ε rzutY(W)

A więc wystarczy, że niezależnie pokażemy:

p.x ε rzutX(A) ∩ rzutX(B)  wtedy i tylko wtedy p.x ε rzutX(W) i
p.y ε rzutY(A) ∩ rzutY(B)  wtedy i tylko wtedy p.y ε rzutY(W)

co tak naprawdę sprowadza się do zrobienia dowodu w przypadku jednowymiarowym.

Załóżmy więc że p.x ε rzutX(A) ∩ rzutX(B). Ponieważ p.x ε rzutX(A) to

A.x1 ≤ p.x ≤ A.x2.

Podobnie dla B, czyli

B.x1 ≤ p.x ≤ B.x2. 

A więc

max(A.x1,B.x1) ≤ p.x ≤ min(A.x2,B.x2) 

Stąd W.x1 ≤ p.x ≤ W.x2, czyli p.x ε rzutX(W).

W drugą stronę dowód przebiega podobnie. Ponieważ p.x ε rzutX(W) to max(A.x1,B.x1) ≤ p.x ≤ min(A.x2,B.x2). Stąd A.x1 ≤ p.x ≤ A.x2 a więc p.x ε rzutX(A). I tak samo dla B. A więc p.x ε rzutX(A) ∩ rzutX(B).

Najważniejszy morał z tego zadania, to pochwała myślenia - trzeba wykonać dużo pracy (myślowej) zanim zacznie się pisać pierwszy wiersz programu/algorytmu.

Inna wersja zadania

A co by było gdyby prostokąty były otwarte (czyli bez brzegu) ?

Reprezentacja używana powyżej jest nadal dobra zarówno dla danych jak i dla wyniku. Tym razem możliwe są tylko dwie postacie wyniku: albo prostokąt (z wnętrzem) o bokach równoległych do osi układu, albo zbiór pusty. Algorytm który podaliśmy powyżej działa również dla prostokątów otwartych; w dowodzie poprawności trzeba by jedynie zamienić nierówności nieostre (≤, ≥) na ostre (<, >).