Урок по теме "Рекуррентные и рекурсивные алгоритмы. Решение Задач" (10 класс)

28.11.2018г.

Информатика 10 класс

Урок №23

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

Цели и задачи урока:

—  образовательные

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

воспитательные

ü  воспитать аккуратность, внимание, организованность;

—  развивающие

ü развить логическое и алгоритмического мышления учащихся;

Тип урока: урок изучения нового материала

Ход урока:

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

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

Что называют рекуррентным соотношением?

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

3)  Решение задач.

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

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

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

F(1) = 1

F(2) = 3

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

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Пояснение.

Последовательно находим:

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

F(4) = F(3) * 4 + F(2) * 3 = 53,

F(5) = F(4) * 5 + F(3) * 4 = 309.

---

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

F(1) = 1

F(2) = 3

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

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Пояснение.

Последовательно находим:

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

F(4) = F(3) * F(2) + 2 = 14,

F(5) = F(4) * F(3) + 3 = 59.

---

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

F(1) = 1

F(2) = 2

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

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Пояснение.

Последовательно находим:

F(3) = 2 * F(2) + (3 – 2) * F(1) = 5,

F(4) = 2 * F(3) + (4 – 2) * F(2) = 14,

F(5) = 2 * F(4) + (5 – 2) * F(3) = 43,

F(6) = 2 * F(5) + (6 – 2) * F(4) = 142.

---

4.    Последовательность чисел Фибоначчи задается рекуррентным соотношением:

F(1) = 1

F(2) = 1

F(n) = F(n–2) + F(n–1), при n >2, где n – натуральное число.

Чему равно восьмое число в последовательности Фибоначчи?

В ответе запишите только натуральное число.

Пояснение.

Последовательно находим:

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

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

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

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

F(7) = F(5) + F(6) = 13,

F(8) = F(6) + F(7) = 21.

Восьмое число в последовательности Фибоначчи равно 21.

5.     Дан рекурсивный алгоритм F (для простоты приведен код на языке программирования Паскаль):

·                     procedure F(n: integer);

·                     begin

·                       writeln(n);

·                       if n < 5 then begin

·                         F(n + 1);

·                         F(n + 3)

·                       end

·                     end;

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

Решение

построение дерева вызовов: 

1.                  поскольку в начале каждого вызова на экран выводится значение единственного параметра функции, достаточно определить порядок рекурсивных вызовов и сложить значения параметров

2.                  поскольку при   выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции:

складывая все эти числа, получаем 25

Правильный ответ: 25.

6.     Ниже записан рекурсивный алгоритм F.

Паскаль

procedure F(n: integer);     begin         writeln(n);         if n < 5 then             begin                 F(n + 1);                 F(n + 3)             end     end

Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?

Пояснение.

Первым действием процедура F(1) выведет число 1. Далее процедура F(1) вызовет процедуру F(n + 1), в результате выполнения которой на экране появится число n + 1 = 2. Процедура F(2) вызовет процедуру F(3), которая выведет на экран число 3 и вызовет процедуру F(4), которая выведет на экран число 4 и вызовет F(5), которая выведет на экран число 5.

После этого управление вернётся к процедуре F(4), которая начнёт выполнять следующий шаг своего алгоритма, т. е. обратиться к процедуре F(n + 3) = F(7). Процедура F(7) выведет на экран число 7. Далее управление вернётся к процедуре F(3). Рассуждая аналогично приходим к выводу, что процедура F(3) дополнительно выведет на экран число 6, процедура F(2) — 5.

Последним действием процедуры F(1) будет вызов процедуры F(n + 3) = F(4), которая выведет на экран числа 4, 5, 7.

Таким образом, на экране будут числа 1, 2, 3, 4, 5, 7, 6, 5, 4, 5, 7. Их сумма равна 49.

Ответ: 49.

4)     Д/з п. 15 стр. 80-83 ответить на вопросы

1.     Последовательность чисел Фибоначчи задается рекуррентным соотношением:

F(1) = 1

F(2) = 1

F(n) = F(n–2) + F(n–1), при n >2, где n – натуральное число.

Чему равно девятое число в последовательности Фибоначчи?

В ответе запишите только натуральное число.