Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Линейная алгоритмическая структура).pdf

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

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

Алголо-подобный алгоритмический язык с русским синтаксисом был введён в употребление академиком А. П. Ершовым в середине 1980-х годов, в качестве основы для «безмашинного» курса информатики [22, c. 48].

Рассмотрим основные служебные слова алгоритмического языка.

1. Описание алгоритма:

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

2. Типы данных:

• цел (целый)
• вещ (вещественный)
• сим (символьный)
• лит (литера) — строка
• лог (логический)
• таб (таблица) — для обозначения массива
• длин (длина) — количество элементов массива

3. Обозначение условий:

• если
• то
• иначе
• все
• выбор
• при
• знач

4. Обозначение циклов:

• нц (начало цикла)
• кц (конец цикла)
• пока
• для
• от
• до
• шаг

Логические функции и значения для составления выражений:

• и
• или
• не
• да
• нет

Ввод-вывод:

• ввод
• вывод

Общий вид алгоритма выглядит так [19]:

1 алг название алгоритма (аргументы и результаты)

2| дано условия применимости алгоритма

3| надо цель выполнения алгоритма

4 нач описание промежуточных величин

5| последовательность команд (тело алгоритма)

6 кон

Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон - телом алгоритма.

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

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

---

Далее приведем шаблоны составления этих структур на алгоритмическом языке [19].

Неполная развилка

1| если условие

2| | то действия

3| всё

Полная развилка

1| если условие

2| | то действия 1

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

4| всё

Ветвление

1| выбор параметр

2| | при знач значение 1

3| | | действия 1

4| | при знач значение 2

5| | | действия 2

6| | иначе

7| | | действия по умолчанию

8| всё

Цикл с предусловием

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

2| | действия

3| кц

Цикл с постусловием

1| нц

2| | действия

3| кц пока условие

Параметрический цикл

1| нц для параметр от НЗ до КЗ шаг Ш

2| | действия

3| кц

Если для выполнения параметрического цикла шаг принимается равным 1, то он может не указываться.

Рассмотрим пример составления алгоритма на алгоритмическом языке [9, c. 43].

Вычислить сумму квадратов целых чисел от 1 до n.

1 алг Сумма квадратов (арг цел n, рез цел S)

2| дано n > 0

3| надо S = 1*1 + 2*2 + 3*3 + … + n*n

4 нач цел i

5| ввод n

6| S:=0

7| нц для i от 1 до n

8| | S:=S+i*i

9| кц

10| вывод "S = ", S

11 кон

Четвертый способ описания алгоритмов - операторные схемы. Операторные схемы алгоритмов являются способом описания алгоритмов, при котором каждый оператор обозначают буквой (например, А – арифметический, Р – логический и т.д.).

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

Обозначения операторов:

B - ввод исходных данных;

A - арифметический оператор;

П - оператор печати (вывода);

Р - логический оператор;

Я - оператор останова.

Логический оператор записывается как функция, аргументом которой служит проверяемое условие P (i = N) или (υ ≤ 0) и т.д.

Ввел этот метод А.А. Ляпунов в 1954 году. Операторные схемы имеют формальный уровень, близкий к алгоритмическим языкам, и поэтому могут рассматриваться как средство автоматизации программирования [20, с. 245].

Пятый способ описания алгоритмов – псевдокод - представляет собой систему команд абстрактной машины. Данный способ записи алгоритмов осуществляется с помощью операторов близких к алгоритмическим языкам [23, c. 125].

---

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

- структура «присваивание, ввод, вывод» - переменная = 0, ввод (переменная), вывод (переменная);

- структура «ветвление» - если условие то (серия1 иначе серия 2);

- цикл ПОКА - пока условие нц серия кц.

Пример программы «Здравствуй, Мир!»

алг ЗДРАВСТВУЙМИР

нач

вывод ('Здравствуй, Мир!')

кон алг ЗДРАВСТВУЙМИР

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

