Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #293000
Алгоритм вычисления значения функции $F(n)$, где $n$ — натуральное число, задан следующими соотношениями:
$F(n)=1$ при $n<3$;
$F(n)=F(n-2)-F(n-1)$, если $n>2$ и при этом $n$ чётно;
$F(n)=2\cdot F(n-1)-F(n-2)$, если $n>2$ и при этом $n$ нечётно.
Чему равно значение функции $F(18)$?
Начальные значения:
$F(1)=1.$
$F(2)=1.$
Последовательно вычислим значения функции:
$F(3)=2\cdot F(2)-F(1)=2\cdot1-1=1.$
$F(4)=F(2)-F(3)=1-1=0.$
$F(5)=2\cdot F(4)-F(3)=2\cdot0-1=-1.$
$F(6)=F(4)-F(5)=0-(-1)=1.$
$F(7)=2\cdot F(6)-F(5)=2\cdot1-(-1)=3.$
$F(8)=F(6)-F(7)=1-3=-2.$
$F(9)=2\cdot F(8)-F(7)=2\cdot(-2)-3=-7.$
$F(10)=F(8)-F(9)=-2-(-7)=5.$
$F(11)=2\cdot F(10)-F(9)=2\cdot5-(-7)=17.$
$F(12)=F(10)-F(11)=5-17=-12.$
$F(13)=2\cdot F(12)-F(11)=2\cdot(-12)-17=-41.$
$F(14)=F(12)-F(13)=-12-(-41)=29.$
$F(15)=2\cdot F(14)-F(13)=2\cdot29-(-41)=99.$
$F(16)=F(14)-F(15)=29-99=-70.$
$F(17)=2\cdot F(16)-F(15)=2\cdot(-70)-99=-239.$
$F(18)=F(16)-F(17)=-70-(-239)=169.$
20
