0

我很高兴在这里问我的第一个问题。我遇到了一些递归问题。我正在用 Python 编码。

我正在使用字典将先前求解的数字存储在数学序列中。然后我在解决后面的序列时检查这本字典，以使程序运行得更快。每个键代表已解决的“起始数字”，值表示序列采用特定公式将起始数字降低到 1 所需的时间。

我正在使用递归解决问题，这本身很容易，但对我来说还有更多。

每个递归步骤都让我有机会更新库中的不同密钥，但我无法找到执行此操作的方法。

所以如果一个序列看起来像 13 -> x -> y -> z ... -> 1，你会怎么做不仅用值更新 13 键，还更新字典中的 x、y、x 值在同一递归路径中？现在我只能为每个序列更新一个数字。

cache = {1:1}

def solve(number):

    if cache.has_key(number):
        return cache[number]
    else:           
      if condition one.. 
            return 1 + solve(number * formula 1)
      else condition two...
            return 1 + solve(number * formula 2)

for x in xrange(1,1000):

cache[x] = solve(x)   <-- right now only cache[x] is being updated.

谢谢！

4

3 回答 3

1

你不能在每次递归调用返回它之前把它放在缓存中吗？

代替：

return 1 + solve(number * formula 1)

你会这样做：

result = 1 + solve(number * formula 1)
cache[number] = result
return result

或者你追求不同的东西？

于 2013-07-03T06:57:04.627 回答
0

原则上，dictionary.update() 方法能够一次更新字典的多个值。但我认为你的问题在于你只在调用者中更新缓存[x]，即在递归之外。

于 2013-07-03T06:57:58.157 回答
0

您可以更新solve的另一个参数以包含序列中的所有数字，例如

def solve(number, valueList):
...
...
if condition one:
        valueList.append(number)
        return 1 + solve(number * formula 1, valueList)

等等。我假设您所说的“序列中的数字”是指在被接受之前满足条件 1 或 2 的数字。

如果您对 Mattias 的回答没有任何疑问，那么他的回答会更直截了当。我假设无论出于何种原因，您都不想在递归完成之前添加到缓存中。

无论如何，当递归完成时，您可以遍历 valueList 并将其添加到缓存中。

于 2013-07-03T07:06:53.890 回答