Система

1969 году нидерландский учёный Эдсгер В. Дейкстра (в некоторых источниках Дийкстра) в статье «Структуры данных и алгоритмы доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций: последовательных, ветвящихся, циклических.

Рассмотрим детально организацию названных ранее алгоритмических конструкций.

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

Как видно из описания и блок – схемы это наиболее простой вид алгоритмов.

Разветвляющийся алгоритм. Разветвляющимся будем называть алгоритм, ход выполнения которого зависит от истинности или ложности некоторого условия. Условие – это всегда логическое выражение, которое может принимать одно значение из двух: либо «Истинна», либо «Ложь». Таким образом, один путь развития алгоритма соответствует тому случаю, когда условие истинно, другой путь – когда условие ложно.

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

Такая конструкция получила название «развилка». Различают «развилку» в полной и неполной формах.

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

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

Составим словесный алгоритм и блок – схему деления любого целого числа А, на любое целое число В.

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

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

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

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

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

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

Цикл организуют по определенным правилам. Циклический алгоритм состоит из:

- условия выхода из цикла (продолжения цикла).

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

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

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

На блок – схемах циклические алгоритмы изображаются следующим образом:

Если параметр цикла превысил конечное значение, то выполнение цикла должно быть прекращено, на блок – схеме соответствует «Да». На блок - схемах «У» – условие выхода из цикла. Пока условие ложно выполняется тело цикла, как только условие становится истинным, выполнение тела цикла прекращается.

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

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

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

В тех случаях, когда количество повторений цикла известно заранее применяют арифметические циклы или как их чаще называют – циклы со счетчиком. Как правило, в качестве счетчиков используются переменные <i> или <j>. Количество повторений цикла определяется начальным и конечным значениями счетчика и шагом изменения значения счетчика.

В качестве примера рассмотрим простейшую задачу:

- Составить алгоритм вычисления квадратов целых чисел от 1 до 10.

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

Составим алгоритм и блок – схему решения данной задачи.

2. задать начальное и конечное значение счетчика, шаг изменения счетчика;

3. проверить, не превышает ли начальное значение счетчика его конечное значение, если «Да», то закончить алгоритм, иначе выполнить действия 4 – 7;

5. вывести полученное в п. 4 значение квадрата;

6. вычислить новое значение счетчика по формуле: <н.з.с.>=<т.з.с.> + шаг[1];

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

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

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

В качестве примера составим алгоритм и блок – схему вывода таблицы Пифагора. Данный алгоритм реализуется путем использования вложенных циклов с одним уровнем вложения, данные циклы организуем по переменным <i> и <j>. Напомним, что каждый элемент таблицы Пифагора получается как произведение номера строки на номер столбца. Строки нумеруются от 1 до 10, следовательно, условием выхода из цикла будет значение соответствующей переменной большее 10. Начальными значениями переменных будет значение – 1.

Таким образом, в результате выполнения данного алгоритма получим таблицу, имеющую вид:

[1] Где <н.з.с> означает – новое значение счетчика, <т.з.с> - означает текущее значение счетчика