2015年5月15日金曜日

R-99 その他 - Prolog-99 Ruby版 日本語訳

R-99: 99 の Ruby の問題 - 7. その他

  • 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

その他の問題

7.01 (**) エイトクイーン問題

これは、コンピュータサイエンスの古典的な問題である。目的は、全てのクイーンが互いを攻撃されないように、 チェス盤に 8 個のクイーンを配置することである。すなわち、どのクイーンも、同じ行、同じ列、または 同じ対角線上にない状態である。

ヒント: 番号 1 から N の配列としてクイーンの位置を表す。例:[4,2,7,3,6,8,5,1] 最初の列のクイーンは4行目にあることを、次の列には2行目、というように解釈する。 生成-試験パラダイム(generate-and-test paradigm)を利用せよ。

訳注: 「生成-試験パラダイム」とは、結果を自動的に可視化する戦略である。ここでは、 クイーンの配置列を求めた時、その結果を画面に描画し、正しいかどうかをチェックすることができるように することを指す。

7.02 (**) ナイトツアー

もう一つの有名は問題は、どのようにすれば 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)

7.03 (***) フォン-コッホの予想から

数年前、解決策を知らないためにある問題に興味をそそられた数学者がいた。名前はファン-コッホ。 この問題は解決されているかどうかわからない。

とにかく、パズルは以下のようになっている。N 個のノードを持つ ツリーを考える(従って N-1 個のエッジがある)。 1からNのノードに応じて1からN-1の各エッジを列挙するための方法を見つけよ。各エッジ K の ノード番号は K と等しいする。 予想では、これは常に可能であるという。

小さなツリーであれば、この問題を手で解くことは簡単である。しかし、大きなツリーや14は 非常に大きく、解を導くことは非常に困難である。しかも、常に解があるかどうかは分からないことを 忘れないように。

与えられたツリーの採番方法を計算する関数を書け。上記のツリーの解は何か?

7.04 (***) 算術パズル

整数のリストを与えると、正しい方程式の結果のような演算記号(演算子)を挿入する方法を発見せよ。 例) 数の配列 [2,3,5,7,11] は方程式で 2 - 3 + 5 + 7 = 11 または 2 = (3 * 5 + 7) / 11 と書ける(他にも10以上書き方がある)。

7.05 (**)

財務書類上、小切手のように、数字は時々単語の組み合わせとして書く必要がある。 例) 175 は、"one-seven-five"と書く必要がある。 単語の組み合わせで(負ではない)整数を表示する関数full_words(a)を書け。

7.06 (**) 構文チェッカー

特定のプログラミング言語(Ada)で識別子は、構文図(鉄道チャート)の反対として定義される。 ループの含まれない構文図のシステムに構文図を変換せよ。すなわち、これは純粋に再帰である。 これらの変更された図を用いて、与えられた文字列が有効な識別子であるか否かを確認することができる 関数identifierを書け。

identifier => str   # str は正しい識別子

7.07 (**) 数独

数独パズルは次のように解く:

    問題文                 解答

    .  .  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までのすべての数を、各行、各列、各プレースに一度だけ現れるように数字の 入っていない場所に埋めることである。

7.08 (***) ノノグラム

訳注: 「ノノグラム」とは、日本では「イラストロジック(お絵描きロジック)」などと呼ばれている。

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で、毎回異なる解を持つ。

7.09 (***) クロスワードパズル

クロスワートパズルの空(またはほとんど空)の枠と単語集が与えらえる。問は、枠に単語を 配置することである。

特定のクロスワードパズルは、最初に任意の順番で単語(1行に一つの単語)をリストにした テキストファイルに指定されている。そして、空行の後、クロスワードの枠組みが定義されている。 この枠の仕様では、空の文字位置をドット(.)で表現する。 解を簡単にするために、文字位置にはあらかじめ定義された文字の値を含むことができる。

単語は少なくとも2文字の文字列である。クロスワードパズルの枠組みの中で文字の入る場所の縦、 横の並びをサイトと呼ぶ。問は、サイト上の単語を矛盾なく配置する方法を見つけることである。

