質問: 自作問題です。 頭の体操として楽しん下さい。 二つの木構造がデータとして与えられるとき (javaで処理しやすい形でデータが与えられると仮定して よいです) 二つの木が根元が違うだけで同じ木かどうか判定する関数 を記述せよ。 例 点aの下に点b、点cがある木構造と同じものは ⇔を点と点が辺でつながっているとして 1 a⇔b a⇔c 2 a⇔c a⇔b 3 b⇔a a⇔c 4 c⇔a a⇔b の4つあります。 1,2は順序木ではない場合。 3、4は1と木の根本が違うだけです。 これで同じ木はすべて尽くされます。 上記のような判定の元、与えられる2つの木が同一である かどうか判断する関数を記述せよ。 中級問題 2つ以上の点に同じアトムが割り当てられる場合も考慮せ よ。 追記 PrologやLisp的に例を書けば aの下にb、cがある木は [a,[b],[c]] [a,[c],[b]] [b,[a,[c]] [c,[a,[b]] の4つが同じ木だと判定されaの下にb、cがある場合はそ れですべて尽くされます。 追記2 私がマナー違反や掲示板のルール違反の書き込みをしてい るならご指摘ください。 すぐに謝罪してこのスレへの書き込みをやめます。 出題者 堀江伸一
回答: 少し問題がわかりにくかったと思いますので 与えられるデータ形式を考えてみました 最初に木の点の数n n行にわたり点0〜点n-1に割り当てれるアトム n-1行にわたり点通しの結合です。 これが2セット与えられるので同じ木か判定せよ。 木が [a,[b],[c]]と [b,[a,[c]]なら 3 a b c 0 1 0 2 3 a c b 2 0 0 1 で2つは同じ木と判定します。 中級は 1 [a,[b,[c],[d]],[e,[a],[c]]] みたいな感じでaが重複したりします。 bを根元に取った 2 [b,[c],[d],[a,[e,[a],[c]]]] 1と2は同じ木だと判定します. [b,[d],[c],[a,[e,[a],[c]]]] [b,[d],[c],[a,[e,[c],[a]]]] [b,[a,[e,[c],[a]]],[d],[c]] ,,, なども2と順序が違うだけで同じ木です。 枝の順序を入れ替える。 根元を変更する。 この操作を繰り返して同じになる木を同じと判定してくだ さい。 一応n^2*log(n)の計算量の答えを用意しております。