Урок 4. Вспомогательные алгоритмы
Предмет: Информатика, 11 класс

Конспект урока

Информатика, 11 класс. Урок № 4.

Тема — Вспомогательные алгоритмы и подпрограммы: правила описания и использования подпрограмм

Перечень вопросов, рассматриваемых в теме: структурное программирование, подпрограммы, формальные параметры, фактические параметры, параметры-значения, параметры-переменные, процедуры, функции, рекурсия.

Глоссарий по теме: структурное программирование, подпрограммы, процедуры, функции, рекурсия.

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2017

Дополнительная литература по теме урока:

- И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова Информатика и ИКТ. Профильный уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2012

- Андреева Е. В. Программирование — это так просто, программирование — это так сложно. Современный учебник программирования. — М.: МЦНМО, 2015

- Молчанова С. И. Основы программирования. Турбо-Паскаль 7.0 для школьников и абитуриентов. — М.: «Аквариум»; ООО «Фирма «Издательство АСТ», 1999

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

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

Основные принципы структурного программирования заключаются в том, что:

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

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

На прошлом уроке мы рассмотрели один из базовых алгоритмов обработки числовых данных — алгоритм нахождения НОД натуральных чисел.

Вернемся к нему для решения задачи нахождения НОД трех натуральных чисел a, b, c. Для решения воспользуемся следующим математическим фактом: если a, b, c — три натуральных числа, то НОД (a, b, c) = НОД (НОД (a, b), c). Иначе говоря, нужно найти НОД двух величин, а затем НОД полученного значения и третьего числа.

Получаем:

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

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

Подпрограммы подразделяются на процедуры (procedure) и функции (function).

Процедуры

Описание процедуры в Паскале имеет следующий формат:

Оформим в нашем примере в качестве процедуры подпрограмму нахождения НОД двух натуральных чисел.

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

Подпрограмма реализует некоторый частный алгоритм, который вызывается в основной программе. Для реализации алгоритма подпрограмме могут понадобиться некоторые данные из основной программы. Обработав эти данные, подпрограмма возвращает результат основной программе, если в этом есть необходимость. Передавать информацию из основной программы в подпрограмму и наоборот мы можем только через переменные, которые носят специальное название — параметры. Именно они и указываются в круглых скобках рядом с именем процедуры.

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

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

Параметры-значения указываются так:

Чаще всего параметры-значения служат для работы с входной в процедуру информацией, а параметры-переменные — для работы с выходной информацией.

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

Здесь мы замечаем, что наша процедура evklid дважды вызывается одинаковым образом. Но это нарушает саму идею решения и может привести к неверному ответу. Чтобы исправить эту ошибку, введем формальные параметры, имена которых отличны от фактических:

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

Чтобы разобраться в этом примере, введем одно важное понятие — область действия описания.

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

В программе nod2 переменные x, y, nod1 являются локальными внутри процедуры; переменные a, b, c — глобальные. Однако внутри процедуры переменные a, b, c не используются. Связь между внешним блоком и процедурой осуществляется через параметры.

В программе nod2 все переменные являются глобальными. В процедуре evklid нет ни одной локальной переменной. Здесь обмен значениями между основной программой и процедурой осуществляется через глобальные переменные.

Функции

Теперь выясним, что такое подпрограмма-функция. Обычно функция используется в том случае, когда результатом работы подпрограммы должна быть скалярная (простая) величина. Тип результата называется типом функции.

Формат описания функции следующий:

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

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

Сравнивая приведенные выше программы, можно сделать вывод, что программа nod4 имеет определенные преимущества перед другими. Функция позволяет получить результат путем выполнения одного оператора присваивания. Здесь также демонстрируется возможность того, что фактическим параметром при обращении к функции может быть эта же функция.

Рекурсия

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

Рекурсивная подпрограмма (функция, процедура) — подпрограмма, содержащая в своем описании вызов самой себя.

Пример 1. Как известно, факториал натурального числа определяется следующим образом:

n! = 1·2·3·…·n.

0! = 1.

Иначе это можно записать так:

F(n)=1 при n ≤ 1;

F(n)=F(n–1) · n при n > 1.

В определении факториала через рекурсию имеется условие n ≤ 1, при достижении которого вызов рекурсии прекращается. Такое условие (оно называется граничным) в рекурсивном определении должно присутствовать обязательно!

Пример 2. Алгоритм вычисления функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n)=1 при n ≤ 2;

F(n)=F(n–1) +3· F(n–2) при n > 2.

Требуется выяснить, чему равно значение функции F(7).

По условию, F(1) = F(2) = 1.

F(3) = F(2) + 3 · F(1) = 1 + 3 · 1 = 4.

F(4) = F(3) + 3 · F(2) = 4 + 3 · 1 = 7.

F(5) = F(4) + 3 · F(3) = 7 + 3 · 4 = 19.

F(6) = F(5) + 3 · F(4) = 19 + 3 · 7 = 40.

F(7) = F(6) + 3 · F(5) = 40 + 3 · 19 = 97.

Подобные вычисления можно проводить в уме, а их результаты фиксировать в таблице:

И в завершение вспомним задачу вычисления НОД и модифицируем с использованием рекурсивной функции.

Применение рекурсивных методов для решения вычислительных задач не всегда эффективно. В большинстве случаев для решения той же задачи можно построить оптимальный не рекурсивный алгоритм. В то же время существуют задачи не вычислительного содержания, решить которые без использования рекурсии оказывается крайне проблематичным. К числу таких задач относится, например, известная головоломка под названием «Ханойские башни», с которой вы можете познакомиться в дополнительном материале.