Stern–Brocot 木 (有理数木)

Stern–Brocot 木

Stern–Brocot 木 は、既約分数をノードに持つ二分木で、下の図のようなものです。(wikipedia より)

木の根から一段ずつ見ていくと、隣り合う2つの分数 $p = \frac{a}{b}$ と$q = \frac{c}{d}$ の間に、新しい分数 $ r = \frac{a+c}{b+d}$ が追加されています。

Stern–Brocot 木には、次のような特徴があります。

• ノードはすべて既約分数であり、かつ、任意の正の既約分数はこの木に含まれる。
• 左($\frac{0}{1}$)から右($\frac{1}{0}$)に向けて値が大きくなる順番に並ぶ。
• ある段階で $p=\frac{a}{b}, q=\frac{c}{d}$ $(p<q)$ が隣り合う分数なら、$bc-ad = 1$ が成り立つ。

ある既約分数まで木をたどる

たとえば、 $\frac{291}{133}$ に到達するためには、ルート($\frac{1}{1}$) からどのように木をたどればいいでしょうか。それには、ユークリッドの互除法を利用します。

$291 = 2\times 133 + 25$
$133 = 5\times 25 + 8 $
$25 = 3\times 8 + 1 $
$8 = 8\times 1$

ここで、各行の商 $ 2,5,3,8 $ に注目します。

最初、$\frac{0}{1}$と $\frac{1}{0}$ の間にルート $\frac{1}{1}$ があります。

二分木の右を2回選ぶと、
$\frac{1}{1}\to\frac{2}{1}\to\frac{3}{1}$
と移動します。

この時点で、$\frac{2}{1}$ と $\frac{1}{0}$ の間の $\frac{3}{1}$ にいます。ここから左を5回選びます。
$\frac{3}{1}\to\frac{5}{2}\to\frac{7}{3}\to\frac{9}{4}\to\frac{11}{5}\to\frac{13}{6}$

$\frac{2}{1}$ と $\frac{11}{5}$ の間の $\frac{13}{6}$ まで来ました。さらに右を3回選びます。
$\frac{13}{6}\to\frac{24}{11}\to\frac{35}{16}\to\frac{46}{21}$

$\frac{35}{16}$ と $\frac{11}{5}$ の間の $\frac{46}{21}$ まで来ました。最後に、左を8-1=7回選びます。
$\frac{46}{21}\to\frac{81}{37}\to\frac{116}{53}\to\frac{151}{69}\to\frac{186}{85}\to\frac{221}{101}\to\frac{256}{117}\to\frac{291}{133}$

これで目的地に到着しました。
このように、ユークリッドの互除法の途中に出てくる商の回数 (ただし、最後のみ商-1 回) だけ左右に移動を繰り返すことで目的の分数まで移動することができます。

コード例

以下のコードは、
Stern–Brocot 木のルートから目的の分数まで、右(R, 大きい方)か左(L, 小さい方)のどちらをたどるか
目的の分数までいくつの辺を通るか
R,L が切り替わるときの分数 ( 目的の分数に近づいていく分数の列 )
を表示します。

python

def Stern_Brocot_Tree ( bunsi, bunbo ):

        L_bunsi = 0     #  0/1
        L_bunbo = 1

        R_bunsi = 1     #  1/0
        R_bunbo = 0

        C_bunsi = 1     #  1/1
        C_bunbo = 1

        direction = 'R'

        count = 0

        node = []
        node.append( [C_bunsi,C_bunbo] )

        s = "";

        while True:
                amari = bunsi % bunbo
                sho = (bunsi - amari) // bunbo
                if amari == 0:
                        sho -= 1

                count += sho

                bunsi = bunbo
                bunbo = amari

                s += sho * direction

                if direction == 'R':
                        C_bunsi += sho * R_bunsi
                        C_bunbo += sho * R_bunbo
                        L_bunsi = C_bunsi - R_bunsi
                        L_bunbo = C_bunbo - R_bunbo

                        direction = 'L'

                elif direction == 'L':
                        C_bunsi += sho * L_bunsi
                        C_bunbo += sho * L_bunbo
                        R_bunsi = C_bunsi - L_bunsi
                        R_bunbo = C_bunbo - L_bunbo

                        direction = 'R'

                if sho>0:
                        node.append( [C_bunsi, C_bunbo] )

                if amari == 0:
                        break

        print(s)
        print(count)
        for nod in node:
                print(str(nod[0])+'/'+str(nod[1]))


Stern_Brocot_Tree ( 291, 133 )

C

#include <stdio.h>

void Stern_Brocot_Tree ( int bunsi, int bunbo ) {

        int L_bunsi = 0;        /*  0/1  */
        int L_bunbo = 1;

        int R_bunsi = 1;        /*  1/0  */
        int R_bunbo = 0;

        int C_bunsi = 1;        /*  1/1  */
        int C_bunbo = 1;

        char direction = 'R';

        int count = 0;

        int i;
        int n = 0;
        int node[100][2];

        node[n][0] = C_bunsi;
        node[n][1] = C_bunbo;
        n++;

        for (;;) {
                int amari = bunsi % bunbo;
                int sho = (bunsi - amari) / bunbo;
                if (amari == 0) sho--;

                count += sho;

                bunsi = bunbo;
                bunbo = amari;

                for (i=0;i<sho;i++) { printf("%c", direction); }

                if (direction == 'R') {
                        C_bunsi += sho * R_bunsi;
                        C_bunbo += sho * R_bunbo;
                        L_bunsi = C_bunsi - R_bunsi;
                        L_bunbo = C_bunbo - R_bunbo;

                        direction = 'L';

                } else if (direction == 'L') {
                        C_bunsi += sho * L_bunsi;
                        C_bunbo += sho * L_bunbo;
                        R_bunsi = C_bunsi - L_bunsi;
                        R_bunbo = C_bunbo - L_bunbo;

                        direction = 'R';

                }

                if (sho>0) { node[n][0] = C_bunsi; node[n][1] = C_bunbo; n++; }

                if (amari == 0) break;
        }
        printf("\n");

        printf("%d\n",count);

        for (i = 0; i < n; i++) {
                printf("%d/%d\n",node[i][0], node[i][1]);
        }
}


int main() {
        Stern_Brocot_Tree ( 291, 133 );
        return (0);
}