Методическая разработка урока Информатики и ИКТ по теме «Рекурсивные алгоритмы»

Муниципальное общеобразовательное бюджетное учреждение

средняя общеобразовательная школа №12

муниципального образования городского округа город Якутск

 

 

 

 

 

 

 

 

Методическая разработка урока Информатики и ИКТ в

соответствии с требованиями ФГОС по теме

«Рекурсия. Рекурсивные алгоритмы»

 

 

 

 

 

 

 

 

 

 

 

 

Автор разработки:

учитель информатики и ИКТ

Кононов Д.И.

 

 

 

 

 

 

 

 

 

 

Якутск

2023 год

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

Класс: 11

Тема урока: Рекурсивные алгоритмы

Количество часов: 1

Тип урока: комбинированный

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

Задачи:

Обучающая: знакомство учащихся с понятием рекурсия, с видами рекурсии; формирование первичных умений и навыков использования рекурсивных процедур в среде программирования «Python».

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

Воспитывающая: воспитание самостоятельности, аккуратности, внимательности

Планируемые образовательные результаты

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

метапредметные – умение самостоятельно планировать пути достижения целей; умение оценивать правильность выполнения учебной задачи;

личностные – алгоритмическое мышление, необходимое для профессиональной деятельности в современном обществе; представление о программировании как сфере возможной профессиональной деятельности.

коммуникативные-развитие учебного сотрудничества с учителем и сверстниками.

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

Оборудование: интерактивный панель, презентация Microsoft Office Power Point, раздаточный материал, приложение Python.

Используемая технология: программируемое обучение.

Структура урока

Тип урока: урок изучения и первичного закрепления новых знаний.

Структура урока:

Организационный момент (2 мин)

Целеполагание (2 мин)

Объяснение нового материала (15 мин)

Первичное закрепление (10 мин)

Физкультминутка (1 мин)

Практическая работа (10)

Постановка домашнего задания. Подведение итогов, рефлексия. (5 мин)

Ход урока

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

Здравствуйте, ребята. Присаживайтесь. Организационный момент – Приветствие. Учитель отмечает отсутствующих.

Целеполагание

Прочитайте высказывания на слайде. Какую особенность вы можете выделить в этом высказывании?

Правильно, в данном высказывании мы как бы возвращаемся в начало высказывания.

Отметьте, особенности изображения на втором слайде.

Объяснение нового материала

Как вы думаете, может ли программа вызывать саму себя? 

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

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

Рекурсивные задачи – это задачи имитации человеческого интеллекта на основе перебора вариантов. Без рекурсии есть возможность решить подобные задачи только для частных случаев.

Рекурсия в программировании

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

В языке программирования Pascal рекурсивностью могут обладать как функции, так и процедуры. Но чаще всего используют рекурсивные функции.

Виды рекурсий

Прямая рекурсия - вызов одной подпрограммы  с изменяющимся набором параметров.

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

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

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

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

IV. Первичное закрепление

Рекурсивные алгоритмы на ЕГЭ

Способ решения: последовательное выполнение операций от начального определения до определения с введенным в алгоритм значением

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

F(1) = 1

F(n) = F(n–1) + n, при n >1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

Решение: последовательно находим:

F(2) = F(1) + 2 = 3,

F(3) = F(2) + 3 = 6,

F(4) = F(3) + 4 = 10,

F(5) = F(4) +5 = 15.

Ответ: 15

Работа в приложении Python.

Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, — определение факториала. С одной стороны, факториал определяется так: n!=1*2*3*...*n, где n∈ Ν. Факториа́л числа n это— произведение всех натуральных чисел до n включительно.

Реализуем приведённые выше рекурсивное определение факториала в виде функции на языке Python.

Работа в группах.

Дифференцированные задания:

На карточках предложены программы.

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

F(0)  =  0;

F(n)  =  F(n / 2), если n > 0 и при этом чётно;

F(n)  =  1 + F(n − 1), если n нечётно.

 Сколько существует таких чисел n, что 1 ≤ n ≤ 1000 и F(n)  =  3?

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

Карточка 1 (уровень сложности 1)

f(n):

if n == :

return 0

if n > 0 and n % 2 == 0:

return f(n / 2)

if n % 2!= 0:

return 1 + f(n - 1)

k = 0

for in (1, 1001):

if f(n) == 3:

k += 1

print(k)

II группа: в программе допущены ошибки и имеются пропуски. Вам необходимо найти ошибки и исправить.

Карточка 2 (уровень сложности 2)

def f(n):

if n == :

return 0

if n > 0 and n % 2 == 0:

return f(n / 2)

if n % 2 != 0:

return 1 + f(n - 1)

k = 0

for n in range(1, 1001):

if f(n) == 3:

k += 1

print(k)

Программа без ошибок:

def f(n):

if n = :

return 0

if n > 0 and n % 2 = 0:

return f(n / 2)

if n % 2 = !0:

return 1 + f(n - 1)

k = 0

for n (1, 1001):

if f(n) = 3:

k += 1

print(k)

Физкультминутка:

Практическая работа. Откройте приложение Python. Откройте программу Factorial, в соответствии с номером карточки, отредактируйте программу и исполните для n=1, 5, 10.

Примеры:

n=1 1!=1

n=5 5!=120

n=10 10!= 3628800

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

Пояснение: НОД - Наибольший Общий Делитель нескольких чисел. При этом деление рассматривается, как целое, само, собою. Например, у двух чисел 12 и 9 НОД будет равен 3. То есть, число 3 это самое большое целое число на которое числа 12 и 9 делятся нацело.

Подведение итогов, запись домашнего задания, рефлексия

Что такое рекурсия?

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

Как выполняется рекурсивный алгоритм?

Что такое зацикливание и как его избежать? (условие окончания рекурсивности)

Объявление оценок  за урок и рефлексия (3 мин)

Объявление и выставление в журнал оценок.

Итак, сегодня мы прошли с вами новую тему. Что вам было сложнее всего выполнить на уроке? Согласны ли вы со своими оценками? А теперь, в конце урока хочется, чтобы вы выразили свое отношение к нашей сегодняшней работе и всему уроку в целом. Ответьте на вопросы в листах рефлексии и сдайте их мне.

+    все понятно                 ±   понятно частично                -     ничего не понятно        

О пишите общее впечатление от урока, выбрав соответствующий смайл:

Литература:

1. Python для студентов и школьников. Санкт-Петербург «БХВ-Петербург», 2005

2. Информатика Справочник для подготовки к ЕГЭ. О. Б. Боголюбова, АСТ Москва, 2015

3. ЕГЭ Информатика и ИКТ. Типовые экзаменационные варианты. С.С. Крылов, Т.Е. Чуркина, 2018.

4. Материалы сайта К.Ю. Полякова kpolyakov.spb.ru.