Запись команды выбора (case) (уточнение таблицы ситуаций) с помощью набора команд ветвления

Если одна ситуация от другой отличается гораздо больше, чем набором значений одной переменной и когда число ситуаций >2, то нужно записать команду выбора с помощью набора команд ветвления (if). Это можно сделать двумя очень похожими путями:

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

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

Рассмотрим пример:

Выбрать

при С1: D1;

при C2: D2;

при C3: D3;

...

при Cn: Dn;

все.

Для этой команды выбора запишем набор команд ветвления двумя способами.

1-й способ

2-й способ (считаем, что ситуации являются зависимыми и наступить может лишь одна из них)

В принципе, оба этих способа делают одно и то же. Однако каждый из них требует разных объемов сравнений (число сравнений и там и там одинаково и равно (n-1)). Различаться по объему сравнений эти способы будут в том случае, если ситуации С1, С2, ..., Сn имеют общий признак.

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

Классический пример: вычисление функций на разных интервалах.

Пример: пусть выражение для вычисления функции имеет следующий вид:

f1(x) при x <= -1

y = f2(x) при -1 < x <= 1

f3(x) при 1 < x <= 3

f4(x) при x > 3

x₁, x₂, x₃, ... – границы интервалов определения функции

Для решения поставленной задачи можно использовать нисходящий и восходящий подходы.

Восходящий подход

При вычислении значений функции мы столкнемся со следующими ситуациями:

Для этой таблицы ситуаций запишем набор команд ветвления. Таких команд ветвления в общем случае будет столько, сколько интервалов имеет функция.

По 1-му сособу записи последовательности операторов if:

if (х > -¥) и (х <= -1)

then вычислить y = f1(x);

Всегда имеют место

if (х > -1) и (х <= 1)

then вычислить y = f2(x);

if (х > 1) и (х <= 3)

then вычислить y = f3(x);

if (х > 3) и (х < ¥)

then вычислить y = f4(x);

Дальнейшие действия:

1) Из описания ситуации нужно выкинуть избыточные признаки (они всегда имеют место).

2) Внимательно рассмотренная последовательность команд показывает, что при той последовательности анализа цепочки ситуаций одни и те же признаки мы неоднократно проверяем.

При проверке х <= -1 и х > -1 проверяется один и тот же признак: "как соотносятся (х) и (-1)?" просто этот признак имеет разное значение на разных интервалах.

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

NB: Здесь общие признаки есть потому, что смежные интервалы имеют общие границы (левую для одного и правую для другого).

x <= -1 x > -1

П1 не П1

x <= 1 x > 1

П2 не П2

Если удалось выявить в ситуации общие признаки и удалось выразить одни признаки через другие, то имеется возможность, при правильном порядке анализа ситуаций (имеющих общие признаки), сократить описание каждой ситуации с двух до одного признака. Правильным порядком в данном случае является порядок, при котором каждая последующая ситуация имеет общий признак с предыдущей. Рассмотрим, как это можно сделать 2-м способом записи команды ветвления (для указанного выше рисунка):

if x <= -1

then вычислить y = f1(x)

else

if x < 1 {уже известно, что x>-1}

then вычислить y = f2(x)

else

if x < 3

then вычислить y = f3(x)

else вычислить y = f4(x);

Здесь при анализе признака x < 1 уже известно, что x > -1. Поэтому проверка ((x > -1) и (x <=1 )) - была бы лишней.

Легко заметить, что объем вычислений (или количество проверок) при этом подходе гораздо меньше.

Нисходящий подход

Выделенные нами ситуации образуют некоторое пространство. Две ситуации С1 и С2 в этом пространстве назовем соседними, если для одной из них обязательным является наличие признака П1, а для другой - его отсутствие:

С1 С2

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

П1 П2 П3

>

П1 не П1 С1 С2 С3 С4

Мы будем использовать метод половинного деления цепочки ситуаций. Чтобы уменьшить число этапов уточнения надо весь анализируемый интервал делить по числу границ приблизительно пополам. В этом случае на каждом этапе уточнения надо анализировать 2 ситуации: а) попали в левую половину промежутка б) попали в правую половину промежутка. После этого и левую и правую половины интервала надо снова поделить пополам и.т.д.

П_i = ( x _i) )

Левая половина цепочки Правая половина цепочки

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

