6

最近、再帰について勉強しています。再帰と再帰は同じものだとしばらく考えていましたが、最近の宿題や小テストの問題で、「再帰」が方法であるというわずかな違いがあると思いました。再帰的なプログラムまたは関数を記述します。

問題やプログラムの「再帰」を記述するために使用される「マスター定理」と呼ばれるものがあることに最近気付くまで、これはすべて私にとって非常にギリシャ語でした。ウィキペディアのページを読んでいるのですが、いつものように、何を言っているのかよくわからないような言葉遣いで書かれています。私は例を使ってはるかによく学びます。

いくつかの質問があります: この繰り返しが与えられたとしましょう:

r(n) = 2*r(n-2) + r(n-1);
r(1) = r(2) = 1

これは実際、マスター定理の形をとっているのでしょうか? もしそうなら、それは言葉で何を言っているのですか？この再帰に基づいて小さなプログラムまたは再帰ツリーを作成しようとすると、どのようになりますか? 数値を代入してパターンを確認し、そのパターンを再帰的に作成できる疑似コードを作成するだけでよいでしょうか、それともマスター定理の形式である可能性があるため、より簡単な数学的アプローチはありますか?

ここで、前回の再帰から作成されたプログラムによって実行された追加の回数の再帰 T(n) を求めるよう求められたとします。基本ケースはおそらく T(1) = T(2) = 0 になることがわかりますが、そこからどこへ行くべきかわかりません。

基本的に、私は特定の繰り返しからコードに移行する方法とその逆を求めています。これはマスター定理のように見えるので、簡単で数学的な方法があるかどうか疑問に思っています。

編集：さて、過去の課題のいくつかを調べて、「再発を見つける」ように求められた別の例を見つけました。これは、投稿の問題を抱えているこの質問の一部です。

次のプログラム フラグメントの加算演算の数を最適な方法で記述する再帰 (l == 1 および r == n で呼び出した場合)

int example(A, int l, int r) {
  if (l == r)
    return 2;
  return (A[l] + example(A, l+1, r);
}
4

5 に答える 5

8

数年前、Mohamad Akra と Louay Bazzi は、Master メソッドを一般化する結果を証明しました。ほとんどの場合、Master メソッドの方が優れています。もうマスター定理を使うべきではありません...

たとえば、次の記事を参照してください: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

基本的には、論文の方程式 1 のように再帰を取得し、係数を取り出して、式を定理 1 に統合します。

于 2008-10-20T17:43:43.590 に答える
2

ザカリー:

この繰り返しが与えられたとしましょう：

r(n) = 2*r(n-2) + r(n-1); r(1) = r(2) = 1

これは実際、マスター定理の形をとっているのでしょうか? もしそうなら、それは言葉で何を言っているのですか？

あなたの再帰関係が言っていることは、「n」をパラメーターとして（入力しているデータセットの総数を表す）「r」の関数の場合、データセットのn番目の位置で得られるものは何でもあると思いますn-1 番目の位置の出力に n-2 番目の位置の結果の 2 倍を加えたもので、非再帰的な作業は行われません。再帰関係を解決しようとするとき、再帰を伴わない方法でそれを表現しようとしています。

しかし、それがMaster Theorem Methodの正しい形だとは思いません。あなたの声明は、「定数係数を持つ二次線形回帰関係」です。どうやら、私の古い Discrete Math の教科書によると、それが再帰関係を解くために必要な形式です。

彼らが与えるフォームは次のとおりです。

r(n) = a*r(n-1) + b*r(n-2) + f(n)

「a」と「b」は定数であり、f(n) は n の関数です。あなたのステートメントでは、a = 1、b = 2、および f(n) = 0 です。f(n) がゼロに等しいときはいつでも、再帰関係は「同種」として知られています。だから、あなたの表現は均質です。

f(n) = 0 であるため、マスター メソッド定理を使用して同次再帰関係を解決できるとは思いません。ゼロにはなりません。私はこの分野の専門家ではないので、間違っているかもしれませんが、Master Method を使用して同種再帰関係を解決できるとは思いません。

同種の再帰関係を解決する方法は、次の 5 つの手順を踏むことだと思います。

1) 次の形式の特性方程式を作成します。

x^k - c[1]*x^k-1 - c[2]*x^k-2 - ... - c[k-1]*x - c[k] = 0

同次再帰関係に再帰インスタンスが 2 つしかない場合は、方程式を次の二次方程式に変更するだけで済みます。

x^2 - a*x - b = 0

という形の再帰関係があるからです。

r(n) = a*r(n-1) + b*r(n-2)

のように書き直せる.

r(n) - a*r(n-1) - b*r(n-2) = 0

2) 再帰関係を特性方程式に書き直したら、次に特性方程式の根 (x[1] と x[2]) を求めます。

3) あなたのルーツにより、解決策は次の 2 つの形式のいずれかになります。

if x[1]!=x[2]
    c[1]*x[1]^n + c[2]*x[2]^n
else
    c[1]*x[1]^n + n*c[2]*x[2]^n

n>2 の場合。4) 再帰解の新しい形式では、初期条件(r(1) と r(2)) を使用して c[1] と c[2] を見つけます。

あなたの例を使用すると、次のようになります。

1) r(n) = 1*r(n-1) + 2*r(n-2) => x^2 - x - 2 = 0

2) x を解く

x = (-1 +- sqrt(-1^2 - 4(1)(-2)))/2(1)

    x[1] = ((-1 + 3)/2) = 1
    x[2] = ((-1 - 3)/2) = -2

3) x[1] != x[2] であるため、ソリューションは次の形式になります。

c[1](x[1])^n + c[2](x[2])^n

4) ここで、初期条件を使用して 2 つの定数 c[1] と c[2] を見つけます。

c[1](1)^1 + c[2](-2)^1 = 1
c[1](1)^2 + c[2](-2)^2 = 1

正直なところ、この状況であなたの定数が何であるかわかりません。私はこの時点でやめました。c[1] と c[2] の両方の値がこれら 2 つの式を満たす値になるまで、数値をプラグインする必要があると思います。それか、C が等しい行列 C で行削減を実行します。

[ 1 1   | 1 ]
[ 1 2   | 1 ]

ザカリー:

次のプログラム フラグメントの加算演算の数を最適な方法で記述する再帰 (l == 1 および r == n で呼び出した場合)

int example(A, int l, int r) {
  if (l == r)
    return 2;
  return (A[l] + example(A, l+1, r);
}

r>l の場合の指定されたコードの時間計算量の値は次のとおりです。

int example(A, int l, int r) {      =>  T(r) = 0
  if (l == r)               =>  T(r) = 1
    return 2;               =>  T(r) = 1
  return (A[l] + example(A, l+1, r);    =>  T(r) = 1 + T(r-(l+1))
}

Total:                      T(r) = 3 + T(r-(l+1))

それ以外の場合、r==l の場合、T(r) = 2 です。これは、if ステートメントと return の両方が実行ごとに 1 ステップを必要とするためです。

于 2010-08-13T05:44:19.743 に答える
1

再帰関数を使用してコードで記述されたメソッドは、次のようになります。

function r(int n) 
{
  if (n == 2) return 1;
  if (n == 1) return 1;
  return 2 * r(n-2) + r(n-1);  // I guess we're assuming n > 2
}

「再帰」とは何かはわかりませんが、再帰関数は単にそれ自体を呼び出す関数です。

再帰関数には、スタックオーバーフローエラー（つまり、関数が呼び出されすぎてインタプリタのメモリが不足するなど）を防ぐために、エスケープ句が必要です（たとえば、「if n == 1 return 1」）。資力）

于 2008-10-20T17:31:41.617 に答える
1

これを実装する単純なプログラムは次のようになります。

public int r(int input) {
    if (input == 1 || input == 2) {
        return 1;
    } else {
        return 2 * r(input - 2) + r(input -1)
    }
}

また、たとえば、最初の入力が1未満の場合、入力によって無限再帰が発生しないことを確認する必要があります。これが有効なケースでない場合は、エラーが返されます（有効な場合）。 、次に適切な値を返します。

于 2008-10-20T17:34:20.690 に答える
1

「『再発』が何なのか正確にはわかりません」

「再帰関係」の定義は、「定義域が整数の無限集合であり、範囲が実数の集合である」数列です。このシーケンスを記述する関数が「シーケンスの 1 つのメンバーを前のものに関して定義する」という追加の条件付き。

そして、それらを解決する目的は、再帰的な定義からそうでない定義に移行することだと思います。すべての n>0 に対して T(0) = 2 および T(n) = 2 + T(n-1) がある場合、式 "T(n) = 2 + T(n -1)" を "2n+2" のようなものにします。

出典: 1) Edgar G. Goodair および Michael M. Parmenter による「Discrete Mathematics with Graph Theory - Second Edition」 2) Ellis Horowitz、Sartaj Sahni、および Sanguthevar Rajasekaran による「Computer Algorithms C++」。

于 2010-08-11T23:22:28.460 に答える