9. Нелинейные алгоритмы. Блок-схемы

9. Нелинейные алгоритмы. Блок-схемы

 

«Налево пойдешь – коня потеряешь, направо пойдешь – жизнь потеряешь, прямо пойдешь – всё потеряешь.»
Надпись в углу палаты

Алгоритм — последовательность команд

Рассматривая различные программы и алгоритмы, мы могли видеть что каждая программа или алгоритм это просто набор команд, выстроенных в определенном порядке. Каждая команда при этом самодостаточна, то есть, в принципе может быть выполнена независимо от других команд. Кроме того, как правило, одиночные (элементарные) команды делаются максимально простыми — для удобства и универсализации: тогда их легче понять и удобнее комбинировать с другими командами для получения нужного результата. В результате комбинирования из таких простых команд мы можем получить алгоритмы любой сложности.

При этом важно понимать, что все команды в каждом алгоритме связаны между собой: каждая команда стоит на своем месте, и выполнение каждой новой команды начинается после выполнения предыдущей. Если этот порядок или связи нарушаются, алгоритм начинает работать по-другому. Да, он все равно будет работать, но результат выполнения будет уже другим. Вы сами можете поэкспериментировать с любым алгоритмом, меняя в нем порядок выполнения команд, и посмотреть, что получится в результате.

Нелинейные алгоритмы. Понятие перехода

Если рассматривать какую-то простую последовательность действий для решения очень простой задачи, то достаточно просто выполнить некоторые шаги. Например, мы хотим выпить чаю. Нам надо вскипятить воду в чайнике, а для этого нам необходимо выполнить ряд шагов:

  1. Взять чайник.
  2. Наполнить чайник водой.
  3. Поставить чайник на плиту.
  4. Включить газ.
  5. Зажечь газ.
  6. Дождаться закипания чайника.
  7. Выключить газ.
  8. Снять чайник с плиты.

Вроде бы всё просто. Но если мы задумаемся над большинством шагов, то поймём, что все они выполняются отнюдь не «в лоб». Например, простой шаг из этого алгоритма — наполнение чайника водой — сам по себе является очень сложным алгоритмом, состоящим из нескольких операций, а самое главное, требующим проверок при выполнении. Рассмотрим ситуацию, когда наш чайник уже находится под краном. Тогда нам нужно:

  1. Открыть кран на какую-то величину.
  2. Проверить уровень воды в чайнике…

Как проверить уровень воды? Очевидно, уровень воды должен находиться в каких-то разумных пределах, например, не менее 70% (разумеется, для различных чайников цифра может отличаться).

Следовательно, нам нужно выполнять проверку и по результатам этой проверки принимать решение: ждать дальше или закрывать водопроводный кран:

  1. Уровень воды больше 70%? Если ДА — переход к пункту №6, если НЕТ — переход к пункту №2.
  2. Открыть кран на какую-то величину.
  3. Ждать 1 секунду.
  4. Уровень воды больше 70%? Если ДА — переход к пункту №5, если НЕТ — переход к пункту №3.
  5. Закрыть кран.
  6. Чайник наполнен.

Мы видим, что даже такой простой процесс как наполнение чайника водой представляет собой довольно сложный алгоритм с проверкой условий. А самое главное — он выполняется уже не последовательно (как записано), а в порядке, задаваемом пунктами №1 и №4. В этих пунктах присутствуют команды, сообщающие, куда (к какой команде) надо переходить в соответствии с тем, выполнено проверяемое условие или нет.

Алгоритмы, в которых прямая последовательность выполнения команд (одна за другой) нарушается с помощью специальных команд, называются нелинейными.

Команды, изменяющие линейное выполнение алгоритмов, называются командами перехода.

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

Простейшим оператором перехода является команда прямого безусловного перехода GoTo, которая существует во многих языках программирования (хотя считается, и небезосновательно, довольно неудобной и «неправильной»). Эта команда полностью соответствует команде процессора «выполнить переход по адресу» (в языке ассемблера такая команда записывается как jmp или jamp — «прыжок» — с указанием адреса, куда нужно перейти).

На таких простейших операторах перехода — построена вся нелинейная логика любых программ: как бы ни были сложны алгоритмические структуры на уровне текста программы, в самом низу — на уровне процессора — они превращаются в простые операторы перехода.

Если в языке ассемблера в команде безусловного перехода указывается числовой адрес команды, куда нужно выполнить переход, то большинство более высокоуровневых языков использует номера строк в файле программы или метки. Использование номеров строк, так же как и адреса команды, не очень удобно, потому что при вставке строки кода нумерация строк и адрес команды могут сместиться. Поэтому самый удобный способ — использование меток, Которые в результате компиляции программы все равно превращаются в адрес.

