Белов М.П. Основы алгоритмизации и программирования

Подождите немного. Документ загружается.

if(B[i][ j] > max)

max = B[i][j]; // переопределение максимума

cout << "max = " << max; // вывод максимального элемента

}

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

Преобразования величин, реализуемые в алгоритмическом языке, осуще-

ствляются по операторам (командам), располагаемым в заданной последова-

тельности. Логическая структура любого алгоритма может быть представлена

комбинацией трех базовых структур: следование, ветвление, цикл. Характерной

особенностью базовых структур является наличие в них одного входа и од-

ного выхода.

Структура алгоритма является линейной, если она образована последова-

тельностью простых операторов (команд).

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

в результате проверки которого ПК обеспечивает переход на один из двух

возможных шагов.

Циклический алгоритм – алгоритм, предусматривающий многократное по-

вторение одного и того же действия (одних и тех же операций) над новыми

исходными данными. Группа команд (операторов), выполняющихся одна за

другой, называется серией. Серия может состоять из одного оператора.

Для построения разветвляющихся и циклических структур алгоритма в

алгоритмическом языке используются составные операторы. К ним относятся

операторы ветвления и цикла.

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

серия 1 иначе серия 2 все. В зависимости от итога проверки условия выполня-

ется только одна из двух серий, входящих в команду ветвления. Если условие

соблюдено, то следует выполнять серию 1, если нет – серию 2. Оператор ветв-

ления используется и в сокращенной форме: если условие то серия все

При этом, если условие соблюдено, необходимо выполнить серию команд,

следующую в записи алгоритма за служебным словом то, в противном случае,

пропуская серию, перейти к выполнению команды, следующей за командой

ветвления (после служебного слова все).

Структура ветвление существует в четырех основных вариантах [1] (см.

табл. 3): если – то; если – то – иначе; выбор; выбор – иначе.

Оператор выбора используется в тех случаях, когда возникает необходи-

мость выбора альтернативы из трех возможностей и более.

Различия в исполнении этих конструкций вытекают из свойств ветвления.

С формальной точки зрения рассмотренные конструкции эквивалентны, их

использование определяется удобством составления алгоритма.

Оператор повторения (цикла) используется для описания алгоритмов, в ко-

торых требуется организовать многократное повторение одних и тех же дейст-

вий.

Циклические структуры (см. табл. 3) имеют особое значение для построе-

ния алгоритмов, так как только на их основе можно добиться компактной записи

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

При выполнении этого оператора серия, включающая одну или несколько

команд, повторяется несколько раз подряд до тех пор, пока условие соблюдает-

ся. Как только условие нарушается, выполнение серии прекращается. Если ус-

ловие изначально неверно, то серия не выполняется.

Алгоритм, в состав которого входит итерационный цикл, называется ите-

рационным алгоритмом. Итерационные алгоритмы используются при реализации

итерационных численных методов.

Возможны случаи, когда внутри тела цикла необходимо повторить некото-

рую последовательность операторов, т. е. организовать внутренний цикл. Такая

структура получила название цикла в цикле или вложенных циклов. Глубина

вложения циклов (количество вложенных друг в друга циклов) может быть раз-

личной.

Таблица 3

Алгоритмический язык Схема алгоритма

если - то

если условие

то действия

все

сло ви

де йствия

да

нет

если – то – иначе

если условие

то действия 1

иначе действия 2

все

усло вие

действия 1

да

нет

действия 2

Продолжение таблицы 3

выбор

при условие 1: действия 1

при условие 2: действия 2

…

при условие n: действия n

все

действия 1

усло вие1

нет

действия 2

усло вие2

да

нет

действия

усло виеn

нет

выбор – иначе

выбор

при условие 1: действия 1

при условие 2: действия 2

…

при условие n: действия n

иначе действия n + 1

все

действия 1

да

усло вие1

нет

действия 2

усло вие2

нет

действия

усло виеn

нет

действия

Примеры команды если

если x > 0

то y := tg(x)

все

> 0

:=tg(

)

да

нет

если a > b

то a := 5·a; b := 1

иначе b := 4·b + 1

все

·5;

:=1

да

нет

:=4·

Продолжение таблицы 3

выбор

при n = 1: y := tg(x)

при n = 2: y := ctg(x)

при n = 3: y := 10

все

:=tg(

)

да

n = 1

нет

:=ctg(

)

n = 2

нет

:=10

n = 3

да

нет

выбор

при a > 5: i:= a – 1

при a = 0: j := a + 1

иначе i := 5; j := 5

все

– 1

a > 5

нет

+ 1

a = 0

нет

:= 5;

:= 5

Цикл типа пока

