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

差分方程式だと思います。

2つの開始値が与えられます。

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

いいえ、あなたは正しいと思います。再帰的です。これは、古典的な再帰問題であるフィボナッチ数列のバリエーションのようです。

再帰的アルゴリズムには2つの部分があることを忘れないでください。

  1. ベースケース
  2. 再帰呼び出し

基本ケースは、これ以上再帰できないポイントを指定します。たとえば、再帰的に並べ替える場合、基本ケースは長さ1のリストです（単一のアイテムが簡単に並べ替えられるため）。

したがって（nが負ではないと仮定すると）、n=0とn=1の2つの基本ケースがあります。関数が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

フィボナッチが再帰とともに教えられる理由の1つは、再帰が悪い考えである場合があることを示しているためです。ここでは説明しませんが、大規模な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

2 つの基本ケースがあります。

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

それ以外は再帰式を使用します。たとえば、f(4) を計算してみましょう。これは基本ケースの 1 つではないため、完全な方程式を使用する必要があります。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) で定義されており、これら 2 つの値が何であるかはわかっています。それらが与えられたので、これ以上再帰的な計算を行う必要はありません。

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 に答える