解决递归序列

Question

最近我为了乐趣解决了一些来自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"

我不知道是否需要将递归关系简化，但由于偶数和奇数都有一个关系，所以我觉得这很难做到（我还没有在学校学习过这方面的内容，所以我对这个主题的了解都是来自互联网文章）。

因此，任何有助于指导我完成这个挑战的帮助都将受到欢迎 :)

- Gonçalo Santos

---

我认为你需要了解一些高级数学知识并使用快速矩阵指数运算。 - Piotr Dabkowski

这可能会有所帮助：https://dev59.com/OHI-5IYBdhLWcg3wKVA9 - Lambda Fairy

@LambdaFairy 或许就是这个！我本以为不会有太大的区别，但结果比之前快了许多！谢谢！我现在会尝试用它实现，如果行了我会告诉你的 :D - Gonçalo Santos

@LambdaFairy，是的，它确实起作用了 :) 我之前尝试过，但可能在编码时犯了一些错误，结果速度差不多。而且，我不知道它被称为记忆化。好吧，在进行其他优化的同时，我让它在不到一秒钟的时间内找到了答案！谢谢！ - Gonçalo Santos

@GonçaloSantos 请添加您的答案并接受它。这将使我们所有人受益 :) - Bhargav Rao

@BhargavRao 哦，好的，我一定会做的！我现在有点忙，但我会尽快完成 :) - Gonçalo Santos

Answer 1

我没有试图在数学上简化这个函数，而是在Python中简化了算法。如@LambdaFairy建议的那样，在getNumberOfZombits（time）函数中实现了备忘录技术。这种优化使函数的速度提高了很多。

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

正如您所看到的，与偶数相比，奇数始终需要更长的时间才能达到相同的输出。

问题是我们无法搜索递增1的数字（这太慢了）。我为解决这个问题采用了类似二分查找的算法。首先，我会使用类似二分查找的算法搜索偶数，直到找到一个答案或没有更多数字可搜索为止。然后，我对奇数执行相同的操作（再次使用类似二分查找的算法），如果找到答案，我将其替换为以前的任何内容（因为它必定比以前的答案大）。

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

- Gonçalo Santos

Answer 2

解决这个难题的关键是使用二分查找。

正如您从序列生成器中看到的那样，它们依赖于大约n/2的递归，因此计算R(N)需要大约2*log2(N)次递归调用；当然，你需要为奇数和偶数都这样做。

这并不太糟糕，但你需要找出在哪里搜索会给你输入的N。为了做到这一点，我首先实现了一个搜索N的上下界。我通过2的幂逐步增加N，直到我有了每个序列（奇数和偶数）的下限和上限，分别为N和2N。

有了这些边界，我就可以在它们之间进行二分查找，快速找到N的值或其不存在。

- Sean