2

私はデータ構造クラスの再帰学習の最初の段階にあり、私たちの教授は、再帰的な方法を取り、再帰方程式とともに問題のサイズを考え出すことができるはずだと言いました。問題のサイズが次のような 1 つの変数 N に依存する場合、次のような再帰方程式を書くことができます。

public static int simpleCounter(int N) {
    if (n == 0) {
        return;
    }
    else {
        return 1 + simpleCounter(N - 1);
    }
 }

ただし、2 つの変数に依存するなど、問題のサイズがより複雑な場合、変数をどう処理するかわからないため、再帰方程式を作成できません。このメソッドは、2 つの数値を互いに減算できる回数をカウントします。カウントは最初の呼び出しで常にゼロであり、a と b は両方とも正であると仮定します。

public static int complexCount(int a, int b, int count) {
    if ((a - b) <= 0) { 
        return 0; 
    }
    else {
      count = 1 + complexCount((a - b), b, count + 1)
      return count;
     }
 }

では、ここでの問題のサイズはどれくらいですか? aとbの両方に関係する必要はありませんか？そして、問題のサイズを知らなければ、再帰方程式を思いつくことができません: ベース: T(0) = 1 再帰: T(N) = 1 + ??

4

1 に答える 1

0

再帰関係は常に単一の変数を含む必要はありません。実際、複数の変数にある再帰関係を持つことは一般的です。ここで、再帰関係は次のようになります。

T(a, b) = 1 + T(a - b, b) (a ≥ bの場合)

T(a, b) = 1 (そうでない場合)

次に、この再帰関係を a と b の両方で解いて、最​​終的な解を導き出すことができます。

お役に立てれば！

于 2013-11-05T00:56:55.020 に答える