Конспект урока по информатике на тему «Подпрограммы. Рекурсивные алгоритмы»

Конспект урока по информатике на тему «Подпрограммы. Рекурсивные алгоритмы»

Цель: познакомить учащихся с понятием «подпрограммы», «рекурсивные алгоритмы».

Задачи урока:

развивающие:

- способствовать развитию логического мышления учащихся, познавательного интереса, памяти, внимательности;

- содействовать развитию у учащихся алгоритмического мышления;

воспитательные:

- содействовать воспитанию информационной культуры учащихся, формированию самостоятельности при решении задач;

Ход урока.

1.      Организационный момент.

2.      Повторение ранее изученной темы.

3.      Изучение новой темы.

4.      Итог урока.

5.      Домашнее задание.

Подпрограммы. Во многих алгоритмах те или иные действия могут повторяться для различных исходных данных. Например, пусть нужно составить алгоритм для вычисления площади кру­говой пластины с круглыми отверстиями (рис. 4.5). Очевидно, для этого нужно вычислить площадь круга, соответствующего внешнему контуру пластины, и вычесть из нее сумму площадей круговых отверстий.

рис. 4.5

В алгоритме для вычисления площади пластины потребуется записать четыре одинаковых вычислительных блока, в которых рассчитывается площадь круга диаметром, соответственно, dO, dl, d2, dS

Существует возможность упростить такой алгоритм, вынеся из него однотипные действия в отдельный, подчинённый алгоритм и обращаясь к подчинённому алгоритму из основного (главного) алгоритма с требуемыми исходными данными (рис. 4.7). Такой подчинённый алгоритм реализуется в виде подпрограммы. Ко­гда подпрограмма завершает работу, происходит возврат из неё в основную программу, которой передаются результаты работы подпрограммы.

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

Функция — это подпрограмма, которая, принимая одно или несколько исходных данных, возвращает единственное значение, являющееся результатом работы этой функции. Такая подпро­грамма аналогична математическим функциям (например, триго­нометрическим, которые по заданному значению угла вычисляют его синус, косинус, тангенс и т. д.). Обращение к функции (вызов функции) обычно записывается так же, как это делается в мате­матике, например:

X = SIN (А) — вызов функции, вычисляющей значение сину­са угла, величина которого задана в переменной А; результат, возвращенный этой функцией, записывается в переменную X;

Y = SQRT (1 - COS(A)*COS(А))                             — реализация вычисления

значения синуса угла по формуле У1 - cos²(A): здесь резуль­таты, возвращаемые функциями вычисления косинуса угла А, сразу же используются в арифметическом выражении, значе­ние которого, в свою очередь, затем используется в качест­ве исходных данных для функции вычисления квадратного корня (SQRT).

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

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

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

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

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

• При написании подпрограммы в её заголовке записывается «шаблон» вызова этой подпрограммы. Он включает имя под­программы и записанный в скобках список локальных пере­менных, используемых внутри подпрограммы. Эти переменные представляют собой передаваемые в подпрограмму исходные {входные) данные, а для процедуры — также список локаль­ных переменных, в которые в процедуре записываются резуль­таты вычислений. Все эти переменные, записанные в заголовке подпрограммы, называют формальными параметрами.

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

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

Процедуры — обработчики событий. Современные программы для компьютеров обычно пишутся по объектному принципу. Рас­сматривается некий набор объектов — как отображаемых визу­ально (изображаемые на экране окна, кнопки и другие элементы интерфейса), так и не имеющих визуального представления (на­пример, аудиозапись). Каждый такой объект может иметь свой набор свойств, значения которых можно задать при создании объекта, а затем изменять при выполнении программы. Кроме того, рассматривается некоторый набор возможных событий — ситуаций, как возникающих при работе самого компьютера и его периферийных устройств (скажем, замятие бумаги в принте­ре), так и инициированных пользователем (например, в качестве события может выступать щелчок кнопкой мыши или нажатие определённой клавиши на клавиатуре).

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

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

Рекурсивные алгоритмы. Возможна ситуация, когда в ходе выполнения подпрограммы её алгоритмом предусматривается вы­зов самой этой же подпрограммы. Такой приём называют рекур­сией, а подобные алгоритмы с «самовызовом» называют рекур­сивными алгоритмами.

Пример использования рекурсии — вычисление факториала.

Факториалом натурального числа называют значение, равное произведению этого числа на все числа натурального ряда, мень­шие данного числа. Факториал обозначается восклицательным знаком, записанным после исходного числа. Например, факториал числа 4 вычисляется так: 4! = 4 • 3 • 2 • 1.

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

Предположим, что мы уже знаем, чему равен факториал пре­дыдущего натурального числа. Тогда для вычисления 4! достаточ­но умножить это уже известное значение 3! на число 4.

Однако мы пока не знаем, чему равен 3!. Вычислить его мы можем... вызвав эту же самую подпрограмму, которую мы пишем для вычисления факториала числа 4. Но теперь в эту подпро­грамму в качестве исходного данного передается число 3. И вы­числение значения 3! производится по тому же принципу: число 3 умножается на 21.

Поскольку величина 2! нам тоже пока неизвестна, её мы вычислим снова вызовом этой же подпрограммы, которой будет передано уже число 2. И здесь вычисление производится тоже умножением числа 2 на факториал предыдущего числа 1 (и тоже вызовом нашей же подпрограммы с передачей ей исходного дан­ного — числа 1).

Но вот чему равен факториал единицы, мы знаем точно: он равен единице. И этот факт можно отразить в нашей подпро­грамме при помощи оператора ветвления типа: «ЕСЛИ переданное число равно 1, то результат равен 1».

А теперь посмотрим, как работает этот алгоритм, например, для числа 4 (из основного алгоритма производится вызов под­программы в виде F = FAKTOR (4)). Для этого будем отслеживать изменение значения переменной N (рис. 4.8).

Как видим, в процессе работы подпрограммы сначала фор­мируется цепочка её вложенных вызовов — до тех пор, пока не сработает условие завершения рекурсии (в данном случае N = 1). После этого в каждом из выполненных вложенных вызовов — на­чиная с самого последнего и в обратном порядке — производится вычисление результата и возврат в предыдущий вложенный вызов подпрограммы. Такая обратная цепочка рекурсивных возвратов выполняется, пока не произойдёт возврат в самый первый вызов подпрограммы. А когда в ней будет вычислен окончательный ре­зультат, происходит возврат в основной алгоритм.

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

F = 1

ПОКА N > 1 выполнять:

F = F * N N = N - 1

КОНЕЦ ПОКА

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

1.      Что такое подпрограмма? Для чего используются подпрограммы?

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

3.      Что понимается под стандартными функциями? Как вы считаете, почему их называют стандартными? Найдите в Интернете информа­цию о том, почему такие функции называют библиотечными.

4.      Как работает механизм передачи данных между основным алгорит­мом и подпрограммой при помощи формальных и фактических па­раметров? Какое основное правило при этом должно соблюдаться?

5.      Что такое обработчики событий? Чем работа таких процедур отли­чается от работы обычных подпрограмм-процедур?

6.      Что такое рекурсия? Как работают рекурсивные алгоритмы?

7.      Приведите свой пример построения рекурсивного алгоритма. Опи­шите последовательность вложенных вызовов и рекурсивных воз­вратов при работе вашего рекурсивного алгоритма.