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

1) Императивные языки описывают процесс вычислений в виде команд, изменяющих состояние программы. Эти языки разрабатывались для фоннеймановской архитектуры ЭВМ, названной так в честь её автора – Джона фон Неймана. В компьютере фон Неймана данные и программы хранятся в одной и той же памяти, называемой оперативной. Центральный процессор получает из оперативной памяти очередную команду, декодирует её, выбирает из памяти указанные данные, выполняет команду и возвращает в память результат. Основными элементами императивных языков являются переменные, моделирующие ячейки памяти ЭВМ; операторы присваивания, осуществляющие пересылку данных; один или несколько итеративных циклов. Примерами императивных языков можно отнести такие языки как Algol, Fortran, Basic, PL/1, Ada.[^[21]]

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

3) Декларативные языки программирования - это языки программирования, в которых операторы представляют собой объявления или высказывания в символьной логике. Типичным примером таких языков являются языки логического программирования(языки, основанные на системе правил)[^[22]].

4) Объектно-ориентированное программирование является развитием императивного программирования. При его создании преследовались две цели:
1) Сократить размеры программ за счет повышения размера строительных элементов и тем самым обеспечить возможность создания более крупных программных приложений.
2) Упростить процесс создания новых программ на базе старых (за счёт применения механизма нследования)
Объектно-ориентированные языки впитали в себя лучшие понятия и механизмы императивных языков. Объектно-ориентированные языки задают вычисления как взаимодействия программных объектов.[^[23]]

Наиболее распространенными языками высокого уровня являются C++,Java, C#, Pascal.

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

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

---

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

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

Специалисты различают следующие виды алгоритмов:
1) Линейный алгоритм - описание действий, которые выполняются однократно в точно заданном порядке.

2) Разветвляющийся – алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения..[^[24]]

3) Циклический алгоритм – это алгоритм, описывающий повторение одних и тех же вычислений над различными вариантами данных для получения необходимого результата. Требуемые вычисления производит основной блок цикла – тело цикла. Циклический процесс организуют вспомогательные блоки цикла. Они устанавливают начальное значение, новые значения данных и проверяют условие окончания циклического процесса.[^[25]]



 

Рис. 5 Пример линейного алгоритма



Алгоритм, в котором команды выполняются в порядке их записи, то есть последовательно друг за другом, называется линейным.[^[26]]

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

Алгоритмы, которые предусматривают 2 возможных варианта действий – более сложные, чем линейные.
Алгоритмы, которые осуществляют выполнение действий в зависимости опроверки условия, называется алгоритмом с разветвлением[^[27]]
Пример алгоритма с ветвлением:

Рис. 6 Пример алгоритма с ветвлением

Алгоритм, осуществляющий повторное выполнение некоторых операций, называется алгоритмом с повторениями или же циклическим алгоритмом.^[28]

Действие или их группа называется телом цикла. Число повторений тела определяется поставленным условием, что также называется условием цикла. За результатами проверки условия выполняется выбор: или еще раз выполнить тело цикла, либо перейти к иным действиям.^[29]

---

Конструкции циклов по своим основным свойствам можно характеризовать как циклы с параметром или циклы по условию, а так же как циклы с предусловием (то-есть те циклы, в которых условие цикла проверяется непосредственно перед выполнением тела цикла), и как циклы постусловием, в которых условие цикла проверяется после выполнения тела цикла.^[30]

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

В цикле с предусловием
1)вычисляется значение условия
2) если условие ложно, выполнение цикла прекращается
3)выполняется тело цикла
4)Выполнение цикла продолжается с пункта 1.

Цикл с постусловием же работает как:
1. Выполняется тело цикла
2. Вычисляется значение условия
3. Если условие принимает определённое значение, выполнение цикла прекращается.
4. Выполнение цикла продолжается с пункта 1.

Рис. 7 Пример алгоритма с постусловием

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

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

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

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

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

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

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

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

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

else оператор;

1. где оператор может быть как простым, так и составным.^[31]

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

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

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

}

---

else {

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

}

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

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

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

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

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

break;

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

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

break;

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

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

...

default:

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

}

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

отсутствует default), оператор switch заканчивает работу при обнаружении конца.^[34]

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

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

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

3. если в операторе switch используются символьные константы, они автоматически преобразуются к целочисленным значениям.^[36]
Рассмотрим реализацию алгоритмов цикла на языке С++, где существуют три разновидности цикла:

– цикл for;

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

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

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

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

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

– тело цикла;

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

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

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

---

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

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

{

тело цикла;

}

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

int summa = 0;

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

s = s + i;

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

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

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

{

тело цикла

};

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

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

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

do

{

тело цикла

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

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

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

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

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

Синтаксис оператора:^[38]

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

{

тело цикла;

}

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

int summa = 0;

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

s = s + i;

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

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

---