2

Java 2 のコースを受講して勉強しようとしていますが、この概念がわかりません。

  • 再帰的プログラミング呼び出しと動的プログラミング呼び出しの違いは何ですか?

  • それぞれの例は何でしょう？

4

4 に答える 4

3

2 つの概念はかなり異なります。

  • 関数は、それ自体を呼び出す場合、再帰的と呼ばれます。

  • 動的計画法は、問題を解決するための手法です。最初に小さな部分問題を解決し、次にその解決策を問題全体の解決策に拡張します。

動的計画法のアルゴリズムは再帰的に表現できることがよくあります。

于 2013-03-18T22:33:12.927 に答える
2

再帰的ソリューションはトップダウンの方法で問題を解決しますが、動的ソリューションはサブ問題に対する最適なソリューションが事前に計算されていることを利用して、ボトムアップの方法で問題を解決します。常に動的計画法を実行できるとは限りません。サブ問題の最適解がグローバル問題の最適解でもあることを確認する必要があります。

古典的な例は、n 番目のフィボナッチ数の計算です。

-再帰的

Fib(n)
  if (n <= 2) return 1
  return Fib(n-1) + Fib(n-2)

-動的

Fib(n)
 previous = 1
 next = 1
 temp = 0
 for i = 2 to n do
   temp = previous
   previous = next
   next = temp + next
 return next

これは疑似コードです。最初のものは呼び出しを繰り返し、2 番目のものは前のケースに基づいています

于 2013-03-18T23:00:46.317 に答える
1

再帰コードはそれ自体を呼び出すコードであり、動的コードはプログラムしてからそれ自体を呼び出すコードです。

コースを書いた人が何を言おうとしているのかを理解するために、ある程度のコンテキストが必要です。動的コードは再帰的である可能性があり、再帰的コードは動的である可能性があるため、質問の意図が混乱していると思います。

于 2013-03-18T22:45:18.143 に答える
1

「DevideandConquer」の概念アルゴリズムは、動的かつ再帰的であると見なされます。たとえば、リスト/配列での並べ替えでは、アイテムを2つの部分に分割し、各部分で並べ替え関数を再度呼び出します...など。

于 2013-03-18T22:39:48.050 に答える