Файл: ОСНОВНЫЕ СТРУКТУРЫ АЛГОРИТМОВ: СРАВНИТЕЛЬНЫЙ АНАЛИЗ И ПРИМЕРЫ ИХ ИСПОЛЬЗОВАНИЯ.pdf

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

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

рис 1.

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

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

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

алг нахождение площади круга по радиусу (арг вещ π, R, рез вещ S)

нач

ввод R

если R <=0 то вывод ‘значение должно быть положительным’

иначе

S:=3.14*(r*r)

вывод ‘площадь круга ’, R

кон

Программная запись алгоритма (тексты на языках программирования).

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

Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем [8, с.12]. Следовательно, язык для записи алгоритмов должен быть формализован [2, с.25].

Как мы знаем любой алгоритм — это последовательность предписанных действий, выполнив которые за конечное число шагов можно прийти от исходных данных к искомому результату. Таким образом, алгоритм должен быть записан на промежуточном языке понятным компьютеру, с точными и однозначными правилами и отличном от естественного языка и языка блок-схем. Такой язык принято называть языком программирования, а запись алгоритма на этом языке – программой для компьютера. К алгоритмическим языкам относится машинный язык (система команд) и языки программирования. На данный момент в мире существует сотни языков программирования реально используемых на практике. Выделим некоторые из них: Java, Python, Ruby, PHP, C++, C#.

Примером записи алгоритма на языке программирования может служить листинг программы на языке С#.

using System;

namespace primer

{

// Программа демонстрации записи на языке программирования.

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

class Program

{

static void Main(string[] args)

{

// Объявляем переменные

int a = 0;

int b = 0;

int m = 0;

// Запрашиваем данные у пользователя

Console.WriteLine(" Введите первое число");

a = Convert.ToInt32(Console.ReadLine());

Console.WriteLine(" Введите второе число");

b = Convert.ToInt32(Console.ReadLine());

//Блок решения

if (a == b)

{

Console.WriteLine(" Числа {0} и {1} равны ", a, b);

}

else

{

if (a>b)

{

m = a;

}

if (a<b)

{

m = b;

}

Console.WriteLine(" Число {0} большee",m);

}

Console.WriteLine("\n Нажмите любую клавишу");

Console.ReadLine(); // Ожидание нажатия клавиши для завершения программы

}

}

}

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

2. Классификация основных структур алгоритма

Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл [2, с.31].

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

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

Алгоритм линейной структуры – алгоритм, в котором все действия выполняются последовательно друг за другом [6, с.5]. Все этапы действий в алгоритме выполняются в том порядке, в котором они записаны. Структура содержит в себе последовательное выполнение этапов:

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

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

Разветвляющийся алгоритм описывает вычислительный процесс, реализация которого происходит по одному из нескольких заранее предусмотренных направлений [5, с.5]. Направление, по которому следует вычислительный процесс, называется ветвью процесса. Выбор определенного направления происходит в зависимости от полученных результатов заданного логического условия заданного в блоке ветвления. Результатами вычисления логического условия являются значения: «истина» (да), если происходит соответствие условию, и «ложь» (нет), когда условие не выполняется. Логические условия в структурах ветвления бывают простые и сложные. В простых условиях применяют две переменных, два числа или два арифметических выражения. Например x>y; x+y=5; a*b = b*a. Сложные условия представляют последовательность простых условий, объединённых знаками логических операций. Например: x>y И a>b. Структуру ветвления можно записать четырьмя основными вариантами:

• если – то

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

• если-то-иначе

В этой структуре после проверки условия при истинном значении выполняется первый блок действия, иначе при ложном значении выполняется второй блок действия. (рис. 3)

• выбор

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

• выбор – иначе

Конструкция выбор – иначе (рис.5) аналогична предыдущей конструкции (рис. 4), единственное тут добавлен блок действия, который выполняется если ни одно условие не выполнено. (рис. 5)

2.3 Циклические структуры алгоритмов

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

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

Циклы до (цикл с предусловием, рис. 6) – повторение до выполнения условия окончания цикла. В этой структуре тело цикла может не выполнится ни разу, условие проверяется еще до начала обработки тела цикла.

Пример использования на (рис. 7).

Циклы пока (циклы с постусловием, рис. 8) – в этой структуре минимум один раз выполняется тело цикла. Условие проверяется после первого выполнения тела цикла и контролирует выход из него.

Пример использования на рисунке 9.

Циклы для (безусловные циклы, рис. 10) или цикл с параметром. Эти циклы имеют в своем составе три обязательных элемента:

• Начальное значение, которое называется параметром цикла
• Значение, при котором цикл завершится
• Шаг цикла

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

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

При составлении циклических алгоритмов нужно придерживаться нескольких правил:

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

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

3. Сравнительный анализ и примеры использования структур алгоритмов

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

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

Рассмотрим самую простую структуру - линейную.

В линейной структуре все блоки выполняются строго один за другим и никак иначе. Такая структура подходит нам для решения большинства задач, где не требуется принимать логическое решение и выполнять многократные действия. Для примера возьмем алгоритм вычисления площади круга по формуле S=π*R², где S это вычисляемая площадь, а R это задаваемый радиус окружности. Словесно этот алгоритм будет выглядеть следующим образом: