Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292974
Алгоритм вычисления значения функции $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(30)$?
Примечание. При вычислении значения $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_{14}=2\cdot24559+14+2=49134.$
$A_{15}=2\cdot49134+15+2=98285.$
Так как $A_{15}=F(30)$, получаем:
$F(30)=98285.$
20
