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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

To są zadania na prostokąty i odcinki.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__


Zadanie 1

Podaj algorytm wyliczający część wspólną dwóch 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ź

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

Odpowiedź

  • Jaka może być postać danych ?

Odpowiedź

  • Jaka może być postać wyniku?

Odpowiedź

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. Prostokaty.png

Wskazówka 1

Wskazówka 2

Rozwiązanie

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 testowanie nie wykryje błędów, nic ono 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

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 (<, >).

Zadanie 2

Podaj algorytm wyliczający najmniejszy prostokąt o bokach równoległych do osi układu współrzędnych, zawierający dwa zadane prostokąty o bokach równoległych do osi układu współrzędnych.

Wskazówka

Rozwiązanie

Zadanie 3

Używając tylko czterech podstawowych działań arytmetycznych, sprawdź, czy dwa odcinki na płaszczyźnie zadane porzez współrzędne końców przecinają się.

Wskazówka 1

Wskazówka 2

Wskazówka 3

Rozwiązanie

Zadanie 4

Sprawdź, czy dane dwa równoległoboki na płaszczyźnie przecinają się. Równoległoboki mają boki dowolnie nachylone do osi współrzędnych i zadane są poprzez współrzędne czterech rogów podanych zgodnie z ruchem wskazówek zegara.

Wskazówka

Rozwiązanie