Основными свойствами алгоритма являются массовость, понятность, дискретность, конечность, определенность и эффективность.

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

2. Сравнительный анализ алгоритмических структур

Алгоритмическая структура - это структура, где каждая часть предназначена для выполнения определенного алгоритма преобразования информации [17, c. 16]. Метод структурной алгоритмизации является одним из системных методов разработки алгоритмов. Он основан на визуальном представлении алгоритмов в виде последовательностей управляющих структурных фрагментов.

Каждый алгоритм состоит из элементарных шагов, которые можно объединить в определенные алгоритмические структуры:

- линейную (последовательную) структуру;

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

- циклическую структуру.

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

2.1. Линейная алгоритмическая структура

Линейной называется структура алгоритма, реализованная в виде последовательности действий, причем каждое действие выполняется только 1 раз, после каждого действия (шага) выполняется увеличение действия на 1 до тех пор, пока значение не станет больше конечного параметра алгоритма. Схема состоит последовательности блоков, расположенных сверху вниз в порядке их выполнения (Рис. 1) [17, c. 20].

---

Начало

Действие 1

Действие 2

Конец

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

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

В Приложении 3 рассмотрен пример решения задачи с помощью блок-схемы линейного алгоритма. Задача: с = а* b (Приложение 3) [17, c. 21].

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

2.2 Разветвляющаяся алгоритмическая структура

Разветвляющейся (ветвящейся) называют алгоритмическую структуру, обеспечивающую выбор между двумя вариантами решений в зависимости от значений входных данных [18, c. 298].

Ветвления бывают двух типов:

- неполное (если - то);

- полное (если – то - иначе).

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

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

Различают четыре варианта структуры ветвления:

1. Неполное ветвление типа «если – то», при котором все действия будут выполняться истинности условия.

2. Полное ветвление типа «если – то – иначе», при котором будут выполняться два действия в зависимости от истинности условия.

3. Ветвление с выбором типа «то», при котором действие 1 будет выполняться при условии 1, действие 2 при условии 2 и т.д.

4. Ветвление с выбором типа «иначе», при котором при условии 1 будет выполняться действие 1, при условии 2 действие 2 и т.д., а иначе будут выполняться все другие действия.

В Приложении 4 приведены блок-схемы разветвляющихся алгоритмов [18, c. 299].

В качестве примера составим алгоритм для вычисления функции: (X+1,Y>0) Z =

(X+Y, Y<0.)

Словесное описание разветвленного алгоритма имеет следующий вид:

1. Ввести X.

2. Если Y > 0, то Z = X + 1.

3. Если Y <0.

4. Вывести Z = X + Y.

5. Конец.

---

В Приложении 5 можно увидеть графическое изображение этого разветвленного алгоритма [13, c. 11].

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

2.3 Алгоритмическая структура «Цикл»

Циклической (или циклом) называется структура алгоритма, в которой некоторая группа идущих подряд действий (шагов) выполняется несколько раз в зависимости от условия задачи и входных данных [15, c. 243]. Такую группу повторяющихся действий на каждом шагу цикла называют телом цикла. В любой циклической конструкции содержатся элементы ветвящейся конструкции алгоритма.

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

Различают три типа циклических алгоритмов:

- цикл с параметром (арифметический цикл – цикл типа для for);

- цикл с предусловием (цикл типа пока while);

- цикл с постусловием (цикл типа до repeat).

Рассмотрим арифметический цикл. Приведем блок-схему данного вида алгоритма (Рис. 2) [15, c. 244].

i, a, b, h

Серия команд

Рис. 2. Арифметический цикл типа для

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

Рассмотрим второй тип циклического алгоритма - цикл с предусловием. В данном цикле количество шагов заранее не определяется, оно зависит от входных данных (Рис. 3) [15, c. 244].

Нет

Условие

Да

Серия команд

Рис. 3. Цикл с предусловием типа пока

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

---