Способы записи алгоритмов

Алгоритмы

Лекция 3 Управляющие структуры

3.1 Введение

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

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

1. операций, которые должны выполняться, и

2. порядка, в котором эти операции должны выполняться,

называется алгоритмом.

Известны два способазаписи алгоритмов: псевдокод и блок-схема.

Псевдокод — это искусственный и неформальный язык, который помогает программистам разрабатывать алгоритмы. Псевдокод, который мы рассматриваем, часто используется для разработки алгоритмов, которые потом должны быть преобразованы в структурированные фрагменты программ на С++. Псевдокод подобен разговорному языку; он удобный и ясный, но это не язык программирования.

Программы на псевдокоде не могут выполняться на компьютере. Их назначение — помочь программисту «продумать программу», прежде чем пытаться написать ее на таком языке программирования, как С++. Тщательно подготовленная программа на псевдокоде может быть легко преобразована в соответствующую программу на С++. Во многих случаях для этого достаточно просто заменить операторы псевдокода их эквивалентами на С++.

Псевдокод обычно включает только исполняемые операторы — те, вызывают конкретные действия, когда программа переведена из псевдокода на С++ и запущена на компьютере. Обычно в псевдокод не включают объявления переменных. Однако некоторые программисты предпочитают составлять список переменных с кратким описанием их назначения и помещать его в начале программ на псевдокоде.

Блок-схема является графическим представлением алгоритма или части алгоритма. При рисовании блок-схемы используются некоторые символы специального назначения, такие как прямоугольники, ромбы, овалы и кружки; эти символы соединяются стрелками, называемыми линиями перехода.

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

Возможно, наиболее важным символом при составлении блок-схем является символ ромба, называемый символом принятия решения, который указывает на

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

3.4. Управляющие структуры

Обычно операторы программы выполняются друг за другом в той последо­вательности, в которой они написаны. Это называется последовательным исполнением. Однако некоторые операторы С++, которые мы будем здесь обсуждать, позволяют программисту указать, что следующим должен выполняться не очередной оператор в последовательности, а какой-то другой. Это называется передачей управления.

В 60-е годы стало ясно, что неосторожное использование передач управле­ния является источником множества трудностей при групповой разработке программного обеспечения. Вина была возложена на оператор goto, который позволяет программисту передавать управление в очень широких пределах (что приводит к коду, который иногда называют «лапшой»). Понятие так называемого структурного программирования стало почти синонимом «исключения goto».

Исследование Бома и Джакопини^[1] показало, что программы могут быть написаны без использования оператора goto. В результате для программистов настала эра перехода к стилю программирования «с минимальным использованием goto». Но только в 70-х годах программисты стали принимать структурное программирование всерьез. Результаты получились впечатляющие: группы разработчиков программного обеспечения сообщали, что время разработок сократилось, производительность труда выросла, и проекты стали чаще укладываться в рамки бюджета. Ключом к успеху явилось то, что структурированные программы стали более прозрачными, легче поддавались отладке и модификации и, что самое главное, в них стало меньше ошибок.

Работа Бома и Джакопини показала, что все программы могут быть написа­ны с использованием всего трех управляющих структур, а именно, последовательной структуры, структуры выбора и структуры повторения. Термин «управляющие структуры» взят из компьютерной теории. Когда мы будем представлять реализацию управляющих структур в С++, мы, в соответствии с терминологией стандартного

Последовательная структура встроена в С++. Если не указано иначе, компьютер автоматически выполняет операторы С++ один за другим в порядке их записи.

Структуры выбора используются для избрания одного из альтернативных направлений действий.

Структура повторения – это многократное повторение одних и тех же действий для решения задачи. На практике это реализуется либо с помощью рекурсии либо с помощью итерации. Итерация — это повторение одних и тех же действий определенное количество раз. Основным методом итерации является цикл.

Управляющие структуры могут присоединяться друг к другу путем соединения точки выхода одной управляющей структуры, с точкой входа последующей. Этот способ соединения структур называется суперпозицией управляющих структур. Существует еще только один способ их соединения — метод, называемый вложением управляющих структур. Таким образом, любая программа на языке C++ может быть построена из различных типов управляющих структур, объединенных одним из двух возможных способов.

3.5 Операторы выбора в С++

Язык С++ предоставляет программисту три типа структур выбора в форме операторов. В операторе выбора if некоторое действие либо выполняется (выбирается), если условие истинно, либо пропускается, если это условие ложно. В операторе выбора if..else некоторое действие выполняется, если условие истинно, и выполняется другое действие, если это условие ложно. В операторе выбора switch выполняется одно из набора различных действий в зависимости от значения некоторого выражения. В языке С++ также существует четвертый оператор выбора - тернарный условный оператор ?:, который является альтернативой оператору if..else.

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