Предписывает выполнять тело цикла до тех пор, пока выполняется условие, за-

писанное после слова

пока.

нц пока условие

тело цикла (последовательность

действий)

кц

словие

те ло цикла

да

Цикл типа для

Предписывает выполнять тело цикла для всех значений некоторой переменной

(параметра цикла) в заданном диапазоне.

нц для i от i1 до i2

тело цикла (последовательность

действий)

кц

те ло цикла

да

нет

Продолжение таблицы 3

Примеры команд пока и для

i := 1; S := 0

нц пока i <= 10

S := S + A[i]

i := i + 1

кц

<= 10

[

]

да

нет

нц для i от 1 до 8

X[i] := i·i

Y[i] := X[i]/8

кц

= 1, 8

[i]

да

нет

[i]

[i]/8

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

необходимо выносить из внутреннего цикла во внешний все операторы, кото-

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

Рассмотрим несколько примеров на циклические структуры.

Пример 1 (Организация цикла). Составить алгоритм вычисления суммы s

вещественных чисел, образующих таблицу А из 10 элементов, пронумерованных

от 1 до 10. Для подсчета просуммированных элементов используется промежу-

точная целая переменная i:

Вариант 1:

алг Сумма вещественных чисел (арг вещ таб А[1:10], рез вещ s)

нач цел i

:= 0;

1 | начальные значения

нц

пока

<= 10 |

условие выхода из цикла

ввод А

[

] |

расчет суммы вещественных чисел таблицы А

кц

вывод s

кон

Вариант 2:

алг Сумма вещественных чисел (арг вещ таб А[1:10], рез вещ s)

нач цел i

:= 0

| начальное значение суммы

нц для i от 1 до 10 | начало цикла по расчету суммы

ввод А

[

] |

расчет суммы вещественных чисел таблицы А

кц

вывод s

кон

На рис. 8, а, б показаны 2-а варианта графического представления алго-

ритма:

Приведенный пример содержит алгоритм поэлементной обработки ли-

нейной таблицы, характерный для многих применений. Для общего случая

линейной таблицы таб A[N:K] его можно представить в виде:

Начало

Ввод

s := 0; i := 1

s := s + A

[

]

Нет

i ≤10

Печать

Конец

Начало

Ввод

s := s + A

[

]

Печать

Конец

i:=1,10

а б

Рис. 8

s := 0

вариант 1 вариант 2

пока

≤

нц для I от

до

нц обработка А[I]

обработка А[I] кц

+ 1

кц

Анализ этого алгоритма показывает, что в общем случае в подобных кон-

струкциях используются: целая переменная (I), указывающая текущий элемент

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

цикла; конечное значение (К), по достижении которого происходит выход из

цикла; шаг переменной – изменение ее значения при каждом проходе цикла (в

данном случае шаг равен 1).

Пример 2 (Вложенные циклы). Составить алгоритм нахождения наи-

большего элемента заданной матрицы B[1:10, 1:10]. Для нахождения наибольше-

го элемента используются промежуточные целые переменные i, j:

алг Нахождение наибольшего эле-

мента (арг цел таб B[1:10, 1:10], рез

цел Max)

Начало

Ввод

i:=1,10

Max := B[i, j]

Печать

Max

Рис. 9

Конец

:=1,10

Нет

[i, j]>Max

Max

B[1, 1]

ввод B

нач цел i, j

Max

B[1, 1]

для

от

до

нц

для

от

до

нц

если B[i, j] > Max

то Max := B[i, j]

все

кц

вывод s

кон

На рис. 9 показано графическое

представление алгоритма:

Пример 3 (итерационный цикл).

Составить алгоритм вычисления суммы

членов бесконечного ряда с точностью ε

...

+++++=

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

слагаемого, равное 1. Для вычисления значения текущего члена ряда h целесооб-

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

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

= h

n-1

·x/n. Поэтому начальное значение h следует взять равным единиц.

На алгоритмическом языке алгоритм можно записать в следующем виде:

алг Сумма бесконечного ряда (арг вещ х, eps, рез вещ s)

дано | 0 < x < 1

надо | s = 1 + x + x

/2! + …+ x

/n! + …

нач цел n вещ h

ввод x, eps

s := 1; h := 1; n := 1 | начальные значения

нц пока abs(h) <= eps

h := h·x/n | очередное слагаемое

s := s + h | частичная сумма

n := n + 1 | номер очередного слагаемого

кц

вывод s

кон

А графическое представление алгоритма показано

на рис. 10.

1.6. Вспомогательные алгоритмы

При построении новых алгоритмов могут использо-

ваться алгоритмы, составленные ранее. Алгоритмы, цели-

