Задание EGEINFFDDA65: Рекурсия и рекуррентные зависимости

Дано: аргумент n — целое число. Правила вычисления:
F(n) = 2 · (G(n − 3) + 8).
G(n) = 2 · n при n ≤ 9.
G(n) = G(n − 2) + 1 при n ≥ 10.
Найти R = F(15548).

Сначала вычислим значения G, которые требуются в формуле F. Правило G(n) = G(n − h) + c означает, что каждый переход уменьшает аргумент на h и добавляет c. После k переходов получаем G(a) = G(a − kh) + kc. Выбираем наименьшее k, при котором b = a − kh попадает в базовую ветвь. Тогда остаётся подставить базовое G(b) и число прибавлений.

Аргумент a = 15545: h = 2, k = 7768, b = 15545 − 7768 · 2 = 9. Значение 9 уже относится к базе; 11 ещё к рекурсии.
G(15545) = G(9) + 7768 · 1 = 18 + 7768 · 1 = 7786.

Теперь используем исходную связь F и G:
F(15548) = 2 · (G(15548 − 3) + 8) = 2 · (7786 + 8) = 15588.

Проверка. Прямой последовательный расчёт G от базовых аргументов даёт те же значения. Остаток аргумента при делении на h сохраняется, поэтому выбран правильный последний аргумент. Подстановка этих значений в формулу F подтверждает ответ 15588.

Ответ: 15588.