Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n)=1 при n 2 и при этом n чётно; F(n)=2× F(n-1)-F(n-2), если n>2 и при этом n нечётно. Чему равно значение функции F(19)?

Решение: Вычисление рекурсивной функции

ЕГЭ · Информатика · Задание 16 · Динамическое программирование

ПовышеннаяФИПИ097227Короткий ответ≈ 4 минутыРазбор в 5 шаговОтвет сверен с ключом

Условие

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

$F(n)=1$ при $n<3$;

$F(n)=F(n-2)-F(n-1)$, если $n>2$ и при этом $n$ чётно;

$F(n)=2\times F(n-1)-F(n-2)$, если $n>2$ и при этом $n$ нечётно.

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

Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.

5 шагов

Так как $1<3$ и $2<3$, начальные значения равны:

$$F(1)=F(2)=1$$

Последовательно применяем соответствующую формулу для чётных и нечётных значений $n$:

$$F(3)=1,\ F(4)=0,\ F(5)=-1,\ F(6)=1,\ F(7)=3,\ F(8)=-2$$

Продолжаем вычисления:

$$F(9)=-7,\ F(10)=5,\ F(11)=17,\ F(12)=-12,\ F(13)=-41,\ F(14)=29$$

Вычисляем последние значения:

$$F(15)=99,\ F(16)=-70,\ F(17)=-239,\ F(18)=169$$

Так как $19$ — нечётное число, используем нечётную формулу:

$$F(19)=2\times F(18)-F(17)=2\times169-(-239)=577$$

Ответ

577

так ответ выглядит в бланке

Перепутать формулы для чётных и нечётных значений $n$.

Ошибиться со знаком при вычислении $F(19)=2\times F(18)-F(17)$.

Начать рекурсию с неверных значений $F(1)$ или $F(2)$.

Закрепить приёмВ теме «Динамическое программирование» ещё 71 задача — с ответом и таким же разбором.