Структуры алгоритмов

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

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

Рассмотрим составление схем алгоритмов:

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

Алгоритм разветвленной структуры (ветвление). Это такая схема, в которой предусмотрено разветвление указанной последовательности действий на два направления в зависимости от итога проверки заданного условия.

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

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

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

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

При исполнении алгоритма переработка информации состоит в изменении значений некоторых величин, с которыми работает алгоритм. Величины можно разбить на постоянные и переменные. Значения постоянных величин остаются неизменными в процессе исполнения алгоритма, а значения переменных изменяются. С величиной помимо значения связано также имя, используемое для обозначения. В качестве имени используется идентификатор, т. е. последовательность букв и цифр, начинающаяся с буквы, например x, x1, alfa, b12c и т. п.

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

< идентификатор > := < выражение >

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

функциональный блок:

Например, команда x:=1; означает, что переменной x присваивается значение 1, а команда y:=y+1; - что переменной y присваивается значение, которое на 1 больше ее прежнего значения.

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

ввод( x, y); означает, что исполнитель должен задать значения, которые должны быть присвоены переменным x и y.

Аналогичная команда вывода:

вывод( x, y); означает, что исполнитель должен выдать для обозрения значения величин x и y (отображение информации).

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

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

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

В общем виде команда следования может быть представлена так:

начало < действие > ; <действие > ; ... ; < действие > конец

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

В дальнейшем будет использоваться запись команд в столбец.

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

Команда следования:

Псевдокод	Паскаль
начало ввод(x); y:=x^2+5; z:=  x^2+y^2 конец	BEGIN WRITELN('ЗАДАТЬ ЛЮБЫЕ ЗНАЧЕНИЯ Х И Y'); READLN(X,Y); Y:=SQR(X)+5; Z:=SQRT(X)+SQR(Y) END.

Схема команды следования:

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

На псевдокоде и Паскале эта команда в общем виде записывается так:

Псевдокод	Паскаль
если < условие> то <действие 1> иначе < действие 2> все	IF< логическое выражение > THEN <действие 1> ELSE < действие 2>;

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

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

Рассмотрим вычисление значения y:

x² , при x<0

y =

x+1 , при x>=0

Схема команды ветвления:

На псевдокоде и Паскале команда ветвления для вычисления значения y будет иметь такой вид:

Псевдокод	Паскаль
если x>=0 то y:=x+1 иначе y:=x^2 все	IFX>=0 THEN Y:=X+1 ELSE Y:=SQR(X) ;

В команде ветвления после служебных слов то или иначе может стоять составная команда, например:

Псевдокод	Паскаль
если x>=0 то начало y:=x; z:=x+y конец иначе y:=x^2 все	IFX>=0 THEN BEGIN Y:=X; Z:=X+Y; END ELSE Y:=SQR(X) ;

В Паскале пара ключевых слов BEGIN END (операторные скобки) позволяют объединить группу операторов.

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

Псевдокод	Паскаль
если < условие> то < действие> все	IF< логическое выражение > THEN<действие 1>;

Схема команды ветвления в сокращенном виде:

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

Схема команды повторения с предусловием:

Команда повторения с предусловием записывается в следующем виде:

Псевдокод	Паскаль
нц пока < условие> тело цикла кц	WHILE_<логическое выражение> DO BEGIN тело цикла END;

Здесь: нц – начало цикла, кц – конец цикла.

Под телом цикла понимается простая или составная команда. Исполнение такой команды повторения состоит в том, что сначала проверяется условие (логическое выражение) - отсюда и название - цикл с предусловием и, если оно соблюдено (значение логического выражения ИСТИНА), то выполняется тело цикла - команда или команды, которые нужно повторять. После этого снова проверяется условие (логическое выражение). Выполнение цикла завершается, когда условие перестает соблюдаться, т.е. значение логического выражения - ЛОЖЬ. Для этого необходимо, чтобы команда, выполняемая в цикле, влияла на условие.

Команда повторения с постусловием выполняется аналогично, только условие (логическое выражение) проверяется после выполнения команды, а повторение выполнения команды происходит в том случае, когда условие не соблюдено, т.е. значение логического выражения - ЛОЖЬ. Повторение производится до соблюдения условия

(значение логического выражения ИСТИНА). Поэтому этот тип цикла называют также циклом “до”.

Цикл с постусловием записывается в виде:

Псевдокод	Паскаль
нц повторять < действие> тело цикла до < условие> кц	REPEAT тело цикла UNTIL _<логическое выражение>;

Схема команды повторения с постусловием:

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

Приведем фрагмент алгоритма, в котором используется команда повторения. Пусть векторы x и y заданы своими координатами: x₁, x₂, . . . , x_n и y₁, y₂, . . . , y_n. Требуется найти их скалярное произведение:

сумма= x_i  y_i.

ⁱ⁼¹

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

Псевдокод	Паскаль
сумма:=0; i:=1; нц пока i<=n повторять начало сумма:=сумма+xiyi; i:=i+1; кц	SUM:=0; I:=1; WHILE I<=N DO BEGIN SUM:=SUM+X*Y; I:=I+1; END;

Этот же фрагмент может быть записан с использованием команды цикла с постусловием:

Псевдокод	Паскаль
сумма:=0; i:=1; нц повторять начало сумма:=сумма+xiyi; i:=i+1; до i>n; кц	SUM:=0; I:=1; REPEAT SUM:=SUM+X*Y; I:=I+1; UNTIL I>N:

Контрольные вопросы:

а) Дана блок-схема алгоритма

Укажите значения A и B на выходе.

1) A =3, B =3

2) значения A и B не определены из-за бесконечной зацикленности

3) A =4, B =3

4) A =0, B =0

5) A =1, B =1

б) Объяснить понятие алгоритма и его свойства.

в) Какие способы записи алгоритмов?

г) Назовите базовые алгоритмические структуры.