0

我的任务是为以下公式编写 MIPS 指令代码： 

f(n) = 3 f(n-1) + 2 f(n-2)  
f(0) = 1
f(1) = 1

我在理解公式的实际含义时遇到问题。

据我了解，我们正在将一个 int n 传递给双递归程序。

因此，对于 f(0)，等式将是： 

f(n)=3*1(n-1) + 2*(n-2)

如果 n=10，则方程为： 

f(10)=3*1(10-1) + 2*(10-2)

我知道我根本没有做到这一点，因为它不会是递归的。您可以阐明方程式的实际含义的任何信息都会很棒。一旦我理解了方程式，我应该能够编写 MIPS 代码。

4

3 回答 3

3

我认为这是一个差分方程。

你有两个起始值：

f(0) = 1
f(1) = 1
f(n) = 3*f(n-1) + 2*f(n-2)

所以现在你可以继续这样：

f(2) = 3*f(1) + 2*f(0) = 3 + 2 = 5
f(3) = 3*f(2) + 2*f(1) = 15 + 2 = 17

所以你的递归方法看起来像这样（我将编写类似 Java 的符号）：

public int f(n) {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return 1; 
    } else { 
        return 3*f(n-1) + 2*f(n-2); // see? the recursion happens here.
    }
}
于 2012-06-05T01:22:14.860 回答
0

不，我认为你是对的，它是递归的。它似乎是斐波那契数列的变体，一个经典的递归问题

请记住，递归算法有两个部分：

  1. 基本情况
  2. 递归调用

基本情况指定了您不能再递归的点。例如，如果您正在递归排序，则基本情况是长度为 1 的列表（因为单个项目是简单排序的）。

所以（假设 n 不是负数），你有 2 个基本情况：n = 0 和 n = 1。如果你的函数接收到一个等于 0 或 1 的 n 值，那么递归就没有意义了

考虑到这一点，您的代码应如下所示：

function f(int n):
    #check for base case

    #if not the base case, perform recursion

所以让我们以斐波那契为例。

在斐波那契数列中，每个数字都是它之前的 2 个数字的总和。因此，给定序列1, 2，下一个数字显然是，1 + 2 = 3之后的数字是2 + 3 = 5，3 + 5 = 8依此类推。通俗地说，第 n 个斐波纳契数是第 (n - 1) 个斐波纳契数加上第 (n - 2) 个斐波纳契数，或f(n) = f(n - 1) + f(n - 2)

但是序列从哪里开始呢？这是基本情况。斐波那契将他的序列定义为从 开始1, 1。这意味着，对于我们的目的，f(0) = f(1) = 1. 所以...

function fibonacci(int n):
    if n == 0 or n == 1:
        #for any n less than 2
        return 1

    elif n >= 2:
        #for any n 2 or greater
        return fibonacci(n-1) + fibonacci(n-2)

    else:
        #this must n < 0
        #throw some error

请注意，斐波那契与递归一起被教授的原因之一是因为它表明有时递归是一个坏主意。我不会在这里讨论它，但是对于大 n 这种递归方法非常低效。另一种方法是有2个全局变量，n1这样n2......

n1 = 1
n2 = 1

print n1
print n2

loop:
    n = n1 + n2
    n2 = n1
    n1 = n

    print n

将打印序列。

于 2012-06-05T01:25:14.857 回答
0

您有两个基本情况：

f(0) = 1
f(1) = 1

其他任何东西都使用递归公式。例如，让我们计算 f(4)。这不是基本情况之一，因此我们必须使用完整的方程式。代入 n=4 我们得到：

f(4) = 3 f(4-1) + 2 f(4-2) = 3 f(3) + 2 f(2)

嗯，还没写完。要计算 f(4)，我们需要知道 f(3) 和 f(2) 是什么。这些都不是基本情况，所以我们必须做一些递归计算。好的...

f(3) = 3 f(3-1) + 2 f(3-2) = 3 f(2) + 2 f(1)
f(2) = 3 f(2-1) + 2 f(2- 2) = 3 f(1) + 2 f(0)

我们去吧！我们已经触底了。f(2) 是根据 f(1) 和 f(0) 定义的，我们知道这两个值是什么。我们得到了这些，所以我们不需要做更多的递归计算。

f(2) = 3 f(1) + 2 f(0) = 3×1 + 2×1 = 5

现在我们知道 f(2) 是什么，我们可以展开递归链并求解 f(3)。

f(3) = 3 f(2) + 2 f(1) = 3×5 + 2×1 = 17

最后，我们再次展开并求解 f(4)。

f(4) = 3 f(3) + 2 f(2) = 3×17 + 2×5 = 61

于 2012-06-05T01:28:05.043 回答