В последнее время я ради развлечения решал некоторые задачи из 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 — это строковое представление числа S с основанием 10, которое возвращает наибольшее 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"
Я не знаю, нужно ли мне решать рекуррентное отношение к чему-то более простому, но так как есть одно для четных и одно для нечетных чисел, мне это очень трудно сделать (я еще не изучал это в школе, поэтому все, что я знаю об этом предмете, из статей в Интернете).
Итак, любая помощь, которая поможет мне закончить эту задачу, будет приветствоваться :)
