(курс 68 ч.) §24. Процедуры | Процедуры в других языках программирования. Рекурсия (informatika_09_68_pol) (68 часов в уч. год)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, углубленный уровень)


Уроки 41 - 42
§24. Процедуры



Содержание урока

Что такое подпрограмма?

Простая процедура

Процедура с параметром

Несколько параметров

Процедуры в других языках программирования. Рекурсия

Выводы

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

Практическая работа № 20 «Процедуры»

Практическая работа № 21 «Рекурсивные процедуры»


Процедуры в других языках программирования
Рекурсия


Процедура printLine с одним параметром на языках Python и С может быть записана так:

В языке Python объявление процедуры начинается ключевым словом def. Тип параметра указывать не нужно, он определяется автоматически. Тело процедуры записывается с отступом вправо, так же, как тело цикла и условного оператора. Вывести п одинаковых символов можно без цикла, построив сразу нужную строку с помощью «умножения» символа '-' на n.

Программа на языке С очень похожа на программу на Паскале. Признак процедуры — слово void в заголовке (вместо procedure на Паскале). Тело процедуры заключено в фигурные скобки. Стандартная функция putchar выводит на экран один символ.

Рекурсия


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

Вспомним алгоритм перевода числа в двоичную систему: нужно делить число на 2, каждый раз выписывая остаток от деления, пока не получится 0. На алгоритмическом языке алгоритм можно записать так:

нц пока <> 0

вывод mod(n,2)

n:= div(n,2)

кц


Проверьте вручную работу этого алгоритма для числа 6. Удалось ли вам получить правильный ответ? Почему?

Проблема только в том, что первой мы получаем последнюю цифру двоичной записи, поэтому остатки выводятся в обратном порядке (не так, как нужно).

Есть разные способы решения этой задачи, которые сводятся к тому, чтобы запоминать остатки от деления (например, в символьной строке) и затем, когда результат будет полностью получен, вывести его на экран. Однако можно применить ещё один красивый подход. Идея такова: чтобы вывести двоичную запись числа п, нужно сначала вывести двоичную запись числа div(n,2), а затем — его последнюю двоичную цифру, которая вычисляется как mod(n,2).

Что же получилось? Прочитайте ещё раз фразу, выделенную курсивом в предыдущем абзаце. Выходит, что для того, чтобы решить задачу для исходного числа, нужно предварительно решить ту же самую задачу для меньшего числа div(n,2).

Такой алгоритм очень просто программируется:

У нас получилось, что процедура printBin вызывает сама себя! Такой приём в программировании называется рекурсией, а процедура — рекурсивной.

Рекурсивная процедура — это процедура, которая вызывает сама себя.

Проверьте с помощью отладчика 1) в пошаговом режиме, что произойдёт при вызове этой процедуры.


1) Для входа в процедуру в пошаговом режиме отладчика используйте клавишу F7.



Приведённая процедура printBin ошибочна, вернее, она не доделана. Представим себе, что мы передали процедуре число 2. Сначала она вызывает сама себя для значения div(2,2) = 1, затем — для значения div(l,2) = 0, и потом ещё бесконечно много раз для нуля. Такие вызовы никогда не закончатся, и программа зациклится. Чтобы этого не произошло, нужно выйти из процедуры (и закончить эти вложенные вызовы), когда значение параметра станет равно нулю:

В алгоритмическом языке для выхода из процедуры используется оператор выход, а в языке Паскаль — оператор exit.

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

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



Следующая страница Выводы



Cкачать материалы урока







Наверх