Returns 满足 R[n] = S 的最大 n

Question

Write a function answer(str_S) which, given the base-10 string representation of an integer S, returns the largest n such that R(n) = S. Return the answer as a string in base-10 representation. If there is no such n, return "None". S will be a positive integer no greater than 10^25.

where R(n) is the number of zombits at time n:

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)

Test cases
==========

Inputs:
    (string) str_S = "7"
Output:
    (string) "4"

Inputs:
    (string) str_S = "100"
Output:
    (string) "None"

我下面的程序是正确的，但它不可扩展，因为这里 S 的范围可以是非常大的数字，如 10^24。谁能帮我提出一些进一步改进代码的建议，以便它可以涵盖任何输入案例。

def answer(str_S):

    d = {0: 1, 1: 1, 2: 2}
    str_S = int(str_S)
    i = 1
    while True:

        if i > 1:
            d[i*2] = d[i] + d[i+1] + i
            if d[i*2] == str_S:
                return i*2
            elif d[i*2] > str_S:
                return None

        if i>=1:
            d[i*2+1] = d[i-1] + d[i] + 1
            if d[i*2+1] == str_S:
                return i*2 + 1
            elif d[i*2+1] > str_S:
                return None

        i += 1

print answer('7')

Answer 1

首先，您在缩放方面遇到了哪些问题？我运行把你的代码放在一个30位的数字上，好像还可以完成。你有内存限制吗？ Python 处理任意大的整数，尽管非常大的整数会转换为数字算术模式。

考虑到 R 值的密度，我怀疑如果切换到直接数组可以节省 space 和时间：使用值作为数组索引而不是字典键。

Returns 满足 R[n] = S 的最大 n

Returns the largest n such that R[n] = S

python

memory

out-of-memory

scalability

space-complexity