Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292981
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=2\cdot n+F(n-1)$, если $n>1$ и при этом $n$ нечётно;
$F(n)=2\cdot F(n-1)$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(22)$?
Рассмотрим два последовательных аргумента $2k-1$ и $2k$, где $k\geqslant2$.
Для нечётного аргумента:
$F(2k-1)=2\cdot(2k-1)+F(2k-2)=4k-2+F(2k-2).$
Для следующего чётного аргумента:
$F(2k)=2\cdot F(2k-1)=2\cdot F(2k-2)+8k-4.$
Начальное значение:
$F(2)=2\cdot F(1)=2\cdot0=0.$
Последовательно вычислим значения функции для чётных аргументов:
$F(4)=2\cdot F(2)+12=2\cdot0+12=12.$
$F(6)=2\cdot F(4)+20=2\cdot12+20=44.$
$F(8)=2\cdot F(6)+28=2\cdot44+28=116.$
$F(10)=2\cdot F(8)+36=2\cdot116+36=268.$
$F(12)=2\cdot F(10)+44=2\cdot268+44=580.$
$F(14)=2\cdot F(12)+52=2\cdot580+52=1212.$
$F(16)=2\cdot F(14)+60=2\cdot1212+60=2484.$
$F(18)=2\cdot F(16)+68=2\cdot2484+68=5036.$
$F(20)=2\cdot F(18)+76=2\cdot5036+76=10148.$
$F(22)=2\cdot F(20)+84=2\cdot10148+84=20380.$
20
