Разработка алгоритмов и проектирование программ

Формы представления алгоритмов

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

Основными способами записи алгоритмов являются:

• — формульно-словесный;
• — графический;
• — на языке программирования (на формальном языке);
• — псевдокод (алгоритмический язык).

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

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

Пример 10.1. Записать в словесно-формульной форме алгоритм решения уравнения ах + b = 0 с произвольными целочисленными коэффициентами.

Решение. Алгоритм можно записать в следующем виде.

• 1. Задать начальные целые значения коэффициентов а, 6.
• 2. Если а 0, то перейти к шагу 3, иначе перейти к шагу 4.
• 3. Решением будет значение х = b/а. Перейти к шагу 5.
• 4. Если Ь = 0, то решением будет любое число, иначе решений нет.
• 5. Закончить алгоритм.

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

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

Блок-схема представляет собой набор графических элементов (называемых так же блоками или символами), которые связаны между собой соединительными линиями. В настоящее время в Российской Федерации действует ГОСТ 19.701−90 «Схемы алгоритмов, программ, данных и систем», согласно которому следует оформлять блоксхемы. Основные блоки, указанные в этом стандарте, приведены в табл. 10.1.

Таблица 10.1

Основные блоки, используелте в блок-схемах

Блок «Терминатор», называемый также блоком «пуск-остановка», предназначен для указания начата и конца алгоритма. В блок помещается соответствующий текст.

(«Начало» или «Конец»). Начальный блок не имеет входа, но имеет выход, конечный блок имеет вход, но нс имеет выхода.

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

Блок «Данные» отображает данные для произвольного носителя. Часто кроме самих данных в блоке указывается и операция над ними, например, «Ввод массива», «Вывод Х, Х2». Блок имеет ровно один вход и ровно один выход.

Блок «Процесс» предназначен для указания обработки данных (изменение значения, формы). Текст блока может включать как конструкции формульно-словесной записи, например, «Объединить массивы», так и чисто математические формулы или операторы языка программирования (например, «5 = /х + 2», «s:=sqrt (2)»). Блок имеет ровно один вход и ровно один выход.

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

Блок «Предопределенный процесс» указывает совокупность операций (шагов алгоритма, вычислений и т. д.), описанных в другом месте (модуле, подпрограмме). Блок имеет ровно один вход и ровно один выход.

Блок «Граница цикла» состоит из двух графических объектов, между которыми располагаются другие блоки, составляющие тело цикла. В зависимости от того, какая циклическая конструкция описывается (см. параграф 10.2), текст в каждом графическом объекте может быть различен. Так, для цикла с параметром верхний блок может содержать «г = 0,20; 2» (изменять значение параметра г от значения 0 до значения 20 с шагом 2), а нижний блок — текст «г», указывающий на завершение циклической конструкции. Для цикла с постусловием верхний блок может, например, содержать текст «j» (начало цикла), а нижний блок — «j > 15» (условие завершения цикла). Блок имеет ровно один вход и ровно один выход.

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

Пример 10.2. Записать алгоритм задачи из предыдущего примера в виде блок-схемы. Решение. Алгоритм приведен на рис. 10.1. ?

Рис. 10.1. Блок-схема задачи примера 10.1.

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

Решение. Часть алоритма, в котором реализована задача, приведена на рис. 10.2. ?

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

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

Рис. 10.2. Блок-схема задачи примера 10.3.

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

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

В настоящее время используется достаточно большое количество языков программирования, каждый из которых имеет свою специфику. В основном, они отличаются синтаксисом (правилами образования языковых конструкций) и семантикой (смысловым значением языковых конструкций). К наиболее популярным языкам можно отнести С (Сн—h, С#), Java, РНР, Visual Basic, Pascal.

Пример 10.4. Записать на языке программирования алгоритм из примера 10.1.

Решение. Алгоритм, записанный в виде блок-схемы в предыдущем примере, приведен ниже в виде программы на языке Pascal.

Program uravnenie ;

Var.

a, b, x:real; begin.

write (' Введите коэффициента: _w '); Readln (a); write (' Введите коэффициент^: _w '); Readln (b); i f a=0 then.

if b=0 then writcln ('x_w—^^Tiio6oe_w4na40 ') else writeln (⁵ Решений «пет ') else begin.

x:=—b/a;

writcln ('Одно^решение: _wx= ', x: 5: 2); end; end.

В текстовых строках программы дополнительно обозначены пробелы. ?

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

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

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

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

менее выразителен, чем на языке Pascal:

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

Пример 10.5. Записать алгоритм из примера 10.1 в виде псевдокода.

Решение. Один из возможных вариантов алгоритма приведен ниже, алг уравнение вещ а, Ь, х нач ввод а, Ь если а=0 то если Ь=0.

то вывод «х — любое» иначе вывод «решений нет» если-все иначе х:=-Ь/а вывод х если-все кон ?

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