Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292977
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n<3$;
$F(n)=F(n-1)+n-1$, если $n>2$ и при этом $n$ чётно;
$F(n)=F(n-2)+2\cdot n-2$, если $n>2$ и при этом $n$ нечётно.
Чему равно значение функции $F(33)$?
Для вычисления $F(33)$ используется формула для нечётных значений аргумента:
$F(n)=F(n-2)+2\cdot n-2.$
Последовательно нечётные аргументы принимают значения $3,5,7,\ldots,33$.
При переходе к очередному нечётному аргументу прибавляется:
$2\cdot n-2.$
Для $n=2k+1$ получаем:
$2\cdot(2k+1)-2=4k.$
Числу $33$ соответствует значение: $33=2\cdot16+1.$
Следовательно: $F(33)=F(1)+4\cdot(1+2+\ldots+16).$
Так как:
$F(1)=1,$
$1+2+\ldots+16=\dfrac{16\cdot17}{2}=136,$
получаем: $F(33)=1+4\cdot136=1+544=545.$
20
