python - 求解递归序列

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 是整数 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"

我不知道我是否需要解决更简单的递推关系，但是因为偶数和奇数都有一个，所以我觉得很难做到(我在学校没学过)然而，所以我对这个主题的所有了解都来自互联网文章)。

因此，欢迎任何指导我完成这一挑战的帮助:)

Answer 1

我没有尝试从数学上简化这个函数，而是用 Python 简化了算法。正如@LambdaFairy 所建议的，我在 getNumberOfZombits(time) 函数中实现了内存。这种优化加快了函数很多。

然后，我进行了下一步，即尝试查看该数量的兔子的输入是什么。我之前分析过这个函数，通过观察它的图，我知道偶数首先得到更高的输出，只有在一段时间后奇数才达到相同的水平。因为我们想要输出的最高输入，所以我首先需要搜索偶数，然后再搜索奇数。

如您所见，奇数总是比偶数花费更多的时间来达到相同的输出。

问题是我们无法搜索每次增加 1 的数字(太慢了)。我为解决这个问题所做的是实现一个类似二进制搜索的算法。首先，我会搜索偶数(使用类似二进制搜索的算法)，直到找到一个答案或者我没有更多的数字可以搜索。然后，我对奇数做了同样的事情(同样，使用类似二进制搜索的算法)，如果找到答案，我用它替换我之前的任何东西(因为它必然比以前的答案大)。

我有我用来解决这个问题的源代码，所以如果有人需要它，我不介意分享它:)