2015年5月15日金曜日

R-99 リスト 多分木 - Prolog-99 Ruby版 日本語訳

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 個のノードの深さ優先探索をし、木探索の間、前の高さに戻る時 特殊文字"^"を挿入する。この動きでバックトラックする。

このルールにより、図のツリーは次のように表される: afgcbde^

文字列の構文を定義して、文字列が与えられた時にツリーを作成するために関数 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 件のコメント:

コメントを投稿