Алгоритм вычисления значения функции 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 тапсырма — жауабымен және дәл осындай талдауымен.