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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Zmiany do zadania o prostokatach)
(Chyba wszystko, najwyzej mozna dodac rysunki)
Linia 1: Linia 1:
 
== Zadanie 1 ==
 
== 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.
+
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 ?
Linia 109: Linia 109:
  
 
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==
 +
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">
 +
'''Wskazówka ''' 
 +
<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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
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
 +
Wtedy algorytm jest następujący:
 +
W.x1 = min(A.x1, B,x1)
 +
W.y1 = max(A.y1, B.y1)
 +
W.x2 = max(A.x2, B.x2)
 +
W.y2 = min(A.y2, B.y2)
 +
(w porównaniu z Zadaniem 1 zamieniliśmy miejscami max i min)
 +
 +
Dowód poprawności jest analogiczny do tego z Zadania 1.
 +
</div>
 +
</div>
 +
 +
== 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ę.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Tym razem nie wystarczy sprawdzić rzutów na oś X i Y.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 2''' 
 +
<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ę
 +
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.
 +
</div>
 +
</div>
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 3''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Najpierw rozwiążemy dwa podzadania:
 +
 +
'''Sprawdzanie czy punkty leżą po przeciwnych stronach prostej'''
 +
 +
Sprawdźmy, czy punkty r i s leżą po przeciwnych stronach prostej zawierającej odcinek pq.
 +
 +
Dla punktów p=(p.x,p.y), q=(q.x,q.y) i r=(r.x,r.y) niech M(p,q,r) oznacza wyznacznik macierzy
 +
  p.x  p.y  1
 +
  q.x  q.y  1
 +
  r.x  r.y  1
 +
Ma on ten sam znak, co sinus kąta nachylenia wektora pr do wektora pq ([[Banachowski, Diks, Rytter Algortmy i struktury danych]], str 259.)
 +
 +
Wartość M(p,q,r) (z ogólnego wzoru na wyznacznik) wynosi p.x*q.y + p.y*r.x + r.y*q.x - (r.x*q.y + q.x*p.y + r.y*p.x).
 +
 +
Niech &phi; to kąt pomiędzy pq i pr. Wtedy:
 +
 +
M(p,q,r) > 0  wtw  0 < &phi; < &pi;
 +
M(p,q,r) = 0  wtw  (&phi; = 0 lub  &phi; = &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:
 +
M(p,q,r)*M(p,q,s) < 0
 +
 +
'''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)).
 +
 +
'''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ć
 +
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
 +
min(p.x,q.x) &le; max(r.x,s.x)  i  min(r.x,s.x) &le; max(p.x,q.x)
 +
To samo dla osi Y. Podsumowując:
 +
'''jeśli''' max(p.x,q.x) &ge; min(r.x,s.x) i max(r.x,s.x) &ge; min(p.x,q.x) i
 +
    i max(p.y,q.y) &ge; min(r.y,s.y) i max(r.y,s.y) &ge; min(p.y,q.y) '''to''' PRZECINAJĄ SIĘ
 +
'''wpp''' ROZŁĄCZNE
 +
</div>
 +
</div>
 +
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie''' 
 +
<div class="mw-collapsible-content" style="display:none">
 +
Chcemy sprawdzić czy odcinki pq i rs się przecinają. Przyjmijmy oznaczenia:
 +
Mp=M(r,s,p)
 +
Mq=M(r,s,q)
 +
Mr=M(p,q,r)
 +
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.
 +
 +
A więc algorytm jest następujący:
 +
'''jeśli''' Mp*Mq > 0 '''lub''' Mr*Ms > 0 '''to''' ROZŁĄCZNE
 +
'''wpp'''
 +
  '''jeśli''' Mp*Mq < 0 '''lub''' Mr*Ms < 0 '''to''' PRZECINAJĄ SIĘ 
 +
  '''wpp'''
 +
    Sprawdź_czy_wpółliniowe_się_przecinają(pq, rs)
 +
</div>
 +
</div>
 +
 +
== 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.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Wskazówka 1''' 
 +
<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.
 +
</div>
 +
</div><div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
'''Rozwiązanie''' 
 +
<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.
 +
 +
Wpierw mamy do sprawdzenia 16 (a tak naprawdę 15) przecięć odcinków:
 +
wynik=ROZŁĄCZNE
 +
'''dla''' i &isin; [1..4]
 +
  '''dla''' j &isin; [1..4]
 +
    '''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.
 +
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)
 +
M14=M(r_1,r_4,q_1) N14=M(q_1,q_4,r_1)
 +
M23=M(r_2,r_3,q_1) N23=M(q_2,q_3,r_1)
 +
 
 +
'''jeśli''' (M12*M43 < 0 i M14*M23 <0) lub (N12*N43 < 0 i N14*N23 <0) '''to''' wynik=PRZECINAJĄ SIĘ
 +
</div>
 +
</div>

Wersja z 16:52, 19 lip 2006

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. rysunek

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 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

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 1

Rozwiązanie