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

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

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

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

Аргумент a = 26728: h = 2, k = 13359, b = 26728 − 13359 · 2 = 10. Значение 10 уже относится к базе; 12 ещё к рекурсии.
G(26728) = G(10) + 13359 · 1 = 10 + 13359 · 1 = 13369.

Теперь используем исходную связь F и G:
F(26728) = 2 · G(26728) + G(26728 − 1) = 2 · 13369 + 13368 = 40106.

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

Ответ: 40106.