Конспект урока по теме "Рекурсия. Решение задач на рекурсию". (9 класс)

ФИО

группа

Конспект урока по информатике в 9 классе.

Предмет: Информатика,9-й класс

Тема урока: Рекурсия. Решение задач на рекурсию.

Цель урока: познакомить учащихся с понятием рекурсия; научить решать задачи на рекурсию без использования компьютера.

Урок направлен на формирование следующих результатов:

1.Предметных:

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

2.Метапредметных УУД:

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

2.2) Регулятивные: умение самостоятельно определять цели своего обучения; ставить и формулировать для себя новые задачи в учёбе и познавательной деятельности; развивать мотивы и интересы своей познавательной деятельности; умение соотносить свои действия с планируемыми результатами; осуществлять контроль своей деятельности в процессе достижения результата; определять способы действий в рамках предложенных условий и требований; корректировать свои действия в соответствии с изменяющейся ситуацией;

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

3.Личностных УУД:

Формировать мотивацию и самомотивацию изучения темы, экологического сознания, реализации творческого потенциала, развитие трудолюбия и ответственности за качество

своей деятельности.

К концу урока учащиеся должны:

1)    знать где применяются базы данных, как создаются базы данных.

2)    уметь сравнивать, обобщать, анализировать, выделять главное.

3)    уметь вести коллективный учебный диалог.

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

 Методы обучения (по характеру познавательной деятельности):

1.      Объяснительно-иллюстративный.

2.      Репродуктивный.

3.      Исследовательский.

Форма организации деятельности учащихся: фронтальная, групповая, индивидуальная

Оборудование:

• компьютеры с ОС MS Windows;

·         персональные компьютеры;

·         программное обеспечение: СУБД Microsoft Access;

• проектор;
• интерактивная доска;

·         презентация на тему «Реляционная модель базы данных»;

• учебник – Информатика. Учебник для 10 класса. Босова Л.Л.;
• Карточки с заданиями для практической работы.

Термины:

·         Вспомогательный алгоритм

·         формальные параметры

·         фактические параметры

·         подпрограмма

·         процедура

·         функция

·         рекурсивная функция

Временная структура урока:

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

2.      Актуализация знаний. (4 мин)

3.      Постановка цели урока (1 мин)

4.      Работа над темой урока. (9 мин)

5.      Физкультминутка. (2 мин)

6.      Закрепление изученного материала. (20 мин)

7.      Итог урока. Рефлексия (2 мин)

8.      Домашнее задание. (1 мин)

Ход урока.

