Javaに関する様々な情報をご紹介します。

Javaに関する様々な情報をご紹介します。
評価

0

木構造に関する練習問題(頭の体操)

自作問題です。
頭の体操として楽しん下さい。

二つの木構造がデータとして与えられるとき
(javaで処理しやすい形でデータが与えられると仮定して
よいです)
二つの木が根元が違うだけで同じ木かどうか判定する関数
を記述せよ。


点aの下に点b、点cがある木構造と同じものは
⇔を点と点が辺でつながっているとして


a⇔b
a⇔c


a⇔c
a⇔b


b⇔a
a⇔c


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
私がマナー違反や掲示板のルール違反の書き込みをしてい
るならご指摘ください。
すぐに謝罪してこのスレへの書き込みをやめます。

出題者 堀江伸一

1

回答

1438

閲覧

1件の回答

評価

0

少し問題がわかりにくかったと思いますので
与えられるデータ形式を考えてみました

最初に木の点の数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)の計算量の答えを用意しております。

質問から6ヶ月以上経過しているので、回答を書き込むことはできません。