Карточки
Тесты
Главная
Курсы
Подписка
16. Рекурсивные алгоритмы: #292991
Алгоритм вычисления функций $F(n)$ и $G(n)$, где $n$ — целое число, задан следующими соотношениями:
$F(n)=2\cdot G(n)+G(n-1);$
$G(n)=n$, если $n\leqslant10$;
$G(n)=G(n-2)+1$, если $n>10$.
Чему равно значение выражения $F(26728)$?
Вычислим $G(26728)$.
Число $26728$ чётное, поэтому будем уменьшать аргумент на $2$ до числа $10$.
Количество применений рекурсии:
$\dfrac{26728-10}{2}=\dfrac{26718}{2}=13359.$
Следовательно:
$G(26728)=G(10)+13359=10+13359=13369.$
Вычислим $G(26727)$.
Число $26727$ нечётное, поэтому будем уменьшать аргумент на $2$ до числа $9$.
Количество применений рекурсии:
$\dfrac{26727-9}{2}=\dfrac{26718}{2}=13359.$
Следовательно:
$G(26727)=G(9)+13359=9+13359=13368.$
Подставим найденные значения:
$F(26728)=2\cdot G(26728)+G(26727).$
$F(26728)=2\cdot13369+13368=26738+13368=40106.$
20
