Математический аппарат инженера

5) вычитай второе число из первого и обозревай два числа — вычитаемое и остаток; переходи к указанию 2.

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

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

!!!!

Рис. 257. Поиск пути в лабиринте от точки a к точке f.

3. Логические алгоритмы. Существует другой тип алгоритмов, которые содержат предписания, относящиеся не к цифрам, а к объектам любой природы. Типичным примером логических алгоритмов может служить алгоритм поиска пути в конечном лабиринте.

Лабиринт удобно изображать в виде графа, вершины которого соответствуют площадкам, а дуги — коридорам (рис. 257). Пусть требуется выяснить, достижима ли площадка f из площадки a, и если да, то найти путь из a в f, а если нет — вернуться в a. Конечно, предполагается, что заранее ничего не известно об устройстве данного лабиринта.

Лицо, ищущее путь в лабиринте, располагает нитью, конец которой закреплен на площадке a, и, двигаясь по лабиринту, может разматывать клубок (Р) или наоборот наматывать на него нить (Н). Можно делать отметки на проходимых коридорах и различать затем коридоры, еще ни разу не пройденные (зеленые — З), пройденные один раз (желтые — Ж) и пройденные дважды (красные — К). Метод поиска может быть задан следующей схемой:

1) площадка f — остановка (цель достигнута);

2) петля (П) — наматывание нити (от данной площадки расходятся, по крайней мере, два желтых коридора);

3) зеленая улица (ЗУ) — разматывание нити (от

- 622 -

данной площадки отходит хотя бы один зеленый коридор);

4) площадка a — остановка (исходный пункт);

5) отсутствие всех предыдущих признаков (ОП) — наматывание нити.

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

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

1) ЗУ — Р — ab — Ж;

2) ЗУ — Р — bc — Ж;

3) ЗУ — Р — cd — Ж;

4) ЗУ — Р — dg — Ж;

5) ЗУ — Р — gh — Ж;

6) ОР — Р — hg — K;

7) ОР — Р — gd — K;

8) ЗУ — Р — db — Ж;

9) П — Р - bd — K;

10) ЗУ — Р — df — Ж;

11) площадка f — остановка.

В данном случае площадка f оказалась достижимой (недостижимыми являются площадки i, k, l , m). Выделив коридоры, которые остались желтыми (ab, bc, cd, df), получим путь от a к f (abcdf, указанный на рис. 257 жирными дугами).

4. Общие свойства алгоритмов. Богатый опыт разработки и применения алгоритмов подсказывает ряд общих свойств, которые детализируют приведенное выше описание.

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

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

Направленность алгоритма. Если способ получения последующей величины из какой-нибудь заданной не приводит к результату, то должно быть указание, что´ надо считать результатом алгоритма. Иначе говоря, алгоритм через конечное число тактов времени (шагов) должен привести к остановке, которая свидетельствует о достижении требуемого результата. Так, при поиске пути в лабиринте остановка наступает либо на достижимой площадке, либо при возвращении на исходную площадку, если указанная цель недостижима.

- 623 -