Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292984
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=2\cdot F(n-1)+2$, если $n>1$ и при этом $n$ нечётно;
$F(n)=n/2+F(n-1)$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(26)$?
Примечание. При вычислении значения $F(n)$ используется операция целочисленного деления.
Обозначим через $A_k$ значение функции для чётного аргумента:
$A_k=F(2k).$
Для нечётного аргумента $2k-1$:
$F(2k-1)=2\cdot F(2k-2)+2=2\cdot A_{k-1}+2.$
Для следующего чётного аргумента:
$A_k=F(2k)=k+F(2k-1)=2\cdot A_{k-1}+k+2.$
Начальное значение:
$A_1=F(2)=2/2+F(1)=1+0=1.$
Последовательно вычислим значения:
$A_2=2\cdot1+2+2=6.$
$A_3=2\cdot6+3+2=17.$
$A_4=2\cdot17+4+2=40.$
$A_5=2\cdot40+5+2=87.$
$A_6=2\cdot87+6+2=182.$
$A_7=2\cdot182+7+2=373.$
$A_8=2\cdot373+8+2=756.$
$A_9=2\cdot756+9+2=1523.$
$A_{10}=2\cdot1523+10+2=3058.$
$A_{11}=2\cdot3058+11+2=6129.$
$A_{12}=2\cdot6129+12+2=12272.$
$A_{13}=2\cdot12272+13+2=24559.$
Так как $A_{13}=F(26)$, получаем: $F(26)=24559.$
20