ком используемые в составе других алгоритмов, называют

вспомогательными (или подчиненными) алгоритмами.

Возможны случаи, когда алгоритм, содержащий ссылку на

вспомогательный, в определенной ситуации также может

оказаться в роли вспомогательного алгоритма.

В некоторых случаях при наличии одинаковых

последовательностей указаний (команд) для различных

данных с целью сокращения записи также выделяют

вспомогательный алгоритм.

Вспомогательные алгоритмы описываются отдель-

но, в терминах так называемых формальных параметров,

которые представлены обозначениями и характеризуют

требуемый порядок выполнения алгоритма. Например, алгоритм поиска больше-

го из двух чисел α и β (обозначим БИД) может быть записан следующим обра-

зом:

Начало

Ввод

s := 1

h := 1

n := 1

h := h·x/n

s := s + h

n := n + 1

Да

Конец

Рис. 10

Печать

|h| ≤ε

Нет

алг

БИД (

арг

вещ

рез

вещ

γ)

нач

если

α ≥

то

γ :=

иначе

γ :=

все

кон

Обращение к вспомогательному алгоритму организуется с помощью спе-

циального оператора вызова, содержащего имя вспомога

тельного алгоритма и

список, фактических параметров. При этом число, тип и порядок перечисления

фактических параметров в списке должны полностью соответствовать числу, ти-

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

ного алгоритма. Так, вызов вспомогательного алгоритма для поиска большего

из трех чисел (обозначим его БИТ) можно составить в форме двукратного об-

ращения к алгоритму БИД:

алг

БИТ (

арг

вещ

рез

вещ

)

нач

вещ

БИД (

)

БИД (

)

кон

Фактические параметры a

полностью соответствуют по смыслу

формальным параметрам α

, γ

. Поэтому после исполнения вспомогательных

алгоритмов в основном алгоритме можно воспользоваться переменной y как ре-

зультатом наибольшего из трех чисел.

Наряду со стандартными функциями sin (x), cos (x), In (x) и т. п., зна-

чения которых вычисляются по известным правилам, для определения значений

других функций в АЯ вводится особый класс вспомогательных алгоритмов, ко-

торые выделяются и оформляются специальным образом.

В виде функций могут быть оформлены алгоритмы, имеющие в каче-

стве результата одно значение простого (т. е. не табличного) типа. Функции

различаются оформлением и способом использования. Обращение к функции не

требует применения специального оператора. Оно осуществляется посредством

указателя функции, тип которой характеризуется типом результата функции.

Указатель функции является элементом арифметического или логического

выражения. В указателе функции записывается имя вспомогательного алгорит-

ма и список фактических параметров, передаваемых в качестве аргументов: In-

tegfun (a, b, h), ploshtr(a, b, c).

По указателю происходит обращение к функции, параметры-аргументы

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

ния возвращается в основной алгоритм как значение указателя функции и участ-

вует в дальнейшем вычислении значения выражения. Так, выполнение опера-

тора: у := интегфун (a, b, h) приведет к обращению к вспомогательному алго-

ритму вычисления интеграла функции, а выполнение оператора: s := ploshtr(a,

b, c) приведет к обращению к вспомогательному алгоритму вычисления пло-

щади треугольника, при этом результатом обращения будут значения функций,

соответствующие заданным фактическим аргументам.

Функции можно представить только как вспомогательные алгоритмы.

Объясняется это тем, что результат функции рассматривается как одно из про-

межуточных значений, необходимых для вычисления выражения. Чтобы вос-

пользоваться этим результатом, функцию необходимо не просто исполнить, а

вызвать из какого-то алгоритма.

Особенности оформления функций заключаются в описании параметров. В

список формальных параметров функций включаются только аргументы. Тип

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

могательного алгоритма аналогично тому, как если бы это был тип алгоритма в

целом. Тем самым вызов функции заменяет обращение к переменной соответст-

вующего типа. Однако следует четко понимать, что тип относится не к самой

функции, а к ее результату.

Примером описания вспомогательного алгоритма-функции является алго-

ритм вычисления площади треугольника по трем его сторонам:

вещ ploshtr(арг вещ a, b, c, рез вещ ploshtr)

нач вещ р

р := (a + b + c)/2

ploshtr := sqrt (p·(p – a)·(p – b)·(p – с))

кон

Имя результата с точки зрения вызывающего алгоритма совпадает с

именем функции. Поэтому может показаться естественным использование име-

ни функции в качестве имени результата и в самой функции. Однако при этом

становится невозможным рекурсивное обращение функции к самой себе, так как

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

зультата. Поэтому в качестве имени результата при рекурсивных вызовах в АЯ

используется специальное ключевое слово знач.