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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вывод:

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

Глава 2. КЛАССИФИКАЦИЯ АЛГОРИТМОВ

Алгоритмы бывают линейные, разветвляющиеся и циклические. [^[31]]

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

• ввод исходных данных в память ЭВМ;

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

• вывод результатов из памяти ЭВМ на информационный носитель. [^[32]]

Пример 1. Составить алгоритм вычисления площади круга по формуле 2 S R = π . Решение показано на рис. 2.1.

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

Пример 2. Составить алгоритм решения для функции F(x) = 1 при x > 0 и F(x) = 0 при x < 0. Блок - схема разветвляющегося алгоритма показана на рис.2.2. Циклический алгоритм описывает вычислительный процесс, этапы которого повторяются многократно. Различают простые циклы, не содержащие внутри себя других циклов, и сложные (вложенные), содержащие несколько циклов. В зависимости от ограничения числа повторений выделяю циклы с известным числом повторений и циклы, число повторений которых заранее неизвестно. [^[33]]

2.1. Циклы с известным числом повторений

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

При организации этих циклов присутствуют стандартные элементы, сопровождающие любой цикл:

•подготовка первого выполнения цикла (присвоение счетчику цикла начального значения);

•тела цикла, которое образуют блоки, выполняемые многократно;

•изменение значения счетчика циклов и сравнение его с конечным значением. [^[35]]

Блок-схемы циклических алгоритмов существенно отличаются структурами повторения "повторять ДО "(повторять до выполнения условия окончания цикла) или "повторять ПОКА " (повторять пока выполняются условия продолжения циклического процесса). В первом варианте проверка условий окончания циклических вычислений осуществляется в конце цикла (рис. 2.3, а), а во втором - в начале цикла (рис. 2.3, б). Как видно из рисунка, цикл "повторять ДО "выполняется, по крайней мере, один раз, а цикл "повторять ПОКА" может сразу привести к выходу из цикла. Подготовка выполнения первого цикла. [^[36]]

Пример 3. Составить алгоритм решения задачи вычисления N первых членов геометрической прогрессии, используя формулу n+1 n b =b *q для любых b и q, где n - текущий член геометрической прогрессии.

Блок-схема алгоритма решения данного примера показана в двух вариантах: с использованием цикла "ДО" (рис. 2.4, а) и цикла "ПОКА"(рис. 2.4, б).

2.2. Циклы с неизвестным числом повторений

Примером циклов, число повторений которых не задано, являются итерационные вычислительные процессы. В них решение задачи реализуется путем последовательного приближения к искомому результату. Процесс является циклическим, поскольку заключается в многократных вычислениях. Начальное приближение Y0 выбирается заранее или задается по определенным правилам. Заканчивается итерационное вычисление при выполнении условия, где d- допустимая ошибка вычисления. [^[37]]

На каком-то шаге условие не выполнится (ложь) и тогда происходит выход из цикла и продолжается выполнение программы. [^[38]]

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

Пример 4. Составить алгоритм вычисления функции с точностью d, используя рекуррентную формулу

Если начальное приближение y1 = x, тогда на первом цикле вычисления будем иметь

Блок - схема алгоритма решения примера 4 приведена на рис. 2.6. [^[39]]

Вывод:

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

Глава 3. ПРИМЕРЫ АЛГОРИТМОВ

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

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

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

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

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

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

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

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

else оператор;

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

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

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

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

}

else {

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

}

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

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

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, может содержать аналогичные константы.[^[44]]

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

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

– цикл for;

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

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

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

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

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

– тело цикла;

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

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

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

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

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

{

тело цикла;

}

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

int summa = 0;

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

s = s + i;

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