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

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

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

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

Условие

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

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

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

К подсказкам

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

5 шагов

Начальные значения: $F(1)=0$, поэтому $F(2)=2F(1)=0$.

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

Получаем значения около искомого аргумента:

$$F(21)=10190,\quad F(22)=2\cdot10190=20380$$

Для нечётного $n=23$:

$$F(23)=2\cdot23+F(22)=46+20380=20426$$

Для чётного $n=24$:

$$F(24)=2F(23)=2\cdot20426=40852$$

Ответ

40852

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

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

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

Забыть, что при чётном $n$ значение функции удваивается без прибавления $2n$.

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

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

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

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

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

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