Язык записи конечного алгоритма и язык разработки алгоритма

⇐ ПредыдущаяСтр 3 из 6Следующая ⇒

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

На последующих этапах в связи с большим пониманием решаемой задачи накапливаются новые факты и идеи, выявляются какие-то закономерности (например, замечается цикличность = повторяемость действий) в будущем алгоритме. Использование естественного языка приводит к громоздким формулировкам и резкому увеличению размеров текста (для описания циклических алгоритмов, например), в связи с чем возникает необходимость использовать новый (более формальный) язык. Такой язык часто является всего лишь расширением естественного языка и позволяет кроме слов и фраз обычного языка использовать математические символы и формулы для компактной записи твердо установленных фактов и найденных закономерностей. В качестве такого языка часто используется так называемый псевдокод (язык Ершова = школьный алгоритмический язык).

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

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

Требования к языку разработки алгоритмов:

· он должен позволять записывать алгоритм на разных этапах детализации;

· он не должен допускать потери элементов структуры, введенных на предыдущих этапах;

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

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

4.2 Классификация алгоритмов.

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

характера задач, для решения которых предназначается алгоритм.

структуры алгоритма.

1).Классификация алгоритмов по характеру решения задач.

Эта классификация делит алгоритмы на:

- нечисловые (в том числе переборные, задачи оптимизации);

- вычислительные (численные расчеты).

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

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

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

2)Классификация алгоритмов по их структуре.

Эта классификация делит алгоритмы на:

- линейные;

- разветвляющиеся;

- циклические.

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

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

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

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

На начальных этапах разработки решения задачи имеется только примерный перечень действий и примерный порядок их выполнения (друг за другом) и еще не выделены возможные ситуации, возникающие при выполнении алгоритма, соответственно схема алгоритма не будет содержать развилок (блоков принятия решений) при наступлении/не наступлении этих ситуаций. Поэтому первоначальный алгоритм решения задачи обычно можно представить в виде следующей линейной схемы (см. ниже Рисунок 1), в которой отдельные этапы вычислений должны выполняться последовательно друг за другом. При исполнении алгоритма блоки выполняются в порядке их записи. Такие алгоритмы, в которых отсутствует анализ возможных ситуаций, называются линейными. Для построения таких алгоритмов в основном используется фигура «Процесс» (в виде прямоугольника) и «Ввод-вывод» (в виде параллелограмма) и в целом получается структура алгоритма типа следования.

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

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

≡ begin

≡ Readln(A);

Задать начальное значение

≡ B: =10;

≡ C: =A+B;

≡ Writeln(С);

≡ end.

Рисунок 1 Линейные алгоритм

if (логическое выражение)

then

Описание ситуации

Действие1

else

Действие2

Да Нет

Действие2

Действие1

Рисунок 2 Разветвления в алгоритме

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

значение Селектора, соответствующее Варианту1

При дальнейшем уточнении алгоритма может оказаться, что:

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

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

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

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

label cycl; Var i: word; s: real; x: array[1..8] of real; begin {ввод значений X} i: =0; s: =0; cycl: if i < 8 then begin i: = i + 1; S: =S+X_i; goto cycl; end; ……….

i: = 0

метка

S: = 0

тело цикла

cycl:

Да

петля (возврат назад)

i: = i + 1; S: =S+X_i;

Нет

Рисунок 3 Циклический алгоритм (неправильное изображение - переходы снизу вверх запрещены )

На рисунке выше в схеме алгоритма и в программе цикл задается неявно (goto вверх).

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

. Для i от 1 до 8 повторить

Пока i< =8 повторить

While

for 1 1

1 ситуация

Метка цикла

продолжения

тело цикла

1 ситуация пока не i > 8

завершения repeat

1 1

В качестве метки цикла часто используется просто некоторое число (может показывать уровень вложенности цикла).

Исходя из этого правильная запись цикла, приведенного выше, будет такая:

То же самое для циклов с неизвестным числом повторений: цикл while i: = 0; s: = 0; while i< 8 do begin i: =i+1; S: =S+x[i]; end; цикл repeat...until: i: = 0; s: = 0; repeat i: =i+1; S: =S+x[i]; until i = 8 do

S: =0

для i от 1 до 8

повторять S: =0;

for i: = 1 to 8 do

S: =S+x[i]

S: =S+x[i];

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

Пусть необходимо в трех разных местах программы сложить элементы трех разных массивов:

Пусть все три массива одного типа:

type

t = array[1..50] on integer;

var

x, y, z: t;

Нам потребуется подпрограмма-процедура:

procedure sum(n: integer; {число суммируемых элементов массива}

a: t; {имя массива, чьи элементы суммируются}

Var S: longint; {результат - сумма});

var

i: word; {параметр-счетчик цикла for}

begin

s: = 0;

for i: =1 to n do

s: = s + a[i];

end;

С использованием такой подпрограммы сложение элементов разных массивов в трех разных местах программы можно оформить как три вызова подпрограммы-процедурыследующим способом:

...............

...sum(8, x, s1); --> будет вызвана sum и s1 получит значение суммы 8 элементов массива X.

фактические параметры вызова

...............

... sum(10, y, s2);

..............

... sum(25, z, s3);

..............

Для вызова подпрограмм в схеме алгоритма используется блок вида

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

Разрыв Возврат

(переход на с другой

другую страницу) страницы

⇐ Предыдущая 1 234 5 6 Следующая ⇒