開発環境
- 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.3(高階手続きによる抽象)、1.3.1(引数としての手続き)の問1.31、1.32、1.33を解いてみる。
その他参考書籍
問題 1.31.
a.(再帰的プロセス)
コード
sample.scm
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
(define (inc x) (+ x 1))
(define (identity x) x)
(define (factorial n)
(product identity 1 inc n))
(define (pi-product a b)
(define (pi-term x)
(/ (* (+ x 1) (+ x 3))
(square (+ x 2))))
(define (pi-next x)
(+ x 2))
(* 4.0 (product pi-term a pi-next b)))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (factorial 0) ;Value: 1 1 ]=> (factorial 1) ;Value: 1 1 ]=> (factorial 2) ;Value: 2 1 ]=> (factorial 10) ;Value: 3628800 1 ]=> (pi-product 1 1) ;Value: 3.5555555555555554 1 ]=> (pi-product 1 10) ;Value: 3.2751010413348074 1 ]=> (pi-product 1 100) ;Value: 3.1570301764551676 1 ]=> (pi-product 1 1000) ;Value: 3.1431607055322663 1 ]=> (pi-product 1 10000) ;Value: 3.1417497057380523
b.(反復的プロセス)
コード
sample.scm
(define (product term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))
(define (inc x) (+ x 1))
(define (identity x) x)
(define (factorial n)
(product identity 1 inc n))
(define (pi-product a b)
(define (pi-term x)
(/ (* (+ x 1) (+ x 3))
(square (+ x 2))))
(define (pi-next x)
(+ x 2))
(* 4.0 (product pi-term a pi-next b)))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (factorial 0) ;Value: 1 1 ]=> (factorial 1) ;Value: 1 1 ]=> (factorial 2) ;Value: 2 1 ]=> (factorial 10) ;Value: 3628800 1 ]=> (pi-product 1 1) ;Value: 3.5555555555555554 1 ]=> (pi-product 1 10) ;Value: 3.2751010413348074 1 ]=> (pi-product 1 100) ;Value: 3.1570301764551676 1 ]=> (pi-product 1 1000) ;Value: 3.1431607055322663 1 ]=> (pi-product 1 10000) ;Value: 3.1417497057380523
問題 1.32.
a.(再帰的プロセス)
コード
sample.scm
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term (next a) next b))))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(define (sum-cubes a b)
(sum cube a inc b))
(define (sum-integers a b)
(sum identity a inc b))
(define (factorial n)
(product identity 1 inc n))
(define (pi-product a b)
(define (pi-term x)
(/ (* (+ x 1) (+ x 3))
(square (+ x 2))))
(define (pi-next x)
(+ x 2))
(* 4.0 (product pi-term a pi-next b)))
(define (cube x) (* x x x))
(define (inc x) (+ x 1))
(define (identity x) x)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (sum-cubes 1 10) ;Value: 3025 1 ]=> (sum-integers 1 10) ;Value: 55 1 ]=> (factorial 0) ;Value: 1 1 ]=> (factorial 1) ;Value: 1 1 ]=> (factorial 2) ;Value: 2 1 ]=> (factorial 10) ;Value: 3628800 1 ]=> (pi-product 1 1) ;Value: 3.5555555555555554 1 ]=> (pi-product 1 10) ;Value: 3.2751010413348074 1 ]=> (pi-product 1 100) ;Value: 3.1570301764551676 1 ]=> (pi-product 1 1000) ;Value: 3.1431607055322663
b.(反復的プロセス)
コード
sample.scm
(define (accumulate combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(define (sum-cubes a b)
(sum cube a inc b))
(define (sum-integers a b)
(sum identity a inc b))
(define (factorial n)
(product identity 1 inc n))
(define (pi-product a b)
(define (pi-term x)
(/ (* (+ x 1) (+ x 3))
(square (+ x 2))))
(define (pi-next x)
(+ x 2))
(* 4.0 (product pi-term a pi-next b)))
(define (cube x) (* x x x))
(define (inc x) (+ x 1))
(define (identity x) x)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (sum-cubes 1 10) ;Value: 3025 1 ]=> (sum-integers 1 10) ;Value: 55 1 ]=> (factorial 0) ;Value: 1 1 ]=> (factorial 1) ;Value: 1 1 ]=> (factorial 2) ;Value: 2 1 ]=> (factorial 10) ;Value: 3628800 1 ]=> (pi-product 1 1) ;Value: 3.5555555555555554 1 ]=> (pi-product 1 10) ;Value: 3.2751010413348074 1 ]=> (pi-product 1 100) ;Value: 3.1570301764551676 1 ]=> (pi-product 1 1000) ;Value: 3.1431607055322663
問題 1.33.
コード
sample.scm
(define (filtered-accumulate combiner null-value term a next b filter)
(define (iter a result)
(cond ((> a b) result)
((filter a) (iter (next a) (combiner (term a) result)))
(else (iter (next a) result))))
(iter a null-value))
; 区間a, bの素数の二乗の和
(define (sum-prime-squares a b)
(filtered-accumulate + 0 square a inc b prime?))
; nと互いの素で、nより小さい正の整数の積
(define (product-relatively-primes n)
(define (filter a) (relatively-prime? a n))
(if (= n 1)
0
(filtered-accumulate * 1 identity 1 inc (- n 1) filter)))
(define (prime? n)
(if (= n 1)
false
(= n (smallest-divisor n))))
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0))
(define (relatively-prime? a b)
(= (gcd a b) 1))
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
; 全問までの手続きを抽象化した手続きで書き名をして、抽象化が正しいか確認
(define (accumulate combiner null-value term a next b)
(define (filter x) true)
(filtered-accumulate combiner null-value term a next b filter))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(define (sum-cubes a b)
(sum cube a inc b))
(define (sum-integers a b)
(sum identity a inc b))
(define (factorial n)
(product identity 1 inc n))
(define (pi-product a b)
(define (pi-term x)
(/ (* (+ x 1) (+ x 3))
(square (+ x 2))))
(define (pi-next x)
(+ x 2))
(* 4.0 (product pi-term a pi-next b)))
(define (cube x) (* x x x))
(define (inc x) (+ x 1))
(define (identity x) x)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (sum-cubes 1 10) ;Value: 3025 1 ]=> (sum-integers 1 10) ;Value: 55 1 ]=> (factorial 0) ;Value: 1 1 ]=> (factorial 1) ;Value: 1 1 ]=> (factorial 2) ;Value: 2 1 ]=> (factorial 10) ;Value: 3628800 1 ]=> (pi-product 1 1) ;Value: 3.5555555555555554 1 ]=> (pi-product 1 10) ;Value: 3.2751010413348074 1 ]=> (pi-product 1 100) ;Value: 3.1570301764551676 1 ]=> (pi-product 1 1000) ;Value: 3.1431607055322663 1 ]=> (sum-prime-squares 8 10) ;Value: 0 1 ]=> (sum-prime-squares 1 2) ;Value: 4 1 ]=> (sum-prime-squares 1 5) ;Value: 38 1 ]=> (sum-prime-squares 1 6) ;Value: 38 1 ]=> (sum-prime-squares 1 10) ;Value: 87 1 ]=> (sum-prime-squares 5 20) ;Value: 1014 1 ]=> (sum-prime-squares 1 20) ;Value: 1027 1 ]=> (sum-prime-squares 1 100) ;Value: 65796 1 ]=> (product-relatively-primes 1) ;Value: 0 1 ]=> (product-relatively-primes 2) ;Value: 1 1 ]=> (product-relatively-primes 3) ;Value: 2 1 ]=> (product-relatively-primes 4) ;Value: 3 1 ]=> (product-relatively-primes 5) ;Value: 24 1 ]=> (product-relatively-primes 6) ;Value: 5 1 ]=> (product-relatively-primes 7) ;Value: 720 1 ]=> (product-relatively-primes 8) ;Value: 105 1 ]=> (product-relatively-primes 9) ;Value: 2240 1 ]=> (product-relatively-primes 10) ;Value: 189 1 ]=> (product-relatively-primes 100) ;Value: 426252881942771063138176712755660145456313428952105524817872601
0 コメント:
コメントを投稿