Как сделать словесный алгоритм
Обновлено: 07.07.2024
запись на псевдокоде — языке со свободным синтаксисом, близким к естественному языку (или языкам программирования). К достоинствам этого способа можно отнести краткость записи алгоритмов, возможность использования собственных символьных конструкций, естественность и простота описания логики решения задачи, возможность представления алгоритма с произвольной степенью детализации. Недостаток состоит в понятности такой записи лишь ограниченному кругу людей;
графическая запись в виде блок-схем получила наибольшее распространение. Такая запись характеризуется следующими достоинствами: использование графических символов, математических записей и записей на естественном языке, наглядность, использование простых правил описания последовательностей действий, понимание записи алгоритма любым человеком, знакомым с алгоритмами;
запись на языке программирования завершает процесс алгоритмизации реализацией соответствующей программы. Однако такая запись достаточно сложна для понимания практически любым человеком, кроме ограниченного круга людей (программистов), — в этом ее недостаток.
Практически любая команда может быть записана на естественном языке или псевдокоде, изображена графически или закодирована на языке программирования. При этом описание алгоритма в формульно-словесном виде является самым простым способом.
Пример. Необходимо составить алгоритм расчета стоимости пробега 100 км для автомобиля по следующим условиям.
Если автомобиль имеет дизельный двигатель, то цена топлива для него (дизельного топлива) составляет 16 руб. за литр, а его расход равен 7 л на 100 км; если автомобиль имеет бензиновый двигатель, то цена топлива для него (бензина) составляет 19 руб. за литр, а его расход равен 10 л на 100 км; если двигатель автомобиля работает на газу, то цена топлива для него (газа) составляет 9 руб. за литр, а его расход равен 11 л на 100 км.
Сначала сформулируем задачу в математическом виде:
где S — стоимость пробега 100 км автомобиля (руб.); D — тип двигателя.
Словесно-формульная запись алгоритма.
- 1. Ввести тип двигателя (D).
- 2. Если D — дизельный, то S = 16-7, перейти к п. 4.
- 3. Если D — бензиновый, то S = 19 • 10, иначе 5=9- 11.
- 4. Вывести рассчитанную стоимость пробега 100 км автомобиля (S).
При описании алгоритма подразумевается четкая логическая последовательность его пунктов по порядку, т.е. после п. 1 по умолчанию (при отсутствии каких-либо условий, например, как в п. 2) выполняется п. 2.
Согласно условиям задачи количество проверяемых типов двигателя ограничивается только тремя, поэтому в п. 3 если двигатель не является бензиновым, это значит, что он работает на газу.
При описании алгоритма графическим способом используются блок-схемы — системы связанных геометрических фигур. Каждая фигура обозначает один этап решения задачи и называется блоком. Порядок их выполнения указывается стрелками, соединяющими блоки. Обычно в схеме блоки располагают сверху вниз в порядке своего выполнения. При описании алгоритма в виде блок-схем используют стандартные геометрические фигуры (табл. 12.1).
Стандартные геометрические фигуры, используемые в блок-схемах
Начало и конец, вход и выход в подпрограммах
Ввод данных, вывод результатов выполнения действий
Вычислительное действие или их последовательность
Проверка условий, переход к действию по условию
Вернемся к нашему примеру расчета стоимости пробега автомобиля. Блок-схема алгоритма будет выглядеть следующим образом (рис. 12.1).
Рис. 12.1. Блок-схема алгоритма расчета стоимости пробега автомобиля
Конечно, запись алгоритма в виде блок-схем имеет преимущества перед словесно-формульной прежде всего своей наглядностью и понятностью (однако она не всегда оказывается компактной).
Словесный способ записи алгоритма отражает собой последовательность действий, необходимых для решения задачи, записанных на естественном языке в произвольном изложении.
Для примера рассмотрим словесную форму алгоритма нахождения наибольшего общего делителя двух натуральных чисел А и В:
- проверить числа на равенство. Если они равны, в качестве ответа можно взять любое из этих чисел, если нет, то продолжить выполнение алгоритма;
- определить, какое число больше - А или В;
- заменить число с предыдущего шага модулем разности чисел А и В;
В основе словесного способа записи алгоритмов лежат общепринятые средства общения между людьми. Запись такого алгоритма достаточно проста и понятна. Свое применение словесный способ находит на начальных этапах решения задачи.
Недостатки словесного метода:
- полное описание сложных алгоритмов является достаточно объемным;
- запись на естественном языке может являться причиной двусмысленности некоторых шагов алгоритма;
- при переходе к этапу программирования необходимо проводить дополнительную работу, которая заключается в формализации алгоритма [3, с.10-11].
Графический способ
Графический способ записи алгоритма отражает выполнение последовательности шагов в виде некоторого изображения. Подобную запись можно встретить на инструкциях по сборке чего-либо, на упаковках с едой и т.п. (см. рисунок 4) [13. с. 7].
Рисунок 4 - Графическая форма записи алгоритма
Рисунок 5 - Операторы блок-схем
В промышленных системах применяются особые виды графических схем:
- диаграммы - описывают какие-либо зависимости входных и выходных переменных, отражают пошаговый процесс выполнения процесса и т.п.;
- схемы блокировки - служат для изображения взаимосвязанности процессов включения/выключения (см. рисунок 6);
Рисунок 6 - Схема блокировки
структурные схемы - отражают структуру и описывают функционирование непрерывных систем (см. рисунок 7);
Рисунок 7 - Структурная схема
- графы автоматов - описывают дискретные состояния системы, а также возможные переходы между ними вместе с изменяющимися параметрами и условиями переходов между состояниями (см. рисунок 8);
Рисунок 8 - Граф автомата
- сети Петри - представляют собой аппарат для моделирования дискретных динамических систем. При помощи сетей Петри можно определить какие именно действия происходят в системе, какие состояния может принимать система после этих действий и т.п. [5, с.123].
Пример сети Петри приведен на рисунке 9;
Рисунок 9 - Сеть Петри
схемы работы - схемы, описывающие процессы, которые протекают линейно и соответствуют системам управления (см. рисунок 10) [3, с.16-18].
Рисунок 10 - Схема работы
Табличный способ
В табличной форме записи все шаги алгоритмов заносятся в таблицу, которая отражает изменение значений входных данных, а также промежуточных значений и результата.
В качестве примера рассмотрим табличную форму записи алгоритма нахождения площади прямоугольника. При этом входными данными являются длины сторон, а результатом - величина площади (см. таблицу 1) [13, с.7].
Схема — это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени — чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены ГОСТ и международными стандартами.
Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.
Содержание:
Элементы блок-схем алгоритмов
Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий. Пунктирная линия используется для соединения символа с комментарием. Сплошная линия отражает зависимости по управлению между символами и может снабжаться стрелкой. Стрелку можно не указывать при направлении дуги слева направо и сверху вниз. Согласно п. 4.2.4, линии должны подходить к символу слева, либо сверху, а исходить снизу, либо справа.
Есть и другие типы линий, используемые, например, для изображения блок-схем параллельных алгоритмов, но в текущей статье они, как и ряд специфических символов, не рассматриваются. Рассмотрены лишь основные символы, которых всегда достаточно студентам.
Примеры блок-схем
В качестве примеров, построены блок-схемы очень простых алгоритмов сортировки, при этом акцент сделан на различные реализации циклов, т.к. у студенты делают наибольшее число ошибок именно в этой части.
Сортировка вставками
Массив в алгоритме сортировки вставками разделяется на отсортированную и еще не обработанную части. Изначально отсортированная часть состоит из одного элемента, и постепенно увеличивается.
Блок-схема алгоритма сортировки вставками
В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (i Блок-схема алгоритма сортировки пузырьком
На блок-схеме показано использование символов начала и конца цикла. Условие внешнего цикла (А) проверяется в конце (с постусловием), он работает до тех пор, пока переменная hasSwapped имеет значение true. Внутренний цикл использует предусловие для перебора пар сравниваемых элементов. В случае, если элементы расположены в неправильном порядке, выполняется их перестановка посредством вызова внешней процедуры (swap). Для того, чтобы было понятно назначение внешней процедуры и порядок следования ее аргументов, необходимо писать комментарии. В случае, если функция возвращает значение, комментарий может быть написан к символу терминатору конца.
Сортировка выбором
В сортировке выбором массив разделяется на отсортированную и необработанную части. Изначально отсортированная часть пустая, но постепенно она увеличивается. Алгоритм производит поиск минимального элемента необработанной части и меняет его местами с первым элементом той же части, после чего считается, что первый элемент обработан (отсортированная часть увеличивается).
Блок-схема сортировки выбором
На блоге можно найти другие примеры блок-схем:
Часть студентов традиционно пытается рисовать блок-схемы в Microsoft Word, но это оказывается сложно и не удобно. Например, в MS Word нет стандартного блока для терминатора начала и конца алгоритма (прямоугольник со скругленными краями, а не овал). Наиболее удобными, на мой взгляд, являются утилиты MS Visio и yEd [5], обе они позволяют гораздо больше, чем строить блок-схемы (например рисовать диаграммы UML), но первая является платной и работает только под Windows, вторая бесплатная и кроссплатфомренная. Все блок-схемы в этой статье выполнены с использованием yEd.
Нужны ли блок-схемы? Альтернативы
Частные конторы никакие блок-схемы не используют, в книжках по алгоритмам [6] вместо них применяют словесное описание (псевдокод) как более краткую форму. Возможно блок-схемы применяют на государственных предприятиях, которые должны оформлять документацию согласно требованиям ЕСПД, но есть сомнения — даже для регистрации программы в Государственном реестре программ для ЭВМ никаких блок-схем не требуется.
Тем не менее, рисовать блок-схемы заставляют школьников (примеры из учебников ГОСТ не соответствуют) — выносят вопросы на государственные экзамены (ГИА и ЕГЭ), студентов — перед защитой диплом сдается на нормоконтроль, где проверяется соответствие схем стандартам.
Разработка блок-схем выполняется на этапах проектирования и документирования, согласно каскадной модели разработки ПО, которая сейчас почти не применяется, т.к. сопровождается большими рисками, связанными с ошибками на этапах проектирования.
Появляются подозрения, что система образования прогнила и отстала лет на 20, однако аналогичная проблема наблюдается и за рубежом. Международный стандарт ISO 5807:1985 мало чем отличается от ГОСТ 19.701-90, более нового стандарта за рубежом нет. Там же производится множество программ для выполнения этих самых схем — Dia, MS Visio, yEd, …, а значит списывать их не собираются. Вместо блок-схем иногда применяют диаграммы деятельности UML [6], однако удобнее они оказываются, разве что при изображении параллельных алгоритмов.
Периодически поднимается вопрос о том, что ни блок-схемы, ни UML не нужны, да и документация тоже не нужна. Об этом твердят программисты, придерживающиеся методологии экстремального программирования (XP) [7], ходя даже в их кругу нет единого мнения.
В ряде случаев, программирование невозможно без рисования блок-схем, т.к. это один процесс — существуют визуальные языки программирования, такие как ДРАКОН [8], кроме того, блок-схемы используются для верификации алгоритмов (формального доказательства их корректности) методом индуктивных утверждений Флойда [9].
В общем, единого мнения нет. Очевидно, есть области, в которых без чего-то типа блок-схем обойтись нельзя, но более гибкой альтернативы нет. Для формальной верификации необходимо рисовать подробные блок-схемы, но для проектирования и документирования такие схемы не нужны — я считаю разумным утверждение экстремальных программистов о том, что нужно рисовать лишь те схемы, которые помогают в работе и не требуют больших усилий для поддержания в актуальном состоянии [10].
Под алгоритмом, как правило, понимается точное предписание, которое задает вычислительный процесс, начинающийся из некоторой совокупности исходных данных и направленный на получение полностью определяемого исходными данными результата. Обосновывать принципы алгоритмизации целесообразно в рамках анализа свойств алгоритмов. Выделяют следующие свойства алгоритмов.
1. Дискретность – свойство, отражающее выполнение вычислительного процесса, задаваемого алгоритмом по шагам.
2. Детерминированность – свойство, означающее, что на каждом шаге любой полученный результат определяется результатами, полученными на предшествующих шагах.
3. Элементарность – свойство, согласно которому действие, которое выполняется на каждом шаге должно быть простым.
4. Направленность – свойство, обуславливающее необходимость указания, что является результатом того шага, на котором нельзя выполнить определенную в нем операцию.
5. Массовость – свойство, согласно которому алгоритм может быть применен к любой совокупности из допустимого множества исходных данных.
Одной и той же задаче может соответствовать множество алгоритмов, поэтому, для обоснования выбора одного из них для решения конкретной задачи, применяют совокупность показателей, основными из которых являются следующие.
1. Временная сложность – показатель, отражающий время выполнения алгоритма или количество шагов его выполнения.
2. Емкостная сложность – показатель, по которому производят оценку количества данных, необходимых для выполнения алгоритма.
3. Сложность описания – показатель, отражающий длину описания алгоритма, количество инструкций операторов.
Средства записи алгоритмов
Словесная запись алгоритмов
Характер языка, используемого для записи алгоритмов, определяется тем, для какого исполнителя предназначен алгоритм. Возможности исполнителя алгоритмов определяют уровень используемых языковых средств, т. е. степень детализации и формализации пред-писаний в алгоритмической записи. Если алгоритм предназначен для исполнителя-человека, то его запись может быть не полностью фор-мализована и детализирована, но должна оставаться понятной и корректной. Для записи таких алгоритмов может использоваться естественный язык. Для записи алгоритмов, предназначенных для исполнителей-автоматов, необходимы строгая формализация средств записи и определенная детализация алгоритмических предписаний. В таких случаях применяют специальные формализованные языки.
Поскольку одним из пользователей языка описания алгоритмов, так или иначе, остается человек, то, говоря об уровне языка, имеют в виду также и уровень его доступности для человека.
К настоящему времени в информатике сложились вполне определенные традиции в представлении алгоритмов.
Самой распространенной формой представления алгоритмов, адресуемых человеку, является обычная словесная запись. В этой форме могут быть выражены любые алгоритмы. Но если такой алгоритм предназначен для его дальнейшей реализации на вычислительном устройстве, то принято придерживаться более формализованного способа построения фраз с тщательно отобранным набором слов. Кроме того, необходимо указывать начало и конец алгоритма, отмечать момент ввода в вычислительное устройство значений исходных данных и вывода/печати полученного результата. В вычислительных алгоритмах широко используется общепринятая математическая символика, язык формул. Вводится необходимая в вычислительной практике операция присваивания: y:=A
х := sin a — присвоить переменной х значение синуса;
у := х — присвоить переменной у значение переменной х;
Z := 5,7 — считать значением переменной z число 5,7;
к := к + 1 — значение переменной к увеличить на единицу.
Введенные соглашения позволяют представлять словесные алгоритмы в компактной и наглядной форме.
Пример Составим алгоритм определения максимального числа из трех чисел: z = mах(а, b, с).
Изложенные рассуждения можно представить в виде следующей словесной записи алгоритма.
2. Если а > b, то z := а, иначе z := b.
3. Если с > z, то z := с.
Вычислительный процесс, который в зависимости от выполнения некоторых условий реализуется по одному из нескольких возможных, заранее предусмотренных направлений, называется разветвляющимся. Каждое отдельное направление называется ветвью вычислений. Выбор той или иной ветви осуществляется при выполнении алгоритма в результате проверки этих условий и определяется свойствами исходных данных и промежуточных результатов. При разработке алгоритма должны быть учтены все возможные ветви вычислений.
Схемы алгоритмов
| символ | название | интерпретация |
 | данные | данные, носитель данных не определён |
 | процесс | функция обработки данных любого вида (выполнение определённой операции или группы операций, приводящие к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться) |
 | предопределённый процесс | предопределённый процесс, состоящий из одной или нескольких операций или шагов, которые определены в другом месте (в подпрограмме, модуле) |
 | подготовка | модификация команды или группы команд с целью воздействия на некоторую последующую функцию |
 | решение | решение или функция переключательного типа, имеющая один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определённых внутри этого символа; соответствующие результаты вычислений могут быть записаны по соседству с линиями, отображающими эти пути |
 | граница цикла | начало и конец цикла; обе части имеют один и тот же идентификатор; условия инициализации, приращения, завершения, и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условия |
 | соединитель | выход в часть схемы и вход из другой части схемы; используется для обрыва линии и продолжении её в другом месте; соответствующие символы-соединители должны содержать одно и то же уникальное обозначение |
 | терминатор | вход из внешней среды и выход во внешнюю среду(начало и конец программы) |
| _______________ | линия | поток данных или управления; для направлений справа -налево и снизу-вверх добавляются стрелки |
| - - - - - - - - - - - - - - | пунктирная линия | используется для обведения аннотируемого участка |
| - - - - - - - - - [ | комментарий | пояснительные записи и примечания |
| ______ . . . _____ | пропуск | пропуск символа или группы символов, в которых не определены ни тип ни число символов; используется только в символах линии или между ними; служит для отображения общих решений с неизвестным числом повторений. |
Приведем основные свойства граф-схем.
1. Графическое представление.
2. Поддержка описания управляющей части алгоритма.
3. Возможность реализации синтаксического контроля.
4. Возможность проверки управляющей части алгоритма.
Пример 1 Рассмотрим задачу определения наибольшего общего делителя (НОД) двух целых положительных чисел М, N.
В математике известен алгоритм решения этой задачи — алгоритм Евклида, который заключается в последовательном делении сначала большего числа на меньшее, затем меньшего на полученный остаток, первого остатка на второй остаток и так до тех пор, пока в остатке не получится нуль. Последний по счету делитель и будет искомым результатом. Запишем алгоритм Евклида, рассматривая деление как много-кратное вычитание:
1) если числа равны между собой, то взять в качестве НОД любое из них;
2) если числа не равны между собой, то большее из чисел заменить их разностью и вернуться к шагу 1.
Алгоритм Евклида может быть представлен следующей словесной записью:
2. Пока М<>N выполнять:
если М> N, то М := М - N;
Блок-схема алгоритма Евклида представлена на блок-схеме 6.1, где блок 1 есть подготовка цикла, блок 2 — управление циклом, блоки 3, 4,5 - тело цикла (разветвляющаяся структура), из них блоки 4, 5 являются блоками модификации значений переменных цикла М и N
 |
