Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292989
Алгоритм вычисления значения функции $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(24)$?
Обозначим значение функции для чётного аргумента:
$A_k=F(2k).$
Для нечётного аргумента $2k-1$ получаем:
$F(2k-1)=2\cdot(2k-1)+F(2k-2)=4k-2+A_{k-1}.$
Для следующего чётного аргумента:
$A_k=F(2k)=2\cdot F(2k-1)=2\cdot A_{k-1}+8k-4.$
Начальное значение:
$A_1=F(2)=2\cdot F(1)=0.$
Последовательно вычислим значения:
$A_2=2\cdot0+8\cdot2-4=12.$
$A_3=2\cdot12+8\cdot3-4=44.$
$A_4=2\cdot44+8\cdot4-4=116.$
$A_5=2\cdot116+8\cdot5-4=268.$
$A_6=2\cdot268+8\cdot6-4=580.$
$A_7=2\cdot580+8\cdot7-4=1212.$
$A_8=2\cdot1212+8\cdot8-4=2484.$
$A_9=2\cdot2484+8\cdot9-4=5036.$
$A_{10}=2\cdot5036+8\cdot10-4=10148.$
$A_{11}=2\cdot10148+8\cdot11-4=20380.$
$A_{12}=2\cdot20380+8\cdot12-4=40852.$
Так как $A_{12}=F(24)$, получаем: $F(24)=40852.$
20
