Алгоритмы и их представление.


Языки программирования (особенно императивные, т.е. "командные") называются также алгоритмическими языками, т.к. программы, написанные на этих языках, выполняют какой-либо алгоритм.

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

Алгоритмы могут описываться простым текстом ("присвоить значение 10 переменной А, присвоить значение 5 переменной В, разделить переменную А на переменную В и присвоить результат переменной С"), с помощью специальных диаграмм - блок-схем и диаграмм Насси-Шнейдермана, и собственно в виде программ на алгоритмических языках.

Теорема Бёма-Якопини о структурном программировании (или о структурировании программ): любой алгоритм может быть реализован при помощи трёх конструкций: последовательного (или линейного) выполнения команд, ветвления и цикла (это менее строгая формулировка теоремы).

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

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


Операторы циклов и вспомогательные операции.

В основных языках программирования используются в основном три типа циклов: пошаговый цикл, для которого имеется оператор, почти во всех языках обозначаемый как for ("для"), цикл с предусловием (while ("пока") или while ... do) и цикл с постусловием (do ... while ("делать пока", в языках Си/Си++ и подобных) или repeat ... until ("повторять пока не...") в Паскале).

В таких развитых и выразительных языках, как Си/Си++ и им подобных (Java, C#) все три оператора циклов могут быть взаимозаменяемыми, т.е. с помощью оператора for можно решить те же задачи, что и с помощью операторов while или do while (хотя не обязательно при этом программа станет проще и понятнее. Т.е. делать так можно, но нужно ли?). И наоборот, цикл (и оператор) while можно использовать вместо оператора for (и вообще вместо любого цикла, и с постусловием тоже). Именно это и указывается в строгой форме теоремы Бёма-Якопини: любой алгоритм может быть реализован при помощи трёх конструкций: линейного выполнения команд, ветвления и цикла с предусловием.

    Оператор for.

   Оператор пошагового (или итеративного) цикла (итерация - повторение).
Формат этого оператора в языках Си/Си++/Java/C#:

for(оператор1;условие1;оператор2)    // заголовок
   оператор3;                        // тело цикла

оператор1 - это инициализация цикла (обычно инициализации счётчика числа проходов (итераций)),
условие1  - это условие продолжения цикла, может быть как простым выражением, так и более сложным,
             цикл выполняется, пока условие истинно,
оператор2 - чаще всего (хотя в этих языках и не обязательно) оператор изменения счётчика цикла.

Ни одна из этих составных частей не является обязательной, но символы "точка с запятой" должны присутствовать обязательно, например,
for(;;) - бесконечный цикл (такой же, как while(1) ). Условие не указано, поэтому считается, что оно всегда истинно.
Кроме того, оператор3 (тело цикла) может быть совмещён с оператором2, тогда в конце заголовка цикла ставится точка с запятой:

for(оператор1;условие1;оператор2,оператор3);


for(;;) // бесконечный цикл
{
... // оператор3
}

while(1) // бесконечный цикл
{
... // оператор3
}

Пример простого цикла for на языке Си++ (печать состояния счётчика цикла на каждом проходе):

for(int i=0; i < 10; ++i)
   printf("%d ",i);

Здесь в качестве условия продолжения цикла используется операция сравнения на меньше. Могут использоваться любые подобные операции: <, >, <=, >=, == (точное равенство), != (не равно), и любые операции, результат которых может считаться логическим (т.е. сравниваться на равенство или неравенство с истиной или ложью).

Этот же цикл на более ранних версия языка Си записывается как
int i;
for(i=0; i < 10; ++i)
   printf("%d ",i);

или даже так:
int i=0;
for(; i < 10; ++i)
   printf("%d ",i);

    Вспомогательные операции.

Во всех этих примерах в операторе2 ++i используется операция ++ увеличения на единицу (инкремент). По смыслу такая же, как выражение i = i + 1; // или i = 1 + i;
но для целых чисел этой операции соответствует более эффективная машинная команда.
Ещё один вариант подобного выражения:
i+=1;   // составное присваивание со сложением, означает то же, что и i=i+1;
В последних двух операциях кроме единицы могут использоваться любые значения:
int a=5;
i=i+a;
i+=a;

Операция ++ является унарной (или "одноместной"), т.к. у неё только один операнд. Такими же являются операции -- (декремент, уменьшение на 1), + (унарный плюс - подтверждение знака), - (изменение знака), ! (отрицание), * (работа с указателями), & (получение адреса) и другие.

Операция ++ (также как и операция --) имеет две формы:
префиксная ++i и постфиксная i++.
В простых выражениях вида i++; C++; эти формы не отличаются. Отличаются они в следующих случаях:

int a=5;
int i=10;
a = a + i++; // a=15, i=11 (к переменной a прибавляется исходное значение (10) переменной i, затем i увеличивается на 1)
a = a + ++i; // a=16, i=11 (сначала i увеличивается на 1, затем к переменной a прибавляется новое значение (11) переменной i)

В языках Си/Си++ подобные конструкции могут приводить к недопониманию, поэтому в сложных случаях их лучше не использовать, заменяя на отдельные операции (показанный выше случай ещё не является сложным):
a = a + i;
++i;

Всё это справедливо и для операции декремента --.

    Оператор while.

Оператор цикла с предусловием ("пока").
Формат оператора:

while(условие1)
   оператор1;

Оператор1 выполняется до тех пор, пока условие1 истинно. Условие1 проверяется сразу при входе в цикл, поэтому, если оно уже ложно, оператор1 может не выполниться ни разу. Тем не менее этот тип цикла считается самым универсальным, которым можно заменить даже цикл с постусловием. В некоторых языках программирования цикл с постусловием даже отсутствует.

Перепишем пример цикла for с использованием оператора while:

int i=0;  // оператор1 цикла for
while(i<10)
{
   printf("%d ",i);
   ++i;  // оператор2 цикла for
}

Здесь мы разнесли в разные места из оператора for оператор1 и оператор2.
Оператор1 цикла while оказался составным (состоящим из нескольких операторов), поэтому нужно использовать операторные скобки { }.
Этот же пример можно переписать в следующем виде:
int i=0;
while(i<10)
   printf("%d ",i),++i;

Здесь вызов функции printf и приращение счётчика цикла разделены операцией "запятая" (бинарной, у неё два операнда - левый и правый, левый выполняется первым).

Все приведённые примеры не будут работать без точки входа в программу, т.е. без функции main. Показанные в примерах отступы в Си/Си++ не являются обязательными (в отличие от языка Питон, где они обязательны), но лучше их использовать для наглядности (фактически эти отступы в текстах программ являются некоторым аналогом диаграмм Насси-Шнейдермана).