シュターン-ブロコ木 (Stern-Brocot Tree)

概要

各頂点に有理数が紐づく、無限に続く二分木。

  • 各頂点には開区間が紐づく

  • 根頂点は 区間 \((0/1, 1/0)\) が紐づく

  • \((a/b, c/d)\) の左右の子頂点は \((a/b, (a+c)/(b+d))\) と \(((a+c)/(b+d), c/d)\) が紐づく

実装

\(a, b, c, d \le n\) を満たす中で \(\sqrt{p}\) に最も近い2つの分数 \(a/b < \sqrt{p}\) と \( \sqrt{p} < c/d\) を求める。

# a/b <= √p <= c/d を満たす a,b,c,d <= n を求める
def stern_brocot(p, n):
    la = 0; lb = 1
    ra = 1; rb = 0
    lu = ru = 1
    lx = 0; ly = 1
    rx = 1; ry = 0
    while lu or ru:
        ma = la + ra; mb = lb + rb
        if p * mb**2 < ma**2:
            ra = ma; rb = mb
            if ma <= n and mb <= n:
                rx = ma; ry = mb
            else:
                lu = 0
        else:
            la = ma; lb = mb
            if ma <= n and mb <= n:
                lx = ma; ly = mb
            else:
                ru = 0
    # lx/ly <= √p <= rx/ry
    return lx, ly, rx, ry

Verified

  • AOJ: "1208: Rational Irrationals": source (Python3, 0.07sec)

参考

戻る