有理数
今回は簡単な例題として、有理数 (分数) を操作するクラスを作ってみましょう。
●有理数の定義
有理数 (Rational) は分子と分母を整数の組で表すと簡単に定義できます。次のリストを見てください。
リスト : 有理数の定義
type Ratio = class
val num: bigint
val den: bigint
// コンストラクタ
new (a: bigint, b: bigint) =
let (x, y) = normalize(a, b)
{num = x; den = y}
new (a: int, b: int) =
let (x, y) = normalize(bigint a, bigint b)
{num = x; den = y}
// ・・・略・・・
end
インスタンス変数 num が分子を表し、次の den が分母を表します。num と den の型は多倍長整数 (bigint) とし、コンストラクタ new で初期化します。有理数を生成するとき、関数 gcd で最大公約数を求めて、約分することに注意してください。それから、有理数の符号は分子に付けることにします。分母 b が負の場合は a と b の符号を反転します。
これらの処理を関数 normalize で行います。プログラムは次のようになります。
リスト : 正規化
// 最大公約数
let rec private gcd a b =
if b = 0I then a else gcd b (a % b)
// 正規化
let private normalize (a, b) =
let g = gcd (abs a) (abs b)
if b.Sign < 0 then
((-a) / g, (-b) / g)
else
(a / g, b / g)
bigint のプロパティ Sign の型は整数で、多倍長整数の符号 (-1, 0, 1) を表します。分母 b が負ならば、- 演算子で a と b の符号を反転します。
●算術演算子のオーバーロード
次は算術演算子 (+. -, *, /) をオーバーロードします。プログラムは次のようになります。
リスト : 算術演算子のオーバーロード
static member ( + ) (a: Ratio, b: Ratio) =
new Ratio(a.num * b.den + b.num * a.den, a.den * b.den)
static member ( - ) (a: Ratio, b: Ratio) =
new Ratio(a.num * b.den - b.num * a.den, a.den * b.den)
static member ( * ) (a: Ratio, b: Ratio) =
new Ratio(a.num * b.num, a.den * b.den)
static member ( / ) (a: Ratio, b: Ratio) =
new Ratio(a.num * b.den, a.den * b.num)
単純な分数の計算なので、難しいところはないでしょう。
●等値演算子の定義
次は等値演算子 (=, <>) を定義します。これは C# と同様にクラス System.Object のメソッド Equals をオーバーライドします。
リスト : 等値演算子のオーバーライド
// 等値演算子
override this.Equals(other: obj) =
let that = other :?> Ratio
this.num = that.num && this.den = that.den
// とても適当なので実際に使ってはいけない
override this.GetHashCode () =
((this.num <<< 7) ^^^ this.den).GetHashCode()
Object はすべてのクラスのスーパークラスで、クラスを定義するときにスーパークラスの指定を省略すると、暗黙のうちに Object が継承されます。F# では obj という省略形が用意されていて、どんな型でも obj にアップキャストすることができます。処理はとても簡単で、左辺 this と右辺 that の num が等しく、かつ den が等しければ真を返します。
Equals をオーバーライドするとき、メソッド GetHashCode もオーバーライドしないとワーニングが表示されます。ここでは num と den から多倍長整数を作り、その GetHashCode() の値を返しています。<<< と ^^^ はビット演算子です。x <<< n は x を左へ n ビットシフトします。x ^^^ y は x と y のビットごとの排他的論理和を求めます。
●比較演算子の定義
次は比較演算子 (<, >,<=, >=) を定義します。これも C# と同様に、インターフェース Sysmte.IComparable のメソッド CompareTo を実装するだけです。
リスト : 比較演算子の定義
interface IComparable with
member this.CompareTo(other: obj) =
let that = other :?> Ratio
(this.num * that.den).CompareTo(that.num * this.den)
CompareTo は左辺 this と右辺 that を比較します。この処理は this と that を通分し、その 2 つの値を bigint のメソッド CompareTo で比較するだけです。
●データ型の変換
最後に有理数を他のデータ型に変換する関数を作ります。
リスト : データ型の変換
// 整数か？
member this.isInteger() = this.den.IsOne
// 整数に変換
member this.toInteger() = this.num / this.den
// 実数に変換
member this.toFloat() = (float this.num) / (float this.den)
// 文字列
override this.ToString() =
if this.den.IsOne then this.num.ToString()
else this.num.ToString() + "/" + this.den.ToString()
整数に変換する場合、無条件に this.num / this.den を計算しています。整数の判定にはメソッド isInteger を使ってください。あとはとくに難しいところはないでしょう。
●実行例
それでは簡単な実行例を示します。
> #load "ratio.fsx";;
[読み込み中 /home/mhiroi/fsharp/ratio.fsx]
namespace FSI_0002
val private gcd:
a: System.Numerics.BigInteger -> b: System.Numerics.BigInteger
-> System.Numerics.BigInteger
val private normalize:
a: System.Numerics.BigInteger * b: System.Numerics.BigInteger
-> System.Numerics.BigInteger * System.Numerics.BigInteger
type Ratio =
interface System.IComparable
new: a: int * b: int -> Ratio + 1 オーバーロード
val num: bigint
val den: bigint
override Equals: other: obj -> bool
override GetHashCode: unit -> int
override ToString: unit -> string
member isInteger: unit -> bool
member toFloat: unit -> float
member toInteger: unit -> System.Numerics.BigInteger
static member ( * ) : a: Ratio * b: Ratio -> Ratio
static member (+) : a: Ratio * b: Ratio -> Ratio
static member (-) : a: Ratio * b: Ratio -> Ratio
static member (/) : a: Ratio * b: Ratio -> Ratio
> open ratio;;
> let a = new Ratio(1, 2);;
val a: Ratio = 1/2
> let b = new Ratio(1, 3);;
val b: Ratio = 1/3
> a + b;;
val it: Ratio = 5/6 {den = 6;
num = 5;}
> a - b;;
val it: Ratio = 1/6 {den = 6;
num = 1;}
> b - a;;
val it: Ratio = -1/6 {den = 6;
num = -1;}
> a * b;;
val it: Ratio = 1/6 {den = 6;
num = 1;}
> a / b;;
val it: Ratio = 3/2 {den = 2;
num = 3;}
> a / a;;
val it: Ratio = 1 {den = 1;
num = 1;}
> a.isInteger();;
val it: bool = false
> (a/a).isInteger();;
val it: bool = true
> a.toFloat();;
val it: float = 0.5
> b.toFloat();;
val it: float = 0.3333333333
> a.toInteger();;
val it: System.Numerics.BigInteger = 0 {IsEven = true;
IsOne = false;
IsPowerOfTwo = false;
IsZero = true;
Sign = 0;}
> (a/b).toInteger();;
val it: System.Numerics.BigInteger = 1 {IsEven = false;
IsOne = true;
IsPowerOfTwo = true;
IsZero = false;
Sign = 1;}
> (a/b).toFloat();;
val it: float = 1.5
正常に動作しているようです。興味のある方はいろいろ試してみてください。
●小町分数
それでは有理数 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 の場合で、参考文献 1 に掲載されています。ちなみに、3 つの分数の和が整数になる場合、その値は 1 しかありません。
プログラムは次のようになります。
リスト : 小町分数の解法
#load "ratio.fsx"
open ratio
// 要素の削除
let remove x xs = List.filter (fun y -> x <> y) xs
// 順列の生成
let rec permutation f nums perm =
if nums = [] then f (List.rev perm)
else
match perm with
[n2; n1] when n1 > n2 -> ()
| [n3; n2; _] when n2 > n3 -> ()
| _ -> List.iter (fun x -> permutation f (remove x nums) (x::perm)) nums
// 定数
let one = new Ratio(1, 1)
// 検定
let check1 = function
[n1;n2;n3;n4;n5;n6;n7;n8;n9] ->
let a = new Ratio(n1, n4 * 10 + n7)
let b = new Ratio(n2, n5 * 10 + n8)
let c = new Ratio(n3, n6 * 10 + n9)
let d = a + b + c
if (one / d).isInteger() then
printfn "%d/%d%d + %d/%d%d + %d/%d%d = %A" n1 n4 n7 n2 n5 n8 n3 n6 n9 d
else ()
| _ -> failwith "check error"
// 実行
let solver1 () = permutation check1 [1..9] []
基本的には単純な生成検定法ですが、分子の数字を n1 < n2 < n3 と限定することで、重複解を生成しないように工夫しています。この処理は枝刈りの効果もあります。関数 permutation の match 式で、n1 > n2 のときと、n2 > n3 のときに枝刈りを行っています。
関数 check1 は分数を生成して小町分数を計算します。その値を d とすると、1/d が整数であれば条件を満たします。関数 printfn で数式を出力します。
実行結果は次のようになります。
> open Komachib;; > solver1();; 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 通りになりました。
●小町分数 (2)
もうひとつ「小町分数」を出題しましょう。
下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。3 つの分数を足すと 1 / N になる配置を求めてください。
A D G 1 --- + --- + --- = --- B*C E*F H*I N 図 : 小町分数 (2)
このパズルの元ネタも値が 1 になる場合で、参考文献 1 に掲載されています。この問題で値が 1 / N (N は整数) になる場合は 1 と 2 の 2 通りしかないようです。
プログラムは「小町分数」を参考にすれば、簡単に作成することができます。
リスト : 小町分数 (2) の解法
// 検定２
let check2 (xs: int list) =
match xs with
[n1;n2;n3;n4;n5;n6;n7;n8;n9] ->
if n4 > n7 || n5 > n8 || n6 > n9 then ()
else
let a = new Ratio(n1, n4 * n7)
let b = new Ratio(n2, n5 * n8)
let c = new Ratio(n3, n6 * n9)
let d = a + b + c
if (one / d).isInteger() then
printfn "%d/%d*%d + %d/%d*%d + %d/%d*%d = %A" n1 n4 n7 n2 n5 n8 n3 n6 n9 d
else ()
| _ -> failwith "check2 error"
// 実行２
let solver2 () = permutation check2 [1..9] []
> open Komachib;; > solver2();; 1/2*4 + 5/3*6 + 7/8*9 = 1/2 1/3*6 + 5/8*9 + 7/2*4 = 1 val it: unit = ()
●単位分数の和
パズルではありませんが、分数のお話を紹介します。分子が 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 % m)
0 < (n % 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 の値は減少していきます。このアルゴリズムを F# でプログラムすると、次のようになります。
リスト : 分数を単位分数の和で表す
let rec bunsu m n =
if n % m = 0 then printfn "1/%d" (n / m)
else
let q = n / m + 1
printf "1/%d + " q
bunsu ((m * q) - n) (n * q)
F# らしく再帰定義を使っています。関数名は適当なので、ふさわしい名前に変更してください。あとは、アルゴリズムをそのままプログラムしただけなので、特に難しいところはないでしょう。それでは実行してみましょう。
> 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 = ()
このほかにも、単位分数の和で表す方法は何通りもあるわけで、この方法はその中のひとつにすぎません。古代エジプトではどのような方法で求めたのでしょうか。興味深いところです。
●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 通りとなります。これと演算子の組み合わせにより数式を生成して、答えを求めてチェックします。
●データ型の定義
最初に数式を表す二分木を定義します。
リスト : 数式の定義 type op = Add | Sub | Mul | Div type expr = Lf of ratio | Node of op * expr * expr
type op は演算子を表します。type expr は数式を表す二分木です。数式の場合、数値は葉 (Lf) に格納され、演算子は節 (Node) に格納されます。値を正確に計算するため、数値には Ratio を使います。
●数式の計算
数式の計算は再帰定義を使うと簡単です。次のリストを見てください。
リスト : 数式の計算
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 _ -> zero
if n.isInteger() && n >= one && n <= ten then (
print_expr node
printf " = "
printfn "%A" n
) else ()
引数が葉の場合、関数 calc は数値 n をそのまま返します。節の場合は、関数 calc を再帰呼び出しして部分木の値を求め、それを op に対応する演算子で計算するだけです。calc は関数 calc_expr から呼び出します。
Ratio は 0 で除算すると例外を送出します。calc_expr では、これを try 式で受け取ります。zero は大域変数で new Ratio(0, 1) で作成します。同様に one と ten も作成しておきます。計算結果 n が整数で 1 <= n <= 10 であれば式を関数 print_expr で出力します。
●数式の生成
次は数式を生成する処理を作ります。
リスト : 数式の生成
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)]
| _ -> failwith "make_exprs4 error"
// 重複を許す順列
let rec solver4 n perm =
if n = 3 then
List.iter (fun x -> calc_expr x) (make_exprs4 (List.rev perm))
else
List.iter (fun x -> solver4 (n + 1) (x::perm)) [Add; Sub; Mul; Div]
演算子の組み合わせは「重複を許す順列」と同じになります。関数 solver4 は演算子の順列を生成し、それを関数 make_exprs4 に渡します。make_exprs4 は 5 通りの数式をリストに格納して返すので、それを List.iter で一つずつ取り出して calc_expr に渡して計算します。
数字が 3 つで演算子が 2 つの場合も、基本的には同じプログラムになります。ただし、数字は引数として渡します。あとは特に難しいところはないでしょう。詳細は プログラムリスト３ を参照してください。
●実行結果
さっそく実行してみたところ、全部で 100 通りの式が出力されました。
> open Fours;; > solver ();; ((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 val it: unit = ()
このプログラムは重複解のチェックを行っていないので、多数の式が出力されることに注意してください。実行結果の一部を示します。
((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 になる式を作ることはできないことがわかります。
また、このプログラムはカッコをはずす処理を行っていないので、数式はちょっとわかりづらいですね。興味のある方は演算子の優先順位を考慮してカッコをはずすプログラムにも挑戦してみてください。
●参考文献, URL
- 芦ヶ原伸之,『超々難問数理パズル 解けるものなら解いてごらん』, 講談社, 2002
- 奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
- ４つの４ - Wikipedia
●プログラムリスト１
//
// ratio.fsx : 有理数クラス
//
// Copyright (C) 2022 Makoto Hiroi
//
module ratio
open System
// 最大公約数
let rec private gcd a b =
if b = 0I then a else gcd b (a % b)
// 正規化
let private normalize (a, b) =
let g = gcd (abs a) (abs b)
if b.Sign < 0 then
((-a) / g, (-b) / g)
else
(a / g, b / g)
// 有理数の定義
type Ratio = class
val num: bigint
val den: bigint
// コンストラクタ
new (a: bigint, b: bigint) =
let (x, y) = normalize(a, b)
{num = x; den = y}
new (a: int, b: int) =
let (x, y) = normalize(bigint a, bigint b)
{num = x; den = y}
// 整数か？
member this.isInteger() = this.den.IsOne
// 整数に変換
member this.toInteger() = this.num / this.den
// 実数に変換
member this.toFloat() = (float this.num) / (float this.den)
// 文字列
override this.ToString() =
if this.den.IsOne then this.num.ToString()
else this.num.ToString() + "/" + this.den.ToString()
// 算術演算子のオーバーロード
static member ( + ) (a: Ratio, b: Ratio) =
new Ratio(a.num * b.den + b.num * a.den, a.den * b.den)
static member ( - ) (a: Ratio, b: Ratio) =
new Ratio(a.num * b.den - b.num * a.den, a.den * b.den)
static member ( * ) (a: Ratio, b: Ratio) =
new Ratio(a.num * b.num, a.den * b.den)
static member ( / ) (a: Ratio, b: Ratio) =
new Ratio(a.num * b.den, a.den * b.num)
// 等値演算子
override this.Equals(other: obj) =
let that = other :?> Ratio
this.num = that.num && this.den = that.den
// とても適当なので実際に使ってはいけない
override this.GetHashCode () =
((this.num <<< 7) ^^^ this.den).GetHashCode()
// 比較演算子
interface IComparable with
member this.CompareTo(other: obj) =
let that = other :?> Ratio
(this.num * that.den).CompareTo(that.num * this.den)
end
●プログラムリスト２
//
// komachib.fsx : パズル「小町分数」
//
// Copyright (C) 2022 Makoto Hiroi
//
#load "ratio.fsx"
open ratio
// 要素の削除
let remove x xs = List.filter (fun y -> x <> y) xs
// 順列の生成
let rec permutation f nums perm =
if nums = [] then f (List.rev perm)
else
match perm with
[n2; n1] when n1 > n2 -> ()
| [n3; n2; _] when n2 > n3 -> ()
| _ -> List.iter (fun x -> permutation f (remove x nums) (x::perm)) nums
// 定数
let one = new Ratio(1, 1)
// 検定
let check1 = function
[n1;n2;n3;n4;n5;n6;n7;n8;n9] ->
let a = new Ratio(n1, n4 * 10 + n7)
let b = new Ratio(n2, n5 * 10 + n8)
let c = new Ratio(n3, n6 * 10 + n9)
let d = a + b + c
if (one / d).isInteger() then
printfn "%d/%d%d + %d/%d%d + %d/%d%d = %A" n1 n4 n7 n2 n5 n8 n3 n6 n9 d
else ()
| _ -> failwith "check error"
// 実行
let solver1 () = permutation check1 [1..9] []
// 検定２
let check2 (xs: int list) =
match xs with
[n1;n2;n3;n4;n5;n6;n7;n8;n9] ->
if n4 > n7 || n5 > n8 || n6 > n9 then ()
else
let a = new Ratio(n1, n4 * n7)
let b = new Ratio(n2, n5 * n8)
let c = new Ratio(n3, n6 * n9)
let d = a + b + c
if (one / d).isInteger() then
printfn "%d/%d*%d + %d/%d*%d + %d/%d*%d = %A" n1 n4 n7 n2 n5 n8 n3 n6 n9 d
else ()
| _ -> failwith "check2 error"
// 実行２
let solver2 () = permutation check2 [1..9] []
●プログラムリスト３
//
// fours.fsx : Fours Four
//
// Copyright (C) 2022 Makoto Hiroi
//
#load "ratio.fsx"
open ratio
// 定数
let zero = new Ratio( 0, 1)
let one = new Ratio( 1, 1)
let four = new Ratio( 4, 1)
let ten = new Ratio(10, 1)
// 数式
type op = Add | Sub | Mul | Div
type expr = Lf of Ratio | Node of op * expr * expr
// 演算子の表示
let print_op = function
Add -> printf " + "
| Sub -> printf " - "
| Mul -> printf " * "
| Div -> printf " / "
// 数式の表示
let rec print_expr = function
Lf n -> printf "%A" n
| Node (op, l, r) ->
printf "("; print_expr l; print_op op; print_expr r; printf ")"
// 計算
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 _ -> zero
if n.isInteger() && n >= one && n <= ten then (
print_expr node
printf " = "
printfn "%A" n
) else ()
// 数式の作成
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)]
| _ -> failwith "make_exprs4 error"
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)]
| _ -> failwith "make_exprs3 error"
// 重複を許す順列
let rec solver4 n perm =
if n = 3 then
List.iter (fun x -> calc_expr x) (make_exprs4 (List.rev perm))
else
List.iter (fun x -> solver4 (n + 1) (x::perm)) [Add; Sub; Mul; Div]
let rec solver3 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 -> solver3 (n + 1) x1 x2 x3 (x::perm)) [Add; Sub; Mul; Div]
let solver2 x1 x2 =
List.iter (fun x -> calc_expr x)
(List.map (fun x -> Node(x, Lf x1, Lf x2)) [Add; Sub; Mul; Div])
// 実行
let solver () =
let a = new Ratio(44, 1)
let b = new Ratio(444, 1)
solver4 0 []
solver3 0 a four four []
solver3 0 four a four []
solver3 0 four four a []
solver2 four b
solver2 b four
solver2 a a