1

在 Python 中：

def g(n):  
    if n <=3:        
        return n   
    return g(n-1) + 2 * g(n-2) + 3 * g(n-3)

我理解这个函数在做什么，但我似乎不知道如何让它迭代。请帮忙。如果可能，请附上解释，以便我能完全理解问题所在。

4

4 回答 4

8

这看起来类似于斐波那契数列问题，并且以迭代方式实现并非易事。它看起来也像家庭作业，所以我将发布获得斐波那契迭代的步骤，您应该能够将其应用于您的问题。

如果你不知道，斐波那契是这样定义的：

def fib(n):
    if n <= 1:  # technically, this is not 100% correct, but it's fine for n>=0
        return n
    return fib(n-1) + fib(n-2)

那么我们来分析一下fib(n)。首先我们看到有两种不同的情况：n <= 1和not n <= 1。For n <= 1,fib(n)没有依赖关系，所以我们可以评估：

def fib_iter(n):
    if n <= 1:
        return n

现在我们需要介绍另一种情况。我们先来做一个依赖分析。我们需要fib(n)什么n > 1？我们调用fib(n-1)和fib(n-2)。在迭代语言中，这将是之前的两个值。很明显，我们需要跟踪这些。我们将从关于那个的两个琐碎案例开始：

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1

我希望这是相当明显的。然后我们按照它们在递归方法中解析的顺序解析这些函数。在展开递归并分析函数时，我们发现要评估的第一个非平凡值当然是fib(2)。然后fib(3)以此类推，直到我们到达n。由于递归方法，多个值被多次评估，但我们不需要在迭代方法中。这些值被加在一起，这为我们提供了以下代码：

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for i in xrange(2, n+1):
        curr = prev1 + prev2        # calculate fib(i)
        prev1, prev2 = prev2, curr  # shift previous value cache

唯一缺少的是返回值，它正好curr在循环结束的时候。正如我们提前xrange(2, n+1)检查的n <= 1那样，循环将至少运行一次，因此curr将在循环之外定义。

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for i in xrange(2, n+1):
        curr = prev1 + prev2
        prev1, prev2 = prev2, curr
    return curr

（这是我的第一个家庭作业答案；如果我太宠坏了，SO 社区可能会给我反馈我本可以做得更好的地方）

于 2012-06-29T16:58:43.197 回答
4 
def g(n):
    if n <= 3:
        return n
    a, b, c = 1, 2, 3
    for i in range(3, n):
        a, b, c = b, c, (a * 3 + b * 2 + c)
    return c
于 2012-06-29T18:00:43.253 回答
3

您的递归函数可以读作

To find the value of g(30), find the value of g(29), g(28), and g(27)
  To find the value of g(29), find the value of g(28), g(27), and g(26)
    To find the value of g(28), find the value of g(27), g(26), and g(25)
      ...
        (repeat until all sub-finds have completed)

迭代函数将从另一端开始，

I know the values of g(1), g(2), and g(3) -> calculate g(4)
I know the values of g(2), g(3), and g(4) -> calculate g(5)
I know the values of g(3), g(4), and g(5) -> calculate g(6)
...
(repeat until the desired g(n) is reached)
于 2012-06-29T18:25:41.507 回答
1

这太有趣了，无法解决......

def g(n, *, _cache=[0, 1, 2, 3]):
    for _ in range(n - len(_cache) + 1):
        _cache.append(sum(i * _cache[-i] for i in (1, 2, 3)))
    return _cache[n]

希望您已经找到了解决方案。

于 2012-06-29T17:33:13.530 回答