Zapisywanie algorytmów w postaci schematu blokowego

Do zapisywania algorytmów można wykorzystać schematy blokowe. Są one graficzną reprezentacją czynności składających się na algorytm. Więcej na ich temat znajdziesz w e‑materiale Zapisywanie algorytmów za pomocą schematu blokowegoPqfiWgaRoZapisywanie algorytmów za pomocą schematu blokowego.

Przykładowy schemat blokowy

Spróbujmy przedstawić inny algorytm w postaci schematu blokowego. Ma on opisywać metodę sprawdzania, czy punkt o określonych współrzędnych należy do zdefiniowanego odcinka.

Formalna prezentacja problemu mogłaby wyglądać następująco:

Algorytm sprawdzania, czy punkt w dwuwymiarowej przestrzeni kartezjańskiej znajduje się na odcinku pomiędzy dwoma zadanymi punktami.

Specyfikacja problemu:

Dane:

  • Ax – współrzędna x punktu A wyznaczającego pierwszy koniec odcinka; liczba rzeczywista.

  • Ay – współrzędna y punktu A wyznaczającego pierwszy koniec odcinka; liczba rzeczywista.

  • Bx – współrzędna x punktu B wyznaczającego drugi koniec odcinka; liczba rzeczywista.

  • By – współrzędna y punktu B wyznaczającego drugi koniec odcinka; liczba rzeczywista.

  • Cx – współrzędna x punktu C, którego przynależność do odcinka AB sprawdzamy; liczba rzeczywista.

  • Cy – współrzędna y punktu C, którego przynależność do odcinka AB sprawdzamy; liczba rzeczywista.

Wynik:

Algorytm zwraca wartość logiczną prawda, jeżeli sprawdzany punkt przynależy do podanego odcinka lub – w przeciwnym wypadku – podaje wartość logiczną fałsz.

Aby sprawdzić, czy trzy punkty leżą na jednej prostej, należy obliczyć wyznacznikwyznacznik macierzywyznacznik macierzymacierzmacierzy, w której jako dwie pierwsze kolumny podamy współrzędne punktów. W pierwszej kolumnie znajdą się składowe współrzędnych oznaczone indeksem x, w drugiej – indeksem y, a w trzeciej umieszczamy wartości jeden. Jeśli wyznacznik macierzy jest równy zero, oznacza to, że punkty leżą na jednej prostej. Nie wiemy jednak, czy punkt C znajduje się między punktami A i B. Aby to sprawdzić, będziemy musieli porównać ich współrzędne.

RAlWZ0MqVnnZ9
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Jeśli sprawdzilibyśmy współrzędne punktów przedstawionych na rysunku, okazałoby się, że leżą one na jednej prostej – wyznacznik jest bowiem równy zero. Punkt C nie leży jednak na odcinku ograniczonym punktami A i B.

Wspomniana wcześniej macierz wygląda następująco:

AxAyjBxBykCxCym

Gdzie jako , podstawiamy wartości .

Wyznacznik macierzy możemy obliczyć, korzystając z następującego wzoru:

M=AIndeks dolny xBIndeks dolny ym + AIndeks dolny ykCIndeks dolny x + BIndeks dolny xCIndeks dolny yj − CIndeks dolny xBIndeks dolny yj − AIndeks dolny yBIndeks dolny xm − AIndeks dolny xCIndeks dolny yk,

gdzie M oznacza wyznacznik.

Przedstawiony wzór wynika z reguły (metody) Sarrusametoda Sarrusareguły (metody) Sarrusa.

Aby dowiedzieć się, czy punkt C jest umieszczony między punktami A i B (wiedząc, że A, B i C leżą na jednej prostej) należy sprawdzić, czy wszystkie współrzędne C leżą między współrzędnymi A i B.

W tym celu trzeba zadać pytania dwa pytania.

  1. Czy współrzędna CIndeks dolny x zawiera się w przedziale AIndeks dolny x, BIndeks dolny x?

  2. Czy współrzędna CIndeks dolny y zawiera się w przedziale AIndeks dolny y, BIndeks dolny y?

Jeśli obie odpowiedzi są twierdzące, punkt C leży między punktami A i B.

Algorytm opisany za pomocą pseudokodu:

