読者です 読者をやめる 読者になる 読者になる

contemporary algorhythm 02

closest pair problem

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

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

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

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

分割して、統治せよ

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

procedure

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

dynamic programming

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

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