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

Решение: Рекурсивная функция F(18)

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

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

Условие

Алгоритм вычисления значения функции $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(18)$?

Открыть задачу и решить самому

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

К подсказкам

Решение по шагам

4 шага

По условию $F(n)=1$ при $n<3$, поэтому $F(1)=1$ и $F(2)=1$.

$$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$$

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

$$F(10)=5,\ F(11)=17,\ F(12)=-12,\ F(13)=-41,\ F(14)=29,\ F(15)=99,\ F(16)=-70,\ F(17)=-239$$

Число 18 чётное, поэтому используем формулу для чётного аргумента.

$$F(18)=F(16)-F(17)=-70-(-239)=169$$

Ответ

169

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

Где здесь ошибаются

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

Неверно выполнить вычитание отрицательного числа на последнем шаге.

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

Тренироваться

ПредыдущаяВычисление рекурсивной функцииСледующаяВычисление рекурсивной функции

Решение по шагам

Где здесь ошибаются

Как решать задание 16 ЕГЭ, информатика