ガジェット通信 GetNews

見たことのないものを見に行こう

第134回「今週のアルゴリズム:幅優先の二分木を深さ優先探索」正解者発表

DATE:
  • ガジェット通信 GetNewsを≫

「今週のアルゴリズム」とは

「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。

第134回は「今週のアルゴリズム:幅優先の二分木を深さ優先探索」の問題です。

問題文「第134回 今週のお題:幅優先の二分木を深さ優先探索」

左図のように、ノードが左から順に埋まっている二分木を考えます。
この二分木に対し、根元の要素を「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

正解者

おめでとうございます!正解者のみなさんです。(新着順)

ksksk様
白珈琲様
KAZAMAI_NaruTo様
maron8676様
pWxEqwSV様
arborvitae666様
Schcat様
isseko様
ILT様
yml様
Theodore様
ebah3770様
mxhan様
カニ戯(ry様
soliton_at_evolve様
やきみかん。様
ガムテープの化身様
ecdsa2024_様
soukiti3様
kotakun様
gmk様
みやはる様
maronta様
np01767様
hebo様
takatoh様
haruya様
隈野リレケム様
とっしゅ様
uni様
0141frog様
南国の果実様
舞葉様
hakhak様
at_cacao_jp様
Naoki_M様
ganchan0523様
Mattsun様
igu様
takashi4様
tnkayu様
のみのみの様
tet_様
distancedsilhouette様
tqtqtq様
fhiyo様
m.h.様
Hiroyuki Kamisaka様
よかいち様
parroty様
乳酸菌飲料様
ふくま_め様
norman-k様
クワトロ様
nonon様
あっき様
yudedako様
Brln様
A_Ishikawa様
ida1ten0様
木くらげ様
painfulness様
i-don様
K9様
kurenaissance様
yuuki12321様
ginneko様
ksga様
opal様
A/M様
nobuo_create様
a992571様
strauss様
おじけん様
イネス様
ラスタ様
touran7様
rw0020様
suconv様
toku-mori様
angel様
hihi123様
nanosan様
tanishi14様
14番様
HHeLiBeX様
hyphen様
neko_the_shadow様
rotary-o様
skeleton.t様
みけCAT様
scherzo2様
見習いコーダー01様
TSUKA325様
el_beatle様
みかんず様
shoek様
todaemon様
ぶれぼ様
cia_rana様
HK17様
vdo様
えちごやえちぜん様
Yasu.Hara.様
ばいおねす様
おどりば様
filling様
まいぺじ様
facil89様
ゆん2様
tnakao様
Count0様
Keck様
dinghing様
kenj4様
myanta様
やまさん様
Leihcrev様
ryagi様
Fudao様
kobapie様
Hira0404様
drhy様
L.star様
cudjo様
chat様
ciel様
Azicore様
smz8110様
R修行中様 

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。