Цепочки до базы и перебор n

Что если аргумент уменьшается не на 1, а сразу на 3?

Тогда от каждого n идёт своя цепочка аргументов. Считаем, сколько в ней переходов до базы и на каком числе она в базу попадёт. Пусть F(n) = n при n ≤ 5; F(n) = F(n − 3) + 4 при n > 5.

F(20): аргументы 20, 17, 14, 11, 8, 5 — пять переходов по 4. F(20) = F(5) + 5 · 4 = 25. А у F(21) цепочка другая: 21, 18, 15, 12, 9, 6, 3 — шесть переходов, и попадает она в 3. F(21) = 3 + 6 · 4 = 27.

Поэтому нельзя считать, что цепочка всегда закончится на границе базы: у каждого остатка от деления на шаг — свой конец.

Что делать с разностью, если аргументы лежат на разных цепочках? Например: F(n) = n при n ≥ 1000; F(n) = n + F(n + 2) при n < 1000. Найдём F(11) − F(10).

От 11 аргумент идёт по нечётным числам, от 10 — по чётным, и общего значения у них нет. Тогда обе суммы расписывают целиком и вычитают слагаемые парами.

F(11) = 11 + 13 + … + 999 + F(1001) = 11 + 13 + … + 999 + 1001. F(10) = 10 + 12 + … + 998 + F(1000) = 10 + 12 + … + 998 + 1000.

Пар столько, сколько чисел 10, 12, …, 998: (998 − 10) / 2 + 1 = 495. Каждая пара даёт 1, и базы 1001 и 1000 — ещё 1. Ответ: 495 + 1 = 496.

Программой такую задачу решают так же, как задачу темы: поднять предел глубины или прогреть кеш — здесь по убыванию, от базы.

А если одна функция переходит в другую и их аргументы движутся в разные стороны?

Пройти цепочку первой функции до места, где она передаёт работу второй, и дальше идти по цепочке второй. Пусть F(n) = F(n − 4) + 20 при n ≥ 12; F(n) = 3 · (G(n − 2) − 1) при n < 12; G(n) = n при n ≥ 30; G(n) = G(n + 7) + 2 при n < 30. Найдём F(39).

1. F идёт вниз: 39, 35, 31, 27, 23, 19, 15, 11 — семь переходов по 20, F(39) = F(11) + 140.
2. При n = 11 правило другое: F(11) = 3 · (G(9) − 1).
3. G идёт вверх: 9, 16, 23, 30 — три перехода по 2, G(9) = G(30) + 6 = 36.
4. F(11) = 3 · (36 − 1) = 105, F(39) = 105 + 140 = 245.

Заметь: 140, накопленные на шагах F, не попадают под умножение на 3 — оно действует только внутри F(11).

def G(n):    if n >= 30:        return n    return G(n + 7) + 2  def F(n):    if n >= 12:        return F(n - 4) + 20    return 3 * (G(n - 2) - 1)  print(F(39))

Что если спрашивают не значение, а аргумент — сколько n подходит или какое n наименьшее?

Тогда функцию вызывают для каждого n по очереди: считают подходящие или останавливаются на первом. Пусть F(0) = 0; F(n) = F(n // 2) + n % 2 при n > 0. Сколько чисел от 1 до 63 дают F(n) = 2?

def F(n):    if n == 0:        return 0    return F(n // 2) + n % 2  count = 0for n in range(1, 64):    if F(n) == 2:        count += 1print(count)

Аргумент здесь каждый раз делится пополам, поэтому вызовы короткие. Почему ответ 15, можно понять и без программы — это в дополнительном уроке.

Наименьшее n ищут циклом while: он увеличивает n, пока условие не выполнено. Для функции задачи темы найдём наименьшее n, при котором F(n) > 1 000 000 000:

def F(n):    if n == 1:        return 1    return n * F(n - 1)  n = 1while F(n) <= 10**9:    n += 1print(n)

Цикл остановился на первом подходящем n — оно и наименьшее: F(12) = 479 001 600, а F(13) = 6 227 020 800.

• Шаг больше 1у каждого остатка своя цепочка, считаем переходы
• Конец цепочкине обязательно на границе базы
• Разные цепочкирасписать обе суммы и вычесть слагаемые парами
• Две функциицепочка одной, потом другой; прибавки внешних шагов — вне скобок
• Сколько nцикл со счётчиком
• Наименьшее nwhile до первого подходящего