Елена Александровна Конова , Галина Андреевна Поллак - Алгоритмы и программы. Язык С++ : учебное пособие для СПО

собственного стиля.
В каждой теме для самостоятельного решения предлагаются по 30 вариантов задач примерно одинакового уровня сложности. Особый интерес, по нашему мнению, представляют содержательные задачи, в которых постановка
задачи выполнена на вербальном уровне, т. е. не формализована. Здесь студент должен самостоятельно осмыслить
задачу, формализовать ее, предложить структуру данных
и выбрать или разработать алгоритм решения. Опыт показывает, что часто именно этот этап в практическом программировании является наиболее трудным.
Материал пособия консолидирует многолетний опыт
работы авторов в преподавании различных курсов программирования.
Соответствует ФГОС ВПО третьего поколения для направления «Прикладная информатика».
Не требуется каких-либо предварительных знаний
о языках программирования, поэтому пособие может
быть рекомендовано для самостоятельного изучения.

Гл ава 1

Основы алгоритмизации

1.1. Определение алгоритма
и его свойства

П

од алгоритмом понимается точное предписание, задающее последовательность действий, которая ведет
от произвольного исходного данного (или от некоторой совокупности возможных для данного алгоритма исходных
данных) к достижению полностью определяемого этим
исходным данным результата.
Алгоритм должен обладать определенными свойствами, наличие которых гарантирует получение решения задачи исполнителем.
Дискретность. Решение задачи должно быть разбито
на элементарные действия. Запись отдельных действий
реализуется в виде упорядоченной последовательности
отдельных команд, образующих дискретную структуру алгоритма. Это свойство непосредственно отражено
в определении алгоритма.
Понятность. На практике любой алгоритм предназначен для определенного исполнителя, и любую команду
алгоритма исполнитель должен уметь выполнить.
Определенность (детерминированность). Каждая команда алгоритма должна определять однозначные действия исполнителя. Результат их исполнения не должен
зависеть от факторов, не учтенных в алгоритме явно. При
одних и тех же исходных данных алгоритм должен давать
стабильный результат.
Массовость. Разработанный алгоритм должен давать
возможность получения результата при различных исходных данных для однотипных задач.

6

Гл а в а 1

Например, пользуясь алгоритмом решения квадратного уравнения, можно находить его корни при любых
значениях коэффициентов.
Свойство массовости полезное, но не обязательное
свойство алгоритма, так как интерес представляют и алгоритмы, пригодные для решения единственной задачи.
Результативность (конечность). Это свойство предполагает обязательное получение результата решения задачи за конечное число шагов. Под решением задачи понимается и сообщение о том, что при заданных значениях
исходных данных задача решения не имеет.
Если решить задачу при заданных исходных данных
за конечное число шагов не удается, то говорят, что алгоритм «зацикливается».
Смысл условий дискретности, понятности и определенности ясен: их нарушение ведет к невозможности
выполнения алгоритма. Остальные условия не столь
очевидны. Для сложных алгоритмов выполнить исчерпывающую проверку результативности и корректности
невозможно. Это равносильно полному решению задачи,
для которой создан алгоритм, вручную.
Можно сформулировать общие правила, руководствуясь
которыми следует записывать алгоритм решения задачи.
1. Выделить величины, являющиеся исходными данными для задачи.
2. Разбить решение задачи на такие команды, каждую
из которых исполнитель может выполнить однозначно.
3. Указать порядок выполнения команд.
4. Задать условие окончания процесса решения задачи.
5. Определить, что является результатом решения задачи в каждом из возможных случаев.
Хотя алгоритмы обычно предназначены для автоматического выполнения, они создаются и разрабатываются людьми. Поэтому первоначальная запись алгоритма обычно производится в форме, доступной для восприятия человеком.
Самой простой является словесная форма записи алгоритмов на естественном языке. В этом виде алгоритм
представляет собой описание последовательности этапов
обработки данных, изложенное в произвольной форме.

7

Ос н о в ы а л г о р и т м и з а ц и и

Словесная форма удобна для человеческого восприятия,
но --">