Wstęp do programowania/Wstęp do algorytmów/Ćwiczenia: Różnice pomiędzy wersjami
m |
|||
| Linia 27: | Linia 27: | ||
Można rozważać kilka różnych postaci: | Można rozważać kilka różnych postaci: | ||
# współrzędne dwu przeciwległych wierzchołków, | # współrzędne dwu przeciwległych wierzchołków, | ||
| − | # współrzędne lewego | + | # współrzędne lewego górnego wierzchołka i prawego dolnego, |
| − | # współrzędne lewego | + | # współrzędne lewego górnego wierzchołka i długości boków, |
| − | # współrzędne środka, długość przekątnych i kąt nachylenia przekątnej łączącej lewy | + | # współrzędne środka, długość przekątnych i kąt nachylenia przekątnej łączącej lewy górny wierzchołek z prawym dolnym, |
| − | # współrzędne lewego | + | # współrzędne lewego górnego wierzchołka, pole prostokąta i stosunek długości boków, |
| − | # współrzędne wszystkich czterech wierzchołków (od lewego | + | # współrzędne wszystkich czterech wierzchołków (od lewego górnego w kolejności zgodnej z ruchem wskazówek zegara), |
# obszar zaznaczony przez użytkownika myszką na ekranie. | # obszar zaznaczony przez użytkownika myszką na ekranie. | ||
| Linia 44: | Linia 44: | ||
* Jaka może być postać wyniku? | * Jaka może być postać wyniku? | ||
{{odpowiedz||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{odpowiedz||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
| − | 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 | + | 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 ujawnia się wyższość reprezentacji 2, która pozwala reprezentować także pusty prostokąt, w przeciwieństwie do reprezentacji 1. (Reprezentacje 3-6 też są dobre, moglibyśmy także np. rysować wynik na ekranie.) |
</div> | </div> | ||
</div>}} | </div>}} | ||
| Linia 77: | Linia 77: | ||
=== Testowanie === | === 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 | + | 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 === | === Dowód poprawności === | ||
| Linia 92: | Linia 92: | ||
co tak naprawdę sprowadza się do zrobienia dowodu w przypadku jednowymiarowym. | 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 | + | Załóżmy więc, że p.x ε rzutX(A) ∩ rzutX(B). Ponieważ p.x ε rzutX(A) to |
A.x1 ≤ p.x ≤ A.x2. | A.x1 ≤ p.x ≤ A.x2. | ||
Podobnie dla B, czyli | Podobnie dla B, czyli | ||
| Linia 104: | Linia 104: | ||
</div>}} | </div>}} | ||
| − | Najważniejszy morał z tego zadania | + | 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=== | ===Inna wersja zadania=== | ||
| Linia 115: | Linia 115: | ||
{{wskazowka|||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | {{wskazowka|||<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none"> | ||
| − | Jeśli zinterpretujemy niejasności w specyfikacji, tak jak to zrobiliśmy w Zadaniu 1, to okaże się że jest to zadanie | + | Jeśli zinterpretujemy niejasności w specyfikacji, tak jak to zrobiliśmy w Zadaniu 1, to okaże się, że jest to zadanie „dualne” do Zadania 1. |
</div> | </div> | ||
</div>}} | </div>}} | ||
| Linia 122: | Linia 122: | ||
Przyjmijmy oznaczenia: | Przyjmijmy oznaczenia: | ||
A, B, W - prostokąty dane i wynikowy (odpowiednio) | A, B, W - prostokąty dane i wynikowy (odpowiednio) | ||
| − | x1,x2,y1,y2 - współrzędne lewego | + | 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 | P.x1 - notacja kropkowa do odwoływania się do współrzędnych | ||
Wtedy algorytm jest następujący: | Wtedy algorytm jest następujący: | ||
Wersja z 19:49, 15 lis 2006
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.
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ównolełoboki na płaszczyźnie przecinają się. Równoległoboki mają boki dowolnie nachylone do osi współrzędnych i zadane są porzez współrzędne czterech rogów podanych zgodnie z ruchem wskazówek zegara.
Wskazówka
Rozwiązanie
