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

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

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

Аргумент a = 37808: h = 3, k = 12596, b = 37808 − 12596 · 3 = 20. Значение 20 уже относится к базе; 23 ещё к рекурсии.
G(37808) = G(20) + 12596 · 1 = 22 + 12596 · 1 = 12618.

Теперь используем исходную связь F и G:
F(37811) = 3 · G(37811 − 3) + 7 = 3 · 12618 + 7 = 37861.

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

Ответ: 37861.