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

Рис.3. Блок «Решение»

3.Предопределенный процесс. Использование созданных ранее и описанных отдельно алгоритмов или же программ (функций, программных модулей, процедур). Символ служит для выполнения обращения к программным модулям. [5]

Рис.4. Блок «Предопределенный процесс»

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

Рис.5. Блок «Ручной ввод»

5.Дисплей. Ввод или вывод данных, если непосредственно подключенное устройство воспроизводит их и позволяет пользователю вносить изменения.[9]

Рис.6. Блок «Дисплей»

6.Документ. Ввод или вывод данных на бумажный носитель.[18]

Рис.7. Блок «Документ»

7.Линия перехода. Указание последовательности перехода.

Рис.8. Линии перехода

8.Соединитель. Указание связей между прерванными линиями перехода, связывающими блоки. Если блок-схема состоит из частей, расположенных на одной странице, то тогда линия перехода одной части заканчивается блоком соединитель, а линия перехода на продолжении блок-схемы будет начинаться с этого символа. [17]

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

Рис.9. Блок «Соединитель»

9. Межстраничный соединитель. Указание связей между частями схем алгоритмов и программ, что являются расположенными на разных листах. [16]

Этот блок служит для аналогичных целей, что и блок соединитель, но при расположении составных блок-схемы на других страницах.[14]

Рис.10. Блок «Междустраничный соединитель»

10.Пуск - остановка. Начало или конец процесса обработки данных.

Рис.11. Блок «Пуск-остановка»

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

Рис.12. Блок «Комментарий»

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

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

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

Со времени разработки первых ЭВМ человечество создало более 2,5 тысяч самых различных языков программирования. Число их пополняется каждый год все новыми и новыми, зачастую специализированными, языками.

С некоторыми из них умеют пользоваться лишь некоторые разработчики, другие – известны многим миллионам людей. Профессиональные разработчики программ иногда применяют больше десятка самых различных языков программирования.[14]

Машинный вид команды для программы, состоящий из обозначений «0» и «1», указывает на то, именно какое действие должен выполнить центральный процессор в своей работе.

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

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

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

Намного проще писать программу на языке программирования, который более близок к естественному языку, а работу по «переводу» данной программы в машинный код поручить компьютеру. [15]

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

– императивные языки программирования, которые описывают процесс вычислений в виде команд, изменяющих состояние программы. Основными элементами императивных языков являются переменные, моделирующие ячейки памяти ЭВМ; операторы присваивания, осуществляющие пересылку данных; один или несколько итеративных циклов.

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

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

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

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

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

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

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

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

По характеру управления часто различают 3 основных типа алгоритмов:

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

– линейные;

– цикличные.

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

Для нахождения объема, например, призмы нужно сначала найти ее площадь основания, далее определить высоту призмы и найти их произведение. Все эти действия надо выполнять для расчета объема каждой призмы.[9]

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

Рис.13. Структура линейных алгоритмов

Примером линейного алгоритма может быть алгоритм посадки саженца:[7]

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

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

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

Алгоритмы, которые осуществляют выполнение действий в зависимости от проверки условия, называется алгоритмом с разветвлением:[6]

Рис.15. Структура разветвляющегося алгоритма

Примером такого алгоритма может быть следующий алгоритм:[7]

Рис.16. Пример разветвляющегося алгоритма

Третий вид алгоритмов применяют в случае повторного выполнения последовательности действий.[4]

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

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

Различают 2 основные вида циклов: [6]

– циклы с предусловием (рис. 17);

– циклы с постусловием (рис. 18).

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

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

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

Циклы с предусловием читают следующим образом:[1]

пока проверка условий дает результат «истина», нужно выполнять действия.

Если в очередной проверке условия получится результат «нет», то повторное выполнение действия прекратится и произойдет выход из рассматриваемого цикла.[3]

Для подсчета остатка деления некоторого целого числа t на целое n с помощью операции вычитания можно применить цикл:

пока t> n, уменьшить параметр t на n.

В цикле с постусловием условие цикла выполняется противоположным образом, а именно: если повторная проверка условия дает результат "истина", происходит выход из имеющегося цикла. Цикл с постусловием можно прочитать следующим образом:[11]

повторять действие пока не будет получен результат «да» при проверке условия цикла.

Стоит также обратить внимание на те особенности, которые являются общими для обоих циклов:[3]

– все базовые структуры являются замкнутыми;

– число повторений цикла всегда определяется его условием;

– окончание цикла происходит лишь через проверку условий цикла.[4]

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

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

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

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

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

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

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

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

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

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

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

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

else оператор;

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

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

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

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

}

else {

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

}

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