Scheme - 手続きとその生成するプロセス(木構造再帰)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.2(木構造再帰)の問題1.11、1.12を解いてみる。

問題 1.10

再帰的プロセスの方法でfを計算する手続き。

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Friday April 13, 2012 at 9:02:52 AM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> 
(define (f n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1))
                 (* 2
                    (f (- n 2)))
                 (* 3
                    (f (- n 3)))))))

(f 1)
(f 2)
(f 3)
(f 4)
(f 5)
(f 6)
(f 7)
(f 8)
(f 9)
(f 10)
;Value: f

1 ]=> 
;Value: 1

1 ]=> 
;Value: 2

1 ]=> 
;Value: 4

1 ]=> 
;Value: 11

1 ]=> 
;Value: 25

1 ]=> 
;Value: 59

1 ]=> 
;Value: 142

1 ]=> 
;Value: 335

1 ]=> 
;Value: 796

1 ]=> 

;Value: 1892

1 ]=> (f 100)
^C
Interrupt option (? for help): 
;Quit!

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$

100は時間がかかったので中断。

反復的プロセスの方法でfを計算する手続き。

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Friday April 13, 2012 at 9:02:52 AM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> 
(define (f n)
  (if (< n 3)
      n
      (g 2 1 0 n)))

(define (g a b c count)
  (if (< count 3)
      a
      (g (+ a
            (* 2 b)
            (* 3 c))
         a
         b
         (- count 1))))

(f 1)
(f 2)
(f 3)
(f 4)
(f 5)
(f 6)
(f 7)
(f 8)
(f 9)
(f 10)
;Value: f

1 ]=> 
;Value: g

1 ]=> 
;Value: 1

1 ]=> 
;Value: 2

1 ]=> 
;Value: 4

1 ]=> 
;Value: 11

1 ]=> 
;Value: 25

1 ]=> 
;Value: 59

1 ]=> 
;Value: 142

1 ]=> 
;Value: 335

1 ]=> 
;Value: 796

1 ]=> 

;Value: 1892

1 ]=> (f 100)

;Value: 11937765839880230562825561449279733086

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$

反復的プロセスでは100でもすぐ評価できた。

問題 1.12

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Friday April 13, 2012 at 9:02:52 AM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> 
(define (pascal-triangle m n)
  (cond ((< m n) (* 0 m)) ; 存在しない場合は0に
        ((or (= n 0)
             (= m n)) 1)
        (else (+ (pascal-triangle (- m 1) (- n 1))
                 (pascal-triangle (- m 1) n)))))

(pascal-triangle 0 1)
(pascal-triangle 0 0)
(pascal-triangle 1 0)
(pascal-triangle 1 1)
(pascal-triangle 2 0)
(pascal-triangle 2 1)
(pascal-triangle 2 2)
(pascal-triangle 3 0)
(pascal-triangle 3 1)
(pascal-triangle 3 2)
(pascal-triangle 3 3)
(pascal-triangle 4 0)
(pascal-triangle 4 1)
(pascal-triangle 4 2)
(pascal-triangle 4 3)
(pascal-triangle 4 4)
(pascal-triangle 4 5)
;Value: pascal-triangle

1 ]=> 
;Value: 0

1 ]=> 
;Value: 1

1 ]=> 
;Value: 1

1 ]=> 
;Value: 1

1 ]=> 
;Value: 1

1 ]=> 
;Value: 2

1 ]=> 
;Value: 1

1 ]=> 
;Value: 1

1 ]=> 
;Value: 3

1 ]=> 
;Value: 3

1 ]=> 
;Value: 1

1 ]=> 
;Value: 1

1 ]=> 
;Value: 4

1 ]=> 
;Value: 6

1 ]=> 
;Value: 4

1 ]=> 
;Value: 1

1 ]=> 

;Value: 0

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$

問題 1.13

ϕ、φは方程式、

x^2 - x - 1 = 0

x^2 = x + 1

の解で、

x^(n+1) = x^n + x

となるから、

(ϕ^(n+1) - φ^(n+1)) / √5

=((ϕ^n + ϕ^(n - 1)) - (φ^n + φ^(n - 1))) / √5

=(ϕ^n - φ^n) / √5 + (ϕ^(n - 1) - φ^(n - 1)) / √5

= Fib(n) + Fib(n - 1) = Fib(n+1)

よって帰納的にnを整数とすれば、

Fib(n) = (ϕ^n - φ^n) / √5

が成り立つ。

|Fib(n) - ϕ^n / √5|

= |φ^n / √5|

< |φ / √5|

= |1/2 - 1/2√5|

< 1/2

よってFib(n)がϕ^n/√5に最も近い整数である。

(証明終)