分割統治法(divide and conquer)
大きな問題を小さな問題に分割して、それぞれを別々に解く
またその小さな問題も同様に、もっと小さな問題分割して解く
基底状態に達したら容易に解ける
分割統治法のアルゴリズムは再帰(recursion)を使って実現されることが多い
分割統治法(divide and conquer)の例
二分探索(binary search)
ハノイの塔(Towers of Hanoi)
マージソート(merge sort)
分割(partition)
クイックソート(quick sort)
ハノイの塔(Towers of Hanoi)
塔を別の柱に移す
動かす円盤は一度に1枚だけ
円盤はより小さな円盤の上には置くことができない
New
サイズを指定し、新しい塔を作る
Step
シングルステップ実行する
Run
自動実行を開始する
分割(partition)
データをある値より大きなアイテムと小さなアイテムの2つのグループに分ける
クイックソート(quick sort)で使われている
New
新しい配列を作る
Size
サイズを変更する
Draw
図形を描きなおす
Run
自動実行を開始する
Step
シングルステップ実行する