Reccurence算法:在n次移动后找到位置

Question

介绍

我正在尝试编写在n中查找位置时引用的问题？.为此,我只使用了问题中公布的公式.我没有通过公式和答案他们对我来说有点太复杂了.我在python中编写了代码,它在这里表示.

算法描述(复制)

这种舞蹈要求每个表演者遵循一系列精确的步骤:

•阶段0:首先,通过在0位设置起点来远离障碍物

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

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

•要遵循,通过特定的计算,每次都可以获得下一步中必须采取的步骤和方向:您在前一阶段采取的步骤数减去您采取的步骤数倒数第二阶段.

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

在阶段3,舞者处于-4位置.

阶段(n)=阶段(n-1) - 阶段(n-2)

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

在第4阶段,舞者位于-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]

Answer 2

对于此类问题，您必须尝试在某些情况下寻找解决方案，可能您会找到像我发现的那样的模式，它可以帮助您在 O(1) 时间内解决此问题，并且仅包含 6 个元素的列表。

让我们迭代它几个初始阶段，

           Steps to take      New position
Stage 0        ---                0
Stage 1         1                 1
Stage 2        -2                -1
Stage 3        -3                -4
Stage 4        -1                -5
Stage 5         2                -3
Stage 6         3                 0
Stage 7         1                 1
Stage 8        -2                -1
Stage 9        -3                -4
Stage 10       -1                -5

所以你可以看到在Stage 6模式重复之后。所以下面的python代码将帮助你更快地解决这个问题。

def getpos(n):
    '''Returns the position of the performer after nth stage.'''
    ls = [0, 1, -1, -4, -5, -3]
    return ls[n % 6]

def getstep(n):
    '''Returns the step taken at nth stage'''
    ls = [3, 1, -2, -3, -1, 2]
    if n == 0:
        return None
    return ls[n % 6]

函数getpos()和getstep()是您在此问题中需要的实用函数。