Технология проведения (этапы, цель)	Деятельность учителя	Деятельность обучающихся
1.Оргнизационный	Приветствие, наличие обучающихся	Подготовка к уроку
2.Актуализация знаний	На прошлых уроках мы с вами изучили разрабатывать программы на языке программирования Паскаль, изучили основные алгоритмические конструкции. Прежде чем приступить к изучению нового материала, давайте с вами закрепим наши знания. 1. Какова структура программы? 2.     Обязателен ли заголовок программы? 3.     Перечислите разделы описаний 4.     Какие служебные слова служат для описания переменных? 5.     Какое служебное слово является началом основной части   программы? 6.     Как заканчивается программа?	Заголовок программы, раздел описаний, тело программы Да Var - раздел описания переменных, Type - раздел описания типов Const - раздел определения констант Label - раздел описания меток Function, Procedure - раздел описаний процедур и функций Begin End
3. Постановка цели урока	Приступим к изучению нового материала. Тему урока запишите в тетрадь.  Запись вспомогательных алгоритмов на языках программирования осуществляется с помощью подпрограмм. Сегодня на уроке мы с вами рассмотрим организацию подпрограмм в Паскале.	Записывают в тетрадь тему урока и определения основных понятий данной темы.
4. Работа по теме урока	При создании программы для решения сложной задачи про­граммисты выполняют разделение этой задачи на подзадачи, подзадачи - на еще меньшие подзадачи и так далее, до легко программируемых элементарных задач. Язык программирования Pascal позволяет разделять программу на отдельные части, которые называются подпрограммами. Сам термин подпрограмма говорит о том, что она подобна и подчинена основной программе. Подпрограммы решают три важные задачи, значительно облегчающие программирование: -     избавляют от необходимости многократно повторять в тексте программы аналогичные фрагменты, т. е. сократить объем про­граммы; -     улучшают структуру программы, облегчая понимание при разборе; -     уменьшают вероятность появления ошибок, повышают устойчивость к ошибкам программирования и непредвиденным по­следствиям при модификации. План  работы: 1.Изучить новые понятия (презентация) 2.Записать ключевые понятия в тетрадь 3.Рассмотреть решения основных типов задач на рекурсию. (приложение 1)	-Слушают объяснения и записывают новые понятия в тетрадь. -Для закрепления полученных знаний выполняют лабораторно-практическую работу. -Выявляют непонятные вопросы при выполнении работы
5.Физкультминутка	Эффект: расслабление тела, снятие нервного напряжения, восстановление     нормального ритма дыхания. •          Моргать в течении 10сек. с напряжением закрывать на 3-5 с попеременно один и другой глаз. •          В течении 10 с несколько раз сильно зажмуриться. •          В течении 10 с менять направление взгляда. •          Медленно опустить подбородок на грудь и оставаться в таком   положении 5 с. Выполнить упражнение 3 раза. Эффект: избавление от усталости. •          Помассировать лицо, чтобы снять напряжение лицевых мышц. •          Надавливая пальцами на затылок в течении 10 с делать вращательные движения вправо, затем влево. •          В положении сидя или стоя опустить руки вдоль тела. Расслабить их. Сделать глубокий вдох и на медленном выдохе в течение 10-15 с слегка потрясти руками. Повторить несколько раз.	Учащиеся выполняют упражнения
6.Закрепление изученного материала	Решение основных типов задач на рекурсию. (приложение 1)
7.Подведение итогов урока	1.Что нового узнали о программировании? Был ли полезным новый материал урока? 2.Достигли ли цели урока?	Отвечают на вопросы на основе записей в тетради и выполнения лабораторно-практической работы.
8. Домашнее задание	Домашнее задание: §4.8. Вопросы 1, 2 Упражнение7. По желанию упр. 9 (дополнительно).	Найти ответы на поставленные вопросы в тексте учебника.

Приложение 1.

Практическая работа.

Цель работы: научиться решать задачи на рекурсию без использования компьютера.

Задания:

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

F(1)=1

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

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

Решение:

F(1)=1

F(2)=F(1)*3=1*3=3

F(3)=F(2)*4=3*4=12

F(4)=F(3)*5=12*5=60

F(5)=F(4)*6=60*6=360

Ответ: 360

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

F(1)=1

F(n)=F(n-1)*(n+2), при n>1

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

Решение:

F(1)=1

F(2)=F(1)*4=1*4=4

F(3)=F(2)*5=4*5=20

F(4)=F(3)*6=20*6=120

F(5)=F(4)*7=120*7=840

Ответ: 840

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

F(1)=1

F(n)=F(n-1)*(2*n+1), при n>1

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

Решение:

F(1)=1

F(2)=F(1)*5=1*5=5

F(3)=F(2)*7=5*7=35

F(4)=F(3)*9=35*9=315

Ответ: 315

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

F(1)=1

F(n)=F(n-1)*(2*n-1), при n>1

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

Решение:

F(1)=1

F(2)=F(1)*3=1*3=3

F(3)=F(2)*5=3*5=15

F(4)=F(3)*7=15*7=105

F(5)=F(4)*9=105*9=945

Ответ: 945

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

F(1)=1

F(n)=F(n-1)*(3*n-2), при n>1

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

Решение:

F(1)=1

F(2)=F(1)*4=1*4=4

F(3)=F(2)*7=4*7=28