y=f1(x) y=f2(x) y=f3(x) y=f4(x)` y=f5(x) y=f6(x)

x1 x2 x3 x4 x5

14.Циклы с неизвестным числом повторений

В тех циклах, которые мы рассматривали до этого, имелся т.н. параметр цикла, который выполнял следующие функции:

1) С его помощью задавалось нужное количество повторений тела цикла.

2) Выполнение цикла начиналось с нужной компоненты.

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

В циклах с неизвестным числом повторений параметр цикла отсутствует. Для этих циклов необходимо "вручную" выполнить следующее:

1) Необходимо позаботиться, чтобы действия начались с нужной компоненты:

- с нужного слагаемого при нахождении суммы;

- с нужного элемента массива, при обработке массива.

2) Надо позаботиться, чтобы на следующем выполнении (повторении) тела цикла использовались новые данные (следующая компонента).

3) Надо позаботиться, чтобы цикл выполнялся нужное число раз.

Существует две разновидности циклов с неизвестным числом повторений на псевдокоде и Паскале:

Цикл с постусловием. Он выполняется всегда хотя бы 1 раз. Цикл с постусловием будет выполняться до тех пор, пока ситуация2 не наступит. Эту ситуацию называют ситуацией завершения.

логическая переменная или лог. выражение

Тело цикла для цикла с предусловием может состоять только из одного оператора. Для цикла с постусловием тело может состоять из нескольких операторов.

В общем случае структура цикла с неизвестным числом повторений имеет следующий вид:

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

цикл с предусловием: < подготовка цикла> цикл: если продолжить то нц тело цикла идти к цикл кц всё	цикл с постусловием: < подготовка цикла> цикл: тело цикла если закончить то идти к финиш иначе идти к цикл все финиш:

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

Циклы, которые не будут выполняться: Примеры простых бесконечных пустых циклов:

While (false) do; - ни разу while true do

Repeat while true; - только один раз. repeat until false;

Рассмотрим простые правильные примеры (шаблоны) использования циклов с неизвестным числом повторений:

1. Цикл, управляемый счетчиком (аналог цикла for, но с произвольным шагом счетчика)

{подготовка цикла}

Счетчик:=0; // инициализация счетчика

while Счетчик <= Конечное_значение do

begin

... проверка счетчика

<Использование текущего значения счетчика>

Счетчик := Счетчик + Шаг; //модификация счетчика (увеличение или уменьшение)

end;

2. цикл, управляемый т.н. «сигнальной меткой»

Используется при обработке потока входных данных, количество которых заранее неизвестно (такие потоки входных данных называются последовательностями).

Последовательность имеет следующие черты:

- число элементов неизвестно;

- последним элементов должен быть признак конца последовательности;

- признак конца последовательности не должен совпадать ни с одним из значащих элементов последовательности;

- нельзя напрямую обратиться к нужному элементу (по имени, по номеру);

- не обязательно хранить в памяти всю последовательность (достаточно хранить только один - текущий для его обработки).

Сигнальная метка (признак конца последовательности) – уникальное значение во входном потоке, которое обозначает конец входного потока, но само это значение не является частью потока - не может использоваться (обрабатываться) как данные. Например, если вводится и обрабатывается поток целых положительных чисел, то в качестве такой сигнальной метки можно принять число = -1. Начинать обработку любой последовательности надо с выбора значения «сигнальной метки» (исходя из типа элементов последовательности).

{подготовка цикла} исходя из типа элементов последовательности

Сигнальная_метка := Выбранное_значение

Считать текущее значение из входного потока и присвоить его входной_переменной

while входная_переменная ≠ Сигнальная_метка do

begin

Обработать текущее значение входной_переменной

Считать текущее значение из входного потока и присвоить его входной_переменной

end;

3. цикл, управляемый событием (флагом)

Чтобы не было зацикливания, следует делать следующее (при отладке): - считать число шагов (и прерывать цикл, когда число шагов превышает некое максимальное, заранее заданное); - считать время (и прерывать цикл, когда время превышает некое максимальное, заранее заданное).

Здесь используется булевская переменная, которая своим значением (True или False) указывает, наступило или нет определенное ожидаемое событие. Такая переменная часто называется флагом (фложком). Начальное значение флага обычно принимается равным False, а цикл должен (будет) продолжаться до тех пор, пока флаг не станет равным True (пока не наступит ожидаемое событие). При этом предполается, что в теле цикла выполняются действия, которые могут изменить значение флага.

{подготовка цикла} или Флаг = false

флаг := False; // инициализация флага

while (Not флаг) do

begin непрерывно гоняя цикл

...

<пусто> если ожидаем наступление внешнего события

или по отношению к программе (процессу)

<выполнение действий, влияющих на флаг>

end;

Рассмотрим более сложный пример:

На интервале [x1, x2] находится корень уравнения. надо найти этот корень.