Сохранение алгоритмов в виде блок-схемы

Сохранение алгоритмов в виде блок-схемы

Блок-схемы можно использовать для написания алгоритмов. Они представляют собой графическое представление действий, составляющих алгоритм. Подробнее о них можно узнать в электронном материале « Алгоритмы написания с блок-схемой».Открывается в новом окне.

Пример блок-схемы

Попробуем представить еще один алгоритм в виде блок-схемы. Предполагается описать способ проверки принадлежности точки с заданными координатами определенному отрезку.

Формальное изложение проблемы может выглядеть так:

Алгоритм проверки того, находится ли точка в двумерном декартовом пространстве на отрезке между двумя заданными точками.

Спецификация:

Данные:

• Ax– координата x точки, Aобозначающей первый конец отрезка; настоящий номер.

• Ay– координата y точки, Aобозначающей первый конец отрезка; настоящий номер.

• Bx– координата x точки, Bобозначающей другой конец отрезка; настоящий номер.

• By– координата y точки, Bобозначающей другой конец отрезка; настоящий номер.

• Cx– координата x точки C, принадлежность которой к отрезку ABпроверяется; настоящий номер.

• Cy– координата y точки C, принадлежность которой к отрезку ABпроверяется; настоящий номер.

Результат:

Алгоритм возвращает логическое значение prawda, если проверяемая точка принадлежит данному сегменту, или, в противном случае, возвращает логическое значение fałsz.

Чтобы проверить, лежат ли три точки на одной прямой , вычислите определитель матрицы, в которой первые два столбца являются координатами точек. В первом столбце будут компоненты координат, отмеченные индексом , во втором — индексом , а в третьем ставим значения единица. Если определитель матрицы равен нулю, то точки лежат на одной прямой. Однако мы не знаем, находится ли точка  между точками  и  . Чтобы проверить это, нам придется сравнить их координаты. xyCAB

Нажмите, чтобы начать предварительный просмотр

Источник: Contentplus.pl Sp. z o. o., лицензия: CC BY-SA 3.0.

Если бы мы проверили координаты точек, изображенных на рисунке, оказалось бы, что они лежат на одной прямой — ведь определитель равен нулю. Однако точка C не лежит на отрезке, ограниченном точками  A и  B.

Вышеупомянутая матрица выглядит следующим образом:

ИИксИуДжбИксбуксИкссум

тогда какДж,ки мподставляем значения1.

Определитель матрицы3×3мы можем рассчитать по следующей формуле:

M=AIndeks dolny x_x⋅BIndeks dolny y_y⋅m + AIndeks dolny y_y⋅k⋅CIndeks dolny x_x + BIndeks dolny x_x⋅CIndeks dolny y_y⋅j − CIndeks dolny x_x⋅BIndeks dolny y_y⋅j − AIndeks dolny y_y⋅BIndeks dolny x_x⋅m − AIndeks dolny x_x⋅CIndeks dolny y_y⋅k,

где M определитель.

Показанная формула следует из  правила (метода) Сарруса .

Чтобы узнать, C находится ли точка между точками A и  B (зная, что Aи B лежат  C на одной прямой), проверьте, что все координаты  C лежат между координатами  A и  B.

Для этого нужно задать два вопроса.

1. Находится ли координата  в диапазонеCIndeks dolny x_x⟨AIndeks dolny x_x, BIndeks dolny x_x⟩?

2. Находится ли координата в диапазонеCIndeks dolny y_y⟨AIndeks dolny y_y, BIndeks dolny y_y⟩?

Если оба ответа да, то точка C лежит между точками A и  B.

Алгоритм, описанный в псевдокоде:

Строка 1. Ax ← введите действительное число. Строка 2. Ay ← введите действительное число. Строка 3. Bx ← введите действительное число. Строка 4. В ← введите действительное число. Строка 5. Cx ← введите действительное число. Строка 6. Cy ← введите действительное число. Строка 8. M ← Ax звездочка By плюс Ay звездочка Cx плюс Bx звездочка Cy минус Cx звездочка By минус Ay звездочка Bx минус Ax звездочка Cy. Строка 10. если M равно 0 open chevron span aria минус метка равные кавычки двоеточие кавычки роль равные кавычки математические кавычки дата минус редактор минус тег равные кавычки латексные кавычки данные минус редактор минус латекс равные кавычки двоеточие кавычки закрыть шевроны открытые шевроны тип скрипта знак равенства кавычка математика обратная косая черта текс кавычка закрыть шеврон двоеточие открыть скобку шеврона правая косая черта script закрыть шеврон открыть шеврон правая косая черта span закрыть шеврон. Строка 11. кавычка закрыть шеврон двоеточие открыть шеврон правая косая черта сценарий закрыть шеврон открыть шеврон правая косая черта пролет закрыть шеврон. Строка 12. кавычка закрыть шеврон двоеточие открыть шеврон правая косая черта сценарий закрыть шеврон открыть шеврон правая косая черта пролет закрыть шеврон. Строка 13. вернуть истину. В противном случае строка 14 возвращает false. Строка 15 в противном случае возвращает false. В противном случае строка 16 возвращает false.

1

Axe ← введите реальное число

2

Ay ← введите реальное число

3

Bx ← введите действительное число

4

To ← введите реальное число

5

Cx ← введите реальное число

6

Cy ← введите реальное число

7

​

8

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

9

​

10

если М = 0:

11

если ((Bx = Cx) и (Ax = Cx) и (Bx

12

если ((By = Cy) и (Ay или ((Ay = Cy) и (By

13

вернуть правду

14

в противном случае вернуть ложь

15

в противном случае вернуть ложь

16

в противном случае вернуть ложь