Конструирование алгоритмов
Ключевые слова:
- последовательное построение алгоритма
- вспомогательный алгоритм
- формальные параметры
- фактические параметры
- рекурсивный алгоритм
2.3.3. Вспомогательные алгоритмы
При построении новых алгоритмов нередко возникают ситуации, когда в разных местах алгоритма необходимо выполнение одной и той же последовательности шагов обработки данных. Для такой последовательности шагов создают отдельный алгоритм, называемый вспомогательным. В качестве вспомогательных могут использоваться алгоритмы, ранее разработанные для решения других задач.
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.
Пример 1. В среде КуМир составим алгоритм для исполнителя Робот, под управлением которого он нарисует узор:
* т
Глава 2. Алгоритмизация и программирование
Начальное положение Робота отмечено звёздочкой. В алгоритме использован вспомогательный алгоритм фигура.
использовать Робот
алгоритм узор
начало
фигура
вправо; вниз
фигура
вправо; вниз
фигура конец
алгоритм фигура начало
закрасить; вниз
закрасить; вправо; закрасить; вправо; закрасить
вверх; закрасить ков
При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 2.3), внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры — входные данные и результаты.
Вспомогательный алгоритм делает структуру алгоритма более понятной.
Пример 2.
Вспомним алгоритм вычисления степени с натуральным показателем у = ап. Соответствующая блок-схема:
Конструирование алгоритмов
С Начало J I
Список данных
п,1- цел а, у-вещ
у:=1
у:=у*а
I
Конец
Степень с целым показателем у = ах, где х — целое число, а * О вычисляется так:
X при л:=О, ах, при до О,
if,
а)
прил:<(Х
В приведённой записи дважды фигурирует вычисление степени с натуральным показателем. Поэтому в алгоритм вычисления степени с целым показателем можно включить вызов вспомогательного алгоритма вычисления степени с натуральным показателем. Соответствующая блок-схема:
Глава 2. Алгоритмизация и программирование
С Конец
Алгоритм, представленный на блок-схеме, является основным по отношению к вызываемому в нём вспомогательному алгоритму.
Параметрами используемого вспомогательного алгоритма являются величины а, п, у. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.
Команда вызова вспомогательного алгоритма исполняется следующим образом (рис. 2.4):
- формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
- для заданных входных данных исполняются команды вспомогательного алгоритма;
- полученные результаты присваиваются переменным с именами
фактических результатов; - осуществляется переход к следующей команде основного алгоритма.
i >,
Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.
Рассмотрим несколько примеров рекурсивных алгоритмов.
Пример 3. Алгоритм вычисления степени с натуральным показателем л для любого вещественного числа а можно представить в виде рекурсивного:
Глава 2. Алгоритмизация и программирование
п-я степень числа а есть не что иное, как произведение а" 1 ■ а;
в свою очередь, а. Интерактивная игра «Ханойские башки» (195747) поможет вам вспомнить условие и алгоритм решения головоломки (http://sc.edu.ru/).
Пример 4. Рассмотрим алгоритм построения геометрической фигуры, которая называется снежинкой Коха. Шаг процедуры построения состоит в замене средней трети каждого из имеющихся отрезков двумя новыми такой же длины, как показано на рисунке:
Начальное состояние Первый шаг Второй шаг Третий шаг
С каждым шагом фигура становится всё причудливее. Граница снежинки Коха — положение кривой после выполнения бесконечного числа шагов.
Попробуйте подсчитать, сколько рёбер в границе снежинки Коха после четвёртого шага; после пятого шага.
Вопросы и задания
- Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Дополняет ли презентация информацию, содержащуюся в тексте параграфа?
- Почему при решении сложной задачи затруднительно сразу конкретизировать все необходимые действия?
- В чём заключается метод последовательного уточнения при построении алгоритма?
- Какая связь между методом последовательного построения алгоритма и такими процессами, как написание сочинения или подготовка к многодневному туристическому походу?
Самое главное
Один из основных методов конструирования алгоритмов — метод последовательного построения алгоритма. Его суть состоит в том, что: исходная задача разбивается на несколько частей, каждая из которых проще всей задачи, и решение каждой части формулируется в отдельной команде; если получаются команды, выходящие за пределы возможностей исполнителя, то они представляются в виде совокупности ещё более простых предписаний. Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.
Алгоритм, в котором прямо или косвенно содержится ссылка на него же как на вспомогательный алгоритм, называют рекурсивным.