Понятие о вспомогательном алгоритме

Вернемся к примеру, разобранному в пункте 7.7. Составляя алгоритм решения задачи, мы выделили повторяющуюся часть пути Робота, записали ее в одну строку алгоритма и повторили эту строку необходимое число раз А2.

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

Избежать этого можно, если вместо повторения строки использовать вызов вспомогательного алгоритма.

А6

Оформим прохождение части лабиринта, показанной на рисунке 3 б, в виде отдельного алгоритма.

 

 

алг участок

дано | Робот в начале участка (рис. 3 б)

надо | Робот в конце участка (рис. 3б)

Нач

I вверх; вверх; вправо; вниз; вниз; вправо

Кон

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

 

алг из А в Б

дано | Робот в клетке А (рис. 3 а)

надо | Робот в клетке Б (рис. 3 а)

Нач

| участок; участок; участок; участок; участок

Кон

 

Запись "участок" в алгоритме "из А в Б" — это команда вызова вспомогательного алгоритма с именем "участок". Выполняя эту команду, компьютер приостанавливает выполнение алгоритма "из А в Б", выполняет алгоритм "участок", а затем продолжает выполнение алгоритма "из А в Б".

 

Основные и вспомогательные алгоритмы

 

В рассмотренном примере алгоритм "участок" называется вспомогательным для алгоритма "из А в Б", а алгоритм "из А в Б" — основным для алгоритма "участок".

Приказ на выполнение вспомогательного алгоритма называется вызовом этого вспомогательного алгоритма.

В общем случае если в записи алгоритма X встречается вызов алгоритма Y, то алгоритм Y называется вспомогательным для X, а алгоритм X называется основным для Y.

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

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

Использование уже написанных алгоритмов как вспомогательных позволяет свести новую задачу к уже решенным. Такой метод построения алгоритмов иногда называют программированием снизу вверх.

Пример использования вспомогательных алгоритмов

Пусть требуется написать алгоритм, который проводит Робота из клетки А в клетку Б и закрашивает клетки, отмеченные точками (рис. 6). На рисунке показан один из возможных путей Робота при решении этой задачи. Видно, что Робот должен закрасить три прямоугольных «блока» размером 3x5 клеток, а между закрашиваниями два раза обойти стену. Запишем эту мысль в виде основного алгоритма:

А8

алг из А в Б с закрашиванием

дано | Робот в точке А (рис. 6)

надо | Робот в точке Б (рис. 6), нужные клетки закрашены

Нач

закрашивание блока

обход стены

закрашивание блока

обход стены

закрашивание блока

кон

Теперь составим вспомогательные алгоритмы, используемые в основном алгоритме "из А в Б с закрашиванием" (А8):

 

А9

алг закрашивание блока

дано |. Робот в левом верхнем углу блока 3x5 клеток

надо | блок закрашен, Робот в его правом нижнем углу

Нач

закрасить; вправо; закрасить; вправо; закрасить; вниз

закрасить; влево; закрасить; влево; закрасить; вниз

закрасить; вправо; закрасить; вправо; закрасить; вниз

закрасить; влево; закрасить; влево; закрасить; вниз

закрасить; вправо; закрасить; вправо; закрасить

Кон

	А10

алг обход стены

дано | Робот в правом нижнем углу блока (рис. 6)

надо | Робот в левом верхнем углу следующего блока (рис. 6)

Нач

вправо; вверх; вверх; вверх; вверх; вверх; вверх

вправо; вправо; вниз; вниз

Кон

 

 

Рис. 6