13. Разветвляющиеся алгоритмы
13.1 Таблица ситуаций и команда выбора.
До этого мы в основном рассматривали линейные алгоритмы, которые получаются на начальных этапах разработки алгоритма (циклы можно тоже рассматривать как сокращенную запись линейной последовательности действий). Линейными они называются потому, что подзадачи в них выполняются в том порядке, как они записаны сверху вниз.
Если при уточнении алгоритма оказывается, что выполнение или невыполнение каких-то действий зависит от наступления или ненаступления каких-то ситуаций, то необходимо
- перечислить эти ситуации и указать этот перечень исполнителю алгоритма,
- для каждой ситуации надо описать:
а) как проверять факт её наличия (наступлении) или отсутствия (ненаступления),
б) что надо делать при наличии (наступлении) ситуации.
Прежде чем описания и действия в каждой ситуации записывать формально, необходимо составить таблицу ситуаций следующего вида:
-
Ситуация
Действие
Ситуация 1
Действие 1
Ситуация 2
Действие 2
...
...
Ситуация n
Действие n
Здесь под словом "ситуация" понимается такое описание каждой ситуации, по которому их можно отличить друг от друга. На начальных этапах разработки алгоритма обычно используют в качестве описания ситуации просто ее название. Порядок анализа ситуаций в таблице ситуаций не фиксируется.
13.2 Средства языка Паскаль для программирования разветствляющихся алгоритмов
Таблицу ситуаций удобно было бы уточнять с помощью команды выбора следующего вида (на Псевдокоде):
Выбрать
при ситуация 1: действие 1;
при ситуация 2: действие 2;
...
при ситуация n: действие n;
Все.
Алгоритм выполнения этой команды выбора следующий (здесь уже порядок действий важен):
1). Просмотреть все ситуации в записанном порядке сверху вниз;
2). При совпадении текущей ситуации с одной из ситуаций из приведенного (в команде выбора) списка выполнить действия, соответствующие данной ситуации;
3). После выполнения действий для конкретной ситуации все оставшиеся строки в команде выбора пропускаются, т.е. выполняется переход к слову все;
4). Если текущая ситуация не совпадает ни с одной ситуацией из приведенного списка, то команда выбора игнорируется (пропускаются все действия в ней)).
К сожалению в том виде, в котором мы команду выбора записали, она не поддерживается ни Паскалем, ни другими языками программирования. На Паскале последней команде выбора соответствует следующий оператор:
селектор
Case C of
набор1: оператор1;
набор2: оператор2;
...
наборn: операторn;
end
Переменная "селектор" (ее начения рассматриваются как признаки наступления ситуаций) может быть любого порядкового типа. Особенность данного вида команды выбора состоит в том, что одна ситуация от другой отличается по набору значений этой переменной. Существуют следующие случаи задания таких наборов:
1-й случай: указывается просто одна константа (порядкового типа)
2-й случай: указывается несколько констант, разделенных запятыми
3-й случай: указывается диапазон значений (констант)
4-й случай: комбинация первых трех случаев.
Замечание1: Переменная селектор на Паскале может быть любого порядкового типа, кроме longint.
Замечание2: После каждого двоеточия вы можете написать действие только из одного оператора. В случае необходимости записать несколько операторов нужно заключать эти операторы в операторные скобки (begin - end).
ПРИМЕР: Стоит задача для введенного символа вывести на экран информацию о том, какой это символ: буква (для простоты примера - латинская) или цифра?
var
C:char;
Begin
Write(‘Введите символ: ’);
readln(C);
Case C of
‘A’..’Z’,’a’..’z’: writeln(‘Это буква’);
‘0’..’9’: writeln(‘Это цифра’);
end;
End.
Дополним текст этой программы, чтобы постараться увеличить число распознаваемых ситуаций ( 1 – цифра, 2 – буква, 3 – строчная буква, 4 – прописная буква):
var
C:char;
Begin
Write(‘Введите символ: ’);
readln(C);
Case C of
‘0’..’9’ : writeln(‘ -->’, C, ‘ – это цифра’);
‘A’..’Z’,’a’..’z’: writeln(‘ -->’, C, ‘ – это буква’);
’a’..’z’ : writeln(‘ -->’, C, ‘ – это строчная буква’);
‘A’..’Z’ : writeln(‘ -->’, C, ‘ – это прописная (заглавная) буква’);
end;
End.
Вопрос: если будет введен символ, например ‘d’, то что будет выведено на экран?
Ответ: для выделенные строки будет выдаваться сообщение компилятора типа
«Duplicate case label».
Дело все в том, что наборы не должны пересекаться, иначке компилятор будет ругаться про дублирование констант.
Вопрос: как же написать, чтобы выводилась информация и о том, что символ есть буква, и о том, какая это буква – строчная или прописная? Ответ - никак.
Если число ситуаций не превышает двух и ситуации взаимоисключающие, то целесообразно для уточнения таблицы ситуаций использовать не команду выбора, а команду ветвления следующего вида: описание ситуации (в виде логического выражения)
if ситуация
then действие 1 //для ситуации 1
else действие 2 //для ситуации 2
Ситуации |
Действия |
Ситуация 1 имеет место |
действие 1 |
Ситуация 1 не наступила |
действие 2 |
Этой
команде соответствует следующая таблица
ситуаций и схема алгоритма:
значит, наступила ситуация 2
(если ситуации взаимоисключающие)
Если при не наступлении ситуации никаких действий выполнять не нужно, то можно использовать сокращенную форму записи команды ветвления:
-
if ситуация
then действие;
Ситуации
Действия
ситуация имеет место
действие 1
ситуация не наступила
- (пусто)
На Паскале команде ветвления соответствует условный оператор (оператор if):
Замечание 1: При записи условного оператора на Паскале наиболее частой ошибкой является запись ';' перед else. Точка с запятой пишется после then только при отсутствии else.
Замечание 2: После then и else можно указать только один оператор, если нужно использовать несколько операторов, то нужно использовать операторные скобки (begin – end).
Замечание 3: else всегда соответствует самому ближайшему выше по тексту программы оператору if, не имеющему части else. Для явного указания того, к какому if из последовательности относится else у программиста есть два пути:
использовать else с пустым оператором в качестве действия в тех вышестоящих (относительно нашего else) операторах if, к которым мы не хотим отнести данный else.
использовать операторные скобки для обозначения границ действий по ветвям then и else для каждого оператора if.
Пример:
if (C1)
then if (C2)
then D1
else D2;
Вопрос: как сделать, чтобы D2 относился не к С2, а к С1?
1-й вариант
if (C1)
then if (C2)
then D1
else ; <-- не ставить ‘;’
else D2
2-й вариант
if (C1)
then
begin
if (C2)
then D1
end ; <-- не ставить ‘;’
else D2
13.3 Виды ситуаций.
Ситуации бывают зависимыми и независимыми.
Независимые - это такие ситуации, наступление или не наступление которых не зависит от наступления каких-либо других ситуаций. Зависимые - это такие ситуации, наступление или не наступление которых зависит от наступления каких-либо других ситуаций.
Независимые ситуации могут иметь место одновременно (а зависимые – нет). Дело в том, что независимые ситуации обычно разнесены по различным подзадачам. Исходя из этого независимые ситуации вместе (в рамках одной подзадачи) обычно не рассматриваются.
Все ситуации, упомянутые ранее в таблице ситуаций, являются зависимыми. Кроме того, ситуации, рассмотренные в таблице ситуаций, должны быть взаимоисключающими, т.е. подчиняются следующим трем правилам:
Эти ситуации образуют полную группу событий в том смысле, что из этой группы нельзя без потери смысла выкинуть и добавить ситуацию.
В каждый конкретный момент времени имеет место только одна ситуация из списка .
В случае отсутствия признаков наступления (n-1)-ной из n ситуаций можно гарантированно сделать вывод о наступлении n-ой ситуации.
Последнее означает, что для n взаимоисключающих ситуаций в команде выбора достаточно описать (n-1) ситуацию.
С учетом сказанного более полная форма команды выбора на Паскале имеет следующий вид:
case имя of
набор 1: оператор 1;
набор 2: оператор 2;
...
набор n-1: оператор n-1 ;
else оператор n ;
end; можно ставить, а можно и не ставить
действия в случае отсутствия признаков наборов с 1 по n
(необязательная конструкция)
Соответственно, для приведенного выше примера распознавания типа введенного символа оператор CASE мог бы иметь следующий расширенный вид:
var
C:char;
Begin
Write(‘Введите символ: ’);
readln(C);
Case C of
‘A’..’Z’,’a’..’z’: writeln(‘Это буква’);
‘0’..’9’ : writeln(‘Это цифра’);
else writeln(‘Неизвестный символ’);
end;
End.
Рассмотрим Пример. Пусть необходимо распознать треугольник по трем его сторонам. Пусть стороны называются a, b, c. Результатом анализа должен являться вывод сообщения на экран о конкретном виде треугольника.
В самом начале мы имеем дело с двумя ситуациями:
Ситуация |
Действие |
Треугольник существует |
Определить вид треугольника |
Треугольник не существует |
Сообщение := 'Треугольник не существует' |
Рассмотрим уточнение действия в первой ситуации. При определении вида треугольника возможны следующие ситуации:
Ситуация |
Действие |
Треугольник равностор. |
Сообщение := 'Треугольник равносторонний' |
Треугольник равнобедр. |
Сообщение := 'Треугольник равнобедренный' |
Треугольник произвол. |
Сообщение := 'Треугольник произвольный' |
Построим итоговый алгоритм.
операторы IF вкладываются один в другой
В итоге получим:
if (треугольник существует)
then
if (треугольник равносторонний)
then writeln(‘Этот треугольник равносторонний’)
else
if (треугольник равнобедренный)
then writeln(‘Этот треугольник равнобедренный’)
else writeln(‘Этот треугольник имеет произвольную форму’)
else writeln(‘Такого треугольника не существует’);
Замечание: из данного примера видно, что для каждой таблицы ситуаций число уточняющих ее операторов if должно быть равно (число ситуаций в таблице) - 1.