Алгоритмы

Решение задач на ЭВМ реализуется программным способом – путем выполнения последовательности операций, предусмотренных алгоритмом решения задачи. Алгоритм – это точная запись конечного числа действий, приводящих к решению задачи. Алгоритм определяет процесс преобразования информации от исходных данных к результатам. Рассмотрим пример простой задачи. Пусть поезд вышел из пункта A в момент времени t₁ и прибыл в пункт B в момент t_n. Во время следования поезда в моменты времени t₁, t₂, … t_i, …, t_n измерены значения скорости его движения v₁, v₂, … v_i, …, v_n. Требуется найти расстояние S от пункта A до пункта B.

Решение этой задачи, как и всякой другой, начато с построения модели явления (объекта). Как уже отмечалось, построение модели состоит в учете только существенных для рассматриваемых задач характеристик, описываемых ограниченным набором параметров. В нашем примере такими параметрами являются S, n и числовые массивы значений t_i и v_i, где i = 1, 2, …, n. Если мы хотим получить точное решение задачи, то требуется детальная модель, в рамках которой значения времени и скорости чаще регистрируются на тех участках пути, где скорость быстро изменяется.

Вторым этапом решения станет построение математической модели, в которой неизвестные параметры модели объекта (явления) связываются математическими выражениями с известными параметрами. В нашем простейшем примере только один параметр S не известен – построим математическую модель в виде равенства:

Символы * и / при описании алгоритмов означают умножение и деление. Следовательно, для вычисления расстояния от точки i до точки i+1 время движения на этом интервале умножается на среднюю скорость.

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

В блоке 1 выполняются начальные присваивания: в начальный момент, когда поезд еще в точке A, i=1, а S=0. Операция присваивания очень важна для понимания компьютерной реализации алгоритмов. Дело в том, что при разработке программы для ЭВМ считается, что i и S – это не только обозначения математических переменных, но и обозначения ячеек памяти компьютера. Операция присваивания – это занесение нового значения в соответствующую ячейку. Присваивание отображает изменение значения соответствующей переменной в процессе реализации алгоритма. Чтобы отличать присваивание от обычного математического равенства, в некоторых языках программирования, например, в Паскале, операция присваивания обозначается не знаком равно (=), а двумя значками – двоеточием и равно (:=). В этом, вообще говоря, нет необходимости, т.к. знак равенства в математическом смысле при записи алгоритмов применяется только для проверки условий.

Рис. 4.1. Изображение алгоритма в виде блок-схемы

На блок-схемах проверка условий помещается в особые – логические блоки, обозначаемые не прямоугольником, а ромбом (см. блок 4 на рис. 4.1), а в программах инструкции по проверке условий начинаются со слова IF (если).

В блоке 2 (см. рис. 4.1) пройденный путь получает приращение: в ячейку S помещается новое значение, равное прежнему, плюс значение пути за время от t_i до t_i+1. В блоке 3 наращивается значение i, т.к. мы собираемся повторить вычисления в блоке 2 для следующего интервала – при новом значении индекса i, увеличенном на 1. Но ведь последнее значение i, при котором надо вычислять приращение пути, равно n-1. Вот поэтому и проверяется условие (i < n?) в логическом блоке 4. До тех пор, пока это условие выполняется, повторно будут работать блоки 2, 3. Как только условие не выполнится, алгоритм завершит работу – к этому моменту в ячейке S накопится значение пройденного пути.

В рассмотренном алгоритме блоки 2-4 работают n-1 раз, т.е. выполняются циклически, и при каждом исполнении цикла переменные (содержимое ячеек) i и S обновляются. Именно циклы позволяют кратко записывать алгоритмы, в которых многие операции повторяются сотни, тысячи и даже миллионы раз.

В алгоритмах выделяют три типа структур: последовательное выполнение, ветвление и повторение. Операции, выполняющиеся последовательно, образуют один блок, например, две операции присваивания в блоке 1. Блок либо получает управление более чем от одного блока (см. блок 2 на рис. 4.1), либо передаёт управление более чем одному блоку (см. блок 4), либо отделён от других блоков блоком одного из уже перечисленных типов (например, блок 3 на рис. 4.1). В последнее время для изображения циклов (структур повторения) на блок-схемах применяют специальные обозначения, позволяющие сделать блок-схемы компактнее. Так, изображение цикла, число повторений которого задано некоторой переменной N, иллюстрируется фрагментом блок-схемы на рис. 4.2, а для изображения циклов, завершающихся по условию, применяют символы, показанные на рис. 4.3.

Рис. 4.2. Фрагмент блок-схемы, изображающий цикл, работающий N раз; после выхода из цикла P=120

Рис. 4.3. Символы, применяющиеся для изображения циклов, завершающихся по условию; условие записывается в одном из них; между этими символами размещаются блоки, выполняющиеся в цикле

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

Рис. 4.4. Блок-схема вычисления квадратного корня

На этой блок-схеме показан итерационный алгоритм, т.е. значение квадратного корня вычисляется методом последовательных приближений. В качестве первого приближения взято Y=1. Если бы это предположение было верным, то оказалось бы, что d = 0. Здесь d – величина, на которую корректируется значение Y. Корректировки продолжаются до тех пор, пока d по абсолютной величине превышает некоторое очень маленькое число e, определяющее точность вычислений.

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

Конфигурация и размеры блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19002-80 и ГОСТ 19003-80 "Схемы алгоритмов и программ".

Алгоритм решения задачи имеет ряд обязательных свойств [4]:

· дискретность – разбиение процесса обработки на более простые шаги,

· определенность – однозначность выполнения каждого шага,

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

· массовость – пригодность алгоритма для решения некоторого класса задач.

С целью реализации на компьютере алгоритм записывают в виде программной процедуры (подпрограммы) на одном из языков программирования. Как уже отмечалось в разделе 2, современное приложение состоит из многих событийных и общих процедур. Для удобства записи текстов этих процедур любая современная система программирования имеет в своем составе редактор текстов. Для получения работающего приложения система программирования компилирует процедуры, осуществляя переход от текстов на языке программирования к так называемым объектным модулям, которые состоят из машинных команд, но откомпилированные процедуры еще не увязаны друг с другом. Создание исполняемого приложения (EXE-файла) завершает редактор связей, также входящий в состав практически каждой системы программирования.

Таблица 4.1