python - 递归算法 : find position after n moves

Question

简介

我正在尝试对 Finding the position at n? 中引用的问题进行编码.为此，我只使用了问题中发布的公式。我没有仔细阅读公式和答案，它们对我来说有点太复杂了。我用 python 编写了代码，它在此处表示。

算法说明(已复制)

这种舞蹈要求每位表演者遵循精确的舞步顺序:

• 第 0 阶段:首先，将起点设置在位置 0 以避开障碍物

• 第 1 阶段:向前迈出一步(+1 步)

• 第 2 阶段:向后退两步(-2 步)

• 为了遵循，您每次必须采取的步数以及下一步行动的方向都将通过特定的计算得出:您在前一阶段采取的步数减去您的步数进入倒数第二阶段。

也就是说，在第 3 阶段，舞者必须向后退 3 步 (-2 - 1)。

在第 3 阶段，舞者在位置 -4。

stage(n) = stage(n-1) - stage(n-2)

pos(n) = pos(n-1) + stage(n)

At stage 4, the dancer is at position -5.

---

源代码

#!/usr/bin/python
if __name__=="__main__":
    s = [0, 1, -2]
    p = [0, 1, -1]
    for n in range(3, 5):
        diff = s[n - 1] - s[n - 2]
        s.append(diff)
        p.append(p[n - 1] + diff)
        print "Position at stage %s is %s" %(n, p[len(p) - 1])

---

问题

我的问题是假设我们有超过 1000 万个阶段。列表 p 和 s 会增长并可能导致内存问题。有没有办法解决这个问题。除了使用列表，我找不到其他解决方案。

如果我删除第一个元素 s.pop() p.pop() 它是一个索引超出范围异常。这是正常的。除此之外，我不知道该从哪里继续。

---

更新

比我想象的要简单。

#!/usr/bin/python
if __name__=="__main__":
    last_move = -2
    penultimate_move = 1
    previous_position = -1
    for n in range(3, 5):
        #compute current move and position
        current_move = last_move - penultimate_move
        current_position = previous_position + current_move
        
        #do switch in here
        penultimate_move = last_move
        last_move = current_move
        previous_position = current_position

        print "current position %s" %current_position

Answer 1

对此有一个简单的解决方案:在第 6、7 和 8 阶段，位置恰好分别为 0、1 和 -1，与初始位置相同。由于下一个阶段和位置仅取决于前一对阶段和前一个位置，因此可以保证重复相同的序列。

因此计算给定 n 位置的函数可以是:

def position(n):
    return [0, 1, -1, -4, -5, -3][n % 6]

以及计算阶段数n的函数:

def stage(n):
    return [3, 1, -2, -3, -1, 2][n % 6]