訳注: データファイルの内容例

PERL
PROLOG
ONLINE
GNU
LINUX
WEB
NFS
XML
SQL
MAC
EMACS

......  .
. .  .  .
. ..... .
. . . ...
  . ... .
 ...

ヒント:

  1. この問題は簡単ではない。この問題を完全に理解するためにはいくらか時間が必要になるだろう。
  2. 読み込むデータファイルの解は、上記のようなファイルで提供される。
  3. 効率上の理由から、大きなパズルのために最小の所で、言葉やサイトを特定の順番で ソートすることが重要である。この問題の一部については、1.28 の解は非常に有効だろう。

R-99 グラフ - Prolog-99 Ruby版 日本語訳

R-99: 99 の Ruby の問題 - 6. グラフ

  • 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

グラフ問題

グラフ理論では、用語の意味がかなり変わる。一部の著者は、異なる意味で同じ単語を使用している。 一部の著者は、同じことを意味する別の単語を使用している。ここで使う用語の定義では、 矛盾がないことを願っている。

グラフは、エッジのセットとノードのセットの集合として定義される。

Ruby でグラフを表現する方法はいくつかある。

一つの方法は、一節として別個にエッジを表す方法である。 この形態では、上記のグラフは以下のように表すことができる。

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つの指定されたノード間で許可されている いわゆるマルチグラフに使用することができる。

6.01 (***) 変換

別のグラフ表現の間で変換する関数を書け。これらの関数では、全ての表現は同等である。 すなわち、以下の問題のために、あなたは常に最も便利な表記法を選ぶことができる。 この問題が(***)に評価された理由は、この問題が特に難しいからではなく、この問題の解が特別な場合に 対処するために役立つためである。

6.02 (**) 別のあるノードからのパス

グラフ G にノード A からノード B への非循環パス P を見つけるための関数 path(G,A,B) を書け。関数は、バックトラックして全てのパスを経由する必要がある。

6.03 (*) 指定されたノードから循環

グラフ G の指定されたノード A から始まる閉じたパス(循環) P を発見する関数 cycle(G,A) を書け。関数は、バックトラックを介して全ての循環を返す必要がある。

6.04 (**) 全てのスパニングツリーを作成せよ

訳注: 「スパニングツリー」とは、ループするグラフ内で、1度とったパスを2度と通らないような パスをツリー状に表したもの。

(バックトラックによって)与えられたグラフの全てのスパニングツリーを作成するための関数 s_tree(graph,tree)を書け。この関数を使用すると、上のグラフにある複数のスパニングツリーを 調べる。 関数s_tree(graph,tree)のための正しい解を持つ時、他の2つの有用な関数を定義して使う: is_tree(graph)is_connected(graph)。両方とも作成するのに5分程度の作業であろう。

6.05 (**)

与えられたラベル付きグラフの最小スパニングツリーを作成するための関数ms_tree(graph,tree) を書け。

ヒント: 「プリムのアルゴリズム」を使用せよ。問題 6.04 の解を小さく変更するのがコツである。

6.06 (**) グラフ同型

全単射 f が存在する時、2つのグラフ G1(n1,e1) 及び G2(n2,e2) が同型である。 f とは、n1 から任意のノード X,Y の間で x と y が隣接する時のみ、f(x) と f(y) が隣接する。

二つのグラフが同型であるかどうかを判断する関数を書け。 ヒント: 関数 f を書くために、オープンエンドリスト(訳注:終端の決まっていない構造のリスト) を使用する。

6.07 (**) ノードの次数とグラフ着色

訳注: 「次数」とは、繋がっているノードの数のこと。

  1. 与えられたノードの次数を測定する関数degree(graph,node)を書け。
  2. 度合いを降順ソートし、グラフの全てのノードのリストを作成する関数を書け。
  3. 隣接ノードは、異なる色を持つようにグラフのノードを描くために、ウェルチ-パウエルのアルゴリズム を使用せよ。

6.08 (**) 深さ優先グラフ探索

