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

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

 Убрать со столов посуду. 
 Вытереть столы. 
 Расставить стулья. 
 Уйти.

Эту последовательность действий предстоит выполнить три раза за дежурство: после завтрака, обеда и ужина. Назовем соответствующий алгоритм "Обязанности", а при написании распорядка дня заменим эти четыре действия одной командой:

 Выполнить алгоритм "Обязанности".

Тогда распорядок дежурства по столовой примет такой вид:

 Прийти в столовую в 7.00. 
 Накрыть столы к завтраку. 
 Дождаться окончания завтрака. 
 Выполнить алгоритм "Обязанности". 
 Прийти в столовую в 13.00. 
 Накрыть столы к обеду. 
 Дождаться окончания обеда. 
 Выполнить алгоритм "Обязанности". 
 Прийти в столовую в 18.00. 
 Накрыть столы к ужину. 
 Дождаться окончания ужина. 
 Выполнить алгоритм "Обязанности".

Легко понять, что использование команды "Выполнить алгоритм..." позволило почти в два раза сократить длину нашей инструкции.

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

Каждому вспомогательному алгоритму - достойное имя

Этот набор действий выделяют в качестве самостоятельного алгоритма и дают ему алгоритму - имя. С этого момента он становится вспомогательным алгоритмом, т. е. появляется возможность его использования в других алгоритмах. Набор команд, из которых состоит вспомогательный алгоритм, заменяют одной командой

 Выполнить алгоритм...,

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

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

Раз уж речь зашла о школе, вспомним материал VIII класса - решение квадратных уравнений. Если бы тогда вы изучали информатику, то могли бы записать решение квадратного уравнения ах² + bx + c = Q (считаем, что а≠0) в виде следующего алгоритма:

 Найти дискриминант d = b2 - 4ac. 
 Если d<0, то: 
 Сообщить "Уравнение корней не имеет". 
 Иначе: 
 Найти квадратный корень из d и обозначить его буквой р. 
 Найти x1 по формуле . 
 Найти x2 по формуле .

Конец ветвления.

Дадим алгоритму решения квадратных уравнений имя "РЕКВУР" (впрочем, вы можете назвать этот алгоритм по-другому, более благозвучно).

И в X классе вы, конечно, сталкивались с квадратными уравнениями в ходе решения различных задач. Но теперь решение квадратных уравнений стало для вас столь же элементарным, как перемножение чисел (возможно, что мы выдаем желаемое за действительное). Можно сказать, что "РЕКВУР" стал вашим вспомогательным алгоритмом.

Давайте проанализируем, как мы выполняем алгоритм "РЕКВУР". Скажем, нужно решить уравнение

Мы вспоминаем "РЕКВУР", подставляем вместо а, b, с числа 2, 3 и 122 и получаем результат: x₁ и х₂. Чтобы решить другое квадратное уравнение, надо подставить вместо а, b, с другие числа.

Как видите, между вспомогательными алгоритмами "Обязанности" и "РЕКВУР" есть существенная разница. В команде вызова алгоритма "РЕКВУР" необходимо указывать значения исходных данных - коэффициентов квадратного уравнения, которое требуется решить. А в алгоритме "Обязанности" нет исходных данных. Поэтому ничего, кроме названия, в команде вызова указывать не надо.

При использовании вспомогательного алгоритма, как правило, никого не интересует, из каких действий он состоит. Важно только, каковы исходные данные (аргументы) этого алгоритма и что является результатом его работы. Точно так же для того, чтобы пользоваться стиральной машиной, не обязательно вникать в ее устройство. Достаточно знать, что "аргументами" Для нее являются стиральный порошок, чистая вода и грязные вещи, а "результатом" - грязная мыльная вода и чистые вещи. Что касается алгоритма "РЕКВУР", то его аргументами являются коэффициенты а, b и с, а результатом - либо корни x₁, x₂, либо сообщение, что корней нет.

Записывая вспомогательный алгоритм, естественно указывать, кроме названия, аргументы и результат. Например, запись вспомогательного алгоритма "РЕКВУР" можно начать так:

 Алгоритм "РЕКВУР". 
 Аргументы: а, b, с (коэффициенты квадратного уравнения). 
 Результаты: x1, х2 или сообщение "Корней нет".

