2 递归方程 - 查找索引

Question

我在弄清楚下面给出的 2 种递归关系之间的关系时遇到了一些麻烦。

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)

所以这个系列是这样的：(索引：0,1,2,3...n(
1,1,2,3,7,4,13,6,15,11,22,12,25,18,28,20,34...

目标是找到序列中任何给定数字出现的索引。
例：
给定： 7
输出：4 即 f(4( = 7

此外，由于一个数字在给定的序列中可能出现多次，因此返回该数字最后一次出现的时间。
例：
给定： 22
这里，f(10( = 22 和 f(17( = 22
所以，输出：17

从 python 代码中 - 我观察到一个数字最多出现两次(虽然不是 100% 确定..(。

我的代码来查找该系列中的第 n 个数字：

memo = {}
def rep(k):
    if k<=1:
        return 1
    if k == 2:
        return 2
    if not k in memo:
        if k%2==0:
            memo[k] = (k/2) + rep((k/2)+1) + rep(k/2)
        else:
            memo[k] = 1 + rep(((k-1)/2)-1) + rep((k-1)/2)
    value_key[memo[k]] = k
    return memo[k]

我已经使用 memo 对我已经生成的值进行哈希处理，但是使用这种方法生成并尝试从 0 开始的数字，直到我得到一个等于给定数字的值(简单的蛮力(需要很长时间，并导致内存错误对于较大的数字(输入将从 1 到 20 位不等(。

那么，我缺少的给定方程之间有什么关系吗？
如果我能找到f(n)(给定输入(和n之间的关系 - 我认为它可以很容易地在代码中实现，但我无法在数学上简化它 - 我尝试用一个替换另一个(给定的递归关系(，但到目前为止我什么都想不通。

Answer 1

编辑：

现在对最接近的值使用二叉搜索以及记忆，需要测试，但这个想法很简单。这仍然依赖于even和odd是增加序列的事实。

#!/usr/bin/env python
# inspired by your code
memo = {'even': {0: 1, 2: 2}, 'odd': {1: 1}}

def f(k):
    if k in memo['even']:
        return memo['even'][k]
    if k in memo['odd']:
        return memo['odd'][k]
    else:
        if k % 2 == 0:
            memo['even'][k] = (k / 2) + f((k / 2) + 1) + f(k / 2)
        else:
            memo['odd'][k] = 1 + f(((k - 1) / 2) - 1) + f((k - 1) / 2)
    return f(k)
# binary search on even values
def seek_even(x):
    left = 0
    right = f(x)
    if right % 2 != 0:
        right += 1
    middle = (right - left) / 2
    if middle % 2 != 0:
        middle += 1
    while f(middle) != x and left < middle < right:
        if f(middle) < x:
            left = middle
        else:
            right = middle
        middle = (left + right) / 2
        if middle % 2 != 0:
            middle += 1
    return middle
# binary search on odd values
def seek_odd(x):
    left = 1
    right = x
    if right % 2 == 0:
        right += 1
    middle = (right - left) / 2
    if middle % 2 == 0:
        middle += 1
    while f(middle) != x and left < middle < right:
        if f(middle) < x:
            left = middle
        else:
            right = middle
        middle = (left + right) / 2
        if middle % 2 == 0:
            middle += 1
    return middle

def seek(x):
    indices = [seek_even(x), seek_odd(x)]
    print "closest indices: " % indices
    return max(filter(lambda c: f(c) == x, indices) + [-1])
tests = [264227, 22, 10, 100000000000000000000, 31]
for i in tests:
    print "seek range [0, %d] for %d" % (f(i), i), seek(i)