Stern-Brocot 木

プログラミング関係 AOJ

シュターン-ブロコ木とか，スターン-ブロコット木とか読むらしい．やっぱりアルファベットで書いてある方がかっこいい．

AOJ Problem 1208: Rational Irrationals で使ったのはいいものの，なんか忘れそうだったので，備忘録代わりに．
僕の勝手な解釈とかが混ざってるので，ちゃんとした文献を当たりましょう．．．

詳しくはSpaghetti Sourceに載っていますが．

次のように定義される2分木のこと．

  • 頂点は区間
  • 根は区間(0/1, 1/0) つまり(0, ∞)
  • 頂点(x/y, z/w)の子は，( x/y, (z+x)/(y+w) )，( (z+x)/(y+w), (z/w) )

特徴

  • 探索木になる．（綺麗に大きさ順で並ぶ）
  • 区間を表す分数はすべて既約有理数
  • すべての既約有理数が出てくる．
  • 深くなればなるほど，分子，分母の数が大きくなる．

なんかファレイ数列と似てるなぁ．．．と思ってたら，Wikipediaのファレイ数列の項目に"Stern-Brocot木と密接な関係にある"って書いてあった．

根の(0/1, 1/0)を(0/1, 1/1)に変えるとファレイ数列になるよね！

というわけで，AOJ1208 で使ったコード

#include<cstdio>
int x, y, u, v, n, p;
void sternBrocot(int pl=0, int ql=1, int pr=1, int qr=0){
	int pm = pl + pr, qm = ql + qr;
	if(pm > n || qm > n) return;
	if(pm * pm < p * qm * qm){
		u = pm; v = qm;
		sternBrocot(pm, qm, pr, qr);
	}
	else if(pm * pm > p * qm * qm){
		x = pm; y = qm;
		sternBrocot(pl, ql, pm, qm);
	}
	else{
		x = u = pm;
		y = v = qm;
	}
}
int main(){
	for(;;){
		scanf("%d%d", &p, &n);
		if(p == 0 && n == 0) return 0;
		sternBrocot();
		printf("%d/%d %d/%d\n", x, y, u, v);
	}
}

ググる前は，各分母について二分探索やって通した．
これなら，時間もかからないしソースも短い．