SML# - Tutorial/012.2 Diff

  • Added parts are displayed like this.
  • Deleted parts are displayed like this.

[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/012.1]] | [[ 次ページ |Tutorial/012.3]] ]
----
!問 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
この例から推測される通り,一般に,末尾再帰関数を設計するには,十分に一般的なループの状態を考え出さなくてはならない,その系統的な方法はない,これを行うのが,効率的なコードを書くことそのものである,
----
[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/012.1]] | [[ 次ページ |Tutorial/012.3]] ]