有理数
今回は簡単な例題として、有理数 (分数) を操作するモジュールを作ってみましょう。
●有理数の定義
有理数 (Rational) は分子と分母を整数の組で表すと簡単に定義できます。次のリストを見てください。
リスト 1 : 有理数の定義 type ratio = Rat of int * int
最初の int が分子を表し、次の int が分母を表します。簡単な定義ですが、OCaml の整数は 64 bit CPU の処理系で -4611686018427387904 (-262) から 4611686018427387903 (262 - 1) までなので、このままでは実用的に使うことはできません。本格的な有理数モジュールを作るのであれば「多倍長整数」が必要になります。今回は簡単な例題ということで、このまま作ることにします。まあ、これでも簡単なパズルであれば解くことができるでしょう。
なお、OCaml には Num というモジュールがあり、整数 (int)、有理数 (ratio)、多倍長整数 (big_int) という 3 種類の数を、num というデータ型で統一的に扱うことができます。Num は標準モジュールではありませんが、OCaml version 4.05 であれば標準パッケージと一緒に配布されています。対話モードで使用するときは次のように nums.cma をロードしてください。
# #load "nums.cma";;
ただし、Num が同梱されているのは version 4.05 までで、version 4.06 以降になると Num は同梱されていないようです。最近は Num のかわりに Zarith というモジュールを使うことがおススメされているようです。
●有理数の生成
次は有理数を生成する関数 make_ratio を作ります。次のリストを見てください。
リスト 2 : 有理数の生成
(* 最大公約数 *)
let rec gcd a b =
if b = 0 then a else gcd b (a mod b)
(* データの生成 *)
let make_ratio a b =
if b = 0 then raise Division_by_zero
else
let f = if b < 0 then -1 else 1 and
z = gcd (abs a) (abs b) in
Rat ((f * a / z), (f * b / z))
make_ratio の引数 a が分子で、b が分母を表します。b が 0 の場合は例外 Division_by_zero を送出します。そうでなければ、Rat (a, b) を生成します。このとき、関数 gcd で最大公約数を求めて、約分することに注意してください。それから、有理数の符号は分子に付けることにします。分母 b が負の場合は a と b に -1 を掛け算します。
●算術演算子の定義
算術演算は make_ratio を使うと簡単に定義できます。このとき、算術演算を中置演算子として定義できると便利です。OCaml の場合、ある記号から始まるカリー化関数は中置演算子として用いることができます。中置演算子として使用できる記号の種類を示します。
先頭文字 = < > @ ^ | & + - * / $ % 他の文字 ! $ % & * + - . / : < = > ? @ ^ | ~
ただし、特定の記号列 (-> や <- など) は中置演算子として使うことはできません。なお、演算子の優先順位は先頭文字によって決められています。また、OCaml は前置演算子も定義することができます。詳細はリファレンスマニュアルをお読みください。
たとえば、整数の演算子 +, -, *, / はカッコで囲むとカリー化関数として用いることができます。
# (+);; - : int -> int -> int = <fun> # (+) 1 2;; - : int = 3
今回はモジュール Num に合わせて、算術演算子として +/, -/, */, // を使うことにしましょう。プログラムは次のようになります。
リスト 3 : 算術演算子の定義 let ( +/ ) (Rat (x1, y1)) (Rat (x2, y2)) = make_ratio (x1 * y2 + x2 * y1) (y1 * y2) let ( -/ ) (Rat (x1, y1)) (Rat (x2, y2)) = make_ratio (x1 * y2 - x2 * y1) (y1 * y2) let ( */ ) (Rat (x1, y1)) (Rat (x2, y2)) = make_ratio (x1 * x2) (y1 * y2) let ( // ) (Rat (x1, y1)) (Rat (x2, y2)) = make_ratio (x1 * y2) (x2 * y1)
演算子をカッコで囲み、カリー化関数として定義します。カッコと演算子の間に空白を入れていますが、(* とするとコメントの開始記号になるので注意してください。単純な分数の計算なので、難しいところはないでしょう。この場合、演算子の優先順位は +, -, *, / と同じです。
●比較演算子の定義
次は比較演算子を定義します。最初に関数 compare_ratio を作ります。
リスト 4 : 有理数の比較 let compare_ratio (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 を使うと比較演算子は簡単に定義できます。
リスト 5 : 比較演算子の定義 let ( =/ ) a b = compare_ratio a b = 0 let ( <>/ ) a b = compare_ratio a b <> 0 let ( </ ) a b = compare_ratio a b < 0 let ( >/ ) a b = compare_ratio a b > 0 let ( <=/ ) a b = compare_ratio a b <= 0 let ( >=/ ) a b = compare_ratio a b >= 0
算術演算子に合わせて、名前の最後に / を付けています。
●データ型の変換
最後に有理数を他のデータ型に変換する関数を作ります。
リスト 6 : データ型の変換 (* 整数の判定 *) let is_integer (Rat (_, y)) = y = 1 (* 整数に変換 *) let int_of_ratio (Rat (x, y)) = x / y (* 浮動小数点数に変換 *) let float_of_ratio (Rat (x, y)) = (float_of_int x) /. (float_of_int y) (* 文字列に変換 *) let string_of_ratio (Rat (x, y)) = if y = 1 then string_of_int x else (string_of_int x) ^ "/" ^ (string_of_int y) (* 表示 *) let print_ratio n = print_string (string_of_ratio n)
整数に変換する場合、無条件に x / y を計算しています。整数の判定には関数 is_integer を使ってください。あとはとくに難しいところはないでしょう。
●実行例
それでは簡単な実行例を示します。
# let a = make_ratio 1 2;; val a : ratio = Rat (1, 2) # let b = make_ratio 1 3;; val b : ratio = Rat (1, 2) # a +/ b;; - : ratio = Rat (5, 6) # a -/ b;; - : ratio = Rat (1, 6) # b -/ a;; - : ratio = Rat (-1, 6) # a */ b;; - : ratio = Rat (1, 6) # a // b;; - : ratio = Rat (3, 2) # a </ b;; - : bool = false # a >/ b;; - : bool = true
正常に動作しているようです。モジュールとして使うのであれば、きちんとしたテストを行ったほうがよいでしょう。
●モジュールの作成
それでは、テストを十分に行ったものとして、モジュールを作成しましょう。最初に mli ファイルを定義します。
リスト 7 : ratio.mli の内容 type ratio val make_ratio : int -> int -> ratio val is_integer : ratio -> bool val int_of_ratio : ratio -> int val float_of_ratio : ratio -> float val ( +/ ) : ratio -> ratio -> ratio val ( -/ ) : ratio -> ratio -> ratio val ( */ ) : ratio -> ratio -> ratio val ( // ) : ratio -> ratio -> ratio val compare_ratio : ratio -> ratio -> int val ( =/ ) : ratio -> ratio -> bool val ( <>/ ) : ratio -> ratio -> bool val ( </ ) : ratio -> ratio -> bool val ( >/ ) : ratio -> ratio -> bool val ( <=/ ) : ratio -> ratio -> bool val ( >=/ ) : ratio -> ratio -> bool val string_of_ratio : ratio -> string val print_ratio : ratio -> unit
データ型は type ratio だけ記述します。これで ratio の詳細を隠蔽することができます。関数 gcd は非公開としました。必要であれば、コメントを書いておくとよいでしょう。
あとはコンパイルするだけです。
$ ocamlc ratio.mli $ ocamlc -c ratio.ml
これでオブジェクトファイル ratio.cmo が生成されます。対話形式で利用する場合は、ocaml を起動するときに引数として ratio.cmo を与えるか、ディレクティブ #load で ratio.cmo をロードしてください。
●小町分数
それではモジュール Ratio を使ってパズルを解いてみましょう。
下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。3 つの分数を足すと 1 / N になる配置を求めてください。
A D G 1
--- + --- + --- = ---
B C E F H I N
ex) 3/27 + 6/54 + 9/81 = 1/3
3/54 + 6/72 + 9/81 = 1/4
図 : 小町分数
このパズルの元ネタは N = 1 の場合で、参考文献 [10-1] に掲載されています。ちなみに、3 つの分数の和が整数になる場合、その値は 1 しかありません。
プログラムは次のようになります。
リスト 8 : 小町分数の解法
open Ratio
(* 要素の削除 *)
let remove x xs = List.filter (fun y -> x <> y) xs
(* 定数 *)
let one = make_ratio 1 1
(* 検定 *)
let check = function
[n1; n2; n3; n4; n5; n6; n7; n8; n9] ->
let a = make_ratio n1 (n4 * 10 + n7) in
let b = make_ratio n2 (n5 * 10 + n8) in
let c = make_ratio n3 (n6 * 10 + n9) in
let d = a +/ b +/ c in
if is_integer (one // d) then begin
Printf.printf "%d/%d%d + %d/%d%d + %d/%d%d = " n1 n4 n7 n2 n5 n8 n3 n6 n9;
print_ratio d;
print_newline ()
end
| _ -> raise (Failure "check")
(* 順列の生成 *)
let rec make_perm nums perm =
if nums = [] then check (List.rev perm)
else match perm with
[n2; n1] when n1 > n2 -> ()
| [n3; n2; _] when n2 > n3 -> ()
| _ -> List.iter (fun x -> make_perm (remove x nums) (x::perm)) nums
(* 実行 *)
let () = make_perm [1;2;3;4;5;6;7;8;9] []
基本的には単純な生成検定法ですが、分子の数字を n1 < n2 < n3 と限定することで、重複解を生成しないように工夫しています。この処理は枝刈りの効果もあります。関数 make_perm の match 式で、n1 > n2 のときと、n2 > n3 のときに枝刈りを行っています。
関数 check は分数を生成して小町分数を計算します。その値を d とすると、1/d が整数であれば条件を満たします。関数 Printf.printf で数式を出力します。モジュール Printf にはＣ言語の標準ライブラリ関数 printf に相当する書式出力関数が定義されています。機能はＣ言語の printf とほぼ同じです。詳細は OCaml のリファレンスマニュアルをお読みください。
最後の let () = ... はＣ言語のメイン関数と同じ働きをします。ここで make_perm を呼び出します。コマンドラインの引数はモジュール Arg を使って、取得・解析することができます。
それでは、実行してみましょう。ファイル名を bunsu.ml とするとコンパイルは次のように行います。
$ ocamlc -c bunsu.ml $ ocamlc -o bunsu ratio.cmo bunsu.cmo
実行結果は次のようになります。
$ ./bunsu 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
結果は全部で 14 通りになりました。
ネイティブコードにコンパイルする場合は ocamlopt を使います。
$ ocamlopt -c ratio.ml $ ocamlopt -c bunsu.ml $ ocamlopt -o bunsu ratio.cmx bunsu.cmx
ocamlopt で生成されるオブジェクトファイルは cmx という拡張子になります。なお、cmx ファイルは対話形式の ocaml で利用することはできません。ご注意くださいませ。あとは cmx ファイルをリンクするだけです。これで単独で実行できる bunsu を作ることができます。
●小町分数 (2)
もうひとつ「小町分数」を出題しましょう。
下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。3 つの分数を足すと 1 / N になる配置を求めてください。
A D G 1 --- + --- + --- = --- B*C E*F H*I N 図 : 小町分数 (2)
このパズルの元ネタも値が 1 になる場合で、参考文献 [10-1] に掲載されています。この問題で値が 1 / N (N は整数) になる場合は 1 と 2 の 2 通りしかないようです。
プログラムは「小町分数」を参考にすれば、簡単に作成することができます。
リスト 9 : 小町分数 (2) の解法
open Ratio
(* 要素の削除 *)
let remove x xs = List.filter (fun y -> x <> y) xs
(* 定数 *)
let one = make_ratio 1 1
(* 検定 *)
let check = function
[n1; n2; n3; n4; n5; n6; n7; n8; n9] ->
if n4 > n7 || n5 > n8 || n6 > n9 then ()
else let a = make_ratio n1 (n4 * n7) in
let b = make_ratio n2 (n5 * n8) in
let c = make_ratio n3 (n6 * n9) in
let d = a +/ b +/ c in
if is_integer (one // d) then begin
Printf.printf "%d/%d*%d + %d/%d*%d + %d/%d*%d = " n1 n4 n7 n2 n5 n8 n3 n6 n9;
print_ratio d;
print_newline ()
end
| _ -> raise (Failure "check")
(* 順列の生成 *)
let rec make_perm nums perm =
if nums = [] then check (List.rev perm)
else match perm with
[n2; n1] when n1 > n2 -> ()
| [n3; n2; _] when n2 > n3 -> ()
| _ -> List.iter (fun x -> make_perm (remove x nums) (x::perm)) nums
(* 実行 *)
let () = make_perm [1;2;3;4;5;6;7;8;9] []
$ ocamlc -c bunsu2.ml $ ocamlc -o bunsu2 ratio.cmo bunsu2.cmo $ ./bunsu2 1/2*4 + 5/3*6 + 7/8*9 = 1/2 1/3*6 + 5/8*9 + 7/2*4 = 1
●単位分数の和
パズルではありませんが、分数のお話を紹介します。分子が 1 の分数を「単位分数」といいますが、単位分数の和は古代エジプト人がよく研究していたそうです。この話は M.Kamada さん からお聞きしたのですが、参考文献 [10-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 の値は減少していきます。このアルゴリズムを OCaml でプログラムすると、次のようになります。
リスト 10 : 分数を単位分数の和で表す
let rec bunsu m n =
if n mod m = 0 then Printf.printf "1/%d\n" (n / m)
else
let q = n / m + 1 in
Printf.printf "1/%d + " q;
bunsu ((m * q) - n) (n * q)
OCaml らしく再帰定義を使っています。関数名は適当なので、ふさわしい名前に変更してください。あとは、アルゴリズムをそのままプログラムしただけなので、特に難しいところはないでしょう。それでは実行してみましょう。
# bunsu 11 13;; 1/2 + 1/3 + 1/78 - : unit = () # bunsu 12 13;; 1/2 + 1/3 + 1/12 + 1/156 - : unit = () # bunsu 19 23;; 1/2 + 1/4 + 1/14 + 1/215 + 1/138460 - : unit = ()
このほかにも、単位分数の和で表す方法は何通りもあるわけで、この方法はその中のひとつにすぎません。古代エジプトではどのような方法で求めたのでしょうか。興味深いところです。
●Four Fours
Ratio を使ってもう一つパズルを解いてみましょう。Four Fours は数字を使ったパズルです。いろいろなルールがあるのですが、今回は簡易ルールで行きましょう。それでは問題です。
数字 4 を 4 つと +, - *, /, () を使って、答えが 1 から 10 になる式を作りなさい。数字は 4 だけではなく、44 や 444 のように合体させてもよい。また、- を符号として使うことは禁止する。
数字の 4 を 4 つ使うので Four Fours という名前なのだと思います。ところで、このルールでは 11 になる式を作ることができません。ほかのルール、たとえば小数点を付け加えると、次のように作ることができます。
4 / .4 + 4 / 4 = 11
今回は簡易ルールということで、小数点を使わないで 1 から 10 までの式を作ってください。まずは、ご自分の頭を使って解いてみましょう。気分転換や息抜きのときにでも考えてみてください。
●数式のパターン
それではプログラムを作りましょう。基本的には、数式を生成して答えをチェックするだけです。Four Four's の場合、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 通りとなります。これと演算子の組み合わせにより数式を生成して、答えを求めてチェックします。
●データ型の定義
最初に数式を表す二分木を定義します。
リスト 11 : 数式の定義 type op = Add | Sub | Mul | Div type expr = Lf of ratio | Node of op * expr * expr
type op は演算子を表します。type expr は数式を表す二分木です。数式の場合、数値は葉 (Lf) に格納され、演算子は節 (Node) に格納されます。値を正確に計算するため、数値には ratio を使います。
●数式の計算
数式の計算は再帰定義を使うと簡単です。次のリストを見てください。
リスト 12 : 数式の計算
let rec calc = function
Lf n -> n
| Node (Add, x, y) -> (calc x) +/ (calc y)
| Node (Sub, x, y) -> (calc x) -/ (calc y)
| Node (Mul, x, y) -> (calc x) */ (calc y)
| Node (Div, x, y) -> (calc x) // (calc y)
let calc_expr node =
let n = try calc node with Division_by_zero -> zero in
if is_integer n && n >=/ one && n <=/ ten then begin
print_expr node; print_string " = "; print_ratio n; print_newline ()
end
引数が葉の場合、関数 calc は数値 n をそのまま返します。節の場合は、関数 calc を再帰呼び出しして部分木の値を求め、それを op に対応する演算子で計算するだけです。calc は関数 calc_expr から呼び出します。
モジュール Ratio は 0 で除算すると例外 Division_by_zero を送出します。calc_expr では、これを try 式で受け取ります。zero は大域変数で make_ratio 0 1 で作成します。同様に one と ten も作成しておきます。計算結果 n が整数で 1 <= n <= 10 であれば式を関数 print_expr で出力します。
●数式の生成
次は数式を生成する処理を作ります。
リスト 13 : 数式の生成
let make_exprs4 = function
[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)]
| _ -> raise (Failure "make_exprs4")
(* 重複を許す順列 *)
let rec solve4 n perm =
if n = 3 then
List.iter (fun x -> calc_expr x) (make_exprs4 (List.rev perm))
else
List.iter (fun x -> solve4 (n + 1) (x::perm)) [Add; Sub; Mul; Div]
演算子の組み合わせは「重複を許す順列」と同じになります。関数 solve4 は演算子の順列を生成し、それを関数 make_expr に渡します。make_expr は 5 通りの数式をリストに格納して返すので、それを List.iter で一つずつ取り出して calc_expr に渡して計算します。
数字が 3 つで演算子が 2 つの場合も、基本的には同じプログラムになります。ただし、数字は引数として渡します。あとは特に難しいところはないでしょう。詳細は プログラムリスト２ を参照してください。
●実行結果
さっそく実行してみたところ、全部で 100 通りの式が出力されました。
$ ocamlc -c four4s.ml $ ocamlc -o four4s ratio.cmo four4s.cmo $ ./four4s ((4 + 4) + (4 - 4)) = 8 (4 + (4 + (4 - 4))) = 8 (((4 - 4) + 4) + 4) = 8 ・・・省略・・・ ((44 / 4) - 4) = 7 ((44 - 4) / 4) = 10 (44 / 44) = 1
このプログラムは重複解のチェックを行っていないので、多数の式が出力されることに注意してください。実行結果の一部を示します。
((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 になる式を作ることはできないことがわかります。
また、このプログラムはカッコをはずす処理を行っていないので、数式はちょっとわかりづらいですね。興味のある方は演算子の優先順位を考慮してカッコをはずすプログラムにも挑戦してみてください。
●補足 : モジュール Num の使い方
ここでモジュール Num の使い方を簡単に説明しておきます。型 num は次のように定義されています。
リスト : 型 num の定義 type num = | Int of int | Big_int of Big_int.big_int | Ratio of Ratio.ratio
Int は整数、Big_int が多倍長整数、Ratio が有理数 (分数) を表します。基本的な演算子と関数を以下に示します。
- val ( +/ ) : num -> num -> num
- val ( -/ ) : num -> num -> num
- val ( */ ) : num -> num -> num
- val ( // ) : num -> num -> num
- val succ_num : num -> num, (引数を +1 する)
- val pred_num : num -> num, (引数を -1 する)
- val ( **/ ) : num -> num -> -> num, (累乗)
- val ( =/ ) : num -> num -> bool
- val ( <>/ ) : num -> num -> bool
- val ( </ ) : num -> num -> bool
- val ( >/ ) : num -> num -> bool
- val ( <=/ ) : num -> num -> bool
- val ( >=/ ) : num -> num -> bool
- val string_of_num : num -> string, (num を文字列に変換)
- val num_of_string : string -> num, (文字列を num に変換)
計算結果が int の範囲を超えると自動的に Big_int に変換されます。また、Int や Big_int の除算が割り切れない場合は、自動的に Ratio に変換されます。簡単な実行例を示します。
# #load "nums.cma";; # open Num;; # let a = Int 1 // Int 2;; val a : Num.num = Ratio <abstr> # let b = Int 1 // Int 3;; val b : Num.num = Ratio <abstr> # string_of_num (a +/ b);; - : string = "5/6" # string_of_num (a -/ b);; - : string = "1/6" # string_of_num (a */ b);; - : string = "1/6" # string_of_num (a // b);; - : string = "3/2" # string_of_num (a // a);; - : string = "1" # let rec fact n = if n = 0 then (Int 1) else (Int n) */ fact (n - 1);; val fact : int -> Num.num = <fun> # string_of_num (fact 50);; - : string = "30414093201713378043612608166064768844377641568960512000000000000" # string_of_num (fact 100);; - : string = "93326215443944152681699238856266700490715968264381621468592963895 217599993229915608941463976156518286253697920827223758251185210916 864000000000000000000000000" # let fibo n = let rec fibo_sub n a b = if n = 0 then a else fibo_sub (n - 1) b (a +/ b) in fibo_sub n (Int 0) (Int 1);; val fibo : int -> Num.num = <fun> # string_of_num (fibo 50);; - : string = "12586269025" # string_of_num (fibo 100);; - : string = "354224848179261915075" # string_of_num (fibo 200);; - : string = "280571172992510140037611932413038677189525"
この他にも、Num にはいろいろ便利な関数が用意されています。興味のある方は Num のマニュアルをお読みください。
- Module Num, (日本語訳, OCaml.jp)
●参考文献, URL
[10-1] 芦ヶ原伸之,『超々難問数理パズル 解けるものなら解いてごらん』, 講談社, 2002[10-2] 奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
[10-3] ４つの４ - Wikipedia
●プログラムリスト１
(*
* ratio.ml : 有理数
*
* Copyright (C) 2008-2020 Makoto Hiroi
*)
(* 有理数の定義 *)
type ratio = Rat of int * int
(* 最大公約数 *)
let rec gcd a b =
if b = 0 then a else gcd b (a mod b)
(* データの生成 *)
let make_ratio a b =
if b = 0 then raise Division_by_zero
else
let f = if b < 0 then -1 else 1 and
z = gcd (abs a) (abs b) in
Rat ((f * a / z), (f * b / z))
(* 算術演算子の定義*)
let ( +/ ) (Rat (x1, y1)) (Rat (x2, y2)) =
make_ratio (x1 * y2 + x2 * y1) (y1 * y2)
let ( -/ ) (Rat (x1, y1)) (Rat (x2, y2)) =
make_ratio (x1 * y2 - x2 * y1) (y1 * y2)
let ( */ ) (Rat (x1, y1)) (Rat (x2, y2)) =
make_ratio (x1 * x2) (y1 * y2)
let ( // ) (Rat (x1, y1)) (Rat (x2, y2)) =
make_ratio (x1 * y2) (x2 * y1)
(* 有理数の比較*)
let compare_ratio (Rat (x1, y1)) (Rat (x2, y2)) =
x1 * y2 - x2 * y1
(* 比較演算子の定義 *)
let ( =/ ) a b = compare_ratio a b = 0
let ( <>/ ) a b = compare_ratio a b <> 0
let ( </ ) a b = compare_ratio a b < 0
let ( >/ ) a b = compare_ratio a b > 0
let ( <=/ ) a b = compare_ratio a b <= 0
let ( >=/ ) a b = compare_ratio a b >= 0
(* 整数の判定 *)
let is_integer (Rat (_, y)) = y = 1
(* 整数に変換 *)
let int_of_ratio (Rat (x, y)) = x / y
(* 浮動小数点数に変換 *)
let float_of_ratio (Rat (x, y)) = (float_of_int x) /. (float_of_int y)
(* 文字列に変換 *)
let string_of_ratio (Rat (x, y)) =
if y = 1 then string_of_int x
else (string_of_int x) ^ "/" ^ (string_of_int y)
(* 表示 *)
let print_ratio n = print_string (string_of_ratio n)
●プログラムリスト２
(*
* four4s.ml : Four Fours
*
* Copyright (C) 2008-2020 Makoto Hiroi
*)
open Ratio
(* 定数 *)
let zero = make_ratio 0 1
let one = make_ratio 1 1
let four = make_ratio 4 1
let ten = make_ratio 10 1
(* 数式 *)
type op = Add | Sub | Mul | Div
type expr = Lf of ratio | Node of op * expr * expr
(* 演算子の表示 *)
let print_op = function
Add -> print_string " + "
| Sub -> print_string " - "
| Mul -> print_string " * "
| Div -> print_string " / "
(* 数式の表示 *)
let rec print_expr = function
Lf n -> print_ratio n
| Node (op, x, y) ->
print_string "(";
print_expr x;
print_op op;
print_expr y;
print_string ")"
(* 計算 *)
let rec calc = function
Lf n -> n
| Node (Add, x, y) -> (calc x) +/ (calc y)
| Node (Sub, x, y) -> (calc x) -/ (calc y)
| Node (Mul, x, y) -> (calc x) */ (calc y)
| Node (Div, x, y) -> (calc x) // (calc y)
let calc_expr node =
let n = try calc node with Division_by_zero -> zero in
if is_integer n && n >=/ one && n <=/ ten then begin
print_expr node; print_string " = "; print_ratio n; print_newline ()
end
(* 数式の作成 *)
let make_exprs4 = function
[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)]
| _ -> raise (Failure "make_exprs4")
let make_exprs3 x1 x2 x3 = function
[op1; op2] ->
[Node (op1, Lf x1, Node(op2, Lf x2, Lf x3));
Node (op1, Node(op2, Lf x1, Lf x2), Lf x3)]
| _ -> raise (Failure "make_exprs3")
(* 重複を許す順列 *)
let rec solve4 n perm =
if n = 3 then
List.iter (fun x -> calc_expr x) (make_exprs4 (List.rev perm))
else
List.iter (fun x -> solve4 (n + 1) (x::perm)) [Add; Sub; Mul; Div]
let rec solve3 n x1 x2 x3 perm =
if n = 2 then
List.iter (fun x -> calc_expr x) (make_exprs3 x1 x2 x3 (List.rev perm))
else
List.iter (fun x -> solve3 (n + 1) x1 x2 x3 (x::perm)) [Add; Sub; Mul; Div]
let solve2 x1 x2 =
List.iter (fun x -> calc_expr x)
(List.map (fun x -> Node(x, Lf x1, Lf x2)) [Add; Sub; Mul; Div])
(* 実行 *)
let () =
let a = make_ratio 44 1 and
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