最近我为了乐趣解决了一些来自Google Foobar的挑战,但现在有一个挑战困扰了我四天多。它涉及到一个递归函数的定义如下:
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的十进制字符串表示形式,该函数返回最大的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"
我不知道是否需要将递归关系简化,但由于偶数和奇数都有一个关系,所以我觉得这很难做到(我还没有在学校学习过这方面的内容,所以我对这个主题的了解都是来自互联网文章)。
因此,任何有助于指导我完成这个挑战的帮助都将受到欢迎 :)