16. Способы записи алгоритмов

На данном уроке рассматриваются разные способы представления алгоритмов: словесный, табличный, графический и запись на алгоритмическом языке. Посмотрев урок, вы поймёте, как структурируются шаги алгоритма, какие блоки используются для обозначения действий и проверки условий в графическом представлении алгоритмов. Вы узнаете, как записать один и тот же алгоритм в разных формах, научитесь преобразовывать алгоритм из одной формы в другую.

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

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

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

Но если вы в ресторане заказали салат и он вам понравился, то вы уверены, что, придя в этот же ресторан через неделю, будете есть точно такое же по вкусу блюдо. Более того, если это сетевой ресторан, то, оказавшись в другом филиале (даже если он в другом городе), вы будете есть точно такой же салат.

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

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

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

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

Кроме того, необходимо уметь записывать алгоритм на таком языке, который будет понятен исполнителю. Вспомните, вы наверняка видели примеры хороших, чётких инструкций и тех, по которым сложно что-либо сделать (рис. 4). В то же время понятная вам инструкция с картинками будет абсолютно непонятной, скажем, для компьютера. А вот понятную ему систему команд в программе вряд ли поймёте вы (рис. 5).

Приведём некоторые примеры алгоритмов из реальной жизни:

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

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

1. При поступлении в Домашнюю школу «ИнтернетУрок» ученик проходит несколько этапов зачисления согласно утверждённому процессу, который описан в интерактивной схеме зачисления (ИСЗ).

1. Журналист в профессиональной деятельности тоже использует определённый алгоритм: сбор материалов, написание статьи, несколько согласований, отправка в печать.

1. В медицинской практике при проведении какой-либо процедуры (например, хирургической операции) доктор обязан выполнять пошагово алгоритм, который, как правило, записывается ещё до начала проведения процедуры (существует даже понятие «медицинский алгоритм»).

Это примеры использования алгоритмов исполнителем «человек».

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

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

Точная запись действий не позволит исполнителю произвольно трактовать команды.

Для формальных исполнителей каждое действие должно быть однозначно определено и понятно.

Неформальный исполнитель сможет быстрее получить результат, если в записи алгоритма будут соблюдаться определённые правила и единообразие.

Составленный, записанный и сохранённый алгоритм при необходимости может быть неоднократно выполнен как самим разработчиком, так и другим исполнителем, в том числе формальным.

Как же записать алгоритм?

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

Самый очевидный и простой способ — записать алгоритм словами.

Словесная форма (построчная запись) — запись алгоритма на естественном языке, в которой все шаги алгоритма пронумерованы и записываются с новой строки.

Строго следуя инструкциям алгоритма, записанного в словесной форме, человек может получить верный результат, даже если алгоритм выполняется им впервые.

Примеры алгоритмов, которые вам, вероятно, приходилось выполнять.

«Упражнение для глаз».

1. Плотно закрыть глаза.

2. Сосчитать до трёх.

3. Широко раскрыть глаза.

4. Сосчитать до трёх.

5. Действия 1–4 повторить 5 раз.

Другой пример — «Построение правильного многоугольника» (рис. 13).

1. С помощью циркуля построить окружность.

2. Вычислить , разделив на количество углов в многоугольнике.

3. Из центра окружности под углом относительно друг друга провести лучи, пересекающие окружность.

4. Соединить точки пересечения.

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

Словесно-формульное описание — это описание на естественном языке с использованием математических формул.

Например, решение квадратного уравнения.

1. Привести уравнение к виду .

2. Определить значения коэффициентов , , .

3. Вычислить дискриминант .

4. Если дискриминант больше нуля, то вычислить корни уравнения по формуле .

5. Если дискриминант равен нулю, то вычислить единственный корень уравнения по формуле .

6. Если дискриминант меньше нуля, то записать в ответ, что действительных корней нет.

Разберём на примерах:

1. Уравнение .

Решение по алгоритму:

2. , ,

Ответ: ; .

2. Уравнение .

Решение по алгоритму:

2. , ,

Ответ: .

3. Уравнение .

Решение по алгоритму:

1. .

2. , ,

Ответ: действительных корней нет.

Построение таблицы — один из самых универсальных и распространённых, а также наглядных методов для решения некоторых задач.

Давайте представим, что ваши родители хотят накопить определённую сумму денег на отпуск. Наверняка первое, что они сделают, — это составят таблицу доходов и расходов семьи (рис. 14). Далее по этой таблице можно вычислить месячный баланс денежных средств, а также проанализировать категории расходов. Затем можно вычислить, какую сумму реально откладывать ежемесячно, а при необходимости определить, какие статьи расходов могут быть скорректированы для ускорения роста накоплений.

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

Представим, что есть -литровая ёмкость, которая заполнена раствором, необходимым для проведения отделочных работ. Требуется разлить раствор поровну с помощью двух вёдер вместимостью литров и литра. Решение такой задачи может быть представлено в виде таблицы.