Linia 1. Ax ← wprowadź liczbę rzeczywistą. Linia 2. Ay ← wprowadź liczbę rzeczywistą. Linia 3. Bx ← wprowadź liczbę rzeczywistą. Linia 4. By ← wprowadź liczbę rzeczywistą. Linia 5. Cx ← wprowadź liczbę rzeczywistą. Linia 6. Cy ← wprowadź liczbę rzeczywistą. Linia 8. M ← Ax asterysk By plus Ay asterysk Cx plus Bx asterysk Cy minus Cx asterysk By minus Ay asterysk Bx minus Ax asterysk Cy. Linia 10. jeżeli M znak równości 0 otwórz nawias ostrokątny span aria minus label znak równości cudzysłów dwukropek cudzysłów role znak równości cudzysłów math cudzysłów data minus editor minus tag znak równości cudzysłów latex cudzysłów data minus editor minus latex znak równości cudzysłów dwukropek cudzysłów zamknij nawias ostrokątny otwórz nawias ostrokątny script type znak równości cudzysłów math prawy ukośnik tex cudzysłów zamknij nawias ostrokątny dwukropek otwórz nawias ostrokątny prawy ukośnik script zamknij nawias ostrokątny otwórz nawias ostrokątny prawy ukośnik span zamknij nawias ostrokątny. Linia 11. jeżeli otwórz nawias okrągły otwórz nawias okrągły Bx zamknij nawias ostrokątny znak równości Cx zamknij nawias okrągły i otwórz nawias okrągły Ax otwórz nawias ostrokątny znak równości Cx zamknij nawias okrągły zamknij nawias okrągły lub otwórz nawias okrągły otwórz nawias okrągły Ax zamknij nawias ostrokątny znak równości Cx zamknij nawias okrągły i otwórz nawias okrągły Bx otwórz nawias ostrokątny znak równości Cx zamknij nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny span aria minus label znak równości cudzysłów dwukropek cudzysłów role znak równości cudzysłów math cudzysłów data minus editor minus tag znak równości cudzysłów latex cudzysłów data minus editor minus latex znak równości cudzysłów dwukropek cudzysłów zamknij nawias ostrokątny otwórz nawias ostrokątny script type znak równości cudzysłów math prawy ukośnik tex cudzysłów zamknij nawias ostrokątny dwukropek otwórz nawias ostrokątny prawy ukośnik script zamknij nawias ostrokątny otwórz nawias ostrokątny prawy ukośnik span zamknij nawias ostrokątny. Linia 12. jeżeli otwórz nawias okrągły otwórz nawias okrągły By zamknij nawias ostrokątny znak równości Cy zamknij nawias okrągły i otwórz nawias okrągły Ay otwórz nawias ostrokątny znak równości Cy zamknij nawias okrągły zamknij nawias okrągły lub otwórz nawias okrągły otwórz nawias okrągły Ay zamknij nawias ostrokątny znak równości Cy zamknij nawias okrągły i otwórz nawias okrągły By otwórz nawias ostrokątny znak równości Cy zamknij nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny span aria minus label znak równości cudzysłów dwukropek cudzysłów role znak równości cudzysłów math cudzysłów data minus editor minus tag znak równości cudzysłów latex cudzysłów data minus editor minus latex znak równości cudzysłów dwukropek cudzysłów zamknij nawias ostrokątny otwórz nawias ostrokątny script type znak równości cudzysłów math prawy ukośnik tex cudzysłów zamknij nawias ostrokątny dwukropek otwórz nawias ostrokątny prawy ukośnik script zamknij nawias ostrokątny otwórz nawias ostrokątny prawy ukośnik span zamknij nawias ostrokątny. Linia 13. zwróć prawdę. Linia 14. w przeciwnym wypadku zwróć fałsz. Linia 15. w przeciwnym wypadku zwróć fałsz. Linia 16. w przeciwnym wypadku zwróć fałsz.

Schemat blokowy prezentujący działanie algorytmu:

R1RzcRxbB0Y1W1
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Grafika przedstawia schemat blokowy, opisujący algorytm wykorzystywany do sprawdzania, czy punkt o określonych współrzędnych należy do odcinka o danych końcach. Najpierw obliczamy wyznacznik wspomnianej macierzy, aby sprawdzić, czy punkty leżą na jednej prostej. Jeśli okaże się, że tak nie jest, zwrócona zostaje wartość fałsz (punkty nie mogą wówczas leżeć na jednym odcinku).

Gdy punkty są umieszczone na jednej prostej, sprawdzamy, czy punkt C leży między punktami A i B. Robimy to w dwóch etapach, sprawdzając kolejno wartość dwóch wyrażeń warunkowych. Moglibyśmy zapisać wszystkie warunki w jednym bloku, jednak schemat byłby wówczas mniej czytelny. Z tego powodu powstały trzy bloki instrukcji warunkowych.

Słownik

macierz
macierz

wykorzystywana w matematyce metoda zapisu wyrażeń lub symboli w postaci tablicy złożonej z k kolumn i l wierszy

metoda Sarrusa
metoda Sarrusa

metoda wykorzystywana do obliczania wyznacznika macierzy stopnia trzeciego; nie może być ona używana do obliczania wyznaczników macierzy wyższych stopni

wyznacznik macierzy
wyznacznik macierzy

liczba, którą można przyporządkować macierzy kwadratowej dowolnego stopnia; każda macierz ma tylko jeden wyznacznik, zależny od wartości zapisanych w niej elementów