幅優先の二分木を深さ優先探索

幅優先の二分木を深さ優先探索

締め切りが 2017/03/21 10:00 AM なので，その 1 分後に投稿されるように予約

設問

下図のように、ノードが左から順に埋まっている二分木を考えます。
この二分木に対し、根元の要素を「1」とし、幅優先で順番に番号を付与していきます。
（ノードの数が10個の場合は左図のような番号が付与されます。）

ノードの番号と探索順



この二分木に対して、深さ優先探索を行います。
深さ優先探索では、左から順にもっとも深くなるまで進み、その後はバックトラックを行いながら順に探索します。
例えば、左図の場合は、右図のような順番に探索を行います。

m 個の要素が存在する二分木について、n 番目に探索したノードの番号を求めます。
例えば、m = 10, n = 6 のとき 5, m = 10, n = 8 のとき 3 となります。

標準入力から m, n がスペース区切りで与えられるとき、n番目に探索したノードの番号を標準出力に出力してください。
(m, n は m ≧ n を満たす整数とし、m は最大で3000とします)

【入出力サンプル】
標準入力
10 6

標準出力
5

=====================================================================

f = function(m, n) {
    tree = matrix(0, m, 3)
    for (i in seq_len(m)) {
        tree[i,] = c(i, ifelse(2*i <= m, 2*i, 0), ifelse(2*i+1 <= m, 2*i+1, 0))　# 値，左の子へのポインター，右の子へのポインター
    }
    node = count = 1
    repeat {
        if (count == n) { # 見つかった
            return(tree[node, 1]) # 値を返す
        }
        if (tree[node, 2] != 0) { # 左の子へ
            nxt = tree[node, 2]
            tree[node, 2] = 0 # 子へのポインターを潰しておく
            count = count+1
        } else if (tree[node, 3] != 0) { # 右の子へ
            nxt = tree[node, 3]
            tree[node, 3] = 0 # 子へのポインターを潰しておく
            count = count+1
        } else { # 終端ならば，子を持つ先祖までさかのぼる
            nxt = node
            repeat {
                nxt = nxt %/% 2
                if (tree[nxt, 2] != 0 || tree[nxt, 3] != 0) break
            }
        }
        node = nxt
    }
}
f(10, 6) # 5
f(100, 43) # 21
f(543, 345) # 410
f(1234, 987) # 896
f(3000, 2999) # 2046

複数の折れ線グラフを描くときの色指定法

中澤さんの書いた記事にある折れ線グラフが，ちょっと見づらいのでいくつか試してみた

中澤さんのプログラムは以下のとおり

# revised version of
# http://minato.sip21c.org/demography-special/asfrworld.R
# minatonakazawa@gmail.com, 20 March 2017
# requires wpp2015 package
library(wpp2015)
data(percentASFR)
worldfertil wfnow z matplot(z, type="l", lty=1, col=topo.colors(201),
 axes=FALSE, ylab="ASFR2010-2015", main="World Fertilities 2010-2015")
axis(1, 1:7, rownames(z))
axis(2, 0:5*10, 0:5*10)

添付図の左上がオリジナルで，col=topo.colors(201) によるもの。

その他の代替案として，いくつか

col=topo.colors(201, alpha=0.5)
col=topo.colors(201, alpha=0.2)
col=terrain.colors(201, alpha=0.2)
col=heat.colors(201, alpha=0.2)
col="#55000022"

alpha を採用することと，単純なモノクロを選択することが効果的と思われる。