Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292968
Алгоритм вычисления функций $F(n)$ и $G(n)$, где $n$ — целое число, задан следующими соотношениями:
$F(n)=2\cdot(G(n-3)+8);$
$G(n)=2\cdot n$, если $n<10$;
$G(n)=G(n-2)+1$, если $n\geqslant10$.
Чему равно значение выражения $F(15548)$?
Подставим значение аргумента в формулу функции $F$:
$F(15548)=2\cdot(G(15548-3)+8)=2\cdot(G(15545)+8).$
При каждом применении рекурсии аргумент функции $G$ уменьшается на $2$, а значение увеличивается на $1$.
Число $15545$ нечётное, поэтому будем уменьшать его до наибольшего нечётного числа, меньшего $10$, то есть до $9$.
Количество применений рекурсии:
$\dfrac{15545-9}{2}=\dfrac{15536}{2}=7768.$
Следовательно:
$G(15545)=G(9)+7768.$
Так как $9<10$, получаем:
$G(9)=2\cdot9=18.$
Тогда:
$G(15545)=18+7768=7786.$
Вычислим значение функции $F$:
$F(15548)=2\cdot(7786+8)=2\cdot7794=15588.$
20