Блок-схема алгоритма Евклида.
Блок-схемы являются исключительно простым и наглядным способом представления алгоритмов. Их очень полезно использовать при разработке общей структуры алгоритма, чтобы отчетливо представить себе алгоритм в целом и проследить все логические связи между его отдельными частями, проверить всели возможные варианты решения поставленной задачи нашли в нем отражение.
Блок-схемы не накладывают никаких ограничений на степень детализации в изображении алгоритма. Степень детализации определяется программистом. Однако следует помнить, что схемы общего характера малоинформативны, а излишне подробные схемы проигрывают в наглядности. При разработке сложных алгоритмов, чтобы понять сущность выполняемых действий и выявить основные связи, алгоритм записывается в виде общей схемы, состоящей из крупных блоков. Блоки соответствуют основным шагам алгоритма (вводу данных, обработке, выводу данных). Затем крупные блоки разбивают на более мелкие, составляя более детальные схемы, позволяющие проверить их логическую правильность.
Именно так мы поступили при разработке алгоритма Евклида, при этом использовали и словесную форму записи, и блок-схему.
ГОСТ 19.701—90 (ИСО 5807-85) предусматривает использование циклической структуры общего вида (безотносительно к типу цикла), представленной в таблице1 (границы цикла).Условие продолжения или окончания цикла может быть указано как в верхнем, так и в нижнем блоке. Ее применение целесообразно только в простых алгоритмах, в более сложных она теряется в общей структуре алгоритма ввиду отсутствия явной передачи управления.
Структурограммы
В практике структурного программирования для представления алгоритмов используются также структурограммы (схемы Насси — Шнейдермана). Этот способ позволяет изображать схему передач управления в алгоритме не с помощью явного указания линий потоков информации, а с помощью представления вложенности структур — функциональных блоков, которые используются для описания выполняемых действий.
1. Блок обработки (вычислений). Каждый блок является блоком обработки. Каждый прямоугольник внутри любого блока представляет собой также блок обработки.
| Вычислить у := sinх/( 1 +ах+Ьх 2 ) |
2. Блок следования. Этот блок объединяет ряд следующих друг за другом процессов обработки.
| у:=fl+sinx |
| z:=x 2 / 2+tgx |
3. Блок решения. Этот блок применяется для обозначения структуры ветвления. Условие располагается в верхнем треугольнике, варианты решения — по сторонам треугольника, процессы обработки — в нижних прямоугольниках. Если блок решения является сокращенным (отсутствует одна из ветвей), то структурограмма видоизменяется соответствующим образом.
4. Блок варианта реализует структуру многоальтернативного выбора. Варианты, которые можно сформулировать точно, размещаются слева, остальные объединяются в один, называемый выходом по несоблюдению условий, располагаемый справа. Правую часть можно оставить незаполненной или опустить.
5. Блок цикла с предусловием реализует циклическую структуру с проверкой условия в начале цикла. Условие продолжения цикла размещается в верхней полосе, сливающейся с левой, указывающей границу цикла. Данный блок может быть использован и для обозначения цикла с параметром, тогда вверху указывают закон изменения параметра цикла.
6. Блок цикла с постусловием аналогичен блоку цикла с предусловием, но условие окончания цикла располагают внизу. Каждый блок имеет форму прямоугольника и может быть вписан в любой внутренний прямоугольник любого другого блока. Блоки дополняются элементами словесной записи с использованием математической символики.
Читайте также: