Stern-Brocot木 3

先日のシュテルンブロコットツリーのプログラムのフローチャート。

若いころはフローチャートの必要性が良くわからなかったが、年のせいか、フローチャートが無いとスクリプトを書いている途中で何を書くべきだったかわからなくなってしまう。
数週間後にはスクリプト中のそれぞれの文の役割もあやふやになってきてしまうので、とても重要です。

Stern-Brocot木 2

昨日のStern-Brocot木のプログラムのアルゴリズムの理解のための例題

Stern-Brocot木

Stern-Brocot木で任意の値に近い分数を探すスクリプトをPythonで書いた。比較しつつ降りて行ってその時の分数と入力値との差を表示。
例えば 0.283/1 を 入れると、15/53 とかが近いなというのがわかる。
連分数展開を解くのでも良いと思うが、簡単。

以下Pythonスクリプト（2.7を使用）

#coding: Shift_JIS
#numerator/denominator
cnum = 1
cdenom = 1

def SternBrocot(lnum, ldenom, cnum, cdenom, rnum, rdenom, inputnum):
    ntemp = float(cnum) / float(cdenom) #Cを計算
    if ntemp < inputnum: #入力の方がCよりも大きい
        # C → L
        lnum = cnum
        ldenom = cdenom
        # 分子分母それぞれにつき C + R → C
        cnum = cnum + rnum
        cdenom = cdenom + rdenom
    else: #入力の方がCよりも小さい
        # C → RL
        rnum = cnum
        rdenom = cdenom
        # 分子分母それぞれにつき C + L → C
        cnum = cnum + lnum
        cdenom = cdenom + ldenom
#
    #print "lnum =", lnum, "ldenom =", ldenom, "cnum =", cnum, "cdenom =", cdenom, "rnum =", rnum, "rdenom =", rdenom, "inputnm =", inputnum
    #print "L =", lnum, "/", ldenom, ", C =", cnum, "/", cdenom, ", R =", rnum, "/", rdenom
    ntemp = float(cnum) / float(cdenom) #新しいCの計算
    diff = (inputnum - ntemp)*10**6
    print "C =", cnum, "/", cdenom, "=", ntemp, ", ", diff, " ppm"
#
    if inputnum == ntemp:
        print "終了"
    else:
        SternBrocot(lnum, ldenom, cnum, cdenom, rnum, rdenom, inputnum)

# Main
x = float(input("Please Enter Numerator: "))
y = float(input("Please Enter Denominator: "))
inputnum = x / y
#まずCenter(1/1)と等しくないことを確認しておく
if inputnum == 1:
    print "oshimai" #入力が1だったら終了
else:
    SternBrocot(0, 1, 1, 1, 1, 0, inputnum)