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:

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

Ilustracja przedstawia prostą, na której umieszczono trzy zielone punkty: A, B i C.
Punkt A znajduje się na początku prostej.
Punkt B znajduje się na około jednej czwartej długości prostej.
Punkt C znajduje się na końcu prostej.

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:

Gdzie jako $j$, $k$ i $m$ podstawiamy wartości $1$.

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

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 xx zawiera się w przedziale $\langle$AIndeks dolny xx, BIndeks dolny xx$\rangle$?

2. Czy współrzędna CIndeks dolny yy zawiera się w przedziale $\langle$AIndeks dolny yy, BIndeks dolny yy$\rangle$?

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

Algorytm opisany za pomocą pseudokodu:

Ax ← wprowadź liczbę rzeczywistą
Ay ← wprowadź liczbę rzeczywistą
Bx ← wprowadź liczbę rzeczywistą
By ← wprowadź liczbę rzeczywistą
Cx ← wprowadź liczbę rzeczywistą
Cy ← wprowadź liczbę rzeczywistą

M ← Ax * By + Ay * Cx + Bx * Cy - Cx * By - Ay * Bx - Ax * Cy

jeżeli M = 0$:$
	jeżeli ((Bx >= Cx) i (Ax <= Cx)) lub ((Ax >= Cx) i (Bx <= Cx))$:$
		jeżeli ((By >= Cy) i (Ay <= Cy)) lub ((Ay >= Cy) i (By <= Cy))$:$
			zwróć prawdę
		w przeciwnym wypadku zwróć fałsz
	w przeciwnym wypadku zwróć fałsz
w przeciwnym wypadku zwróć fałsz

Schemat blokowy prezentujący działanie algorytmu:

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