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

Для строгого задания различных структур данных и алгоритмов их обработки требуется иметь такую систему формальных обозначений и правил, чтобы смысл всякого используемого предписания трактовался точно и однозначно. Соответ­ствующие системы правил называют языками описаний. К средствам описания алгоритмов относятся следующие основные способы их представления: словесный, графический (блок-схема), псевдокоды, программный, диаграмма Несси—Шней­дермана (рис. 14.5).

Рис. 14.5. Способы представления алгоритмов

14.2.1. Словесный способ представления алгоритма

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

Рассмотрим понятие словесного представления алгоритма на примере нахож­дения произведения п натуральных чисел — факториала числа п (с = я!), то есть вычисления по формуле с = 1 х 2 х 3 х ... х п.

Этот процесс может быть записан в виде следующей последовательности шагов (инструкций, пунктов, указаний):

1. Присваиваем переменной с значение, равное единице, и переходим к следую­щему шагу.

2. Присваиваем переменной г значение, равное единице, и переходим к следующему шагу.

3. Вычисляем выражение г х с, полученное значение присваиваем переменной с и переходим к следующему шагу.

4. Проверяем, равно ли значение переменной г значению переменной п. Если г = я, то вычисления прекращаем. Если г < п, то увеличиваем г на единицу и переходим к шагу 3.

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

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

К недостаткам словесного способа записи можно отнести следующее:

□ полное подробное словесное описание алгоритма получается очень громоздким;

□ естественный язык допускает неоднозначность толкования инструкций;

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

По этим причинам словесный способ записи алгоритмов не получил широкого распространения.

14.2.2. Графический способ записи алгоритма

Запись алгоритма с помощью графических объектов в виде блок-схемы (ГОСТ 19.701-90, ИСО 5807-85) применяется довольно широко для представления про­стых алгоритмов небольшого размера. Однако по мере роста сложности отобража­емого фрагмента алгоритма (программы) его логическая структура перегружается деталями и связями («спагетти») и схема становится нечитабельной. По этой причине в настоящее время блок-схемы алгоритмов используются в основном для иллюстрации программ^[4].

При графическом представлении алгоритма с помощью схемы каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой (блоком) и дополняется элементом словесного описания. Блоки на схемах соединяются линиями потоков информации. Основное направление потока информации идет сверху вниз и слева направо (стрелки могут не указываться), снизу вверх и спра­ва налево (стрелки обязательны). Количество входящих линий для блока не ограничено. Выходящая линия должна быть одна (исключение составляет блок решения).

Основные элементы блок-схемы алгоритма приведены в табл. 14.2.

На рис. 14.6 в виде блок-схемы представлен алгоритм нахождения минималь­ного числа M в последовательности из п чисел а_и а₂,а_п (п * 0).

Рис. 14.6. Блок-схема алгоритма нахождения минимума в последовательности чисел

14.2.3. Представление алгоритма с помощью диаграммы Нэсси—Шнейдермана

Диаграмма Нэсси—Шнейдермана была предложена в сочетании со структур­ным программированием как средство борьбы с присущей схемам алгоритмов проблемой большого количества стрелок, отображающих передачу управления на другую часть программы (так называемого «спагетти-кода») . Эта диаграмма заменяет одномерное представление вложенных операторов двухмерным. Тем не менее и в этом случае по мере роста сложности программного кода проявляются проблемы отображения, поскольку элементы диаграммы быстро становятся все меньше и меньше.

На рис. 14.7 приведены составные элементы диаграммы Нэсси—Шнейдермана. На рис. 14.8 представлен алгоритм нахождения действительных корней ква­дратного уравнения ах² + Ьх + с = 0, представленный при помощи диаграммы Нэсси—Шнейдермана.

Заголовок программы

Программа

Тело программы

Простая конструкция

Рис. 14.7. Элементы диаграммы Нэсси—Шнейдермана

Рис. 14.8. Алгоритм, представленный при помощи диаграммы Нэсси—Шнейдермана

14.2.4. Представление алгоритма с помощью псевдокодов

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

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

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

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

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

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

Пример программы, записанной на алгоритмическом языке:

алг Сунна квадратов (арг цел п, рез цел 5) дано | п > О

надо j 5-11 + 2-2 + 3-3 + ... + п-п

нач

цел 7

ввод п; 5:==0 нц для 7 от 1 до л

5:=5 + 7 7 кц

вывод "5 = 5 кон

14.2.5. Программный способ представления алгоритмов

При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить ал­горитм. Однако на практике в качестве исполнителей алгоритмов используются компьютеры или иные вычислительные устройства (однокристальные микроЭВМ, промышленные компьютеры, технологические контроллеры и др.), поэтому алго­ритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполни­телем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.

В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения. В зависи­мости от степени детализации предписаний обычно определяется уровень языка программирования — чем язык менее детален, тем выше его уровень. По этому кри­терию можно выделить следующие уровни языков программирования (рис. 14.9) ^[5]I

□ машинно-ориентированные языки — машинные языки и языки ассемблера;

□ машинно-независимые языки — языки высокого уровня.

Рис. 14.9. Классификация языков программирования

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

Языки высокого уровня делятся на процедурные, логические и объектно-ориен- тированные.

□ Процедурные, или алгоритмические, языки (Basic, Pascal, С и др.) предназначены для однозначного описания алгоритмов в виде некоторой последовательности операторов языка.

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

□ Объектно-ориентированные языки (Object Pascal, С++, Java, С# и др.), в основе которых лежит понятие объекта, сочетают в себе данные и действия над ними. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче. Описание действитель­ности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.