Урок 28

 

---

                                                          Конструирование алгоритмов

Ключевые слова:

• последовательное построение алгоритма
• вспомогательный алгоритм
• формальные параметры
• фактические параметры
• рекурсивный алгоритм

2.3.3. Вспомогательные алгоритмы

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

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

Пример 1. В среде КуМир составим алгоритм для исполнителя Робот, под управлением которого он нарисует узор:

* т

Глава 2. Алгоритмизация и программирование

Начальное положение Робота отмечено звёздочкой. В алгоритме использован вспомогательный алгоритм фигура.

использовать  Робот

алгоритм узор

начало

фигура

вправо; вниз

фигура

вправо; вниз
фигура конец

алгоритм фигура начало

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

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

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

При представлении алгоритмов с помощью блок-схем для обозначения команды вызова вспомогательного алгоритма используется блок «предопределённый процесс» (рис. 2.3), внутри которого записывается название (имя) вспомогательного алгоритма, после которого в скобках перечисляются параметры — входные данные и результаты.

Вспомогательный алгоритм делает структуру алгоритма более понятной.

Пример 2.

Вспомним алгоритм вычисления степени с натуральным показателем у = а^п. Соответствующая блок-схема:

Конструирование алгоритмов

С  Начало   J I

Список данных

п,1- цел а, у-вещ

у:=1

 

у:=у*а

I

Конец

Степень с целым показателем у = а^х, где х — целое число, а * О вычисляется так:

X при л:=О, а^х,    при до О,

if,

а)

прил:<(Х

В приведённой записи дважды фигурирует вычисление степени с натуральным показателем. Поэтому в алгоритм вычисления степени с целым показателем можно включить вызов вспомогательного алгоритма вычисления степени с натуральным показателем. Соответствующая блок-схема:

Глава 2. Алгоритмизация и программирование

С    Конец

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

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

Команда вызова вспомогательного алгоритма исполняется следующим образом (рис. 2.4):

1. формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
2. для заданных входных данных исполняются команды вспомогательного алгоритма;
3. полученные результаты присваиваются переменным с именами
   фактических результатов;
4. осуществляется переход к следующей команде основного алгоритма.

i >,

 

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

Рассмотрим несколько примеров рекурсивных алгоритмов.

Пример 3. Алгоритм вычисления степени с натуральным показателем л для любого вещественного числа а можно представить в виде рекурсивного:

Глава 2. Алгоритмизация и программирование

п-я степень числа а есть не что иное, как произведение а" ¹ ■ а;

в свою очередь, а. Интерактивная игра «Ханойские башки» (195747) поможет вам вспомнить условие и алгоритм решения головоломки (http://sc.edu.ru/).

Пример 4. Рассмотрим алгоритм построения геометрической фи­гуры, которая называется снежинкой Коха. Шаг процедуры построе­ния состоит в замене средней трети каждого из имеющихся отрезков двумя новыми такой же длины, как показано на рисунке:

Начальное состояние Первый шаг Второй шаг Третий шаг

С каждым шагом фигура становится всё причудливее. Граница снежинки Коха — положение кривой после выполнения бесконечно­го числа шагов.

Попробуйте подсчитать, сколько рёбер в границе снежинки Коха после четвёртого шага; после пятого шага.

---

Вопросы и задания

1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Дополняет ли презентация информацию, содержащуюся в тексте параграфа?
2. Почему при решении сложной задачи затруднительно сразу конкретизировать все необходимые действия?
3. В чём заключается метод последовательного уточнения при построении алгоритма?
4. Какая связь между методом последовательного построения алгоритма и такими процессами, как написание сочинения или подготовка к многодневному туристическому походу?

   ---

Самое главное

Один из основных методов конструирования алгоритмов — метод последовательного построения алгоритма. Его суть состоит в том, что: исходная задача разбивается на несколько частей, каждая из ко­торых проще всей задачи, и решение каждой части формулируется в отдельной команде; если получаются команды, выходящие за преде­лы возможностей исполнителя, то они представляются в виде сово­купности ещё более простых предписаний. Процесс продолжается до тех пор, пока все предписания не будут понятны исполнителю.
Вспомогательный алгоритм — алгоритм, целиком используемый в составе другого алгоритма.

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

---