深さ優先グラフ探索の探索順を作成する関数をかけ。出発点を与える必要があり、出力は(深さ優先順で) この出発点から到達可能なノードのリストである必要がある。

6.09 (**) 連結した構成要素

その連結した構成要素にグラフを分割する関数をかけ。

6.10 (**) 2部グラフ

与えられたグラフは2部グラフであるかどうかを調べる関数を書け。

訳注: 「2部グラフ」とは、グラフのノードを2つのグループ A,B に分け、各エッジがグループ A の ノードからグループ B のノードに繋がっている(すなわち、同じグループ同士のノードが繋がっていない)時、 このグラフを「2部グラフ」と呼ぶ。

6.11 (***) N 個のノードを持つ K-正則単純グラフを作成せよ。

K 正則グラフでは、全てのノードは K の次数を持っている。すなわち、各ノードに繋がるエッジの数は K である。ノードが 6 個ある 3-正則グラフはいくつか。(非同型のもの!)

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 でのツリー表現を作成せよ。違うツリーを用いよ。

R-99 バイナリツリー - Prolog-99 Ruby版 日本語訳

R-99: 99 の Ruby の問題 - 4. バイナリツリー

  • 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

バイナリツリー問題

バイナリツリーは、空か、ルート要素と二つのノードで構成されているバイナリツリー自体のいずれかである。

ここで用いる関数 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            # 空のバイナリツリー

4.01 (*) 指定された関数がバイナリツリーを表しているかどうかを確認せよ

関数 istree(a) は、その引数はバイナリツリーを表すノードがある場合のみ成功するように書け。

例)
istree(t(a,t(b,nil,nil),nil)) => true
istree(t(a,t(b,nil,nil))) => false

4.02 (**) 完全にバランスの取れたバイナリツリーを作成せよ

完全にバランスの取れたバイナリツリー(訳注:以降「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)

4.03 (**) 対称バイナリツリー

ルートノードを介して垂直線を描くことができるとき、右サブツリーが左サブツリーの鏡像である場合、 対称バイナリツリーと呼ぶことにする​​。 指定されたバイナリツリーが対称であるかどうかを確認する関数 symmetric(a) を書く。

参考: 一本のツリーが別の鏡像であるかどうかをチェックする関数 mirror(a,b) を書く。 ここでは、ツリーの構造にだけチェックできればよく、ノードの値は無視して良い。

4.04 (**) 二分探索ツリー (辞書)

例)
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

4.05 (**) 生成と検査の方法

指定された数のノードを使用して、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のノードがあるツリーがいくつあるか? 指定された数のノードのためにいくつ解があるかについて調査せよ。 数が偶数である場合はどうすれば? 適切な関数を書け。

4.06 (**) 高さバランスバイナリツリーの作成

高さバランスバイナリツリーにおいて、ノードごとに次の特徴がある。 その左のサブツリーの高さとその右のサブツリーの高さは、その差が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

4.07 (**) 指定された数のノードの高さバランスBツリーを作成

高さ 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であるいくつかの高さバランスツリーが存在する方法を確認せよ。

4.08 (*) バイナリツリーの葉の数をかぞえよ

「葉」とは、後が続かないノードのことである。それらをカウントする関数 count_leaves(a) を書け。

count_leaves(T) => N    # バイナリツリー T には N 個の葉がある。

4.09 (*) 配列内のバイナリツリーの葉を集めよ

「葉」とは、後が続かないノードのことである。それらを配列にする関数 leaves(T) を書け。

leaves(T) => S      # S はバイナリツリー T の全ての葉の配列である。

4.10 (*) 配列内のバイナリツリーに含まれるノードを集めよ

バイナリツリーに含まれるノードには、1つ、2つまたはノードを含まない場合のいずれかである。 配列にそれらを集めるために、関数 internals(T) を書きます。

internals(T) => S   # S はバイナリツリー T に含まれるノードの配列です。

4.11 (*) 配列内の指定された高さでのノードを集めよ

バイナリツリーのノードでは、ルートノードからある高さにあるノード N へのパス(訳注:経路)は、長さ N - 1を持つ。 ルートノードは、高さ 1 にある。 配列内の指定された高さで、全てのノードを集める関数 atlevel(T,L) を書け。

