Japanese 字幕

← 01-28 Divide And Conquer

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

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

  1. ロシア農民のアルゴリズムが
    なぜ足し算の繰り返しであるnaiveよりも
  2. よいアルゴリズムなのか設計の観点から考察します
  3. 整数のかけ算を見てみましょう
  4. a×bは足し算の繰り返しです
    aが偶数の場合に注目します
  5. a×bはbをa回足すという足し算の式に書き換えられます
  6. aは偶数なのでbを2グループに分けることができます
  7. bをa/2回足したものと同じくbをa/2回足したものを
  8. 足すという式に書き換えられます
    前半と後半は同じ計算なので
  9. 1度だけに省略することができます
  10. bをa/2回足したものを2倍すればよいのです
  11. bをa/2回足すだけで
    同じ計算を2度したことになります
  12. 分割して足し算をすることで
  13. 多大な時間を節約できます
  14. 分割統治法を用い問題を副問題に分割し
  15. その結果を合わせることで元の問題を解決できます
  16. この例では2つの副問題は同じ内容なので
  17. 1度解くだけで済み労力を半分に節約できます
  18. 分割する度に労力は半分になるため
  19. 短時間での問題解決が可能となります
  20. この分割統治の考え方を用いて
    ロシア農民のアルゴリズムを
  21. 再帰的に表してみました
  22. ここで求めようとしているのはaとbの積です
  23. もしaをゼロにして実行すればゼロを返して終了します
  24. aが偶数の場合は先ほど説明したように
  25. a×bはbをa/2回足して求めることができるので
  26. russian(a/2,b)を再帰的に計算します
  27. するとアルゴリズムrussianが作動し
    a/2とbの積が計算されます
  28. 計算結果が出たら
  29. それに2をかけると元の問題の答えが出ます
  30. このように副問題の解を用いて
    元の問題を解決できます
  31. aが奇数の場合は少し複雑です
  32. aが奇数なのでa回足すbのうちの1つを取り出します
  33. すると残るのはa-1個のbです
  34. a-1は偶数なのでa-1を半分に割り
    (a-1)/2×bを再帰的に計算すればよいのです
  35. rec_russian((a-1)/2,b)の解が出たらこれに2をかけます
  36. するとa-1とbの積が出てこれはab-bと同じなので
  37. bを足せば元の問題の答えが出ます
  38. このように副問題の解を用いて
    元の問題を解くことができます
  39. 少し回りくどいようにも見えますが副問題として
  40. ロシア農民のアルゴリズムが
    呼び出される際のaの値は半分なので
  41. 多くの労力を節約することができます
    ではこのアルゴリズムを解析します
  42. 答えはロシア農民のアルゴリズムと同じですが
  43. アルゴリズム解析における有用なツールを
  44. 見いだすことができるはずです