開発環境
- 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.4(べき乗)の問題1.16、1.17、1.18、1.19を解いてみる。
その他参考書籍
問題 1.16.
入出力結果(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 (expt b n)
(fast-expt b n 1))
(define (fast-expt b n a)
(cond ((= n 0) a)
((even? n) (fast-expt (square b) (/ n 2) a))
(else (fast-expt b (- n 1) (* a b)))))
(define (even? n)
(= (remainder n 2) 0))
(define (square n)
(* n n))
(expt 2 10)
(expt 2 1000)
(expt 5 10)
(expt 5 1000)
;Value: expt
1 ]=>
;Value: fast-expt
1 ]=>
;Value: even?
1 ]=>
;Value: square
1 ]=>
;Value: 1024
1 ]=>
;Value: 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
1 ]=>
;Value: 9765625
1 ]=>
;Value: 933263618503218878990089544723817169617091446371708024621714339795966910975775634454440327097881102359594989930324242624215487521354032394841520817203930756234410666138325150273995075985901831511100490796265113118240512514795933790805178271125415103810698378854426481119469814228660959222017662910442798456169448887147466528006328368452647429261829862165202793195289493607117850663668741065439805530718136320599844826041954101213229629869502194514609904214608668361244792952034826864617657926916047420065936389041737895822118365078045556628444273925387517127854796781556346403714877681766899855392069265439424008711973674701749862626690747296762535803929376233833981046927874558605253696441650390625
1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$
問題 1.17.
入出力結果(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 (* a b)
(cond ((= b 0) 0)
((even? b) (double (* a (halve b))))
(else (+ a (* a (- b 1))))))
(define (even? n)
(= (remainder n 2) 0))
(define (double n)
(+ n n))
(define (halve n)
(/ n 2))
(* 5 0)
(* 5 1)
(* 0 5)
(* 0 1)
(* 5 6)
(* 6 5)
(* 12345 67890)
(* 67890 12345)
;Value: *
1 ]=>
;Value: even?
1 ]=>
;Value: double
1 ]=>
;Value: halve
1 ]=>
;Value: 0
1 ]=>
;Value: 5
1 ]=>
;Value: 0
1 ]=>
;Value: 0
1 ]=>
;Value: 30
1 ]=>
;Value: 30
1 ]=>
;Value: 838102050
1 ]=>
;Value: 838102050
1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$
問題 1.18.
入出力結果(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 (* a b)
(cond ((= b 0) 0)
((even? b) (double (* a (halve b))))
(else (+ a (* a (- b 1))))))
(define (* a b)
(multiply a b 0))
(define (multiply a b product)
(cond ((= b 0) product)
((even? b) (multiply (double a) (halve b) product))
(else (multiply a (- b 1) (+ product a)))))
(define (even? n)
(= (remainder n 2) 0))
(define (double n)
(+ n n))
(define (halve n)
(/ n 2))
(* 5 0)
(* 5 1)
(* 0 5)
(* 0 1)
(* 5 6)
(* 6 5)
(* 12345 67890)
(* 67890 12345)
;Value: *
1 ]=>
;Value: *
1 ]=>
;Value: multiply
1 ]=>
;Value: even?
1 ]=>
;Value: double
1 ]=>
;Value: halve
1 ]=>
;Value: 0
1 ]=>
;Value: 5
1 ]=>
;Value: 0
1 ]=>
;Value: 0
1 ]=>
;Value: 30
1 ]=>
;Value: 30
1 ]=>
;Value: 838102050
1 ]=>
;Value: 838102050
1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$
問題 1.19.
(a, b)一回T_pqで変換。
(bq + aq + ap, bp + aq)
これをもう一回T_pqで変換。
((bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p, (bp + aq)p + (bq + aq + ap)q)
これを変形すると、
(b(2pq + q^2) + a(2pq + q^2) + a(q^2 + p^2), b(q^2 + p^2) + a(2pq + q^2))
よって変換T_pqを二回使うのは同じ形式のT_p'q'を一回使うのとその効果は同じ。そしてそのp'とq'は、
p' = q^2 + p^2, q' = 2pq + q^2
これを使って、Fibonacci数を対数的ステップ数で計算する手続きを完成させる。
入出力結果(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 (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (square p) (square q))
(+ (* 2 p q) (square q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (+ (* b p) (* a q)))
p
q
(- count 1)))))
(fib 0)
(fib 1)
(fib 2)
(fib 3)
(fib 4)
(fib 5)
(fib 6)
(fib 7)
(fib 8)
(fib 9)
(fib 10)
(fib 1000)
(fib 1001)
(fib 1002)
(fib 1003)
(fib 1004)
(fib 1005)
;Value: fib
1 ]=>
;Value: fib-iter
1 ]=>
;Value: 0
1 ]=>
;Value: 1
1 ]=>
;Value: 1
1 ]=>
;Value: 2
1 ]=>
;Value: 3
1 ]=>
;Value: 5
1 ]=>
;Value: 8
1 ]=>
;Value: 13
1 ]=>
;Value: 21
1 ]=>
;Value: 34
1 ]=>
;Value: 55
1 ]=>
;Value: 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
1 ]=>
;Value: 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
1 ]=>
;Value: 113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376
1 ]=>
;Value: 184127293109783088079359037429407725342927200190089245887691539263845629654342919049888378829204478636271423491563854616951582416154140320616683185749744683454267866160695248396179713539084659942285657496035877
1 ]=>
;Value: 297924218508143360336882819981631900915673130543819759032778173440536722190488904520034508163846345539055096533885943242814978469042830417586260359446115245634668393210192357419233828310479227982326069668668253
1 ]=>
;Value: 482051511617926448416241857411039626258600330733909004920469712704382351844831823569922886993050824175326520025449797859766560885196970738202943545195859929088936259370887605815413541849563887924611727164704130
1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$
0 コメント:
コメントを投稿