6.5. «Часовые»

Следующий раздел не касается языков программирования как таковых; ско­рее, он предназначен для того, чтобы показать, что программу можно улуч­шить за счет более совершенных алгоритмов и методов программирования, не прибегая к «игре» на языковых частностях. Этот раздел включен в книгу, по­тому что тема выхода из цикла при последовательном переборе является пред­метом интенсивных дебатов, однако существует и другой алгоритм, который является одновременно ясным, надежным и эффективным.

В последнем примере предыдущего раздела (поиск в массиве) есть три ко­манды перехода в каждой итерации цикла: условный переход цикла for, услов­ный переход if-оператора и переход от конца цикла обратно к началу. Пробле­ма поиска в данном случае состоит в том, что мы проверяем сразу два условия: найдено ли значение key и достигнут ли конец массива? Используя «часового» (sentinel) *, мы можем два условия заменить одним. Идея состоит в том, чтобы ввести в начале массива дополнительно еще один элемент («часового») и хра­нить в нем эталонное значение key, которое нужно найти в массиве (рис. 6.4).

Поскольку мы обязательно найдем key либо как элемент массива, либо как искусственно введенный элемент, постольку достаточно проверять только од­но условие внутри цикла:

Ada

type А_Туре is array(0 .. 100) of Integer;

-- Дополнительное место в нулевой позиции для «часового»

function Find_Key(A: A_Type; Key: Integer)

return Integer is

I: Integer := 100; -- Поиск с конца

begin

A(0) := Key; -- Установить «часового»

while A(l) /= Key loop

I:=I-1;

end loop;

return I;

end Find_Key;

Если при возврате управления из функции значение I равно нулю, то Key в

массиве нет; в противном случае I содержит индекс найденного значения.

Этот код более эффективен, цикл чрезвычайно прост и может быть легко про-

верен.