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 == 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  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 のためのハフマン符号表