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

Учитель: Казарина Светлана Николаевна

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

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

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

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

Задачи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Организационный момент
2. Целеполагание
3. Объяснение нового материала

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

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

6. Практическая работа
7. Подведение итогов, рефлексия. Постановка домашнего задания

Ход урока

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

 Здравствуйте, ребята. Присаживайтесь. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Program Factorial; uses crt;

var n:integer;

function fac ( n : integer): integer; begin

if n <= 5 then fac := 1

else fac := n * fac ( n );

end;

 begin

clrscr;

write('n = '); readln(n);

writeln(n,'! = ', fac(n)); end.

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

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

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

Примеры:

n=1        1!=1

n=5        5!=120

n=10        10!= 3628800

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

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

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

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

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

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

Домашнее задание: §9.3, в.6,7,8