Spaghetti Source logo

Stern-Brocot 木

説明

有理数 p = x/y と q = z/w に対し,二項演算 p@q を p@q = (x+z)/(y+w) で定義する.Stern-Brocot 木は,次で定義される無限に伸びる二分木である.

この木の主な特徴は次のものである.

木の具体形は http://mathworld.wolfram.com/Stern-BrocotTree.htmlなどを参照.

プログラミングの視点では,この木は「有理数を効率的に探索する」ために用いることができる.たとえば実数 x が与えられたとき,x-ε < q < x+ε を満たす有理数 q の中で分子と分母の和が最小のものを求める問題を考えると,Stern-Brocot 木から区間 (x-ε,x+ε) を分断する区間を求めるだけで求まることがわかる.

ソースコード

// Stern-Brocot Tree for enumerating rationals
//   Enumerating all irreducible rationals ascending order,
//   whose sum of N and D is atmost B
void sternBrocot(Int B, Int pl = 0, Int ql = 1,
                        Int pr = 1, Int qr = 0) {
  Int pm = pl + pr, qm = ql + qr;
  if (pm + qm > B) return;
  sternBrocot(B, pl, ql, pm, qm); // [pl/ql, pm/qm]
  cout << pm << "/" << qm << endl;
  sternBrocot(B, pm, qm, pr, qr); // [pm/qm, pr/qr]
}

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.11.14 20:50:30.