Wstęp do programowania/Wstęp do algorytmów/Ćwiczenia: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 38 wersji utworzonych przez 5 użytkowników)
Linia 1: Linia 1:
 +
To są zadania na prostokąty i odcinki.
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Oglądaj wskazówki i rozwiązania __SHOWALL__<br>
 +
Ukryj wskazówki i rozwiązania __HIDEALL__
 +
</div>
 +
 +
 
== Zadanie 1 ==
 
== 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.
 
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===
 
===Analiza specyfikacji===
* Czy specyfikacja podana w zadaniu jest wystarczająca do zapisania algorytmu ?
+
*Czy specyfikacja podana w zadaniu jest wystarczająca do zapisania algorytmu?
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Odpowiedź''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Odpowiedź</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
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.
+
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.
 
</div>
 
</div>
 
</div>
 
</div>
 +
 
*Co może być częścią wspólną ?  
 
*Co może być częścią wspólną ?  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Odpowiedź''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Odpowiedź</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
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.
+
 
 +
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.
 
</div>
 
</div>
 
</div>
 
</div>
* Jaka może być postać danych ?
+
 
 +
*Jaka może być postać danych ?
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Odpowiedź''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Odpowiedź</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
 +
 
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-górnego wierzchołka i prawego-dolnego,
+
# współrzędne lewego górnego wierzchołka i prawego dolnego,
# współrzędne lewego-górnego wierzchołka i długości boków,
+
# 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-górny wierzchołek z prawym-dolnym,
+
# 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-górnego wierzchołka, pole prostokąta i stosunek długości boków,
+
# 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-górnego w kolejności zgodnej z ruchem wskazówek zegara).
+
# 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.
  
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ć.
+
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 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).   
+
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 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.</div>
 
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.</div>
 
</div>
 
</div>
* Jaka może być postać wyniku ?
+
 
 +
*Jaka może być postać wyniku?
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Odpowiedź''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Odpowiedź</span>
<div class="mw-collapsible-content" style="display:none">  
+
<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 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.)
+
 
 +
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>
  
 
=== Znajdowanie algorytmu ===
 
=== 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.
+
Gdy zaczniemy analizować możliwe wzajemne położenia prostokątów, okaże się, że przypadków jest co najmniej kilkanaście.
 
[[Grafika:Prostokaty.png]]
 
[[Grafika:Prostokaty.png]]
 +
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Wskazówka 1''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
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.  
+
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.  
 
</div>
 
</div>
 
</div>
 
</div>
 +
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Wskazówka 2''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
Dane są dwa odcinki na prostej. Zastanów się jaka może być wartość lewego końca części wspólnej tych odcinków.
+
Dane są dwa odcinki na prostej. Zastanów się, jaka może być wartość lewego końca części wspólnej tych odcinków.
 
</div>
 
</div>
 
</div>
 
</div>
 +
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
<div class="mw-collapsible-content" style="display:none">  
+
<div class="mw-collapsible-content" style="display:none">
 
Załóżmy, że mamy operacje min i max. Przyjmijmy oznaczenia:
 
Załóżmy, że mamy operacje min i max. Przyjmijmy oznaczenia:
 
  A, B, W - prostokąty dane i wynikowy (odpowiednio)
 
  A, B, W - prostokąty dane i wynikowy (odpowiednio)
Linia 76: Linia 93:
  
 
=== Testowanie ===
 
=== Testowanie ===
Mając algorytm/program powinniśmy go przetestować, czyli sprawdzić
+
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).   
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 ===
 
=== 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.  
+
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 &cap; B) i zrobić formalny dowód, że dla każdego punktu p zdanie p &epsilon; A &cap; B jest równoważne temu, że p &epsilon; W. Teraz już możemy spać spokojnie - nasz algorytm '''jest''' poprawny (o ile nie pomylilismy się w dowodzie)!
+
Powinniśmy ustalić, co jest formalną specyfikacją naszego zadania (W = A &cap; B), i zrobić formalny dowód, że dla każdego punktu p zdanie p &epsilon; A &cap; B jest równoważne temu, że p &epsilon; W. Teraz już możemy spać spokojnie - nasz algorytm '''jest''' poprawny (o ile nie pomylilismy się w dowodzie)!
 +
 
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Dowód''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Dowód</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
 
Najpierw zauważmy, że  
 
Najpierw zauważmy, że  
Linia 93: Linia 110:
 
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 &epsilon; rzutX(A) &cap; rzutX(B).  Ponieważ p.x &epsilon; rzutX(A) to  
+
Załóżmy więc, że p.x &epsilon; rzutX(A) &cap; rzutX(B).  Ponieważ p.x &epsilon; rzutX(A) to  
 
  A.x1 &le; p.x &le; A.x2.
 
  A.x1 &le; p.x &le; A.x2.
 
Podobnie dla B,  czyli  
 
Podobnie dla B,  czyli  
Linia 104: Linia 121:
 
</div>
 
</div>
 
</div>
 
