Python递归限制解决方法

Question

我目前正在研究一个python问题：

给定一个从-无穷大到+无穷大的数行。从0开始，可以向左或向右。条件是，在我的行动中，你采取我的步骤。第一步走1步，第二步走2步，依此类推。 提示：可以通过两个步骤（0，1）（1，3）达到3。可通过3个步骤（0，1）（1，-1）（-1，2）达到2

a）找到到达位置1000000000和-1000000000的最佳步数。你知道吗

我成功地编写了以下代码：

def steps(source, step, dest):
    if abs(source) > dest:
        return sys.maxint
    if source == dest:
        return step

    pos = steps(source+step+1, step+1, dest)
    neg = steps(source-step-1, step+1, dest)

    return min(pos, neg)

问题是，即使这个函数给了我正确的答案，它也不能扩展到我要求的范围。有没有解决这个问题的办法，或者我需要换一种方法来解决这个问题？你知道吗

Answer 1

为了避免递归，您可以将状态保存在列表中，我会更好地解释。你知道吗

def steps(source, step, dest):
    q = Queue()
    q.put((0,1))
    while True:
        source, ste = q.get()
        if abs(source) > dest:
            return sys.maxint
        if source == dest:
            return step

        q.put(source+step+1, step+1)
        q.put(source-step-1, step+1)

这样做可以在队列中保存要检查的位置，并且每次检查不是最后一个位置的位置时，都会在队列末尾添加新的2位置。这种方法也保证了所求的解是最短的。 为了进一步提高速度，你可以保存一个已经访问过的数字列表，这样每次你再次找到相同的数字时，就会停止研究，这会大大加快任务的速度

Answer 2

我认为这实际上可以用笔、纸和计算器来解决。我不想破坏整个拼图（听起来像家庭作业），但我会给你一些提示。你知道吗

假设我们只是朝着1000000000的方向走，也就是说，我们每次都向右边走。你知道吗

• 你能想出一个封闭的公式来告诉你在n步之后你在哪里吗？

• 从那开始，你能计算出要走多少步直到你“超过”1000000000吗？这显然是所需步数的下限，因为步数越少，我们就越走越远。

• 在你超量的那一刻，你到底在哪里结束？

• 最后，您能否修改您的路径，使您以相同的步数精确地到达目标？