Меткой называют специальную команду, содержащую некое уникальное имя. Это имя может быть расположено где-то в коде программы (в отдельной строке или в начале строки), и также, указывается в операторе GoTo чтобы при выполнении этого оператора программа перешла на строку, где стоит метка. Разумеется, в программе не может быть две метки с одинаковым именем.

«Неправильность» оператора GoTo связана с тем, что его применение способно «запутать» текст программы, сильно усложнить его восприятие и создать возможности для возникновения логических ошибок. Поэтому в настоящее время рекомендуется избегать этого оператора, используя другие, более логичные команды.

Кстати, линейные алгоритмы встречаются в программировании очень редко: подавляющее большинство алгоритмов — нелинейные.

Блок-схемы алгоритмов

Блок-схемы алгоритмов позволяют отобразить алгоритм графически, в частности, для лучшего понимания его структуры и работы.

Любой алгоритм, как и любая программа, обязательно должны где-то начинаться. Как правило, начало любой программы — это первая команда, которая выполняется. Также это может быть первая команда потока в многопоточной программе или первая команда отдельной подпрограммы (функции или процедуры).

Поэтому уместно отметить точку старта программы или отдельного блока (потока, подпрограммы и т.п.). Обычно в блок-схемах это овальный элемент со словом «Начало» (или «Start» или «Begin» — по-английски)

Точно так же, конец любой программы, подпрограммы или потока обозначается овальным элементом со словом «Конец» («End» или «Finish» — по-английски).

Любая команда или блок команд обозначается прямоугольником.

Внутри прямоугольника записывается суть выполняемой команды.

Все блоки программы связаны меду собой. Связь задается стрелками, обозначающими последовательность выполнения команд, обозначенных блоками.

Иногда на стрелках могут присутствовать информационные пометки.

Команды ввода-вывода (взаимодействия с внешним миром) обычно обозначаются параллелограммом со скошенными боковыми сторонами. Также ввод-вывод может обозначаться прямоугольным блоком с волнистой нижней стороной — как желтый блок в заголовке этой статьи.

Внутри блока указывается, что будет введено или выведено.

Команды проверки условия обозначаются ромбом с двумя (или более) выходящими из них стрелками.

Внутри блока записывается проверяемое условие.

Циклы в алгоритмах (о них мы узнаем чуть позже) обозначаются шестиугольниками.

Параметры цикла указываются внутри блока. Стрелки указывают на первую команду цикла и на конец цикла.

Обращения к подпрограммам (о них мы тоже поговорим чуть позже) обозначаются прямоугольниками, но с двойными боковыми сторонами.

Внутри блока указывается имя подпрограммы и передаваемые ей параметры.

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

Такие маркеры позволяют разделить блок-схему одного большого алгоритма на несколько маленьких фрагментов, сохранив при этом все связи.

Таким образом, простейший линейный алгоритм из Урока номер 2 «Алгоритмы и программы» мы можем изобразить в виде следующей блок-схемы:

Более сложный, нелинейный алгоритм с проверкой условия из того же урока — вот так:

А алгоритм проверки уровня воды в чайнике будет выглядеть вот так:

Двигаясь по стрелкам в этих блок-схемах и выполняя в уме (или на бумажке) команды можно понять, как работает данный алгоритм и что должно получиться в результате его работы.

Следует иметь в виду, что при написании кода создание блок-схемы алгоритма должно предшествовать написанию кода. Именно в процессе рисования блок-схемы вы сможете разобраться в алгоритме и понять, что и как должно работать, и как это правильно написать в коде программы.

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

Итак:

  1. Любой алгоритм, любая программа — это связанная последовательность простых команд, выполняющихся друг за другом в определенном порядке.
  2. Алгоритмы со строго последовательным выполнением команд называют линейными.
  3. Все остальные алгоритмы — нелинейные. Таких алгоритмов — большинство.
  4. Нелинейность алгоритмов обеспечивается командами перехода.
  5. Команды перехода меняют линейный порядок выполнения команд в алгоритмах.
  6. Для графического отображения алгоритмов используются блок-схемы алгоритмов, которые существенно упрощают восприятие алгоритмов.

На следующем занятии мы познакомимся с видами программных ошибок и способами борьбы с ними.


   10. Ошибки программ. Тестирование и отладка →


Оглавление


Поделиться: 

Мы используем cookie-файлы для наилучшего представления нашего сайта. Продолжая использовать rubasic.ru, вы соглашаетесь на использование файлов cookie.
Понятно