</div>
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.
+
 
 +
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===
A co by było gdyby prostokąty były otwarte (czyli bez brzegu) ?
+
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 (&le;, &ge;) na ostre (<, >).
 
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 (&le;, &ge;) na ostre (<, >).
  
 
== Zadanie 2==
 
== 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.
+
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.
 +
 
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Wskazówka ''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span>
<div class="mw-collapsible-content" style="display:none">  
+
<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 "dualne" do Zadania 1.  
+
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>
 +
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
<div class="mw-collapsible-content" style="display:none">  
+
<div class="mw-collapsible-content" style="display:none">
 
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-górnego, i prawego-dolnego wierzchołka (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
 
  P.x1 - notacja kropkowa do odwoływania się do współrzędnych
 
Wtedy algorytm jest następujący:
 
Wtedy algorytm jest następujący:
Linia 138: Linia 158:
  
 
== Zadanie 3==
 
== 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ówprzecinają się.  
+
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ę.  
 +
 
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Wskazówka 1''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 1</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
 
Tym razem nie wystarczy sprawdzić rzutów na oś X i Y.
 
Tym razem nie wystarczy sprawdzić rzutów na oś X i Y.
 
</div>
 
</div>
 
</div>
 
</div>
 +
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Wskazówka 2''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 2</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
 
Oznaczmy końce odcinków jako p,q oraz r,s.  Dwa odcinki pq i rs się
 
Oznaczmy końce odcinków jako p,q oraz r,s.  Dwa odcinki pq i rs się
przecinają wtedy i tylko wtedy, gdy punkty p i q leżą po przeciwnych stronach prostej rs, zaś punkty r i s po przeciwnych stronach prostej pq lub któryś z końców jednego z odcinków należy do drugiego
+
przecinają wtedy i tylko wtedy, gdy punkty p i q leżą po przeciwnych stronach prostej rs, zaś punkty r i s po przeciwnych stronach prostej pq lub któryś z końców jednego z odcinków należy do drugiego
 
odcinka.
 
odcinka.
 
</div>
 
</div>
 
</div>
 
</div>
 +
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Wskazówka 3''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka 3</span>
<div class="mw-collapsible-content" style="display:none">  
+
<div class="mw-collapsible-content" style="display:none">
Najpierw rozwiążemy dwa podzadania:
+
Najpierw rozwiążmy kilka zadań pomocniczych:
 
   
 
   
'''Sprawdzanie czy punkty leżą po przeciwnych stronach prostej'''
+
'''Sprawdzanie, czy punkty leżą po przeciwnych stronach prostej'''
  
 
Sprawdźmy, czy punkty r i s leżą po przeciwnych stronach prostej zawierającej odcinek pq.
 
Sprawdźmy, czy punkty r i s leżą po przeciwnych stronach prostej zawierającej odcinek pq.
Linia 176: Linia 199:
 
  M(p,q,r) < 0  wtw  &pi; < &phi; < 2&pi;
 
  M(p,q,r) < 0  wtw  &pi; < &phi; < 2&pi;
  
Zatem aby punkty r i s leżały po przeciwnych stronach prostej pq, potrzeba i wystarczy aby M(p,q,r) i M(p,q,s) były przeciwnych znaków, co można zapisać krócej jako:  
+
Zatem aby punkty r i s leżały po przeciwnych stronach prostej pq, potrzeba i wystarczy, aby M(p,q,r) i M(p,q,s) były przeciwnych znaków, co można zapisać krócej jako:  
 
  M(p,q,r)*M(p,q,s) < 0
 
  M(p,q,r)*M(p,q,s) < 0
  
'''Sprawdzanie czy punkt należy do odcinka'''
+
'''Sprawdzanie, czy punkt należy do odcinka'''
  
Aby punkt p należał do odcinka qr to musi należeć do prostej zawierającej qr (czyli M(q,r,p) musi byc równy 0), oraz rzuty p na osie X i Y muszą zawierać się w rzutach odcinka (czyli min(q.x,r.x) &le; p.x &le; max(q.x,r.x) i min(q.y,r.y) &le; p.y &le; max(q.y,r.y)).
+
Aby punkt p należał do odcinka qr, to musi należeć do prostej zawierającej qr (czyli M(q,r,p) musi byc równy 0), oraz rzuty p na osie X i Y muszą zawierać się w rzutach odcinka (czyli min(q.x,r.x) &le; p.x &le; max(q.x,r.x) i min(q.y,r.y) &le; p.y &le; max(q.y,r.y)).
  
'''Sprawdzanie czy współliniowe odcinki przecinają się'''
+
'''Sprawdzanie, czy współliniowe odcinki przecinają się'''
  
Aby współliniowe odcinki pq i rs przecinały się potrzeba i wystarcza by r &isin; pq lub s &isin; pq. Dla osi X powinniśmy więc mieć  
+
Aby współliniowe odcinki pq i rs przecinały się, potrzeba i wystarcza by r &isin; pq lub s &isin; pq. Dla osi X powinniśmy więc mieć  
 
  min(q.x,p.x) &le; r.x &le; max(q.x,p.x)  lub  min(q.x,p.x) &le; s.x &le; max(q.x,p.x)  
 
  min(q.x,p.x) &le; r.x &le; max(q.x,p.x)  lub  min(q.x,p.x) &le; s.x &le; max(q.x,p.x)  
 
czyli  
 
czyli  
Linia 197: Linia 220:
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
Chcemy sprawdzić czy odcinki pq i rs się przecinają. Przyjmijmy oznaczenia:
+
Chcemy sprawdzić, czy odcinki pq i rs się przecinają. Przyjmijmy oznaczenia:
 
  Mp=M(r,s,p)
 
  Mp=M(r,s,p)
 
  Mq=M(r,s,q)
 
  Mq=M(r,s,q)
Linia 205: Linia 228:
 
  Ms=M(p,q,s)
 
  Ms=M(p,q,s)
  
Punkty r i s leżą po różnych stronach prostej pq wtedy i tylko wtedy gdy Mr*Ms < 0 zaś leżą po tej samej stronie, wtedy i tylko wtedy gdy Mr*Ms > 0. Jeśli Mr*Ms = 0 to co najmniej jeden z punktów s lub r leży na prostej pq.
+
Punkty r i s leżą po różnych stronach prostej pq wtedy i tylko wtedy, gdy Mr*Ms < 0, zaś leżą po tej samej stronie wtedy i tylko wtedy, gdy Mr*Ms > 0. Jeśli Mr*Ms = 0, to co najmniej jeden z punktów s lub r leży na prostej pq.
  
 
A więc algorytm jest następujący:
 
A więc algorytm jest następujący:
Linia 217: Linia 240:
  
 
== Zadanie 4==
 
== 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.  
+
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.  
 +
 
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Wskazówka 1''' 
+
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka</span>
<div class="mw-collapsible-content" style="display:none">  
+
<div class="mw-collapsible-content" style="display:none">
 
I tym razem nie wystarczy sprawdzić rzutów na oś X i Y. Trzeba użyć zadania o przecinaniu się odcinków.  
 
I tym razem nie wystarczy sprawdzić rzutów na oś X i Y. Trzeba użyć zadania o przecinaniu się odcinków.  
 
</div>
 
</div>
</div><div class="mw-collapsible mw-made=collapsible mw-collapsed">
+
</div>
'''Rozwiązanie''' 
+
 
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie</span>
 
<div class="mw-collapsible-content" style="display:none">  
 
<div class="mw-collapsible-content" style="display:none">  
Niech R=(r_1,r_2,r_3,r_4) i Q=(q_1,q_2,q_3,q_4) to dane równoległoboki. Żeby R i Q się przecinały to albo ich boki muszą się przecinać, albo jeden równoległobok musi być zawarty w drugim.  
+
Niech R=(r_1,r_2,r_3,r_4) i Q=(q_1,q_2,q_3,q_4) to dane równoległoboki. Żeby R i Q się przecinały, to albo ich boki muszą się przecinać, albo jeden równoległobok musi być zawarty w drugim.  
  
 
Wpierw mamy do sprawdzenia 16 (a tak naprawdę 15) przecięć odcinków:
 
Wpierw mamy do sprawdzenia 16 (a tak naprawdę 15) przecięć odcinków:
Linia 234: Linia 260:
 
     '''jeśli''' PrzecinająSię(r_ir_(i+1 mod 4), q_jq_(j+1 mod 4) '''to''' wynik=PRZECINAJĄ SIĘ  
 
     '''jeśli''' PrzecinająSię(r_ir_(i+1 mod 4), q_jq_(j+1 mod 4) '''to''' wynik=PRZECINAJĄ SIĘ  
  
Jeśli po wykonaniu tych przecięć wynik nadal ma wartość ROZŁĄCZNE to powinniśmy jeszcze sprawdzić zawieranie równoległoboków. Żeby Q zawierało się w R potrzeba i wystarcza by q1 &isin; R. Do tego zaś trzeba by q_1 znajdowało się po przeciwnych stronach naprzeciwległych boków R, do czego użyjemy metody z wyznacznikiem z poprzedniego zadania.
+
Jeśli po wykonaniu tych przecięć wynik nadal ma wartość ROZŁĄCZNE, to powinniśmy jeszcze sprawdzić zawieranie równoległoboków. Żeby Q zawierało się w R, potrzeba i wystarcza by q1 &isin; R. Do tego zaś trzeba, by q_1 znajdowało się po przeciwnych stronach naprzeciwległych boków R, do czego użyjemy metody z wyznacznikiem z poprzedniego zadania.
 
  M12=M(r_1,r_2,q_1) N12=M(q_1,q_2,r_1)      
 
  M12=M(r_1,r_2,q_1) N12=M(q_1,q_2,r_1)      
 
  M43=M(r_4,r_3,q_1) N43=M(q_4,q_3,r_1)
 
  M43=M(r_4,r_3,q_1) N43=M(q_4,q_3,r_1)

Aktualna wersja na dzień 14:22, 26 maj 2020

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