atlevel(T,L) => S       # S は高さ L にあるバイナリツリーのノードのリストである。

atlevel(T,L) を使用して、関数 levelorder を作成し、そのノードの高さの帰りがけ順の並びを 作成することは簡単である。 しかし、それを行うためのより効率的な方法がある。

4.12 (**) 完全バイナリツリーを作成せよ

次のように高さ H の完全バイナリツリーが定義されている。

高さ 1,2,3,...,H - 1は、ノードの最大数を含む。 つまり、2**(i - 1) が高さ i の時、ルートにの高さは 1 とカウントすることに注意せよ。

ノードの最大数よりも少なく、含まれても良い n 個の高さ H は、全てのノードが「左調整」 されています。 これは、全ての含まれるノードが最初に来る高さ順ツリー探索では、ノードが最初で、 2番目に葉、後に何もないもの(nil は実際にはノードではない!)がくる。

特に、完全バイナリツリーは、ヒープのためのデータ構造(またはアドレス指定方式)として使用されている。

数 1 でルートから始まる、高さの帰りがけ順のツリーに含まれるノードを列挙することによって、 完全バイナリツリー内の各ノードへのアドレス番号を割り当てることができる。 そうすることで、アドレス A を持つ全てのノード X は、次の特徴を保持していることを実現する。

X の左右に続くノードのアドレスは、2 * A2 * A + 1のそれぞれのノードが存在すると想定する。 この事実は優雅な完全バイナリツリー構造を構築することができる。 次に関数 complete_binary_tree(N) の仕様を書く。

complete_binary_tree(N) => T    # T は N 個のノードを持つ完全バイナリツリーである。

適切な方法でその関数をテストせよ。

4.13 (**) バイナリツリーのレイアウト その1

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 はバイナリツリーから得られた「位置付け」バイナリツリーです。

適切な方法で作成した関数をテストせよ。

4.14 (**) バイナリツリーのレイアウト その2

代替のレイアウト方法は、上の図に示されている。規則を見つけ、対応する Ruby の関数を記述せよ。

ヒント: 指定された高さでは、隣接ノードとの水平距離は一定である。

問題 4.13 と同様の規則を使用して、適切な方法でその関数をテストせよ。

4.15 (***) バイナリツリーのレイアウト その3

されに別のレイアウト方法は、上の図に示されている。 この方法は、全てのノードで特定の対称性を維持しながら非常にコンパクトなレイアウトが得られる。 規則を見つけ、対応する Ruby 関数を書け。

ヒント: ノードとその後ろのノード間の水平距離を考慮せよ。

もれなく組み合わされたバイナリツリーを作成するためにどのように2つのサブツリーをひとまとめにするか?

問題 4.13 と 4.14 と同様の規則を使用して、適切な方法でその関数をテストせよ。

注: これは難しい問題だ。簡単に諦めてはいけない!

もっとも好みのレイアウトはどれか?

4.16 (**) バイナリツリーの文字列表現

誰かが次のタイプ(例を参照)の文字列としてバイナリツリーを表示する。

a(b(d,e),c(f(g,)))
  1. ツリーが(nil または t(X,L,R)の用語として)いつものように与えられている場合、 この文字列表現を生成する Ruby 関数を書け。そして、この逆を行う関数を書け。 すなわち、通常の形でツリーを作成し、文字列表現を与える。最後に、両方の方向で使用することができる 単一の関数 tree_string(a,b) の二つの引数を組み合わせる。
  2. 差分配列とツリーの両方向の差分リストを変換し、関数 tree_dlist(a,b) を使用して 関数 tree_string(a,b) と同じ関数を書け。

簡単にするために、ノード内の情報は単一の文字であるとし、文字列にはスペースは含まない。

4.17 (**) バイナリツリーの行きがけ順と帰りがけ順

