Решая рекурсивную последовательность

Question

В последнее время я решал некоторые проблемы из Google Foobar для удовольствия, и теперь я застрял в одном из них более 4 дней. Речь идет о рекурсивной функции определяются следующим образом:

R(0) = 1 
R(1) = 1 
R(2) = 2 
R(2n) = R(n) + R(n + 1) + n (for n > 1) 
R(2n + 1) = R(n - 1) + R(n) + 1 (for n >= 1) 

Задача состоит в написании функции answer(str_S), где str_S является основанием 10 строковое представление целого числа S, который возвращает наибольшее n таким образом, что R(n) = S. Если такого n нет, верните «None». Кроме того, S будет положительным целым числом не более 10^25.

Я много исследовал рекурсивные функции и о решении рекуррентных отношений, но не повезло. Я вывел первые 500 номеров, и я не нашел никакого отношения к каждому из них. Я использовал следующий код, который использует рекурсию, поэтому он становится очень медленным, когда числа начинают становиться большими.

def getNumberOfZombits(time): 
    if time == 0 or time == 1: 
     return 1 

    elif time == 2: 
     return 2 

    else: 
     if time % 2 == 0: 
      newTime = time/2 
      return getNumberOfZombits(newTime) + getNumberOfZombits(newTime+1) + newTime 

     else: 
      newTime = time/2 # integer, so rounds down 
      return getNumberOfZombits(newTime-1) + getNumberOfZombits(newTime) + 1 

Задача также некоторые тестовые случаи так, вот они:

Test cases 
========== 

Inputs: 
    (string) str_S = "7" 
Output: 
    (string) "4" 

Inputs: 
    (string) str_S = "100" 
Output: 
    (string) "None" 

Я не знаю, если мне нужно решить рекуррентное соотношение к чему-либо более простым, но есть один для даже и один для нечетных чисел, мне очень сложно это сделать (я еще не узнал об этом в школе, поэтому все, что я знаю об этом, - это интернет-статьи).

Таким образом, любая помощь на всех ведя меня, чтобы закончить этот вызов будет приветствоваться :)

Answer 1

Вместо того, чтобы пытаться упростить эту функцию математически, я упростил алгоритм в Python. Как было предложено @LambdaFairy, я реализовал memoization в функции getNumberOfZombits (time). Эта оптимизация ускорила функцию много.

Затем я перешел к следующему шагу, пытаясь понять, что было вкладом в это количество кроликов. Я проанализировал эту функцию раньше, наблюдая за ее графиком, и я знал, что четные числа получили более высокие выходы в первую очередь, и только через некоторое время нечетные числа попали на один уровень. Поскольку нам нужен самый высокий вход для этого вывода, мне сначала нужно было искать в четных числах, а затем в нечетных числах.

Как вы можете видеть, нечетные числа всегда занимают больше времени, чем даже для достижения того же выхода.

Проблема в том, что мы не могли искать числа, увеличивающиеся 1 каждый раз (это было слишком медленно). То, что я сделал, чтобы решить, было реализовать бинарный алгоритм поиска. Во-первых, я бы искал четные числа (с бинарным поиском, подобным алгоритму), пока не нашел один ответ, или у меня не было больше номеров для поиска. Затем я сделал то же самое с нечетными числами (опять же, с бинарным алгоритмом поиска, подобным алгоритму), и если бы был найден ответ, я заменил все, что у меня было раньше (поскольку это было обязательно больше, чем предыдущий ответ).

У меня есть исходный код, я использовал, чтобы решить эту проблему, так что если кто-то нуждается в этом, я не против делиться своим опытом :)

Answer 2

Ключ к решению этой загадки было с помощью двоичного поиска.

Как вы можете видеть из генераторов последовательности, они полагаются на грубую n/2 рекурсию, поэтому вычисление R (N) принимает около 2 * log2 (N) рекурсивных вызовов; и, конечно же, вам нужно сделать это как для нечетного, так и для четного.

Это не так уж плохо, но вам нужно выяснить, где искать N, который даст вам вход. Для этого я впервые применил поиск верхней и нижней границ для N. Я прошел N по степеням 2, пока не получил N и 2N, которые соответствовали нижней и верхней границам соответственно для каждой последовательности (нечетной и четной).

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