幅優先の二分木を深さ優先探索
締め切りが 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 を採用することと,単純なモノクロを選択することが効果的と思われる。