私は、本屋や図書館で背表紙からインスパイアされるのが好きなので、
Webで同じことができないか考えていました。
しかし残念ながら、現在背表紙の画像をまとめて処理できる有力な
データベースが存在しないため、とりあえずキーワードと関連ワードで
検索される本のタイトルと著者のリストを表示するサイトを作ってみました。
本当は背表紙の画像でやりたかったのですが、とりあえず日本語の時だけ
縦書きにしてみました。(対応ブラウザ：MS Edge、Firefox41以上、Chrome45.0.2454.101以上)
英語モードの時は横書きです。
お試し運用なので heroku を使っていますが、近々本稼働予定。
使ってみていただけると幸いです。
2015/10/08 追記
スマホ対応しました。
前記事（ Mac 10.10.2 で gutenprint が使えた！ ）で、
「Macでドライバがないプリンタを使えるようにできるよ！」と言ったんですが、
OSのバージョンアップした途端に印刷できなくなりました…
よくよく調べてみると、前記事で紹介した「gutenprint」で
印刷できる方法がわかりました！
公式フォーラムで回答していた方すごいです！
なんでこんな方法がわかるのでしょうか？
それではやり方です。
以上でMac非対応のプリンタが使えるようになることがあります。
この方法見つけた人、本当に感心感謝しますね〜。
一応元記事へのリンクも貼っておきます。
http://sourceforge.net/p/gimp-print/discussion/4359/thread/4fcff20f/
これは、コンピュータサイエンスの古典的な問題である。目的は、全てのクイーンが互いを攻撃されないように、 チェス盤に 8 個のクイーンを配置することである。すなわち、どのクイーンも、同じ行、同じ列、または 同じ対角線上にない状態である。
ヒント: 番号 1 から N の配列としてクイーンの位置を表す。例:[4,2,7,3,6,8,5,1] 最初の列のクイーンは4行目にあることを、次の列には2行目、というように解釈する。 生成-試験パラダイム(generate-and-test paradigm)を利用せよ。
訳注: 「生成-試験パラダイム」とは、結果を自動的に可視化する戦略である。ここでは、 クイーンの配置列を求めた時、その結果を画面に描画し、正しいかどうかをチェックすることができるように することを指す。
もう一つの有名は問題は、どのようにすれば N×N マスのチェス盤の全てのマスに1度ずつナイトを 移動させることができるか? というものである。
ヒント: 正方形の座標を X/Y と表す時、X,Y の両方は 1〜N の間の整数である。('/'は単に便利な 演算子ではなく、区切りであることに注意せよ!) ナイトは、N×N個のチェス盤上に X/Y から U/V へジャンプすることができるという事実を表現するために 関数jump(x,y,u,v)を定義する。 最後に、N×Nのナイトの位置を配列として問題の解とする。(ナイトの旅:knight's tour)
数年前、解決策を知らないためにある問題に興味をそそられた数学者がいた。名前はファン-コッホ。 この問題は解決されているかどうかわからない。
小さなツリーであれば、この問題を手で解くことは簡単である。しかし、大きなツリーや14は 非常に大きく、解を導くことは非常に困難である。しかも、常に解があるかどうかは分からないことを 忘れないように。
与えられたツリーの採番方法を計算する関数を書け。上記のツリーの解は何か?
整数のリストを与えると、正しい方程式の結果のような演算記号(演算子)を挿入する方法を発見せよ。 例) 数の配列 [2,3,5,7,11] は方程式で 2 - 3 + 5 + 7 = 11 または 2 = (3 * 5 + 7) / 11 と書ける(他にも10以上書き方がある)。
財務書類上、小切手のように、数字は時々単語の組み合わせとして書く必要がある。 例) 175 は、"one-seven-five"と書く必要がある。 単語の組み合わせで(負ではない)整数を表示する関数full_words(a)を書け。
特定のプログラミング言語(Ada)で識別子は、構文図(鉄道チャート)の反対として定義される。 ループの含まれない構文図のシステムに構文図を変換せよ。すなわち、これは純粋に再帰である。 これらの変更された図を用いて、与えられた文字列が有効な識別子であるか否かを確認することができる 関数identifierを書け。
identifier => str # str は正しい識別子数独パズルは次のように解く:
問題文 解答
. . 4 | 8 . . | . 1 7 9 3 4 | 8 2 5 | 6 1 7
| | | |
6 7 . | 9 . . | . . . 6 7 2 | 9 1 4 | 8 5 3
| | | |
5 . 8 | . 3 . | . . 4 5 1 8 | 6 3 7 | 9 2 4
--------+---------+-------- --------+---------+--------
3 . . | 7 4 . | 1 . . 3 2 5 | 7 4 8 | 1 6 9
| | | |
. 6 9 | . . . | 7 8 . 4 6 9 | 1 5 3 | 7 8 2
| | | |
. . 1 | . 6 9 | . . 5 7 8 1 | 2 6 9 | 4 3 5
--------+---------+-------- --------+---------+--------
1 . . | . 8 . | 3 . 6 1 9 7 | 5 8 2 | 3 4 6
| | | |
. . . | . . 6 | . 9 1 8 5 3 | 4 7 6 | 2 9 1
| | | |
2 4 . | . . 1 | 5 . . 2 4 6 | 3 9 1 | 5 7 8パズル内のすべて場所は(水平)行と(垂直)列に属し、1つの3x3の正方形(略してプレースと呼ぶ)も 同様である。はじめに、場所のいくつかには、1から9の1桁の数字が知らされる。 問は、1から9までのすべての数を、各行、各列、各プレースに一度だけ現れるように数字の 入っていない場所に埋めることである。
訳注: 「ノノグラム」とは、日本では「イラストロジック(お絵描きロジック)」などと呼ばれている。
1994年頃、あるパズルがイギリスで非常に人気があった。「ノノグラムは、日本から来たパズルであり、 現在はサンデーテレグラフで毎週公開されています。単純にマスを埋め、絵や図を明らかにするために 論理と技術を使います。」と「サンデーテレグラフ」 紙に掲載された。Ruby プログラマとして、 よい場面である。使っているコンピュータに仕事をさせることができる!
パズルは以下の通り。本質的に、長方形の方眼の各行と列に、占有する一続きのマスの数が列挙されている。 パズルを解くにはこれらの長さが指定されたマスを埋める必要がある。
問題 解答
|_|_|_|_|_|_|_|_| 3 |_|X|X|X|_|_|_|_| 3
|_|_|_|_|_|_|_|_| 2 1 |X|X|_|X|_|_|_|_| 2 1
|_|_|_|_|_|_|_|_| 3 2 |_|X|X|X|_|_|X|X| 3 2
|_|_|_|_|_|_|_|_| 2 2 |_|_|X|X|_|_|X|X| 2 2
|_|_|_|_|_|_|_|_| 6 |_|_|X|X|X|X|X|X| 6
|_|_|_|_|_|_|_|_| 1 5 |X|_|X|X|X|X|X|_| 1 5
|_|_|_|_|_|_|_|_| 6 |X|X|X|X|X|X|_|_| 6
|_|_|_|_|_|_|_|_| 1 |_|_|_|_|X|_|_|_| 1
|_|_|_|_|_|_|_|_| 2 |_|_|_|X|X|_|_|_| 2
1 3 1 7 5 3 4 3 1 3 1 7 5 3 4 3
2 1 5 1 2 1 5 1 上記の例の場合、問題は2つの配列 [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] と [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] として行と列、上から下と左から右のそれぞれの 塊の長さとして与えることができる。 公開されたパズルは、この例よりも大きい。例えば25x20で、毎回異なる解を持つ。
クロスワートパズルの空(またはほとんど空)の枠と単語集が与えらえる。問は、枠に単語を 配置することである。
特定のクロスワードパズルは、最初に任意の順番で単語(1行に一つの単語)をリストにした テキストファイルに指定されている。そして、空行の後、クロスワードの枠組みが定義されている。 この枠の仕様では、空の文字位置をドット(.)で表現する。 解を簡単にするために、文字位置にはあらかじめ定義された文字の値を含むことができる。
単語は少なくとも2文字の文字列である。クロスワードパズルの枠組みの中で文字の入る場所の縦、 横の並びをサイトと呼ぶ。問は、サイト上の単語を矛盾なく配置する方法を見つけることである。
訳注: データファイルの内容例
PERL
PROLOG
ONLINE
GNU
LINUX
WEB
NFS
XML
SQL
MAC
EMACS
...... .
. . . .
. ..... .
. . . ...
. ... .
...ヒント:
グラフ理論では、用語の意味がかなり変わる。一部の著者は、異なる意味で同じ単語を使用している。 一部の著者は、同じことを意味する別の単語を使用している。ここで使う用語の定義では、 矛盾がないことを願っている。
グラフは、エッジのセットとノードのセットの集合として定義される。
一つの方法は、一節として別個にエッジを表す方法である。 この形態では、上記のグラフは以下のように表すことができる。
a = new Edge(h,g),
b = new Edge(k,f),
c = new Edge(f,b),
...ここでは、この形態をエッジ節フォームと呼ぶ。
明らかに、孤立したノードを表現することができない。別の方法は、1つのデータオブジェクトとして グラフ全体を表すことである。 二組(ノードとエッジ)のグラフの組の定義に従うと、上記の例のグラフを 表すために、次の関数を使用することがある。
graph([b,c,d,f,g,h,k],[e(b,c),e(b,f),e(e,f),e(f,k),e(g,h)])ここではこれをグラフ要素フォームと呼ぶ。リストがソートされていることに注意せよ。 それらは既に設定されているものと重複する要素はない。各エッジは、エッジのリストに一度だけ表される。 たとえば、エッジ表現のノード X からノード Y は e(x,y)と表され、要素e(y,x)は存在しない。 グラフ要素フォームは、ここでの標準的な表現とする。
第3の表現方法は、各ノードにそのノードに隣接するノードの集合を関連付けることである。 ここでは、これを隣接リストフォームと呼ぶ。この例では：
[n(b,[c,f]), n(c,[b,f]), n(d,[]), n(f,[b,c,k]), ...]これまでに導入された表現は、構文がユーザフレンドリではない。 要素を手入力すると、面倒でエラーを起こしやすい。次のように、よりコンパクトで「ヒューマンフレンドリ」な 表記法を定義する。 グラフはタイプ X-Y の最小単位と要素数で表される(例えば、関数記号 '-' と引数の数 2)。 最小単位は孤立ノードを表し、X-Y の要素はエッジを表す。 X は、エッジの終端として表されている場合、自動的にノードとして定義されている。 今回の例は以下のように記述できる。
[b-c, f-c, g-h, d, f-b, k-f, h-g]ここでは、ヒューマンフレンドリフォームと呼ぶ。例が示す通り、リストをソートする必要はなく、さらに 同一エッジを複数回含むことができる。孤立ノード d に注目せよ。 (実際には、孤立ノードも例の d の代わりに、d(3.75,"blue")のように、要素を混ぜ合わせることができ、 Ruby の最小単位である必要はない。
エッジに向きがある時、孤(アーク)と呼ぶ。これらは、順序のペアで表される。 このようなグラフは、有向グラフ(略してダイグラフ)と呼ぶ。
有向グラフを表すには、上のフォームをわずかに変更する。例えば、次のようにグラフが表される。
エッジ節フォーム
arc(s,u),
arc(u,r),
...グラフ要素フォーム
digraph([r,s,t,u,v],[a(s,r),a(s,u),a(u,r),a(u,s),a(v,u)])間接リストフォーム
[n(r,[]),n(s,[r,u]),n(t,[]),n(u,[r]),n(v,[u])]隣接リストは、それがグラフや有効グラフであるかどうかについての情報を持っていないことに注意せよ。
ヒューマンフレンドリフォーム
[s > r, t, u > r, s > u, u > s, v > u] 最後に、グラフと有向グラフは、ノードとエッジ(アーク)に取り付けられた追加情報を有していてもよい。
アーク節フォーム
arc(m,q,7)
arc(p,q,9)
arc(p,m,5)グラフ要素フォーム
digraph([k,m,p,q],[a(m,p,7),a(p,m,5),a(p,q,9)])間接リストフォーム
[n(k,[]),n(m,[q/7]),n(p,[m/5,q/9]),n(q,[])]エッジ情報が対応するノードで、関数記号 '/' で引数が 2 の要素にパックされたことに注目せよ。
ヒューマンフレンドリフォーム
[p>q/9, m>q/7, k, p>m/5]ラベルづけされたグラフの表記法では、複数のエッジ(アーク)は2つの指定されたノード間で許可されている いわゆるマルチグラフに使用することができる。
別のグラフ表現の間で変換する関数を書け。これらの関数では、全ての表現は同等である。 すなわち、以下の問題のために、あなたは常に最も便利な表記法を選ぶことができる。 この問題が(***)に評価された理由は、この問題が特に難しいからではなく、この問題の解が特別な場合に 対処するために役立つためである。
グラフ G にノード A からノード B への非循環パス P を見つけるための関数 path(G,A,B) を書け。関数は、バックトラックして全てのパスを経由する必要がある。
グラフ G の指定されたノード A から始まる閉じたパス(循環) P を発見する関数 cycle(G,A) を書け。関数は、バックトラックを介して全ての循環を返す必要がある。
訳注: 「スパニングツリー」とは、ループするグラフ内で、1度とったパスを2度と通らないような パスをツリー状に表したもの。
(バックトラックによって)与えられたグラフの全てのスパニングツリーを作成するための関数 s_tree(graph,tree)を書け。この関数を使用すると、上のグラフにある複数のスパニングツリーを 調べる。 関数s_tree(graph,tree)のための正しい解を持つ時、他の2つの有用な関数を定義して使う: is_tree(graph)とis_connected(graph)。両方とも作成するのに5分程度の作業であろう。
与えられたラベル付きグラフの最小スパニングツリーを作成するための関数ms_tree(graph,tree) を書け。
ヒント: 「プリムのアルゴリズム」を使用せよ。問題 6.04 の解を小さく変更するのがコツである。
全単射 f が存在する時、2つのグラフ G1(n1,e1) 及び G2(n2,e2) が同型である。 f とは、n1 から任意のノード X,Y の間で x と y が隣接する時のみ、f(x) と f(y) が隣接する。
二つのグラフが同型であるかどうかを判断する関数を書け。 ヒント: 関数 f を書くために、オープンエンドリスト(訳注:終端の決まっていない構造のリスト) を使用する。
訳注: 「次数」とは、繋がっているノードの数のこと。
degree(graph,node)を書け。深さ優先グラフ探索の探索順を作成する関数をかけ。出発点を与える必要があり、出力は(深さ優先順で) この出発点から到達可能なノードのリストである必要がある。
その連結した構成要素にグラフを分割する関数をかけ。
与えられたグラフは2部グラフであるかどうかを調べる関数を書け。
訳注: 「2部グラフ」とは、グラフのノードを2つのグループ A,B に分け、各エッジがグループ A の ノードからグループ B のノードに繋がっている(すなわち、同じグループ同士のノードが繋がっていない)時、 このグラフを「2部グラフ」と呼ぶ。
K 正則グラフでは、全てのノードは K の次数を持っている。すなわち、各ノードに繋がるエッジの数は K である。ノードが 6 個ある 3-正則グラフはいくつか。(非同型のもの!)
多文木は、ルート要素、後に続くノード(nil があり得る)、多文木そのもので構成される。 多文木が空になることはありません。後に続く木の集まりは、「森」と呼ばれています。
Ruby では、X はルートノードを表し、F は後に続く木の森である関数t(X,F)によって 多分木を表します。 以下に描かれている例のツリーは、以下の関数で表されます。
T = t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])その引数が多文木を表す場合のみ成功する関数 istree(a) を書け。
例)
istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])) => true与えられた多分木のノードを数える関数 nnodes(T) を書け。
例)
nnodes(t(a,[t(f,[])])) => 2ノードの数からツリーを作るバージョンの関数を書け。
多分木のノードに単一の文字を持つとする。n 個のノードの深さ優先探索をし、木探索の間、前の高さに戻る時 特殊文字"^"を挿入する。この動きでバックトラックする。
文字列の構文を定義して、文字列が与えられた時にツリーを作成するために関数 tree(string,tree) を書け。文字列の代わりに1文字単位で動作します。 文字列からツリー、ツリーから文字列の両方向に動作するよう 関数を作成せよ。
内部パスの長さは、多分木のルートからの全てのノードへのパスの長さの合計であると定義する。 この定義により、問題 5.03 の図中のツリーの内部パスの長さは 9 である。
行きがけ順と帰りがけ順のパターンのための関数ipl(tree,ipl)を書け。
多分木のノードのボトムアップ順配列を作る関数 bottom_up(tree,seq) を書け。
関数を逆順(訳注:トップダウン)にした場合、何が起こるか。
以下に 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 でのツリー表現を作成せよ。違うツリーを用いよ。
バイナリツリーは、空か、ルート要素と二つのノードで構成されているバイナリツリー自体のいずれかである。
ここで用いる関数 t(X,L,R) では、X はルートノードを表し、L、R はそれぞれ左と右のサブツリー(訳注:部分木)を表す。 最小構成をnilと空ではないツリー、関数 t で表すツリーとする。
したがって、図4-1 のツリーは以下のように表すことができる。
T1 = t(a,t(b,t(d,nil,nil),t(e,nil,nil)),t(c,nil,t(f,t(g,nil,nil),nil)))他の例は、ルートノードのみで構成されたバイナリツリーである。
T2 = t(a,nil,nil) # ルートノードのみのバイナリツリー
T3 = nil # 空のバイナリツリー関数 istree(a) は、その引数はバイナリツリーを表すノードがある場合のみ成功するように書け。
例)
istree(t(a,t(b,nil,nil),nil)) => true
istree(t(a,t(b,nil,nil))) => false完全にバランスの取れたバイナリツリー(訳注:以降「Bツリー」と呼ぶ)では、次の特性がノードごとに保持されている。 それは左サブツリーのノード数とその右サブツリーのノード数がほぼ等しく、それらの差が1以下であることを意味する。
ノードの数を指定された、Bツリーを作成するために関数 cbal_tree(a,b) を書く。 関数は、バックトラックを介してすべての解を生成する必要がある。 ツリーのすべてのノードに情報として文字 x を置く。
例)
x = "X"
T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil)))
T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil))
cbal_tree(4,T)ルートノードを介して垂直線を描くことができるとき、右サブツリーが左サブツリーの鏡像である場合、 対称バイナリツリーと呼ぶことにする。 指定されたバイナリツリーが対称であるかどうかを確認する関数 symmetric(a) を書く。
参考: 一本のツリーが別の鏡像であるかどうかをチェックする関数 mirror(a,b) を書く。 ここでは、ツリーの構造にだけチェックできればよく、ノードの値は無視して良い。
例)
construct([3,2,5,7,1],T).
T = t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))そして、この問題の解答をテストするには、この関数を使用している。
例)
test_symmetric([5,3,18,1,4,12,21]) => true
test_symmetric([3,2,5,7,4]) => false指定された数のノードを使用して、Bツリーを 作成するために生成と検査の方法を適用する。
(訳注: 生成と検査の方法(generate-and-test paradigm)とは、 複数の解を生成し、与えられた評価基準を満たさないものを排除することとによる問題解決方法のこと。)
例)
sym_cbal_trees(5)
=> [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]57のノードがあるツリーがいくつあるか？ 指定された数のノードのためにいくつ解があるかについて調査せよ。 数が偶数である場合はどうすれば？ 適切な関数を書け。
高さバランスバイナリツリーにおいて、ノードごとに次の特徴がある。 その左のサブツリーの高さとその右のサブツリーの高さは、その差が1より大きくないことを意味し、ほぼ等しい。
所定の高さのために高さバランスバイナリツリーを作成するための関数 hbal_tree(a,b) を書く。 その関数は、バックトラックを介してすべての解を生成する必要がある。 ツリーのすべてのノードに情報としての文字'X'をセットする。
例)
hbal_tree(3) =>
t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil)))
t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil))
false高さ H の高さバランスバイナリツリーを考える。それに含めることができるノードの最大数はいくつか？ MaxN = 2**H -1であることが明らかな時、最も小さなMaxNはいくつか？ この問題は、より困難である。再帰的な式を発見するために、 関数minNodes(a)として定義することに挑戦せよ。
minNodes(H) => N # 高さ H の高さバランスバイナリツリーの最小数 N が返るもう一つの問う。N個のノードを持つ高さバランスバイナリツリーが 持つことのできる最大の高さ H はいくつか？
maxHeight(N) => N # 高さ H は N 個のノードを持つ高さバランスバイナリツリーの最大の高さ今、ノードの数を与えられたすべての高さバランスバイナリツリーを作成する問題に着手することができます。
hbal_tree_nodes(N) => T # T は N個のノードを持つ高さバランスバイナリツリーです。N = 15であるいくつかの高さバランスツリーが存在する方法を確認せよ。
「葉」とは、後が続かないノードのことである。それらをカウントする関数 count_leaves(a) を書け。
count_leaves(T) => N # バイナリツリー T には N 個の葉がある。「葉」とは、後が続かないノードのことである。それらを配列にする関数 leaves(T) を書け。
leaves(T) => S # S はバイナリツリー T の全ての葉の配列である。バイナリツリーに含まれるノードには、1つ、2つまたはノードを含まない場合のいずれかである。 配列にそれらを集めるために、関数 internals(T) を書きます。
internals(T) => S # S はバイナリツリー T に含まれるノードの配列です。バイナリツリーのノードでは、ルートノードからある高さにあるノード N へのパス(訳注:経路)は、長さ N - 1を持つ。 ルートノードは、高さ 1 にある。 配列内の指定された高さで、全てのノードを集める関数 atlevel(T,L) を書け。
atlevel(T,L) => S # S は高さ L にあるバイナリツリーのノードのリストである。atlevel(T,L) を使用して、関数 levelorder を作成し、そのノードの高さの帰りがけ順の並びを 作成することは簡単である。 しかし、それを行うためのより効率的な方法がある。
次のように高さ H の完全バイナリツリーが定義されている。
高さ 1,2,3,...,H - 1は、ノードの最大数を含む。 つまり、2**(i - 1) が高さ i の時、ルートにの高さは 1 とカウントすることに注意せよ。
ノードの最大数よりも少なく、含まれても良い n 個の高さ H は、全てのノードが「左調整」 されています。 これは、全ての含まれるノードが最初に来る高さ順ツリー探索では、ノードが最初で、 2番目に葉、後に何もないもの(nil は実際にはノードではない!)がくる。
特に、完全バイナリツリーは、ヒープのためのデータ構造(またはアドレス指定方式)として使用されている。
数 1 でルートから始まる、高さの帰りがけ順のツリーに含まれるノードを列挙することによって、 完全バイナリツリー内の各ノードへのアドレス番号を割り当てることができる。 そうすることで、アドレス A を持つ全てのノード X は、次の特徴を保持していることを実現する。
X の左右に続くノードのアドレスは、2 * Aと2 * A + 1のそれぞれのノードが存在すると想定する。 この事実は優雅な完全バイナリツリー構造を構築することができる。 次に関数 complete_binary_tree(N) の仕様を書く。
complete_binary_tree(N) => T # T は N 個のノードを持つ完全バイナリツリーである。適切な方法でその関数をテストせよ。
Ruby のクラスとしてTree::initialize(X,L,R)というバイナリツリーが与えられる。 ツリーを描画するための準備として、レイアウトアルゴリズムは、矩形グリッド内の各ノードの位置を決定する ために必要とされる。いくつかのレイアウト方法の内の一つは、以下の図のように示すことができると考えられる。
このレイアウト方法において、ノード V の位置は、次の2つのルールによって得ることができる。
x(v)はノード v の位置に等しい正常なノードy(v)はツリーの帰りがけ順内のノード v の深さに等しいノードの位置を記憶するために、ノード(およびその次)を次のように表すように Ruby の用語を拡張します。
nilが(いつものように)空のツリーを表すt(W,X,Y,L,R)は(X,Y)に位置するルート W、およびサブツリー L と R の空でない バイナリツリーを表す。次の仕様で関数 layout_binary_tree(T) を書けlayout_binary_tree(T) => PT # PT はバイナリツリーから得られた「位置付け」バイナリツリーです。適切な方法で作成した関数をテストせよ。
代替のレイアウト方法は、上の図に示されている。規則を見つけ、対応する Ruby の関数を記述せよ。
ヒント: 指定された高さでは、隣接ノードとの水平距離は一定である。
問題 4.13 と同様の規則を使用して、適切な方法でその関数をテストせよ。
されに別のレイアウト方法は、上の図に示されている。 この方法は、全てのノードで特定の対称性を維持しながら非常にコンパクトなレイアウトが得られる。 規則を見つけ、対応する Ruby 関数を書け。
ヒント: ノードとその後ろのノード間の水平距離を考慮せよ。
もれなく組み合わされたバイナリツリーを作成するためにどのように2つのサブツリーをひとまとめにするか？
問題 4.13 と 4.14 と同様の規則を使用して、適切な方法でその関数をテストせよ。
注: これは難しい問題だ。簡単に諦めてはいけない!
もっとも好みのレイアウトはどれか？
a(b(d,e),c(f(g,)))t(X,L,R)の用語として)いつものように与えられている場合、 この文字列表現を生成する Ruby 関数を書け。そして、この逆を行う関数を書け。 すなわち、通常の形でツリーを作成し、文字列表現を与える。最後に、両方の方向で使用することができる 単一の関数 tree_string(a,b) の二つの引数を組み合わせる。簡単にするために、ノード内の情報は単一の文字であるとし、文字列にはスペースは含まない。
問題 4.16 の例のように、単一の小文字で識別されるノードとバイナリツリーについて検討する。
preorder(a,b) と inorder(a,b) を書け。。 結果は最小構成であるべきだ。例えば問題 4.16 の例の行きがけ順のための'abdecfg'。preorder(a,b)を逆方向に利用できるようにせよ。 すなわち行きがけ順が与えられると、対応するツリーを構築する。ない場合は、必要な手配をせよ。pre_in_tree(a,b,c)を書け。同じ文字が複数のノードに表示された場合はどうなるか。`pre_in_tree("aba","baa")'を試せ。
問題 4.16 の例のように、単一の小文字で識別されたノードと、再びバイナリツリーを検討する。 このようなツリーは、空のサブツリー(nil)は、ツリー探索中に遭遇されるドット(".")が挿入された そのノードの行きがけ順によって表すことができます。 例えば、問題 4.16 に示すツリーは次のように表現される: "abd..e..c.fg..." まず、構文(BNFや構文ダイアグラム)を確立しようとした時、両方向の変換を行い、関数 tree_dotstring(a,b)のように書く。差分配列を使用せよ。
それぞれの関数が true または false を返すように定義せよ。 and(a,b), or(a,b), nor(a,b), xor(a,b), iml(a,b), equ(a,b)
例) A == true、B == trueのとき、and(A,B)はtrueを出力する。
参考: A と B は真偽値をとることとする。
さらに、二つの変数に与えられた論理式の真理値表を表示する table関数 を作成せよ。
table(A,B,and(A,or(A,B))).
true true true
true false true
false true false
false false false3.01 で作られた and関数、or関数を引き続き使い、演算子を定義せよ。
例)
A and (A or not B)さらに、よく使われるように演算子の優先順位を定義せよ。
例)
table(A,B, A and (A or not B)).
true true true
true false true
false true false
false false false論理式は、true/false を任意の数を含むことができ、このような方法で 3.02 を 一般化します。table関数を定義し、その table関数は引数を (配列、式) とし、 配列と式には true/false を列挙し、真理値表を表示せよ。
例)
table([A,B,C], A and (B or C) equ A and B or A and C).
true true true true
true true false true
true false true true
true false false true
false true true true
false true false true
false false true true
false false false truen ビットのグレーコードは、一定のルールに従って構築された n ビット列の配列です。 例えば、
C(1) = [”0","1"] # n = 1
C(2) = ["00","01","11","10"] # n = 2
C(3) = ["000","001","011","010","110","111","101","100"] # n = 3ビット列の構築にルールがあり、次の仕様に合うように関数を作成する。
gray(N) # N ビットのグレーコードを返すまず、ハフマン符号の詳細については、離散数学やアルゴリズムの良い本を研究するか、 ウィキペディアを参照せよ。
ここでは関数 fr(s,f) を、その出現頻度と記号のセットを配列として与えられると仮定する。
例)
[fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)] 目的は、記号 s のためのハフマン符号語である hc(s,c) の配列を構築することである。 この例では、結果はHs = [hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'), hc(e,'1101'), hc(f,'1100')] [hc(a,'01'),...等等]。 次のようにタスクが定義されて、関数 huffman(a,b) によって実行できなくてはならない。
huffman(Fs,Hs) # Hs が出現頻度表 Fs のためのハフマン符号表