contemporary algorhythm 02

closest pair problem

input n point on Euclid space ( 2dimension)
p1(x1, y1) p2(x2,y2),
座標に、任意の点が散らばっている状態。

output　どの点とどの点が一番、距離が小さいのか。

解法　片っ端から２点間の距離を計算する。

もっと速い計算法はないのか？

分割して、統治せよ

putting thing together 統治の本質
step0 preparation
sort n point along x axis
sort n point along y axis

procedure

点の集合を二つにわける
座標平面に、直線を１本ひく。
その直線の左右でわけてしまう。
その２つの点集合でclosest pairを算出。
手順　に分けていく。

dynamic programming

equal partition problem
input 整数の集合
output 2のグループに分ける

要素の和をとったときに、その和が等しくなるような二つのグループ
85 10 53 62 45 5
要素の数は問題にしない　　１つと５つとかでもいい。
野球の試合を１５人でやる
９人と６人とか。
８人と７人とか。
バランスのよい、人数割りを探す。