ГлавнаяИнформатикаКак решатьАлгоритм вычисления значения функции F(n)

Алгоритм вычисления значения функции F(n)

2016-06-29 01:18:15

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

Задание входит в ЕГЭ по информатике для 11 класса под номером 11 (Рекурсивные алгоритмы).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

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

F(n) = 1 при n ≤ 2;

F(n) = F(n − 1) + 3 × F(n − 2) при n > 2.

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

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

Решение:

Вычислим значения функции при n, начиная с единицы:

F(1) = 1

F(2) = 1

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

F(4) = F(3) + 3 ⋅ F(2) = 4 + 3 ⋅ 1 = 7

F(5) = F(4) + 3 ⋅ F(3) = 7 + 3 ⋅ 4 = 19

F(6) = F(5) + 3 ⋅ F(4) = 19 + 3 ⋅ 7 = 40

F(7) = F(6) + 3 ⋅ F(5) = 40 + 3 ⋅ 19 = 97

Таким образом, значение функции F(7) равно 97.

Ответ: 97

Есть другой способ решения?

Наверх