Повторить информацию о табличной форме записи плана действий можно, посмотрев материалы урока «Табличная форма записи плана действий».

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

Рассмотрим табличный способ записи алгоритма решения простой арифметической задачи.

Задача.

Коля и Петя вместе с бабушкой собирали грибы. В результате у бабушки в корзине оказалось грибов, у Коли — грибов, у Пети — грибов. Бабушка переложила из своей корзины по грибов в корзину каждого внука. Затем Коля выбросил червивых гриба из своей корзины. После этого мальчики решили свои грибы нести в одной корзине, и Петя переложил собранные им грибы в корзину Коли. На сколько меньше грибов оказалось в корзине бабушки, чем в корзине мальчиков?

Разумеется, такую задачу вы можете решить по действиям и, возможно, даже в уме. Но сегодня мы говорим о способах записи алгоритмов. Алгоритм решения задачи можно представить в виде таблицы (табл. 1). Количество грибов в корзинах бабушки, Коли и Пети на каждом шаге алгоритма будем отображать в виде значений столбцов, которые обозначим , и соответственно. Сначала в столбцах , и запишем исходные данные.

На 1-м шаге в корзине бабушки становится на грибов меньше, а в корзине Коли — на грибов больше.

На 2-м шаге выполняется аналогичная операция, только количество грибов увеличивается в корзине Пети.

На 3-м шаге значение столбца уменьшается на (Коля выбросил гриба).

Затем Петя перекладывает грибы из своей корзины в корзину Коли, то есть в столбце записываем — сумму и , а в столбце записываем .

Табл. 1. Алгоритм решения задачи в виде таблицы

В теории алгоритмов и программировании подобные таблицы называют трассировочными (от французского tracer — отследить). В них отражаются значения переменных на каждом шаге выполнения алгоритма. О таких таблицах мы ещё будем говорить на одном из уроков.

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

Закончим решение задачи. Для этого найдём разность и . Получаем , то есть в корзине бабушки оказалось на грибов меньше, чем в корзине мальчиков.

Ещё один удобный и наглядный способ записи алгоритма — графический.

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

Ранее мы рассмотрели алгоритм выполнения гимнастики для глаз и записали его словами. Если этот алгоритм выразить в виде изображений, то получится графический алгоритм.

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

Также, например, вы можете вспомнить изображение схемы эвакуации (рис. 18), которая есть практически во всех организациях. На ней наглядно представлен маршрут выхода из здания в случае пожара — по своей сути тоже алгоритм.

Считается, что человек лучше всего воспринимает именно графическую информацию, не зря история передачи информации началась с наскальной живописи (рис. 19а), а первая письменность в истории человечества была иероглифической (рис. 19б). Вот почему наиболее важные алгоритмы представлены именно в графическом виде, чтобы человек, даже не владеющий языком страны, мог без труда разобраться, что и как ему делать (рис. 19в).

В начальной школе графически нередко описываются вычислительные алгоритмы.

Допустим, что уменьшаемое, вычитаемое и разность обозначены графическими объектами — квадратом, треугольником и ромбом соответственно:

Тогда алгоритм нахождения уменьшаемого может быть записан следующим образом:

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

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

Каждая геометрическая фигура используется для обозначения определённого действия (рис. 20):

• овал обозначает начало и конец алгоритма;

• параллелограмм — ввод и вывод данных;

• в прямоугольнике записывается действие или описывается какой-то процесс;

• ромб используется для проверки условия;

• шестиугольник начинает блок действий (его называют «модификация»), которые выполняются в алгоритме несколько раз.

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

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

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

На рисунке 22 представлен пример: блок-схема алгоритма Евклида. Более подробно узнать об этом алгоритме можно в уроке алгебры.

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

А сейчас попробуем прочитать блок-схему на рисунке 23 и понять, какой алгоритм в неё заложен.

В начале мы видим, что алгоритм ожидает ввода некоего значения .

Далее идёт проверка — число больше и меньше или нет. Для нас это означает, что алгоритм проверит, является ли число трёхзначным.

Если является, то в переменные , и записываются цифры этого трёхзначного числа.

Цифру сотен мы получаем с помощью целочисленного деления числа на . В программировании, как правило, целочисленное деление обозначается с помощью знака //.

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

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

Представим, что мы ввели трёхзначное число . При делении нацело на получим .

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

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

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

Таким образом пользователь увидит запись числа в перевёрнутом виде. Обратите внимание, что все эти вычисления производятся только тогда, когда исходное число трёхзначное (рис. 24). Если же нет, то алгоритм просто завершится.

Мы чуть раньше рассмотрели алгоритм нахождения корней квадратного уравнения. Давайте изобразим его в виде блок-схемы.

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

Далее вычислим дискриминант. Вычисление поместим внутрь прямоугольника, что означает «Действие». После этого возможны варианты. Каждый из них нужно поместить в свой ромб.

