練習問題 3.11 ①

① ユークリッドの互除法で二整数の第大公約数を求める関数 gcd

(* ユークリッドの互除法 *)
(*
ふたつの自然数 m と n の最大公約数を求める。ただし、m <= n
m = n の場合は、m が最大公約数。
m <> n の場合は、n - m と m の最大公約数。
*)
let rec gcd (m, n) =
    if m = n
    then m
    else
      if (m > n)
      then
        gcd(m - n, n)
      else
        gcd(n - m, m);;

(*  TEST  *)
let test1 = gcd (100, 25) = 25;;
let test2 = gcd (20, 20) = 20;;
let test3 = gcd (45, 12) = 3;;

Tweet