求解递推公式的有效算法

Question

给出了一个公式f(n)，其中f(n)对所有非负整数定义为：

f(0) = 1

f(1) = 1

f(2) = 2

f(2n) = f(n) + f(n + 1) + n (for n > 1)

f(2n + 1) = f(n - 1) + f(n) + 1 (for n >= 1)

我的目标是，对于任何给定的数s，找出f(n) = s的最大n，如果没有这样的n，则不返回。S最多可达10^25。

我有一个使用递归和动态规划的强力解决方案，但两者都不够有效。哪些概念可以帮助我找到解决这个问题的有效方法？

Answer 1

1. 你能计算出f(x)的值吗?x从0到MAX_SIZE只计算一次？ 我的意思是:用DP计算值。 f(0) =1 f(1) =1 f(2) =2 f(3) =3 f(4) =7 f(5) =4 ... f(MAX_SIZE) = ?？
2. 如果第一步是非法的，退出。否则，将值从小到大进行排序。 如1,1,2,3,4,7，. 现在，您可以发现在O(log(MAX_SIZE))时间内是否存在对f(n)=s满意的n。

Answer 2

在2n和2n+1的每一次迭代中，这种递归都会增加值，因此，如果在任何时候，您的值都会大于s，那么您可以停止算法。

要做出有效的算法，你必须找到或很好的公式，它将计算值，或使它在小循环中，这将比你的递归要有效得多。递归一般是O(2^n)，其中循环是O(n)。循环的外观如下：

int[] values = new int[1000];
values[0] = 1;
values[1] = 1;
values[2] = 2;
for (int i = 3; i < values.length /2 - 1; i++) {
    values[2 * i] = values[i] + values[i + 1] + i;
    values[2 * i + 1] = values[i - 1] + values[i] + 1;
}

在这个循环中添加可能破坏它的条件和失败的成功。

Answer 3

不幸的是，您没有提到您的算法应该有多快。也许你需要找到一些非常聪明的重写你的公式，使它足够快，在这种情况下，你可能想把这个问题张贴在一个数学论坛。

根据主定理，公式的运行时间是f(2n + 1)的O(n)和f(2n)的O(n log n)，因为：

T_even(n) =2* T(n / 2) +n/2

T_odd(n) =2* T(n / 2) +1

因此，整个公式的运行时间是O(n log )。

因此，如果n是问题的答案，这个算法将运行大约。O(n^2 log n)，因为您必须执行公式大约n次。

您可以通过存储先前的结果来使其更快一些，但当然，这是与内存的权衡。

下面是Python中的这样一个解决方案。

D = {}

def f(n):
    if n in D:
        return D[n]
    if n == 0 or n == 1:
        return 1
    if n == 2:
        return 2
    m = n // 2
    if n % 2 == 0:
        # f(2n) = f(n) + f(n + 1) + n (for n > 1)
        y = f(m) + f(m + 1) + m
    else:
        # f(2n + 1) = f(n - 1) + f(n) + 1 (for n >= 1)
        y = f(m - 1) + f(m) + 1
    D[n] = y
    return y

def find(s):
    n = 0
    y = 0
    even_sol = None
    while y < s:
        y = f(n)
        if y == s:
            even_sol = n
            break
        n += 2
    n = 1
    y = 0
    odd_sol = None
    while y < s:
        y = f(n)
        if y == s:
            odd_sol = n
            break
        n += 2
    print(s,even_sol,odd_sol)

find(9992)