Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292994
Алгоритм вычисления значения функции $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(36)$?
Так как $36$ — чётное число, получаем:
$F(36)=F(35)+36-1=F(35)+35.$
Вычислим $F(35)$. Для нечётных аргументов используется соотношение:
$F(n)=F(n-2)+2\cdot n-2.$
Пусть $n=2k+1$. Тогда:
$F(2k+1)=F(2k-1)+2\cdot(2k+1)-2=F(2k-1)+4k.$
Так как $35=2\cdot17+1$, получаем:
$F(35)=F(1)+4\cdot(1+2+\ldots+17).$
$F(1)=1.$
$1+2+\ldots+17=\dfrac{17\cdot18}{2}=153.$
Следовательно: $F(35)=1+4\cdot153=1+612=613.$
Тогда: $F(36)=613+35=648.$
20