F(4)=F(3)*10=28*10=280

Ответ: 280

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

F(0)=1, F(1)=1

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

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

Решение:

F(0)=1

F(1)=1

F(2)=F(1)+F(0)=1+1=2

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

F(4)=F(3)+F(2)=3+2=5

F(5)=F(4)+F(3)=5+3=8

F(6)=F(5)+F(4)=8+5=13

F(7)=F(6)+F(5)=13+8=21

Ответ: 21

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

F(0)=1, F(1)=1

F(n)=2*F(n-1)+F(n-2), при n>1

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

Решение:

F(0)=1

F(1)=1

F(2)=2*F(1)+F(0)=2*1+1=3

F(3)=2*F(2)+F(1)=2*3+1=7

F(4)=2*F(3)+F(2)=2*7+3=17

F(5)=2*F(4)+F(3)=2*17+7=41

F(6)=2*F(5)+F(4)=2*41+17=99

Ответ: 99

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

F(0)=1, F(1)=1

F(n)=F(n-1)+2*F(n-1), при n>1

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

Решение:

F(0)=1

F(1)=1

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

F(3)=F(2)+2*F(2)=3+2*3=9

F(4)=F(3)+2*F(3)=9+2*9=27

F(5)=F(4)+2*F(4)=27+2*27=81

F(6)=F(5)+2*F(5)=81+2*81=243

Ответ: 243

9.      Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

writeln(n);

if n<6 then begin

F(n+2);

F(n*3)

end

end;

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

Решение:

1)      сначала определим рекурентную формулу; обозначим через F(n) сумму чисел, которая при вызове F(n)

2)      при n>=6 процедура выводит число n и заканчивает работы без рекурсивных вызовов: F(n)=n, при n>=6

3)      при n<6 процедура выводит число n и дважды вызывает сама себя F(n)=n+F(n+2)+F(3n), при n<6

4)      в результате вызова F(1) получаем:

F(1)=1+F(3)+F(3)

F(3)=3+F(5)+F(9)=3+F(5)+9

F(5)=5+F(7)+F(15)=5+7+15=27

5)      используем обратную подстановку

F(3)=3+F(5)+F(9)=3+F(5)+9=3+27+9=39

F(1)=1+2*F(3)=79

6)      ответ: 79

10.  Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

writeln(‘*’);

if n>0 then begin

F(n-2);

F(n div 2)

end

end;

Сколько…

Решение:

1)      сначала определим рекурентную формулу; обозначим через F(n), количество звездочек при вызове программы

2)      из программы видим, что

F(n)=1, при n<=0

F(n)=1+F(n-2)+F(n div 2), при n>0

3)      вспомним, что n div 2 – это частное от деления n на 2

4)      по этим формулам заполняем таблицу, начиная с 0:

F(0)=1

F(1)=1+F(-1)+F(0)=1+1+1=3

F(2)=1+F(0)+F(1)=1+1+3=5

F(3)=1+F(1)+F(1)=1+3+3=7

F(4)=1+F(2)+F(2)=1+5+5=11

F(5)=1+F(3)+F(2)=1+7+5=13

F(6)=1+F(4)+F(3)=1+11+7=19

F(7)=1+F(5)+F(3)=1+13+7=21

n	0	1	2	3	4	5	6	7
F(n)	1	3	5	7	11	13	19	21

5)      ответ: 21

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

F(1)=1, G(1)=1;

F(n)=F(n-1)-G(n-1),

G(n)= F(n-1)+G(n-1), при n>=2

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

Решение:

1)      фактически рекурентная формула задана для пары (F(n);G(n))

2)      замечаем, что F(n) – это разновидность предыдущей пары, аG(n) – сумма тех же значений

3)      заполняем таблицу, начиная с известной первой пары

n	1	2	3	4	5
F(n)	1	0	-2	-4	-4
G(n)	1	2	2	0	-4

4)      искомое значение F(5)/G(5) равно 1

5)      Ответ: 1