Japanese 字幕

← 01-29 Recurrence Relation

埋め込みコードを取得する
2言語

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. ここで取り扱うのは漸化式
  2. すなわち再帰関数の一種です
  3. 再帰的なアルゴリズムであるrec_russianに
  4. 最適なテーマです
  5. rec_russianの構造を見ると
    aがゼロの場合実行されるのは1文だけです
  6. aはゼロだと判断して終わりです
  7. ではaがゼロより大きく偶数の場合
    rec_russianは何をするでしょう
  8. aにゼロより大きく偶数である数値を入力すると
  9. まずはaはゼロでないという判断をします
  10. 次にaは偶数であるという判断をし
    再帰的にa/2×bを求め
  11. 最後に2をかけます
  12. つまり2つのステップに加えa/2とbの積を
    求めるのにかかる時間が必要となりますが
  13. これにかかる時間は不明です
  14. 積を求めるのにかかる時間に
  15. T関数と名前をつけ
  16. T(a/2)としておきます
  17. 最後にaが奇数の場合まずはaがゼロでないと判断し
  18. 次にaは偶数でないと判断し
  19. それから(a-1)/2とbの積を再帰的に求め
    2をかけbを足します
  20. つまり3つのステップに加え(a-1)/2とbの積を
  21. 再帰的に求めるのにかかる時間が必要となります
  22. これらはT関数の数学的仕様で
  23. aとT(a)の関係性はまだ分かっていません
  24. しかし仕様は分かっています
  25. 実は答えは簡単に求めることができます
  26. 先ほど解説したaを2で割り
    商の端数を切り捨てる作業を
  27. 何度繰り返せば解がゼロになるかを
  28. 表す式を用いればよいのです
  29. これと仕様を合わせて考え
  30. 4つのうちいずれがT(a)に等しいかを答えてください