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

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

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

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

А6

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

алгучасток

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

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

Нач

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

Кон

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

алгиз А в Б

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

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

Нач

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

Кон

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

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

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

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

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

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

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

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

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

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

А8

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

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

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

Нач

Понятие о вспомогательном алгоритме - student2.ru закрашивание блока