Закрепление нового материала при решении задач

1 2

КАРТА УРОКА

для организации занятий с использованием

Дистанционных технологий обучения

Учитель: Лавриненко А.П.

Предмет: Информатика и ИКТ

Класс: 10А

Дата проведения урока: 15.05.2020 Пт

Выполненное практическое задание необходимо предоставить в любом доступном формате (скан, фотография, документ MS Word):

- обязательно присоединено файлом выполненного домашнего задания в Виртуальной школе в своем дневнике;

- можно электронным письмом на адрес a-lvr@yandex.ru;

- можно сообщением на странице в социальной сети https://vk.com/club193796786 (в контакте).

Название файла (сообщение) должно содержать название предмета, фамилию ученика, дата и класс. Например: Информатика Иванов 15052020 10А.doc

Тема урока: Стек и очередь. Рекурсия. Практическая работа 34 «Рекурсия».

Цель урока:

- познакомиться с рекурсивными алгоритмами, проанализировать их работу, рассмотреть типичные задачи ЕГЭ по этой теме.

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

Задание на урок:

ТЕОРЕТИЧЕСКИЙ НОВЫЙ МАТЕРИАЛ.

1. Ознакомиться с презентацией по теме урока, которая называется «ИНФ 10 кл Рекурсия 15 05 2020» и расположена на Яндекс диске по ссылке https://yadi.sk/i/v5vpZmAgBE9q4A

Ознакомьтесь с теоретическим материалом, представленным ниже.

Рекурсия

Слово рекурсия от лат. recursio означает круговорот. Синонимами этого слова являются возвращение, повторение. Классическим примером рекурсивного алгоритма является алгоритм решения задачи "Ханойские башни". Есть три стержня, на одном из которых находятся кольца разного диаметра. Необходимо переложить их с первого стержня на свободный, используя еще один.

Рассмотрим случай с пятью кольцами.

Учащимся предлагается самостоятельно составить алгоритм к этой задаче и устно описать его.

Далее учитель загружает файл Hanoy.exe и демонстрирует учащимся работу алгоритма.

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

Рекурсия это способ определения объекта, который опирается на само понятие объекта на основе заданных простых базовых случаев. Преимущество такого определения заключается в том, что оно способно описывать бесконечно большое число объектов. Мы разрабатываем алгоритм, сводя исходную задачу к более простым. Рекурсия позволяет сделать решение более понятным, сократить текст программы, упростить ее.

Рекурсивная (процедура) функция вызывает сама себя напрямую или через другие процедуры и функции. Количество таких вызовов называется глубиной рекурсии.

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

базовые случаи здесь: 0!=1, 1!=1

рекурентная формула: N!=N*(N-1)! при N>=2

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

function factorial(N: integer): longint;
begin
if N = 0 then factorial:= 1
else
factorial:= factorial(N-1) * N
end;

Что же происходит, если одна функция вызывает другую?

· в памяти размещаются параметры, передаваемые функции

· для внутренних переменных вызываемой функции также отводится новая область памяти (несмотря на совпадение их имен и типов с переменными вызывающей функции);

· запоминается адрес возврата в вызывающую функцию;

· управление передается вызванной функции.

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

Действия, выполняемые функцией до входа на следующий уровень рекурсии, выполняются на прямом ходу рекурсии, а действия, выполняемые по возврату с более глубокого уровня к текущему, – выполняются на обратном ходу рекурсии.

Практическая работа за компьютером

Продемонстрируем ход рекурсии. Предлагается ввести программу в компьютер и пошагово проследить как она работает.

var glubina: integer:= 0;
function factorial(N: integer): longint;
begin
{при входе в функцию увеличиваем переменную, которая считает глубину рекурсии}
glubina:= glubina + 1;
writeln('Прямой ход рекурсии. Глубина = ', glubina);
result:= 1;
if N > 0 then result:= factorial(N-1) * N;
Writeln('Обратный ход рекурсии. Глубина = ', glubina);
{при выходе из функции - уменьшаем эту переменную}
glubina:= glubina - 1;
end;
begin
factorial(3);
end.

При запуске этой программы, будет выведено:

Прямой ход рекурсии. Глубина = 1
Прямой ход рекурсии. Глубина = 2
Прямой ход рекурсии. Глубина = 3
Прямой ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 4
Обратный ход рекурсии. Глубина = 3
Обратный ход рекурсии. Глубина = 2
Обратный ход рекурсии. Глубина = 1

Закрепление нового материала при решении задач.

Рассмотрим задачи ЕГЭ, в которых присутствуют рекурсивные алгоритмы выполнения процедур. В процессе выполнения таких задач будут осуществляться рекурсивные вызовы процедуры. Необходимо правильно проследить порядок вызовов. Это возможно сделать разными способами, один из которых нарисовать дерево вызовов. Дерево может получится достаточно громоздким, поэтому более простым способом решения является анализ алгоритма, его связи с вопросом задачи. Внутри алгоритма могут находится следующие операторы:

Writeln(*); в этом случае возможен вопрос: сколько * выведется на экран после выполнения алгоритма.

Writeln(n); в этом случае может быть задан вопрос:какова сумма всех n, выводимых на экран или потребуется записать последовательность из выводимых n.

Рассмотрим следующую задачу:

procedure F(n: integer);

Begin

writeln(n);

if n < 6 then begin

F(n+2);

F(n*3)

end

end;

Найдите сумму чисел, которые будут выведены при вызове F(2).