Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292967
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями:
$F(n)=0$ при $n\leqslant1$;
$F(n)=(n+1)/2+F(n-1)$, если $n>1$ и при этом $n$ нечётно;
$F(n)=2\cdot F(n-1)+1$, если $n>1$ и при этом $n$ чётно.
Чему равно значение функции $F(33)$?
Примечание. При вычислении значения $F(n)$ используется операция целочисленного деления.
Так как $33=2\cdot16+1$, рассмотрим значения функции для нечётных аргументов. Обозначим:
$G(k)=F(2k+1).$
Тогда для чётного аргумента $2k$:
$F(2k)=2\cdot F(2k-1)+1=2\cdot G(k-1)+1.$
Для следующего нечётного аргумента:
$G(k)=F(2k+1)=\dfrac{2k+2}{2}+F(2k).$
Следовательно:
$G(k)=k+1+2\cdot G(k-1)+1=2\cdot G(k-1)+k+2.$
Введём выражение:
$H(k)=G(k)+k+4.$
Тогда:
$H(k)=2\cdot G(k-1)+k+2+k+4=2\cdot G(k-1)+2k+6.$
Получаем:
$H(k)=2\cdot\bigl(G(k-1)+(k-1)+4\bigr)=2\cdot H(k-1).$
Начальное значение:
$H(0)=G(0)+4=F(1)+4=0+4=4.$
Поэтому:
$H(k)=4\cdot2^k=2^{k+2}.$
Значит:
$G(k)=2^{k+2}-k-4.$
Вычислим значение при $k=16$:
$F(33)=G(16)=2^{18}-16-4=262144-20=262124.$
20
