R-99: 99 の Ruby の問題 - 5. 多分木
- 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。
多分木問題
多文木は、ルート要素、後に続くノード(nil があり得る)、多文木そのもので構成される。 多文木が空になることはありません。後に続く木の集まりは、「森」と呼ばれています。
Ruby では、X はルートノードを表し、F は後に続く木の森である関数t(X,F)
によって 多分木を表します。 以下に描かれている例のツリーは、以下の関数で表されます。
T = t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])
5.01 (*) 指定された項目が多分木を表しているか確認せよ
その引数が多文木を表す場合のみ成功する関数 istree(a)
を書け。
例)
istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])) => true
5.02 (*) 多分木のノードを数えよ
与えられた多分木のノードを数える関数 nnodes(T)
を書け。
例)
nnodes(t(a,[t(f,[])])) => 2
ノードの数からツリーを作るバージョンの関数を書け。
5.03 (**) ノードの文字列からツリーを作成
多分木のノードに単一の文字を持つとする。n 個のノードの深さ優先探索をし、木探索の間、前の高さに戻る時 特殊文字"^"
を挿入する。この動きでバックトラックする。
文字列の構文を定義して、文字列が与えられた時にツリーを作成するために関数 tree(string,tree)
を書け。文字列の代わりに1文字単位で動作します。 文字列からツリー、ツリーから文字列の両方向に動作するよう 関数を作成せよ。
5.04 (*) ツリーの内部パス長を決定
内部パスの長さは、多分木のルートからの全てのノードへのパスの長さの合計であると定義する。 この定義により、問題 5.03 の図中のツリーの内部パスの長さは 9 である。
行きがけ順と帰りがけ順のパターンのための関数ipl(tree,ipl)
を書け。
5.05 (*) ツリーノードのボトムアップ順配列を作れ
多分木のノードのボトムアップ順配列を作る関数 bottom_up(tree,seq)
を書け。
関数を逆順(訳注:トップダウン)にした場合、何が起こるか。
5.06 (**) Lisp のようなツリー表現
以下に Lisp の多分木の特定の表記がある。Lisp は人工知能の問題に主に使用されている著名な 関数型プログラミング言語である。Lisp では、ほとんどすべてのものをリストで表す。
以下の画像は多分木構造が Lisp で表される方法を示している。
リストの最初の要素は常にツリー内の後に続く(子)ノード達を「lisp風」に表記することに注意せよ。 多分木の「lisp風」表記法は、最小単位の配列であり、ここでは「トークン」と呼ぶものとし、 カッコ「(」と「)」で表す。
Ruby の配列としてトークンの配列を表すことができる。 例えば、lisp風表記法で「(a (b c))」を Ruby の配列では['(',a,'(','b','c',')',')']
と表す。 もしツリー T が Ruby の一般的な表記法で与えられた時、「lisp風トークン配列」(LTL)を 作成する関数 tree_ltl(T) を書け。
tree_ltl(a,[t(b,[]),t(c,[])])) => ['(','a','(','b','c',')',')']
次に、さらに興味深い演習として、逆変換も可能であるように tree_ltl(T) を書き直せ。 リスト LTL を与えると、Ruby でのツリー表現を作成せよ。違うツリーを用いよ。
0 件のコメント:
コメントを投稿