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

Графический способ описания базируется на основании реализации блок-схем.

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

Графический метод представления алгоритмов читают более компактным по сравнению с словесным.[11]

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

Указанное графическое представление является схемой алгоритма или же блок-схемой.

На рисунке 3 приведены самые употребляемые геометрические фигуры.

Рис.3. Составные части блок-схемы

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

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

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

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

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

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

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

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

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

---

Однако вовсе не любой граф, составленный с вершин указанных типов, является корректно созданным алгоритмом. К примеру, из операторной вершины выходить более 1 дуги не может.[1]

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

2.2.Основные структуры алгоритмов

К основным структурам алгоритмов относятся такие:

– линейные

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

– циклические

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

Рис.4. Линейный алгоритм

Разветвляющимся является такой алгоритм, где действие выполняется только по одной с возможных ветвей решения заданий, в зависимости от конкретного выполнения условий. [14]

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

Рис.5. Разветвленный алгоритм

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

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

Заметим, что в цикл входят структуры:

– блок условия

– тело цикла.

На рисунке 6 показаны 3 типа циклов:

Рис.6. Типы циклических алгоритмов

Самая существенная разница между видами циклов заключается в том факте, что тело цикла с послеусловием обязательно выполняется один раз – до самой первой проверки условия, цикл с предусловием может даже не выполнятся вообще, если при первой проверке условия получим результат «нет». [13]

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

Отметим, что в циклических алгоритмах могут использоваться и линейные алгоритмы, и разветвленные в качестве их составных частей.

---

3.Практическая реализация базовых структур алгоритмов

3.1.Операторы языка С++ для реализации базовых структур алгоритмов

Для выполнения линейных алгоритмов на языке С++ используется операция присваивания.[13]

Общий вид оператора присваивания следующий:[14]

имя_переменной = выражение;

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

Для реализации разветвляющих алгоритмов используются два оператора: логический оператор if и оператор выбора case.

Стандартная форма оператора if следующая:

if (выражение) оператор;

else оператор;

где оператор может быть или простым, или составным. [2]

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

if (выражение) {

последовательность операторов

}

else {

последовательность операторов

}

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

Оператор принятия решений switch, выполняющий действия, основываясь на сравнении значения со списком констант символов или целых чисел. При обнаружении совпадения выполняется оператор или операторы, ассоциированные с данным значением. Оператор switch имеет следующий вид:[4]

switch (выражение) {

case константа1:

последовательность операторов

break;

case константа2:

последовательность операторов

break;

case константа3:

последовательность операторов break;

...

default:

последовательность операторов

}

Оператор default выполняется, если не найдено соответствий, default необязателен и, если его нет, то в случае отсутствия совпадений ничего не происходит. Когда обнаруживается совпадение, операторы, ассоциированные с соответствующим case, выполняются до тех пор, пока не встретится оператор break. В случае default (или последнего case, если отсутствует default), оператор switch заканчивает работу при обнаружении конца.[5]

---

Следует знать о трех важных моментах оператора switch:[11]

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

2. не может быть двух констант в одном операторе switch, имеющих одинаковые значения. Конечно, оператор switch, включающий в себя другой оператор switch, может содержать аналогичные константы.[15]

3. если в операторе switch используются символьные константы, они автоматически преобразуются к целочисленным значениям.

Рассмотрим реализацию алгоритмов цикла на языке С++, где существуют три разновидности цикла:[19]

– цикл for;

– оператор цикла while;

– оператор цикла do ... while.

Все эти операторы цикла содержат непременно следующие составные части:

– условие продолжения цикла;

– присваивания исходных значений;

– тело цикла;

– изменение счетчика цикла.

Оператор for используется, когда есть известное заранее количество повторений.

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

Синтаксис оператора:

for (инициализация счетчика; условие выполнения; модификация)

{

тело цикла;

}

Простой пример вычисления суммы иллюстрирует использования данного оператора for:[5]

int summa = 0;

for (i = 1; i <= 15; i ++)

s = s + i;

Операторы с предусловием и постусловием используются для организации циклов и являются альтернативными к оператору for. Обычно цикл с предусловием используется, если количество повторений заранее неизвестно, а для многократного повторения тела цикла известно условие, при истинности которого цикл продолжает выполнение. Это условие следует проверять каждый раз перед очередной итерацией. Например, при считывании данных из файла условием цикла является наличие данных непосредственно в файле, то есть повторять чтение данных следует до тех пор, пока указатель не будет указывать на конец файла.[15]

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

while (условие выполнения)

{

тело цикла

};

Последовательность операторов выполняется пока условие истинно, а выход из цикла выполняется, когда условие будет ложным. Если условие ошибочное при вхождении в цикл – операторы ни разу не выполнятся, а управление передастся к следующему оператору.[1]

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

---

Синтаксис цикла do … while:

do

{

тело цикла

}

while (условие выполнения);

Последовательность операторов (тело цикла) выполняется один или несколько раз, пока условие станет ложным. Оператор цикла do ... while используется в тех случаях, когда есть необходимость выполнить тело цикла хотя бы один раз, поскольку проверка условия осуществляется после выполнения операторов.[7]

Если тело цикла состоит из одного оператора, то операторные скобки {} не является обязательны.[4]

Операторы цикла while и do ... while преждевременного могут завершиться при выполнении операторов break или же return внутри тела циклов.

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

Отнести определенный алгоритм к какой-то структуре из них удается не совсем часто, поскольку вычислительные задачи бывают разными по сути и методам их решений. [2]

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

Каждая структура применяет свои особенности и принципы построения.

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

Такие алгоритмы состоят с 3-х основных частей:

– ввод информации;

– вычисление;

– вывод данных.

Порядок выполнения составных блоков, определяют несколько линий потока.

Для реализации линейного алгоритма приведем пример.

Необходимо на языке С++ реализовать алгоритм в графическом виде и на языке программирования, который по введенным параметрам:[18]

– ширина окна;

– высока окна;

– количество окон;

– цена окна,

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

Рассмотрим на рисунке 7 блок-схему данного алгоритма.

Рис.7. Блок-схема линейного алгоритма

Аналогично продемонстрируем алгоритм на языке программирования С++.[9]

//модуль main

int main()

{

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

float w,h,q,p,s,a;

//ввод ширины окна

cout << "Input width: ";

cin >> w;

//ввод высоты

cout << "Input heigth: ";

cin >> h;

//ввод количества окон

cout << "Input quantity: ";

---