Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292986
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n=1$;
$F(n)=n+F(n-1)$, если $n$ чётно;
$F(n)=2\cdot F(n-2)$, если $n>1$ и при этом $n$ нечётно.
Чему равно значение функции $F(24)$?
Сначала найдём значение $F(23)$.
Для нечётных аргументов значение функции удваивается:
$F(3)=2\cdot F(1)=2.$
$F(5)=2\cdot F(3)=4.$
Следовательно, для нечётного числа $n=2k+1$ выполняется:
$F(2k+1)=2^k.$
Число $23$ представим в виде: $23=2\cdot11+1.$
Поэтому: $F(23)=2^{11}=2048.$
Так как $24$ — чётное число:
$F(24)=24+F(23)=24+2048=2072.$
20
