Глава 5. Основы алгоритмизации и программирования
5.1. Понятие алгоритма. Свойства и способы описания
Алгоритм – это конечная последовательность точно определенных действий, приводящих к решению поставленной задачи. При составлении алгоритмов следует учитывать ряд требований, выполнение которых приводит к формированию необходимых свойств.
•Алгоритм должен быть однозначным, исключающим произвольность толкования любого из предписаний и заданного порядка исполнения. Это свойство алгоритма называется оп-
ределенностью.
•Любой алгоритм должен иметь только одну точку входа (начало) и одну точку выхода (окончание).
•В результате реализации процесса, предусмотренного алгоритмом, должны быть получены результаты или выдано сообщение о невозможности решения задачи. Это свойство алгоритма называется результативностью.
•Способность алгоритма обеспечить решение любого большого количества однотипных задач с различными исходными данными называется массовостью.
•Расчленение процесса, предусмотренного алгоритмом, на отдельные этапы (элементарные операции) принято назы-
вать свойством дискретности.
Для строгого задания различных структур данных и алгоритмов, их обработки требуется иметь такую систему формальных обозначений и правил, чтобы смысл всякого используемого предписания трактовался точно и однозначно. Для выполнения этого условия или требования существуют следующие способы описания алгоритмов:
•словесное описание (запись на естественном языке);
•графическое описание (блок-схемы);
•программное описание (тексты программ на алгоритмическом языке).
198
5.1.1. Графический способ описания
Для изображения алгоритма в виде блок-схемы применяются следующие основные геометрические фигуры.
Начало(Конец)
Ввод a,b,N
(Вывод S)
S=0 h=(b–a)/N
i=1 to N
x>=b
2
14
−Начало или конец алгоритма (пуск-останов).
−Ввод исходных данных или вывод результатов (ввод-вывод).
−Выполнение операции или группы операций (процесс).
−Цикл по счетчику, то есть с определенным (конечным) числом шагов (подготовка или модификация).
−Выбор направления выполнения алгоритма в зависимости от некоторых условий (решение).
−Модуль подпрограммы-процедуры или подпрограммы-функции (типовой или предопределенный процесс).
−Линии потока, соединяющие фигуры блок-схемы. Направление линии указывается при ее ходе слева направо. Изменение направления линии задается под прямым углом.
−Разрыв линии потока.
−Ссылка на другую страницу.
199
5.1.2. Базовые конструкции алгоритмов
При разработке и составлении блок-схемы того или иного алгоритма применяются следующие базовые конструкции: линейная, циклическая и ветвящаяся. В теории алгоритмов доказано, что на основе этих трех конструкций может быть построен любой алгоритм. Абсолютно все системы программирования располагают языковыми средствами для реализации основных алгоритмических конструкций.
Линейная конструкция (следование) – это последовательное выполнение операций без повторов и разветвлений (рис. 5.1).
Начало
Ввод a, b, p
S1=(b-a)×p
S2=(a+b)/p
S=S1+S2
Вывод S
Конец
Рис. 5.1. Линейная конструкция
Ветвящаяся конструкция (ветвление) – это выполнение операций по одному из нескольких направлений в зависимости от заданных условий (рис. 5.2).
200
Начало
Ввод a,b,N
|
|
|
N=1 |
|
|
|
Да |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||
|
|
Да |
Нет |
|
||||||||
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N=2 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
|
|
|
|
|
|
|
S=a^2+b^2 |
|
S=(a+b)^2 |
|
|
|
|
|
S=Sqr(a+b) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вывод S
Конец
Рис. 5.2. Ветвящаяся конструкция
Циклы (конструкция повторения) используются для организации повторного выполнения какой-либо операции (инструкции) или блока операций (инструкций). Цикл состоит из двух частей: условия цикла и тела цикла. У каждого цикла есть параметр. Параметр цикла – это переменная, которая изменяется в теле цикла и задействована в условии его окончания. Для организации повторов могут применяться следующие виды циклических конструкций: цикл с предусловием, цикл с постусловием, цикл с фиксированным количеством повторов или цикл по счетчику.
201
Вариант 1 |
|
Вариант 2 |
|
Условие |
Нет |
Условие |
Да |
Да |
|
Нет |
|
Тело цикла |
|
Тело цикла |
|
Рис. 5.3. Цикл с предусловием |
|
||
Вариант 1 |
|
Вариант 2 |
|
Тело цикла |
|
Тело цикла |
|
Условие |
Да |
Условие |
Нет |
Нет |
|
Да |
|
Рис. 5.4. Цикл с постусловием |
|
||
Конструкция цикла с предусловием (рис. 5.3) в зависимости от |
|||
результата выполнения условия может быть двух вариантов. В пер- |
|||
вом варианте повторение осуществляется до тех пор, пока условие |
|||
|
|
202 |
|
имеет значение Истина (True). В другом варианте повторение |
|
осуществляется до тех пор, пока условие имеет значение Ложь |
|
(False). |
|
|
I=1 to N |
|
Тело цикла |
|
Рис. 5.5. Цикл по счетчику |
Вариант 1 |
Вариант 2 |
Рис. 5.6. Примеры вложенных циклов |
|
Конструкция цикла с постусловием (рис. 5.4) в зависимости от результата выполнения условия может быть двух вариантов. В первом варианте повторение осуществляется до тех пор, пока условие
203