Первая проверка условия — дискриминант больше нуля. В этом случае вычисляем корни по формуле в блоке «Действие».

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

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

Мы проверили, равен ли дискриминант нулю или он больше нуля. Если ни одно из этих условий не оказалось истинным, то единственный вариант, который остаётся, — это когда дискриминант меньше нуля. Для этого случая отдельную проверку организовывать нет смысла, действуем методом исключения и выводим на экран фразу «Действительных корней нет».

В программировании блок-схема — это стандарт способа записи алгоритма для решения задачи. Перед непосредственным написанием кода на этапе проектирования программы сначала создаётся именно его графическая форма, блок-схема. Далее она анализируется на предмет правильности составленного решения, и только после этого программист может начать реализовывать этот алгоритм на языке программирования.

В дополнение можно рассмотреть пример блок-схемы решения задачи из реальной жизни.

Представим ситуацию, что в магазине нужно купить определённый набор товаров согласно списку покупок (рис. 27). Мама выделяет вам нужную сумму денег и даёт список. Если после покупки остаётся сдача, вы можете купить себе к чаю любимое печенье. Представим этот алгоритм в виде блок-схемы (рис. 28).

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

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

Рассмотренные сегодня примеры алгоритмов предназначались для исполнителя «человек», поэтому какие-то слова в словесном описании алгоритма могли быть заменены синонимами. Слово «умножить», знаки «*» и «⋅» понимаются человеком как одно и то же действие.

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

В таком случае алгоритм записывается на формальном языке, который «понимает» исполнитель.

Алгоритмические языки — формальные языки для записи алгоритмов.

Программа — алгоритм, записанный на языке, понятном исполнителю.

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

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

Любой формальный язык, в том числе алгоритмический, включает:

• алфавит — набор используемых символов;

• синтаксис — систему правил для записи алгоритмических конструкций;

• семантику — систему правил, определяющую смысл конструкций языка.

Структура алгоритма, записанного на школьном алгоритмическом языке, в общем виде выглядит так:

• Сначала записывается служебное слово алг (алгоритм), затем указывается название алгоритма.

• После — нач (начало алгоритма).

• Затем — команды, которые последовательно выполняются в алгоритме.

• Завершается алгоритм служебным словом кон (конец).

То есть структура алгоритма на школьном алгоритмическом языке выглядит так:

алг название

нач

команды

кон

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

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

• Заголовок алгоритма.

• Начало.

• Описание имён и типа переменных, используемых в алгоритме.

• Ввод исходных данных, а именно — коэффициентов квадратного уравнения.

• Вычисление дискриминанта.

• Проверка, получится ли дискриминант больше нуля. Вычисление корней уравнения и вывод на экран.

• Если дискриминант не больше нуля, то проверка его на равенство нулю. Если равен, то вычисление корня и вывод его на экран, иначе — вывод пользователю сообщения «Действительных корней нет».

• Конец алгоритма.

Запись алгоритма на школьном алгоритмическом языке выглядит так:

алг Квадратное_уравнение

нач

цел , ,

вещ , ,

ввод , ,

если

   то

       вывод

       вывод

       вывод

иначе

          если

            то

                вывод

             иначе

                 вывод (\"Действительных корней нет\")

             все

все

кон

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

Исполнитель Робот имеет следующую систему команд: «влево», «вправо», «вверх», «вниз», «закрасить».

При выполнении этого алгоритма в среде исполнителя и указанном начальном положении Робота закрашиваются клетки поля вокруг фигуры.

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

Между служебными словами нач (начало) и кон (конец) записываем команды из системы команд исполнителя Робот.

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

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

использовать Робот

алг Фигура

нач

• закрасить

• вверх

• закрасить

• вправо

• закрасить

• вверх

• закрасить

• вправо

• закрасить

• вправо

• закрасить

• вниз

• закрасить

• вправо

• закрасить

• вниз

• закрасить

• вниз

• закрасить

• влево

• закрасить

• влево

• закрасить

• влево

• закрасить

• влево

• закрасить

кон

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

Полезные ссылки

1. Список рекомендованных учебников

2. РОССИЙСКАЯ ЭЛЕКТРОННАЯ ШКОЛА. Информатика. 8 класс. Урок 7. Исполнители и алгоритмы. Способы записи алгоритма

Проверь себя

1. Какие существуют способы записи алгоритма?

2. Приведите примеры алгоритмов, с которыми вы сталкиваетесь в реальной жизни.

3. Что такое блок-схема и для чего она используется?

4. В чём преимущество графической формы записи алгоритма?

5. Разработайте блок схему решения уравнения для любых значений и , введённых в клавиатуры, при условии, что на делить нельзя.

6. Напишите программу решения уравнения на алгоритмическом языке.

Список использованных источников:

Изображения используются согласно лицензии Shutterstock / FOTODOM
Иллюстратор Гусева Н. С.