(12-2)[ML] 演習1解答例

問 1

以下に再帰的な定義と対応するSML#コード例を示す.

1 xをyで割った商を求める関数 shou(x,y)を引き算を使って定義せよ.

  • shou(x,y) = 0 (x < y の時)
  • shou(x,y) = 1 + shou (x -y, y) (x >= y の時)
fun shou(x,y) = if x < y then 0 else 1 + shou(x - y, y)

2 xをyで割ったあまりを求める関数 amari(x,y)引き算を使って定義せよ.

  • amari(x,y) = x (x < y の時)
  • amari(x,y) = amari (x -y, y) (x >= y の時)
fun amari(x,y) = if x < y then x else amari(x - y, y)

3 1からnまでの自然数のk乗の和を求める関数sigmaN(k,n)を書け.

  • sigmaN(k,0) = 0
  • sigmaN(k,n) = sigmaN (k, n - 1) + power(n, k)
fun sigmaN (k,0) = 0
  | sigmaN (k,n) = sigmaN (k, n - 1) + power(n, k)

4 初項A(0)がa公差がbの等差数列のn番目の項 A(a,b,n)を求める関数を書け.

  • A(a,b,0) = a
  • A(a,b,n) = b + A(a,b,n - 1)
fun A(a,b,0) = a
  | A(a,b,n) = b + A(a,b,n - 1)

5 初項B(0)がa公比がbの等比数列のn番目の項 B(a,b,n)を求める関数を書け.

  • B(a,b,0) = a
  • B(a,b,n) = b * B(a,b,n - 1)
fun B(a,b,0) = a
  | B(a,b,n) = b * B(a,b,n - 1)

6 初項C(0)がa漸化式 C(n) = b + c * C(n - 1)のn番目の項を求める関数を書け.

  • C(a,b,c,0) = a
  • C(a,b,c,n) = b + c * C(a,b,c,n - 1)
fun C(a,b,c,0) = a
  | C(a,b,c,n) = b + c * C(a,b,c,n - 1)

これら定義をファイルex1-1.smlに書きSML#コンパイラで実行した結果は以下の通り.(1-4で以前定義したpower関数を使っているので,ex1.smlファイルにその定義を加えてある.)

SML# 0.20 (2007-04-19 14:20:41)
use "ex1-1.sml";
val power = fn : int * int  -> int
val shou = fn : int * int  -> int
val amari = fn : int * int  -> int
val sigmaN = fn : int * int  -> int
val A = fn : int * int * int  -> int
val B = fn : int * int * int  -> int
val C = fn : int * int * int * int  -> int
# shou (10,4);
val it = 2 : int
# amari(10,4);
val it = 2 : int
# sigmaN(4,5);
val it = 979 : int
# A(2,3,4);
val it = 14 : int
# B(2,3,4);
val it = 162 : int
# C(2,3,4,5);
val it = 3071 : int
#

問2

SML#コード例を示す.1. xをyで割った商を求める関数 shou(x,y)を引き算を使って定義せよ.

fun shou(x,y) =
  let
    fun loop(s,i) =
      if i < y then s
      else loop(s + 1, i - y)
  in
    loop(0,x)
  end

2. xをyで割ったあまりを求める関数 amari(x,y)引き算を使って定義せよ.

fun amari(x,y) =
  let
    fun loop s =
      if s < y then s
      else loop (s - y)
  in
    loop x
  end

3. 1からnまでの自然数のk乗の和を求める関数sigmaN(k,n)を書け.

  fun sigmaN(k,n) =
    let
      fun loop(s,0) = s
        | loop(s, i) = loop(s + power(i,k), i - 1)
    in
      loop(0,n)
    end

4. 初項A(0)がa公差がbの等差数列のn番目の項 A(a,b,n)を求める関数を書け.

  fun A(a, b, n) =
    let
      fun loop(s, i) =
       if i >=n then s
       else loop(s + b , i + 1)
    in
      loop(a, 0)
    end

5. 初項B(0)がa公比がbの等比数列のn番目の項 B(a,b,n)を求める関数を書け.

  fun B(a, b, n) =
    let
      fun loop(s, i) =
       if i >=n then s
       else loop(s * b , i + 1)
    in
      loop(a, 0)
    end

6. 初項C(0)がa漸化式 C(n) = b + c * C(n - 1)のn番目の項を求める関数 C(a,b,c,n).

  fun C(a, b, c, n) =
    let
      fun loop(s, i) =
       if i >=n then s
       else loop(b + c * s, i + 1)
    in
      loop(a, 0)
    end

これら定義をファイルex1-2.smlに書きSML#コンパイラで実行した結果は以下の通り.(1-4で以前定義したpower関数を使っているので,ex1-2.smlファイルにその定義を加えてある.)

SML# 0.20 (2007-04-19 14:20:41)
use "ex1-2.sml";
val power = fn : int * int  -> int
val shou = fn : int * int  -> int
val amari = fn : int * int  -> int
val sigmaN = fn : int * int  -> int
val A = fn : int * int * int  -> int
val B = fn : int * int * int  -> int
val C = fn : int * int * int * int  -> int
# shou (10,4);
val it = 2 : int
# amari(10,4);
val it = 2 : int
# sigmaN(4,5);
val it = 979 : int
# A(2,3,4);
val it = 14 : int
# B(2,3,4);
val it = 162 : int
# C(2,3,4,5);
val it = 3071 : int
#

問3

fun fib 0 = 1
  | fib 1 = 1
  | fib n = fib (n - 1) + fib (n - 2)

問4

この問題は,ループの中間の値をうまく設計しないときれいに解けない,以下が,その一つの戦略である,

  • 途中の値を持つ変数:A,B
  • 状態変数:i
  • 途中の状態
    • A(i) = fib(n - i)
    • B(i) = fib(n - (i - 1))
  • 初期状態(最初のloopの呼び出しの値)
    • A(n) = fib(n - n) = fib 0 = 1
    • B(n) = fib(n - (n - 1)) = fib 1 = 1
  • 状態の更新方法(末尾コールの仕方)
    • 以下の等式が成り立つことに注意
      • A(i - 1) = A(i) + B(i)
      • B(i - 1) = A(i)
  • 最終状態:i = 0;このときA = fib(n - 0) = fib n

以上から,以下の様なループコードが書ける,

 fun fib n =
   let
      fun loop (A, B, 0) = A
        | loop (A, B, i) = loop(A + B, A, i - 1)
   in
     loop(1,1,n)
   end

この例から推測される通り,一般に,末尾再帰関数を設計するには,十分に一般的なループの状態を考え出さなくてはならない,その系統的な方法はない,これを行うのが,効率的なコードを書くことそのものである,


[ トップ | 目次 | 前ページ | 次ページ ]