有理数
今回は簡単な例題として、有理数 (分数) を操作する演算子を作ってみましょう。
●有理数の定義と生成
有理数 (Rational) は分子と分母を整数の組で表すと簡単に定義できます。次のリストを見てください。
リスト : 有理数の定義 datatype ratio = Rat of IntInf.int * IntInf.int
最初の IntInf.int が分子を表し、次の IntInf.int が分母を表します。
次は有理数を生成する関数 make_ratio を作ります。次のリストを見てください。
リスト : 有理数の生成
(* 最大公約数 *)
fun gcd(a : IntInf.int, 0) = a
| gcd(a, b) = gcd(b, a mod b)
(* 有理数の生成 *)
exception Ratio_err
fun make_ratio(_, 0) = raise Ratio_err
| make_ratio(n, m) =
let
val a = gcd(IntInf.abs(n), IntInf.abs(m))
val f = if m > 0 then 1 else ~1
in
Rat ((n div a) * f, (m div a) * f)
end
make_ratio の引数 n が分子で、m が分母を表します。m が 0 の場合は例外 Ratio_err を送出します。そうでなければ、Rat (a, b) を生成します。このとき、関数 gcd で最大公約数を求めて、約分することに注意してください。それから、有理数の符号は分子に付けることにします。分母 m が負の場合は n と m に -1 を掛け算します。
●算術演算子の定義
算術演算は make_ratio を使うと簡単に定義できます。このとき、算術演算を中置演算子として使うことができると便利です。SML/NJ の場合、次に示す文を用いることで、関数やデータ構成子などを中置演算子として使用することができます。
infix レベル 識別子 ... infixr レベル 識別子 ...
infix で宣言された識別子は左結合の中置演算子に、infixr で宣言された識別氏は右結合の中置演算子になります。レベルは優先順位を表します。SML/NJ の場合、比較演算子のレベルは 4、加法型演算子 (+, - ) のレベルは 5、乗法型演算子 (*, /, div, mod) のレベルは 6 に設定されています。
簡単な例を示しましょう。たとえば、最大公約数を求める関数 gcd を中置演算子に設定してみましょう。
- gcd; val it = fn : IntInf.int * IntInf.int -> IntInf.int - infix 4 gcd; infix 4 gcd - 45 gcd 30; val it = 15 : IntInf.int - 15 * 3 gcd 10 + 20; val it = 15 : IntInf.int
infix 4 gcd とすると、gcd を優先順位が 4 の中置演算子として使うことができます。加法演算子と乗法演算子よりも優先順位が低いので、式 15 * 3 と 10 + 20 が先に計算されます。
op を付加すると、通常の関数として呼び出すことができます。また、nonfix gcd とすると、中置演算子の設定を取り消すことができます。
- (op gcd) (45, 30); val it = 15 : IntInf.int - nonfix gcd; nonfix gcd - gcd(45, 30); val it = 15 : IntInf.int
今回は OCaml のモジュール Num に合わせて、算術演算子として +/, -/, */, -/ を使うことにしましょう。プログラムは次のようになります。
リスト : 算術演算子の定義
fun +/ (Rat(p1, q1), Rat(p2, q2)) =
make_ratio(p1 * q2 + p2 * q1, q1 * q2)
fun -/ (Rat(p1, q1), Rat(p2, q2)) =
make_ratio(p1 * q2 - p2 * q1, q1 * q2)
fun */ (Rat(p1, q1), Rat(p2, q2)) =
make_ratio(p1 * p2, q1 * q2)
fun // (Rat(p1, q1), Rat(p2, q2)) =
make_ratio(p1 * q2, p2 * q1)
infix 6 +/ -/
infix 7 */ //
単純な分数の計算なので、難しいところはないでしょう。演算子の優先順位は +, -, *, / と同じです。
●比較演算子の定義
次は比較演算子を定義します。最初に関数 compare_ratio を作ります。
リスト : 有理数の比較 fun ratio_compare (Rat (x1, y1), Rat (x2, y2)) = x1 * y2 - x2 * y1
compare_ratio は有理数 a と b を比較して、a < b ならば負の整数を返し、a = b ならば 0 を返し、a > b ならば正の整数を返します。この処理は a と b を通分して、a の分子から b の分子を引き算するだけで実現できます。
compare_ratio を使うと比較演算子は簡単に定義できます。
リスト : 比較演算子の定義 fun =/ (x, y) = ratio_compare(x, y) = 0 fun <>/ (x, y) = ratio_compare(x, y) <> 0 fun </ (x, y) = ratio_compare(x, y) < 0 fun >/ (x, y) = ratio_compare(x, y) > 0 fun <=/ (x, y) = ratio_compare(x, y) <= 0 fun >=/ (x, y) = ratio_compare(x, y) >= 0 infix 4 =/ <>/ </ >/ <=/ >=/
算術演算子に合わせて、名前の最後に / を付けています。
●データ型の変換
最後に有理数を他のデータ型に変換する関数を作ります。
リスト : データ型の変換
(* 整数か *)
fun isInteger(Rat(p, q)) = q = 1
(* 文字列に変換 *)
fun ratio_toString(Rat(p, q)) =
if q = 1 then IntInf.toString(p)
else IntInf.toString(p) ^ "/" ^ IntInf.toString(q)
(* 整数に変換 *)
fun ratio_toInteger(Rat(p, q)) = IntInf.quot(p, q)
(* 実数に変換 *)
fun ratio_toReal(Rat(p, q)) =
Real.fromLargeInt(p) / Real.fromLargeInt(q)
(* 有理数の表示 *)
fun print_ratio(x) = ratio_toString(x)
整数に変換する場合、無条件に関数 IntInf.quot を使っています。整数の判定には関数 isInteger を使ってください。あとはとくに難しいところはないでしょう。
●実行例
それでは簡単な実行例を示します。
- val a = make_ratio(1, 2); val a = Rat (1,2) : ratio - val b = make_ratio(1, 3); val b = Rat (1,3) : ratio - a +/ b; val it = Rat (5,6) : ratio - a -/ b; val it = Rat (1,6) : ratio - b -/ a; val it = Rat (~1,6) : ratio - a */ b; val it = Rat (1,6) : ratio - a // b; val it = Rat (3,2) : ratio - b // a; val it = Rat (2,3) : ratio - a </ b; val it = false : bool - a >/ b; val it = true : bool - a =/ b; val it = false : bool - a <>/ b; val it = true : bool
正常に動作しているようです。実際はもっとテストする必要がありますが、今回は先へ進むことにしましょう。
●プログラムリスト１
(*
* ratio.sml : 有理数
*
* Copyright (C) 2012-2021 Makoto Hiroi
*
*)
(* データ型の定義 *)
datatype ratio = Rat of IntInf.int * IntInf.int
(* 最大公約数 *)
fun gcd(a : IntInf.int, 0) = a
| gcd(a, b) = gcd(b, a mod b)
(* 有理数の生成 *)
exception Ratio_err
fun make_ratio(_, 0) = raise Ratio_err
| make_ratio(n, m) =
let
val a = gcd(IntInf.abs(n), IntInf.abs(m))
val f = if m > 0 then 1 else ~1
in
Rat ((n div a) * f, (m div a) * f)
end
(* 整数か *)
fun isInteger(Rat(p, q)) = q = 1
(* 文字列に変換 *)
fun ratio_toString(Rat(p, q)) =
if q = 1 then IntInf.toString(p)
else IntInf.toString(p) ^ "/" ^ IntInf.toString(q)
(* 整数に変換 *)
fun ratio_toInteger(Rat(p, q)) = IntInf.quot(p, q)
(* 実数に変換 *)
fun ratio_toReal(Rat(p, q)) =
Real.fromLargeInt(p) / Real.fromLargeInt(q)
(* 有理数の表示 *)
fun print_ratio(x) = ratio_toString(x)
(* 四則演算 *)
fun +/ (Rat(p1, q1), Rat(p2, q2)) =
make_ratio(p1 * q2 + p2 * q1, q1 * q2)
fun -/ (Rat(p1, q1), Rat(p2, q2)) =
make_ratio(p1 * q2 - p2 * q1, q1 * q2)
fun */ (Rat(p1, q1), Rat(p2, q2)) =
make_ratio(p1 * p2, q1 * q2)
fun // (Rat(p1, q1), Rat(p2, q2)) =
make_ratio(p1 * q2, p2 * q1)
(* 比較演算子 *)
fun ratio_compare (Rat (x1, y1), Rat (x2, y2)) =
x1 * y2 - x2 * y1
fun =/ (x, y) = ratio_compare(x, y) = 0
fun <>/ (x, y) = ratio_compare(x, y) <> 0
fun </ (x, y) = ratio_compare(x, y) < 0
fun >/ (x, y) = ratio_compare(x, y) > 0
fun <=/ (x, y) = ratio_compare(x, y) <= 0
fun >=/ (x, y) = ratio_compare(x, y) >= 0
(* 中置演算子 *)
infix 6 +/ -/
infix 7 */ //
infix 4 =/ <>/ </ >/ <=/ >=/
●小町分数
それでは ratio.sml を使ってパズルを解いてみましょう。
下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。3 つの分数を足すと 1 / N になる配置を求めてください。
ex)
3/27 + 6/54 + 9/81 = 1/3
3/54 + 6/72 + 9/81 = 1/4
図 : 小町分数
このパズルの元ネタは N = 1 の場合で、参考文献 [1] に掲載されています。ちなみに、3 つの分数の和が整数になる場合、その値は 1 しかありません。
プログラムは次のようになります。
リスト : 小町分数の解法
(* 小町分数 *)
(* 要素の削除 *)
fun remove(_, []) = []
| remove(x, y::ys) = if x = y then remove(x, ys) else y :: remove(x, ys)
(* 順列の生成 *)
fun permutation f n xs =
let
fun iter(0, _, a) = f (rev a)
| iter(i, xs, a) =
List.app (fn x => iter(i - 1, remove(x, xs), x::a)) xs
in
iter(n, xs, [])
end
(* 検定 *)
exception Puz_err
fun check([n1,n2,n3,n4,n5,n6,n7,n8,n9]) =
let
val a = make_ratio(n1, n4 * 10 + n7)
val b = make_ratio(n2, n5 * 10 + n8)
val c = make_ratio(n3, n6 * 10 + n9)
val d = a +/ b +/ c
val one = make_ratio(1, 1)
in
if n1 < n2 andalso n2 < n3 andalso isInteger(one // d) then (
print(IntInf.toString(n1) ^ "/" ^ IntInf.toString(n4) ^ IntInf.toString(n7));
print(" + ");
print(IntInf.toString(n2) ^ "/" ^ IntInf.toString(n5) ^ IntInf.toString(n8));
print(" + ");
print(IntInf.toString(n3) ^ "/" ^ IntInf.toString(n6) ^ IntInf.toString(n9));
print(" = ");
print_ratio(d); print("\n")
) else ()
end
| check(_) = raise Puz_err
(* 解法 *)
fun solver() = permutation check 9 [1,2,3,4,5,6,7,8,9]
プログラムは単純な生成検定法です。関数 check は分数を生成して小町分数を計算します。その値を d とすると、1/d が整数であれば条件を満たします。解を表示するとき、分子の数字を n1 < n2 < n3 に限定しています。順列を生成するときにこの条件を追加すると、枝刈りの効果により処理速度はもっと高速になります。興味のある方は試してみてください。
実行する前に ratio.sml をロードしておいてください。結果は次のようになります。
- solver(); 1/38 + 2/95 + 4/76 = 1/10 1/24 + 3/56 + 7/98 = 1/6 1/56 + 3/72 + 9/84 = 1/6 1/26 + 5/39 + 7/84 = 1/4 1/32 + 5/96 + 7/84 = 1/6 1/48 + 5/32 + 7/96 = 1/4 1/96 + 5/32 + 7/84 = 1/4 1/96 + 5/48 + 7/32 = 1/3 2/19 + 4/57 + 6/38 = 1/3 2/18 + 5/63 + 7/49 = 1/3 3/48 + 5/16 + 9/72 = 1/2 3/27 + 6/54 + 9/81 = 1/3 3/54 + 6/72 + 9/81 = 1/4 5/34 + 7/68 + 9/12 = 1 val it = () : unit
結果は全部で 14 通りになりました。
●単位分数の和
パズルではありませんが、分数のお話を紹介します。分子が 1 の分数を「単位分数」といいますが、単位分数の和は古代エジプト人がよく研究していたそうです。この話は M.Kamada さん からお聞きしたのですが、参考文献 [2] に「分数を単位分数の和で表す方法」がありましたので紹介します。
0 < m / n < 1 の分数を単位分数の和で表します。まず、n / m の商 q を求めます。もし、割り切れれば単位分数になりますね。そうでなければ、m / n から 1 / (q + 1) を引き算して M / N を求めます。あとは、M / N に対して同じ処理を繰り返すだけです。次の式を見てください。
M / N = m / n - 1 / (q + 1) M / N = (m(q + 1) - n) / n(q + 1) M = m(q + 1) - n = m - (n - mq) = m - (n mod m)
0 < (n mod m) < m ですから、M は必ず m より小さな値になります。つまり、この処理を繰り返していくと m は必ず 1 になるので、分数を単位分数の和で表すことができる、というわけです。なるほど納得のアルゴリズムですね。たとえば、11 / 13 を単位分数の和で表してみましょう。
11 / 13 => q = 1, 11 / 13 - 1 / 2 = 9 / 26 9 / 26 => q = 2, 9 / 26 - 1 / 3 = 1 / 78 => 11 / 13 = 1 / 2 + 1 / 3 + 1 / 78
このように、分子 m の値は減少していきます。このアルゴリズムを SML/NJ でプログラムすると、次のようになります。
リスト : 分数を単位分数の和で表す
fun bunsu(m, n) =
if n mod m = 0 then
print("1/" ^ Int.toString(n div m) ^ "\n")
else
let
val q = n div m + 1
in
print("1/" ^ Int.toString(q) ^ " + ");
bunsu(m * q - n, n * q)
end
val bunsu = fn : int * int -> unit
SML/NJ らしく再帰定義を使っています。関数名は適当なので、ふさわしい名前に変更してください。あとは、アルゴリズムをそのままプログラムしただけなので、特に難しいところはないでしょう。
それでは簡単な実行例を示します。
- bunsu(11, 13); 1/2 + 1/3 + 1/78 val it = () : unit - bunsu(12, 13); 1/2 + 1/3 + 1/12 + 1/156 val it = () : unit - bunsu(19, 23); 1/2 + 1/4 + 1/14 + 1/215 + 1/138460 val it = () : unit
このほかにも、単位分数の和で表す方法は何通りもあるわけで、この方法はその中のひとつにすぎません。古代エジプトではどのような方法で求めていたのでしょうか。興味深いところです。
[1] 芦ヶ原伸之,『超々難問数理パズル 解けるものなら解いてごらん』, 講談社, 2002
[2] 奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
●Four Fours
ratio.sml を使ってもう一つパズルを解いてみましょう。Four Fours は数字を使ったパズルです。いろいろなルールがあるのですが、今回は簡易ルールで行きましょう。それでは問題です。
数字 4 を 4 つと +, - *, /, () を使って、答えが 1 から 10 になる式を作りなさい。数字は 4 だけではなく、44 や 444 のように合体させてもよい。また、- を符号として使うことは禁止する。
数字の 4 を 4 つ使うので Four Fours という名前なのだと思います。ところで、このルールでは 11 になる式を作ることができません。ほかのルール、たとえば小数点を付け加えると、次のように作ることができます。
4 / .4 + 4 / 4 = 11
今回は簡易ルールということで、小数点を使わないで 1 から 10 までの式を作ってください。まずは、ご自分の頭を使って解いてみましょう。気分転換や息抜きのときにでも考えてみてください。
●数式のパターン
それではプログラムを作りましょう。基本的には、数式を生成して答えをチェックするだけです。Four Fours の場合、4 つの数値に 3 つの演算子しかありませんから、数式のパターンは簡単に求めることができます。数式を二分木で表すと、次に示す 5 つのパターンになります。
X, Y, Z が演算子を表します。これを式で表すと、次のようになります。
(1) (4 Y 4) X (4 Z 4) (2) 4 X (4 Y (4 Z 4)) (3) ((4 Z 4) Y 4) X 4 (4) 4 X ((4 Z 4) Y 4) (5) (4 Y (4 Z 4)) X 4
あとは、X, Y, Z に演算子 +, -, *, / を入れて数式を計算すればいいわけです。
Four Four's は数字を合体できるので、数字が 3 つで演算子が 2 つ、数字が 2 つで演算子がひとつ、というパターンもあります。演算子がひとつの場合は簡単ですね。演算子が 2 つの場合は、次の式になります。
(A) (a Y b) X c (B) a X (b Y c)
a, b, c が数字で X, Y が演算子を表しています。数字は 4 か 44 になります。この場合、a, b, c の組み合わせを生成する必要があります。組み合わせを (a, b, c) で表すと、(4, 4, 44), (4, 44, 4), (44, 4, 4) の 3 通りとなります。これと演算子の組み合わせにより数式を生成して、答えを求めてチェックします。
●データ型の定義
最初に数式を表す二分木を定義します。
リスト : 数式の定義 datatype code = Add | Sub | Mul | Div datatype expr = Lf of ratio | Node of code * expr * expr
code は演算子を表します。expr は数式を表す二分木です。数式の場合、数値は葉 (Lf) に格納され、演算子は節 (Node) に格納されます。値を正確に計算するため、数値には ratio を使います。
●数式の計算
数式の計算は再帰定義を使うと簡単です。次のリストを見てください。
リスト : 数式の計算
fun calc(Lf n) = n
| calc(Node (Add, x, y)) = calc(x) +/ calc(y)
| calc(Node (Sub, x, y)) = calc(x) -/ calc(y)
| calc(Node (Mul, x, y)) = calc(x) */ calc(y)
| calc(Node (Div, x, y)) = calc(x) // calc(y)
fun calc_expr(node) =
let
val n = calc(node) handle _ => zero
in
if isInteger(n) andalso n >=/ one andalso n <=/ ten then (
print_expr(node);
print " = ";
print_ratio(n);
print "\n"
) else ()
end
引数が葉の場合、関数 calc は数値 n をそのまま返します。節の場合は、関数 calc を再帰呼び出しして部分木の値を求め、それを code に対応する演算子で計算するだけです。calc は関数 calc_expr から呼び出します。
ratio は 0 で除算すると例外 Ratio_err を送出します。calc_expr では、これを handle 式で受け取ります。zero は大域変数で make_ratio(0, 1) で作成します。同様に one と ten も作成しておきます。計算結果 n が整数で 1 <= n <= 10 であれば式を関数 print_expr で出力します。
●数式の生成
次は数式を生成する処理を作ります。
リスト : 数式の生成
exception Make_expr_err
fun make_exprs4([op1, op2, op3]) =
[Node (op1, Node (op2, Lf four, Lf four), Node (op3, Lf four, Lf four)),
Node (op1, Lf four, Node (op2, Lf four, Node (op3, Lf four, Lf four))),
Node (op1, Node (op2, Node (op3, Lf four, Lf four), Lf four), Lf four),
Node (op1, Lf four, Node (op2, Node (op3, Lf four, Lf four), Lf four)),
Node (op1, Node (op2, Lf four, Node (op3, Lf four, Lf four)), Lf four)]
| make_exprs4(_) = raise Make_expr_err
(* 重複を許す順列 *)
fun solve4(n, perm) =
if n = 3 then
List.app (fn x => calc_expr(x)) (make_exprs4(rev perm))
else
List.app (fn x => solve4(n + 1, x::perm)) [Add, Sub, Mul, Div]
演算子の組み合わせは「重複を許す順列」と同じになります。関数 solve4 は演算子の順列を生成し、それを関数 make_exprs4 に渡します。make_exprs4 は 5 通りの数式をリストに格納して返すので、それを List.app で一つずつ取り出して calc_expr に渡して計算します。
数字が 3 つで演算子が 2 つの場合も、基本的には同じプログラムになります。ただし、数字は引数として渡します。あとは特に難しいところはないでしょう。詳細は プログラムリスト２ を参照してください。
●実行結果
さっそく実行してみたところ、全部で 100 通りの式が出力されました。このプログラムは重複解のチェックを行っていないので、多数の式が出力されることに注意してください。実行結果の一部を示します。
((4 - 4) + (4 / 4)) = 1 ((4 / 4) + (4 / 4)) = 2 (((4 + 4) + 4) / 4) = 3 (4 + (4 * (4 - 4))) = 4 (((4 * 4) + 4) / 4) = 5 (((4 + 4) / 4) + 4) = 6 (4 + (4 - (4 / 4))) = 7 ((4 + 4) + (4 - 4)) = 8 ((4 + 4) + (4 / 4)) = 9 ((44 - 4) / 4) = 10
この中で、10 になる式は (44 - 4) / 4 しかありません。数字 4 を 4 つと +, -, *, / () だけでは、10 になる式を作ることはできないことがわかります。
また、このプログラムはカッコをはずす処理を行っていないので、数式はちょっとわかりづらいですね。興味のある方は演算子の優先順位を考慮してカッコをはずすプログラムにも挑戦してみてください。
●プログラムリスト２
(*
* four.sml : Four Fours
*
* Copyright (C) 2012-2021 Makoto Hiroi
*
*)
(* 定数 *)
val zero = make_ratio(0, 1)
val one = make_ratio(1, 1)
val four = make_ratio(4, 1)
val ten = make_ratio(10, 1)
(* 数式 *)
datatype code = Add | Sub | Mul | Div
datatype expr = Lf of ratio | Node of code * expr * expr
(* 演算子の表示 *)
fun print_code(Add) = print " + "
| print_code(Sub) = print " - "
| print_code(Mul) = print " * "
| print_code(Div) = print " / "
(* 数式の表示 *)
fun print_expr(Lf n) = print_ratio(n)
| print_expr(Node (code, x, y)) = (
print "(";
print_expr(x);
print_code(code);
print_expr(y);
print ")"
)
(* 計算 *)
fun calc(Lf n) = n
| calc(Node (Add, x, y)) = calc(x) +/ calc(y)
| calc(Node (Sub, x, y)) = calc(x) -/ calc(y)
| calc(Node (Mul, x, y)) = calc(x) */ calc(y)
| calc(Node (Div, x, y)) = calc(x) // calc(y)
fun calc_expr(node) =
let
val n = calc(node) handle _ => zero
in
if isInteger(n) andalso n >=/ one andalso n <=/ ten then (
print_expr(node);
print " = ";
print_ratio(n);
print "\n"
) else ()
end
(* 数式の作成 *)
exception Make_expr_err
fun make_exprs4([op1, op2, op3]) =
[Node (op1, Node (op2, Lf four, Lf four), Node (op3, Lf four, Lf four)),
Node (op1, Lf four, Node (op2, Lf four, Node (op3, Lf four, Lf four))),
Node (op1, Node (op2, Node (op3, Lf four, Lf four), Lf four), Lf four),
Node (op1, Lf four, Node (op2, Node (op3, Lf four, Lf four), Lf four)),
Node (op1, Node (op2, Lf four, Node (op3, Lf four, Lf four)), Lf four)]
| make_exprs4(_) = raise Make_expr_err
fun make_exprs3(x1, x2, x3, [op1, op2]) =
[Node (op1, Lf x1, Node(op2, Lf x2, Lf x3)),
Node (op1, Node(op2, Lf x1, Lf x2), Lf x3)]
| make_exprs3(_, _, _, _) = raise Make_expr_err
(* 重複を許す順列 *)
fun solve4(n, perm) =
if n = 3 then
List.app (fn x => calc_expr(x)) (make_exprs4(rev perm))
else
List.app (fn x => solve4(n + 1, x::perm)) [Add, Sub, Mul, Div]
fun solve3(n, x1, x2, x3, perm) =
if n = 2 then
List.app (fn x => calc_expr(x)) (make_exprs3(x1, x2, x3, rev perm))
else
List.app (fn x => solve3(n + 1, x1, x2, x3, x::perm)) [Add, Sub, Mul, Div]
fun solve2(x1, x2) =
List.app (fn x => calc_expr(x))
(map (fn x => Node(x, Lf x1, Lf x2)) [Add, Sub, Mul, Div])
(* 実行 *)
fun solve_exec () =
let
val a = make_ratio(44, 1)
val b = make_ratio(444, 1)
in
solve4(0, []);
solve3(0, a, four, four, []);
solve3(0, four, a, four, []);
solve3(0, four, four, a, []);
solve2(four, b);
solve2(b, four);
solve2(a, a)
end
改訂 2021 年 5 月 29 日