Ах, эти математические загадки! Они как те загадочные родственники на семейных праздниках — вроде и знаешь, что с ними делать, но каждый раз приходится напрягаться.
Сегодня у нас в меню алгоритм вычисления функций F(n) и G(n), где n — целое число. И звучит это всё так запутанно, будто автор специально решил проверить нашу внимательность и терпение.
Итак, начнём с того, что F(n) зависит от самого себя, но через четыре шага назад.
То есть: если n ≥ 19, то F(n) = F(n−4) + 3580. А если n < 19 — внимание — тут начинается веселье: F(n) = 6 × (G(n−7) − 36). Вот это поворот!
Функция вдруг решила дружить с другой функцией G. Ну а G, в свою очередь — о да — тоже не скучает. Если n ≥ 248045, то G(n) = n/20 + 28.
Но если меньше — тогда G(n) заглядывает вперёд на девять шагов и вычитает четыре: G(n) = G(n+9) − 4.
Как говорил мой знакомый программист перед экзаменом: «Задачи с рекурсией — это как коты: сначала кажется мило и просто, а потом они начинают царапаться и прятаться под диваном». Так вот тут примерно такая же история.
Попробуем разобраться на примере нашего героя – F(673). Сначала вспоминаем правило: 673 ≥ 19?
Конечно! Значит,
F(673) = F(669) + 3580.
А теперь представьте себе бесконечную лестницу из значений функции F с шагом в четыре вниз: от 673 до 669, потом к 665, затем к 661 и так далее… Каждый раз прибавляя по 3580. Это напоминает мне анекдот:
— Доктор, у меня память как у золотой рыбки!
— Сколько времени?
— Пять секунд.
Вот примерно так и с нашей функцией: мы прыгаем по значениям вниз по лестнице из чисел с шагом четыре до тех пор, пока не дойдём до n <19.
Давайте посчитаем количество таких шагов:
Сколько раз нужно вычесть по 4 из 673 чтобы получить число меньше 19?
Ну,
(673 — x*4) <19
=> x*4 > (673 -19)
=> x*4 >654
=> x >163.5
То есть после примерно 164 шагов мы доберёмся до n <19.
Каждый такой шаг добавляет +3580 к значению функции.
Значит итоговое значение будет равно:
F(673) = F(some_n<19) + (164 ×3580)
Теперь осталось вычислить F(some_n<19). Для этого нам нужно обратиться к формуле для n<19:
F(n)=6×(G(n−7)-36).
Но тут начинается самое забавное – чтобы найти G(k), где k<248045 (а наши n<19 однозначно меньше), нам опять придётся прыгать вперёд на девять шагов и вычитать четыре каждый раз! Это напоминает мне историю про моего друга Васю, который пытался объяснить бабушке компьютерные игры:
«Бабушка, там герой бежит вперёд на девять метров и падает на четыре назад.»
«А зачем он так делает?»
«Ну… чтобы было интереснее!»
Вот точно такая же логика у функции G.
Но есть спасение! Если прыгать вперед по девяти шагах достаточно много раз, мы выйдем за пределы порога в 248045 и сможем применить простую формулу: G(n)=n/20+28.
Так что задача сводится к тому, чтобы понять сколько раз нам надо прыгнуть вперёд по девять единиц из числа меньше чем ~12 (поскольку n-7 для n<19 будет максимум около десятка), чтобы достичь хотя бы 248045.
С учётом того что каждый прыжок увеличивает аргумент функции на +9:
k + m*9 ≥248045
Где k — исходное значение (n-7).
Пусть k=12 (максимум), тогда:
12 + m*9 ≥248045
m*9 ≥248033
m ≥27559
То есть нам придётся сделать более двадцати семи тысяч прыжков вперед!
Это заставляет меня вспомнить старую шутку про математика в метро:
«Почему ты идешь пять станций пешком?»
«Потому что я математик — считаю лучше идти пешком.»
«Но это займет час!»
«А я считаю время ожидания следующего поезда!»
В нашем случае функция G считает время до достижения порога… очень долго!