История алгоритма

Если разработанная Вами последовательность действий не обладает хотя бы одним из перечисленных выше свойств, то она не может считаться  алгоритмом [3].

 

4. Правила оформления схем алгоритмов

Условные обозначения  и правила выполнения схем алгоритмов регламентируются требованиями Единой системы программной документации в соответствии с ГОСТ 19.701-90 [4].

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

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

Рис. 1.

Символы в схеме соединяются  линиями, которые указывают потоки управления. Направление потока слева  направо и сверху вниз считается  стандартным. Направление потока, отличное от стандартного, должно быть отмечено стрелкой на конце линии (при вхождении  потока в символ или в другую линию  потока). Линии должны быть направлены к центру символа. Следует избегать пересечения линий, если потоки в  данном месте не входят друг в друга. При необходимости линии в  схемах следует разрывать во избежание  лишних пересечений или слишком  длинных линий, а также, если схема  состоит из нескольких страниц. Соединитель  в начале разрыва является внешним, а в конце разрыва - внутренним. В комментариях к соединителям могут  быть приведены ссылки к страницам (рис.2).

Рис. 2.

Как правило, каждый символ имеет один вход и один выход. Исключение составляют символы:

• "терминатор" (у операции "начало" нет входа, у операции "конец" нет выхода),
• "решение" (один вход и несколько выходов),
• "подготовка".

Символ "решение" является логическим. Каждый выход из символа "решение" должен сопровождаться значением условия, приведенного внутри (рис.3).

 

  

Рис. 3

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

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

 

5. Типовые структуры алгоритмов

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

• линейная,
• разветвляющаяся,
• циклическая.

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

5.1. Линейная структура

Линейным называется алгоритм, в котором всегда выполняются все действия строго последовательно.

Как правило, алгоритмы линейной структуры  состоят из трех частей: ввод исходных данных, вычисления результатов по формулам, вывод значений результатов. Это самые простые алгоритмы.

5.2. Разветвляющаяся структура

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

 
5.3. Циклическая структура

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

• циклы с известным заранее числом повторений (классические);
• циклы с неизвестным числом повторений (итерационные).

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

• начальное значение параметра (обозначим его    );
• конечное значение параметра (обозначим его    );
• шаг изменения параметра (обозначим его   ).

 

 

Зная эти 3 величины, можно вычислить  количество повторений цикла по формуле:          

В этой формуле квадратные скобки обозначают, что после деления  берется только целая часть числа (дробная часть всегда отбрасывается, а не округляется), т.к. количество повторений цикла - это целая величина. 
Классический цикл имеет 4 части:

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

Итерационный цикл отличается другой организацией.

 

Заключение

Вместе с математической логикой теория алгоритмов составляет теоретический фундамент современных  вычислительных наук. "Понятие алгоритма  является не только центральным понятием теории алгоритмов, не только одним  из главных понятий математики вообще, но одним из главных понятий современной  науки. Более того, с наступлением эры информатики, алгоритмы становятся одним из важнейших факторов цивилизации. Многие достижения теории алгоритмов имеют общематематический и, возможно, общечеловеческий интерес" [3].

 

Литература

1. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. - М.: Наука, 1980.- 608
2. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987.- 288 с. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985.-385 с.
3. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
4. ГОСТ 19.701-90. Единая система программной документации. Схемы алгоритмов и программ. Условные обозначения и правила выполнения. - М.: Изд-во стандартов, 1991.- 26 с.
5. Интернет - ресурсы: http://comp5.ru/Teoria/algoritm/Alglit.php
6. Интернет - ресурсы: http://pascal.proweb.kz/