Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292970
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=2$ при $n<3$;
$F(n)=F(n-2)+F(n-1)-n$, если $n>2$ и при этом $n$ чётно;
$F(n)=F(n-1)-F(n-2)+2\cdot n$, если $n>2$ и при этом $n$ нечётно.
Чему равно значение функции $F(32)$?
Рассмотрим нечётное число $n=2k+1$:
$F(2k+1)=F(2k)-F(2k-1)+4k+2.$
Для чётного числа $2k$:
$F(2k)=F(2k-2)+F(2k-1)-2k.$
Подставим это выражение:
$F(2k+1)=F(2k-2)+F(2k-1)-2k-F(2k-1)+4k+2=F(2k-2)+2k+2.$
Теперь найдём следующее чётное значение:
$F(2k+2)=F(2k)+F(2k+1)-(2k+2).$
Подставим найденное выражение:
$F(2k+2)=F(2k)+F(2k-2)+2k+2-(2k+2)=F(2k)+F(2k-2).$
Следовательно, каждое чётное значение функции равно сумме двух предыдущих чётных значений.
Начальные значения:
$F(2)=2.$
$F(3)=F(2)-F(1)+2\cdot3=2-2+6=6.$
$F(4)=F(2)+F(3)-4=2+6-4=4.$
Последовательно вычислим чётные значения:
$F(6)=F(4)+F(2)=4+2=6.$
$F(8)=F(6)+F(4)=6+4=10.$
$F(10)=F(8)+F(6)=10+6=16.$
$F(12)=F(10)+F(8)=16+10=26.$
$F(14)=F(12)+F(10)=26+16=42.$
$F(16)=F(14)+F(12)=42+26=68.$
$F(18)=F(16)+F(14)=68+42=110.$
$F(20)=F(18)+F(16)=110+68=178.$
$F(22)=F(20)+F(18)=178+110=288.$
$F(24)=F(22)+F(20)=288+178=466.$
$F(26)=F(24)+F(22)=466+288=754.$
$F(28)=F(26)+F(24)=754+466=1220.$
$F(30)=F(28)+F(26)=1220+754=1974.$
$F(32)=F(30)+F(28)=1974+1220=3194.$
20
