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

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

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

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

Условие

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

$F(n)=0$ при $n\leq 1$;

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

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

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

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

3 шага

Начинаем вычисление с базового значения:

$$F(1)=0$$

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

$$F(19)=2\cdot19+F(18)=5074$$

Так как $20$ чётно, $21$ нечётно, а $22$ чётно:

$$F(20)=2F(19)=10148;\quad F(21)=2\cdot21+F(20)=10190;\quad F(22)=2F(21)=20380$$

Ответ

20380

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

Использование формулы для нечётного $n$ при чётном значении аргумента.

Забывают, что при $n\leq 1$ значение функции равно нулю.

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