Методика подготовки к КЕГЭ по теме «Рекурсивные алгоритмы»
учебно-методический материал по информатике и икт (10 класс)

Методика подготовки к КЕГЭ по теме «Рекурсивные алгоритмы»

Опишу свой опыт преподавания темы «Рекурсия».

Я преподаю информатику в 10-11 классах на профильном уровне по учебнику Семакина И.Г. На тему «Рекурсивные методы программирования» отведено 5 часов в 11 классе:

1 урок Ввожу понятия: рекуррентная последовательность, рекуррентная формула, частично-рекурсивная функция, рекурсивная подпрограмма (функция, процедура). Разбираем примеры задач 1, 2, 3 из п.2.3.1. учебника Семакина И.Г. «Информатика и ИКТ. Профильный уровень».

2 урок Рассматриваем пример 4 из п.2.3.1. и №3,4 к данному параграфу.

3 урок Задача о Ханойской башне (урок одной задачи)

4 урок Рассматриваю алгоритм быстрой сортировки.

5 урок Так как на решение задач для подготовки к ЕГЭ в данной теме не выделяется уроков, 5 урок я отвожу для решения таких задач. На этом уроке мы рассматриваем следующие типы задач:

1. Вызов рекурсивных процедур

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

F(1) = 2; 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)? В ответе запишите только целое число.

Решение:

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

F(3)=F(2)-G(2)=-2         G(3)=F(2)+G(2)=4

F(4)=F(3)-G(3)=-6         G(4)=F(3)+G(3)=2

F(5)=F(4)-G(4)=-8         G(5)=F(4)+G(4)=-4

Ответ: F(5)/G(5)=2

2. Алгоритмы, опирающиеся на несколько предыдущих значений

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

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

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

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

Решение:

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

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

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

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

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

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

3. Алгоритмы, опирающиеся на одно предыдущее значение

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

F(1) = 1

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

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

Решение:

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

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

F(4)=F(3)*(2*4+1)=35*9=315

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

Для самостоятельной работы учащимся предлагаю использовать Интернет-ресурсы, представленные ниже. Также отвожу время данной теме на дополнительных занятиях по подготовке к КЕГЭ. Я провожу со своими учениками все диагностические и тренировочные работы в системе «Статград». Если возникают трудности у учащихся при решении задач, анализируя работы, обращаю внимание на разбор данного задания.

Изучив тему, переходим на программирование рекурсивных алгоритмов на Python.

Ресурсы, используемые для подготовки к КЕГЭ:

Тесты:

1. On-line тест по теме: «Рекурсивные алгоритмы» (сайт Полякова)  - http://kpolyakov.spb.ru/school/egetest/b11.htm
2. Каталог заданий. Алгоритмы, опирающиеся на несколько предыдущих значений - https://inf-ege.sdamgia.ru/test?theme=275&ttest=true
3. Каталог заданий. Вызов рекурсивных процедур - https://inf-ege.sdamgia.ru/test?theme=279&ttest=true
4. Каталог заданий. Алгоритмы, опирающиеся на одно предыдущее значение - https://inf-ege.sdamgia.ru/test?theme=209&ttest=true

Презентации:

1. Презентация «Основы языка Паскаль» (раздел «Рекурсия») - http://kpolyakov.spb.ru/download/pasppt1.zip
2. Презентация «Конструирование алгоритмов» (Босова Л.Л.) - http://metodist.lbz.ru/authors/informatika/3/eor9.php
3. Презентация «Рекурсивные алгоритмы» - http://www.myshared.ru/slide/1012444
4. Презентация «Рекурсивные алгоритмы. Подготовка к ЕГЭ» - http://www.metod-kopilka.ru/prezentaciya_po_informatike_na_temu-53459.htm

Задания:

1. 11: рекурсивные алгоритмы - http://kpolyakov.spb.ru/download/ege11.doc
2. 11с: рекурсивные алгоритмы (язык C, Д.Ф. Муфаззалов) - http://kpolyakov.spb.ru/download/ege11c.doc
3. 11py: рекурсивные алгоритмы (язык Python, А.А. Паршев, Е.П. Стонт) - http://kpolyakov.spb.ru/download/ege11py.doc
4. Каталог заданий. Алгоритмы, опирающиеся на несколько предыдущих значений - https://inf-ege.sdamgia.ru/test?theme=275
5. Каталог заданий. Вызов рекурсивных процедур - https://inf-ege.sdamgia.ru/test?theme=279
6. Каталог заданий. Алгоритмы, опирающиеся на одно предыдущее значение - https://inf-ege.sdamgia.ru/test?theme=209
7. Демоверсии КИМ с 2007г. По 2017г. - http://www.fipi.ru/ege-i-gve-11/demoversii-specifikacii-kodifikatory
8. Открытый банк заданий ЕГЭ по информатики - http://85.142.162.119/os11/xmodules/qprint/index.php?proj=B9ACA5BBB2E19E434CD6BEC25284C67F
9. Рекурсия. Тренировочные задачи - https://habrahabr.ru/post/275813/