При вызове вспомогательного алгоритма надо указывать значения исходных данных. Например, вызов вспомогательного алгоритма "РЕКВУР" можно записать так:

 Выполнить алгоритм "РЕКВУР" при а = ..., b = ..., с =... . 
 Или так: 
 Выполнить алгоритм "РЕКВУР", взяв в качестве аргументов ..., ... и ... .

(вместо многоточий надо писать конкретные числа или выражения).

Давайте с помощью алгоритма "РЕКВУР" решим какую-нибудь задачу из вашего учебника "Алгебра и начала анализа". Заглянем в него. Вот, например, тема "Показательные уравнения и неравенства". В ней объясняется, как решать уравнения вида

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

 Запросить d, р, q. 
 Выполнить алгоритм "РЕКВУР" при а = 1, b = р, c = q. 
 Если р2 - 4q ≥ 0 (т. е. если квадратное уравнение t2 + pt + q = 0 имеет корни), то: 
 Решить уравнение dx = x1. 
 Сообщить x. 
 Решить уравнение dx = x2. 
 Сообщить х. 
 Конец ветвления.

Здесь необходимо упомянуть об одном очень важном обстоятельстве. Представьте себе, что вы подарили своему товарищу вспомогательный алгоритм "РЕКВУР" и объяснили, как им пользоваться. Разумеется, вашему товарищу нет никакого дела до того, какие обозначения вы использовали в вашем алгоритме. Поэтому может случиться, что в его основном алгоритме будут использоваться те же обозначения, что и в "РЕКВУРЕ", например d и р (именно это произошло в только что написанном алгоритме) .

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

Образно говоря, переменные, имеющие одно и то же название в основном и вспомогательном алгоритмах,- просто "однофамильцы". При вызове вспомогательного алгоритма значения переменных основного алгоритма как бы "замораживаются", а после окончания работы вспомогательного алгоритма они "размораживаются".

Без такого "замораживания" то и дело происходили бы пренеприятнейшие вещи. Какие? Сейчас увидите!

Попробуем решить уравнение

Посмотрим, как выполнился бы написанный выше алгоритм, если бы "замораживания" не происходило. Выполнив команду "Запросить d, p, q", мы присвоим переменной d значение 5, переменной р - значение - 8, переменной q - значение - 425.

Теперь выполним алгоритм "РЕКВУР", взяв в качестве а, b, с числа 1, -8, -425 соответственно. Получим x₁ = 25, x₂ = -17. Далее, для проверки условия надо подсчитать значение р² - 4q. Но что это? Значение р уже не равно - 8! При выполнении алгоритма "РЕКВУР" ему было присвоено значение 42. Да и d уже не то, что прежде. Теперь d = 1764. От такой "помощи" вспомогательного алгоритма становится не по себе. Это все равно, как если бы ваш магнитофон при воспроизведении записей одновременно заменял на кассете, скажем, "Танец с саблями" А. И. Хачатуряна на "Танец маленьких лебедей" П. И. Чайковского. В действительности же после выполнения вспомогательного алгоритма значения р и q "размораживаются", т. е. снова становятся равными -8 и -425, и алгоритм дает верный результат (какой?).

"Замораживание" переменных надежно предохраняет их от порчи вспомогательными алгоритмами

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

Результат верного алгоритма

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

Вопросы

1. Что такое вспомогательный алгоритм?

2. Как сделать алгоритм вспомогательным?

3. Как записывается команда вызова вспомогательного алгоритма?

4. В чем заключается "замораживание" и "размораживание" переменных при использовании вспомогательного алгоритма?

Задания для самостоятельного выполнения

1. Какие вспомогательные алгоритмы можно выделить в распорядке дня в школе?

2. Имеется следующий вспомогательный алгоритм:

 Алгоритм "Воздействие". 
 Аргументы: предметы х, у, z время t. 
 Результат: х. 
 Поместить у на х. 
 Подождать t минут. 
 Удалить у с помощью z.

Записать команды вызова этого вспомогательного алгоритма, выполнив которые исполнитель (человек):

а) выведет пятно с куска ткани;

б) вымоет окно;

в) съест ложку варенья;

г) почистит зубы.