問題 4.16 の例のように、単一の小文字で識別されるノードとバイナリツリーについて検討する。

  1. 与えられたバイナリツリーの行きがけ順と帰りがけ順 をそれぞれ作成する関数 preorder(a,b)inorder(a,b) を書け。。 結果は最小構成であるべきだ。例えば問題 4.16 の例の行きがけ順のための'abdecfg'
  2. 問題 a からpreorder(a,b)を逆方向に利用できるようにせよ。 すなわち行きがけ順が与えられると、対応するツリーを構築する。ない場合は、必要な手配をせよ。
  3. バイナリツリーのノードの行きがけ順と帰りがけ順が与えられた場合、次のように明確にツリーが 決定する。関数 pre_in_tree(a,b,c)を書け。
  4. 問題 a から c を異なる配列で解け。解答を比較するために関数の実行時間を取得せよ。

同じ文字が複数のノードに表示された場合はどうなるか。`pre_in_tree("aba","baa")'を試せ。

4.18 (**) バイナリツリーのドットストリング記法

問題 4.16 の例のように、単一の小文字で識別されたノードと、再びバイナリツリーを検討する。 このようなツリーは、空のサブツリー(nil)は、ツリー探索中に遭遇されるドット(".")が挿入された そのノードの行きがけ順によって表すことができます。 例えば、問題 4.16 に示すツリーは次のように表現される: "abd..e..c.fg..." まず、構文(BNFや構文ダイアグラム)を確立しようとした時、両方向の変換を行い、関数 tree_dotstring(a,b)のように書く。差分配列を使用せよ。

R-99 論理演算と符号化 - Prolog-99 Ruby版 日本語訳

R-99: 99 の Ruby の問題 - 3. 論理演算と符号化

  • 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

論理、符号化問題

3.01 (**) 論理式の真理値表

それぞれの関数が true または false を返すように定義せよ。 and(a,b), or(a,b), nor(a,b), xor(a,b), iml(a,b), equ(a,b)

例) A == trueB == 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  false

3.02 (*) 理式の真理値表 その2

3.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

3.03 (**) 理式の真理値表 その3

論理式は、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 true

3.04 (**) グレーコード

n ビットのグレーコードは、一定のルールに従って構築された 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 ビットのグレーコードを返す

3.05 (***) ハフマン符号

まず、ハフマン符号の詳細については、離散数学やアルゴリズムの良い本を研究するか、 ウィキペディアを参照せよ。

ここでは関数 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 のためのハフマン符号表

R-99 数学 - Prolog-99 Ruby版 日本語訳

R-99: 99 の Ruby の問題 - 2. 数学

  • 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

数学問題

2.01 (**) 指定された整数が素数であるかどうかを確認せよ

例)
is_prime(7) => true

2.02 (**) 与えられた正の整数の素因数を決定し、昇順に素因数を含む1次元配列を作成せよ

例)
prime_factors(315) => [3,3,5,7]

2.03 (**) 与えられた正の整数の素因数を決定せよ

素因数とその多重度を含むリストを作成します。

例)
prime_factors_mult(315) => [[3,2],[5,1],[7,1]]

ヒント: P1.10 の解答を参考にすることができる。

2.04 (*) 素数の配列を取得せよ。その下限と上限によって整数の範囲を与えると、 その範囲内のすべての素数のリストを表示するようにせよ

例)
get_prime(1,10) => [1,3,5,7,9]

2.05 (**) ゴールドバッハ予想: 2より大きいすべての正の偶数は2つの素数の和である

例)
28 = 5 + 23

これは、一般的なケースでは正しいことが証明されていなかった数論の中で最も有名な事実の一つです。 これは、数値的に(私たちはRubyで行うことができるよりもはるかに大きい)、非常に大きな数まで確認されています。 指定された偶数の整数に合計2つの素数を見つけるために、引数を入力します。

例)
goldbach(28) => [5,23]

2.06 (**) ゴールドバッハ数の配列

その下限と上限によって整数の範囲を与える。このとき、すべての偶数と そのゴールドバッハ数のリストを表示せよ。

例)
goldbach_list(9,20).
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17

偶数の2つの素数の和として書かれている場合、ほとんどのケースでは、そのうちの一つは非常に小さい。 ごくまれに、両方の素数が 50 よりも大きいことがある。範囲 2〜3000 で、このようなケースがあることを 調べよ。

例: 最大 50 個出力する)
goldbach_list(1,2000,50).
992 = 73 + 919
1382 = 61 + 1321
1856 = 67 + 1789
1928 = 61 + 1867

2.07 (**) 2つの正の整数の最大公約数を表示せよ

ユークリッドのアルゴリズムを使用せよ。

訳注: ユークリッドのアルゴリズム(ユークリッドの互除法)とは、 「2つの自然数 a, b (a≥b) について、r = a % bとすると、a と b との最大公約数は b と r との最大公約数に等しいことから、r2 = b % rr3 = r % r2...と続けて 剰余が 0 になったとき(r[n]==0)のr[n-1]が最大公約数となる。」という手法。

例)
gcd(36,63) => 9

2.08 (*) 2つの正の整数が互いに素かどうかを判定せよ

二つの数字の最大公約数が 1 のとき、互いに素であるという。

例)
coprime(35,64) => true

2.09 (**) オイラーのトーシェント関数φ(m)を計算せよ

オイラーのトーシェント関数φとは、正の整数 (1≤r<m) が互いに素であると定義される。

例)
m = 10 のとき、r = 1,3,7,9 となる。
phi(m) => 4

totient_phi(10) => 4

参考: 特殊な場合に注意すること。( phi(1) == 1 )

mが素数であれば φ(m) の値があるかを調べる。 オイラーのトーシェント関数は、最も広く使用されている公開鍵暗号方式(RSA)において 重要な役割を果たしている。 この演習では、この関数を計算するために、最も原始的な方法を使用する必要がある。 この問を解くために 2.10 で使用しなければならない、よりスマートな方法がある。

2.10 (**) オイラーのトーシェント関数φ(m)を計算せよ その2

オイラーのトーシェント関数の定義については、2.09 を参照せよ。 数 m の素因数のリストは、2.03 関数 φ(m) の形で知られている場合、 次のように効率的に計算することができる。 [[p1,m1],[2,m2],[p3,m3],...] 指定された数 m の素因数(およびその多重)の配列です。次に、&phi(m) は、 以下を用いて計算することができる。

関数:

phi(m) = (p1 - 1) * p1**(m1 - 1) * (2 - 1) * 2**(m2 - 1) * (p3 - 1) * p3**(m3 - 1) * ...

訳注: 関数 phi(m) を上記の式を使うように改修せよ。

参考: 「a**b」とは、「a の b 乗」を表す。

2.11 (*) オイラーのトーシェント関数を計算する2つのメソッドを比較せよ

アルゴリズムを比較するために、2.09 と 2.10 の解答を使用せよ。 効率の尺度として関数の実行時間を取る。例として phi(10090) を計算させ、 それぞれの回答の実行時間を確認せよ。

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

R-99: 99 の Ruby の問題 - 1. 配列

  • 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

配列の操作

1.01 (*) 配列の最後の要素を取得せよ

1.02 (*) 配列の最後から2番目の要素を取得せよ

1.03 (*) 配列のK番目の要素を取得せよ

1.04 (*) 配列の要素数を取得せよ

1.05 (*) 配列を逆順にせよ

1.06 (*) 配列が回文であるかどうか調べよ

回文であるリストの例)
["x","a","m","a","x"]、["し","ん","ぶ","ん","し"]

1.07 (**) 配列されたリスト構造を平坦化せよ

例)
["a", ["b", ["c", "d"], "e"]] => ["a", "b", "c", "d", "e"]

1.08 (**) 配列の要素の連続した重複を排除せよ

例)
compress(["a","a","a","a","b","c","c","c","c","c","d","e","e","e","e"]) => 
["a","b","c","d","e"]

1.09 (**) 配列の中の連続して重複する要素を配列にして、それらを一つの配列にまとめよ

例)
pack(["a","a","a","a","b","c","c","c","c","c","d","e","e","e","e"]) => 
[["a","a","a","a"],["b"],["c","c","c","c","c"],["d"],["e","e","e","e"]]

1.10 (*) 配列のランレングス符号化(連続して重複する要素の名前と数を取り出す)せよ

例)
encode(["a","a","a","a","b","c","c","c","c","c","d","e","e","e","e"]) =>
[[4,"a"],[1,"b"],[5,"c"],[1,"d"],[4,"e"]]

1.11 (*) 連続して重複しない要素の場合は符号化しないよう、1.10を修正せよ

例)
encode_modified(["a","a","a","a","b","c","c","c","c","c","d","e","e","e","e"]) =>
[[4,"a"],"b",[5,"c"],"d",[4,"e"]]

1.12 (**) ランレングス符号化された配列をデコード(元に戻す)せよ。 1.11の出力形式をデコードするものとする

例)
decode([[4,"a"],"b",[5,"c"],"d",[4,"e"]]) => ["a","a","a","a","b","c","c","c","c","c","d","e","e","e","e"]

1.13 (**) 1.11と同様のランレングス符号化を行う関数を作成せよ

1.14 (*) 配列の要素を連続して重複させよ

例)
dupli(["a","b","c","d"]) => ["a","a","b","b","c","c","d","d"]

1.15 (**) 配列の要素を連続する重複させる数を与え、その数だけ重複させよ

例)
dupli(["a","b","c"],3) => ["a","a","a","b","b","b","c","c","c"]

1.16 (**) 配列からNの倍数番目にある要素を全て削除せよ。ただし、配列の先頭の要素を1番目とする

例)
drop(["a","b","c","d","e","f","g","h","i","k"],3) => 
["a","b","d","e","g","h","k"]

1.17 (*) 配列を二つにわけよ。このとき、一つ目の配列の長さを与えられるようにせよ

例)
split(["a","b","c","d","e","f","g","h","i","k"],3) =>
[["a","b","c"],["d","e","f","g","h","i","k"]]

1.18 (**) 配列の部分配列を取得せよ。このとき、開始要素と終了要素の2つの インデックスを与える。部分配列には開始要素と終了要素も含まれるものとする

例)
slice(["a","b","c","d","e","f","g","h","i","k"],3,7) => ["c","d","e","f","g"]

1.19 (**) 配列要素を左に回転させよ。あふれた要素は配列の最後尾に追加するものとする。負の数を入力したときは右に回転するものとする

例1)
rotate(["a","b","c","d","e","f","g","h"],3) => ["d","e","f","g","h","a","b","c"]

例2)
rotate(["a","b","c","d","e","f","g","h"],-2) => ["g","h","a","b","c","d","e","f"]  # 負の数を入力すると右に回転

1.20 (*) 配列からK番目の要素を削除せよ

例)
remove_at(["a","b","c","d"],2) => ["a","b","d"]

1.21 (*) 配列の指定された位置に任意の要素を挿入せよ

例)
insert_at(alfa,["a","b","c","d"],2) => ["a","b","alfa","c","d"]

1.22 (*) 与えられた範囲内の全ての整数を含む配列を作成せよ

例)
range(4,9) => [4,5,6,7,8,9]

1.23 (**) 配列からランダムに選択された指定の要素数分を抽出する。このとき、同じ要素を2度抽出してはならない

例1)
rnd_select(["a","b","c","d","e","f","g","h"],3) => ["e","d","a"]

例2)
rnd_select(["a","b","c","d","e","f","g","h"],3) => ["g","b","h"]

1.24 (*) ロト(番号くじ):集合1..MからN個の異なる乱数を抽出する。このとき、同じ要素を2度抽出してはならない

例)
rnd_select(6,49) => [23,1,17,33,21,37]

ヒント: 1.22 と 1.23 の回答を組み合わせている。

1.25 (*) 配列要素のランダムな順列を生成せよ

例)
rnd_permu(["a","b","c","d","e","f"]) => ["b","a","d","c","e","f"]

ヒント: 1.23の回答が使える。

1.26 (**) 配列のN個の要素から選択されたK個の異なるオブジェクトの組み合わせを表示せよ

例)
combination(3,["a","b","c","d","e","f"]) => ["a","b","c"], ["a","b","d"], ... , ["c","e","f"], ["d","e","f"]

1.27 (**) 配列要素を重複しないようにグループにわけよ

  1. 9つのグループが、2、3、4つの3互いに重複のないサブグループにせよ。すべての組み合わせを生成できるようにせよ。
例)
group3(["あか","いし","うら","えび","おじ","かみ","きり","くじ","けん"],G1,G2,G3)
=> G1 = ["あか","いし"], G2 = ["うら","えび","おじ"], G3 = ["かみ","きり","くじ","けん"]
  1. 上記の引数を変更し一般化する。グループサイズの配列を指定し、グループの配列を返すようにせよ。
例)
group(["あか","いし","うら","えび","おじ","かみ","きり","くじ","けん"],[2,2,5])
=> [["あか","いし"],["うら","えび"],["おじ","かみ","きり","くじ","けん"]]

注意: 同じ要素の順番違いは同じものであるとする。

離散数学の「多項定理」という用語で、この組み合わせの問題の詳細を見つけることができる。

1.28 (**) 要素配列の長さに応じて配列の配列のソートせよ

  1. 短い配列から長い配列の順にソートせよ。
例)
lsort([["a","b","c"],["d","e"],["f","g","h"],["d","e"],["i","j","k","l"],["m","n"],["o"])
=> [["o"],["d","e"],["d","e"],["m","n"],["a","b","c"],["f","g","h"],["i","j","k","l"]]
  1. 「同じ配列の長さ」が出てくる回数で昇順(小さい順)にソートせよ。
例)
lsort([["a","b","c"],["d","e"],["f","g","h",],["d","e"],["i","j","k","l"],["m","n"],["o"])
=> [["i","j","k","l"],["o"],["a","b","c"],["f","g","h"],["d","e"],["d","e"],["m","n"]]

注意: 上記の例では、結果の最初の2つの配列が長さ4と1を持っていることに注意せよ。 両方の長さは一度だけ表示される。第3及び第4の配列は、長さ3を持っている。 この長さの2つの配列がある。そして最後に、残りの3つの配列は、これは最も たくさんある長さの長さ2を持っている。

2015年5月5日火曜日

heroku にムームードメインで取得した独自ドメインを設定する

事前準備については説明しないので、各自ご用意ください。

事前準備

  1. heroku にアカウントを作る。
  2. heroku にウェブアプリを作る。
  3. ムームードメインでアカウントを作る。
  4. ムームードメインで独自ドメインを取得する。

手順

heroku の設定

  1. heroku のウェブアプリのダッシュボードから、「Settings」を開く。
  2. 「Name」カテゴリのアプリケーション名を調べてメモしておく。ムームードメインで使います。
  3. 「Domains」カテゴリの「Domain names」欄の「Edit」ボタンをクリック。
  4. サブドメイン付きの独自ドメインを設定する。

    appname.自分のドメイン
  5. 「Domain namas」欄の「Save」ボタンを押して保存。

ムームードメインの設定

  1. ログインして画面左の「コンパネメニュー」から「ドメイン管理」の中の 「ムームーDNS」をクリック。
  2. heorku に使用したいドメインの「処理」欄の「変更」ボタンをクリック。
  3. 画面を下にスクロールし、「設定2」カテゴリの表に heorku で設定した サブドメイン付きの独自ドメインを設定する。詳細は以下。
    1. 「サブドメイン」欄に。サブドメインを入力する。上の例だと「appname」 と入力する。
    2. 「種別」欄のドロップダウンリストから、「CNAME」を選択する。
    3. 「内容」欄に heroku で調べておいたアプリケーション名を使い、 "アプリケーション名.herokuapp.com" を入力する。「"」は入力しません。
  4. 「セットアップ情報変更」ボタンをクリックして、設定する。

お疲れ様でした。以上で設定完了です。 設定が有効になるまで20分〜2日くらいかかるそうです。私の場合は30分ほどで 有効になりました。