開発環境
- OS X Lion - Apple(OS)
- Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
- プログラミング言語: MIT/GNU Scheme
計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.2(階層データ構造と閉包)、2.2.3(公認インターフェースとしての並び)の問題 2.40、問題 2.41、問題 2.42、問題 2.43を解いてみる。
その他参考書籍
問題 2.40
コード
sample.scm
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divide? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divide? a b)
(= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
(define (enumerate-interval low high)
(if (> low high)
(list)
(cons low (enumerate-interval (+ low 1) high))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (flatmap proc seq)
(accumulate append (list) (map proc seq)))
(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))
(define (make-pair-sum pair)
(list (car pair) (cadr pair) (+ (car pair) (cadr pair))))
(define (unique-pairs n)
(flatmap
(lambda (i)
(map (lambda (j) (list j i))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
(define (prime-sum-pairs n)
(filter prime-sum? (unique-pairs n)))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (prime-sum-pairs 6) ;Value 2: ((1 2) (2 3) (1 4) (3 4) (2 5) (1 6) (5 6))
問題 2.41
コード
sample.scm
(define (enumerate-interval low high)
(if (> low high)
(list)
(cons low (enumerate-interval (+ low 1) high))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (flatmap proc seq)
(accumulate append (list) (map proc seq)))
(define (remove item sequence)
(filter (lambda (x) (not (= x item)))
sequence))
(define (permutations-3 s)
(if (< (length s) 3)
(list)
(flatmap (lambda (i)
(flatmap (lambda (j)
(map (lambda (k)
(list i j k))
(remove j (remove i s))))
(remove i s)))
s)))
(define (sum-permutation n s)
(define (make-sum items)
(accumulate + 0 items))
(define (sum-s? items)
(= s (make-sum items)))
(filter sum-s?
(permutations-3 (enumerate-interval 1 n))))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (sum-permutation 5 6) ;Value 2: ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)) 1 ]=> (sum-permutation 5 7) ;Value 3: ((1 2 4) (1 4 2) (2 1 4) (2 4 1) (4 1 2) (4 2 1)) 1 ]=> (sum-permutation 5 8) ;Value 4: ((1 2 5) (1 3 4) (1 4 3) (1 5 2) (2 1 5) (2 5 1) (3 1 4) (3 4 1) (4 1 3) (4 3 1) (5 1 2) (5 2 1)) 1 ]=> (sum-permutation 5 9) ;Value 5: ((1 3 5) (1 5 3) (2 3 4) (2 4 3) (3 1 5) (3 2 4) (3 4 2) (3 5 1) (4 2 3) (4 3 2) (5 1 3) (5 3 1)) 1 ]=> (sum-permutation 5 10) ;Value 6: ((1 4 5) (1 5 4) (2 3 5) (2 5 3) (3 2 5) (3 5 2) (4 1 5) (4 5 1) (5 1 4) (5 2 3) (5 3 2) (5 4 1)) 1 ]=> (sum-permutation 50 10) ;Value 7: ((1 2 7) (1 3 6) (1 4 5) (1 5 4) (1 6 3) (1 7 2) (2 1 7) (2 3 5) (2 5 3) (2 7 1) (3 1 6) (3 2 5) (3 5 2) (3 6 1) (4 1 5) (4 5 1) (5 1 4) (5 2 3) (5 3 2) (5 4 1) (6 1 3) (6 3 1) (7 1 2) (7 2 1)) 1 ]=> (sum-permutation 50 20) ;Value 8: ((1 2 17) (1 3 16) (1 4 15) (1 5 14) (1 6 13) (1 7 12) (1 8 11) (1 9 10) (1 10 9) (1 11 8) (1 12 7) (1 13 6) (1 14 5) (1 15 4) (1 16 3) (1 17 2) (2 1 17) (2 3 15) (2 4 14) (2 5 13) (2 6 12) (2 7 11) (2 8 10) (2 10 8) (2 11 7) (2 12 6) (2 13 5) (2 14 4) (2 15 3) (2 17 1) (3 1 16) (3 2 15) (3 4 13) (3 5 12) (3 6 11) (3 7 10) (3 8 9) (3 9 8) (3 10 7) (3 11 6) (3 12 5) (3 13 4) (3 15 2) (3 16 1) (4 1 15) (4 2 14) (4 3 13) (4 5 11) (4 6 10) (4 7 9) (4 9 7) (4 10 6) (4 11 5) (4 13 3) (4 14 2) (4 15 1) (5 1 14) (5 2 13) (5 3 12) (5 4 11) (5 6 9) (5 7 8) (5 8 7) (5 9 6) (5 11 4) (5 12 3) (5 13 2) (5 14 1) (6 1 13) (6 2 12) (6 3 11) (6 4 10) (6 5 9) (6 9 5) (6 10 4) (6 11 3) (6 12 2) (6 13 1) (7 1 12) (7 2 11) (7 3 10) (7 4 9) (7 5 8) (7 8 5) (7 9 4) (7 10 3) (7 11 2) (7 12 1) (8 1 11) (8 2 10) (8 3 9) (8 5 7) (8 7 5) (8 9 3) (8 10 2) (8 11 1) (9 1 10) (9 3 8) (9 4 7) (9 5 6) (9 6 5) (9 7 4) (9 8 3) (9 10 1) (10 1 9) (10 2 8) (10 3 7) (10 4 6) (10 6 4) (10 7 3) (10 8 2) (10 9 1) (11 1 8) (11 2 7) (11 3 6) (11 4 5) (11 5 4) (11 6 3) (11 7 2) (11 8 1) (12 1 7) (12 2 6) (12 3 5) (12 5 3) (12 6 2) (12 7 1) (13 1 6) (13 2 5) (13 3 4) (13 4 3) (13 5 2) (13 6 1) (14 1 5) (14 2 4) (14 4 2) (14 5 1) (15 1 4) (15 2 3) (15 3 2) (15 4 1) (16 1 3) (16 3 1) (17 1 2) (17 2 1))
問題 2.42
コード
sample.scm
(define (enumerate-interval low high)
(if (> low high)
(list)
(cons low (enumerate-interval (+ low 1) high))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (flatmap proc seq)
(accumulate append (list) (map proc seq)))
(define empty-board (list))
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
; 座標を作成
(define (make-position row col)
(list row col))
(define (position-row position)
(car position))
(define (position-col position)
(cadr position))
(define (adjoin-position row col positions)
(append positions (list (make-position row col))))
(define (safe? k positions)
(define (get-position-k k positions)
(if (= k 1)
(car positions)
(get-position-k (- k 1) (cdr positions))))
(define k-position (get-position-k k positions))
(define k-row (position-row k-position))
(define (remove-position position positions)
(filter (lambda (x)
(not (equal? position x)))
positions))
(define rest-of-positions (remove-position k-position positions))
(and (null? (filter (lambda (position)
(= k-row (position-row position)))
rest-of-positions))
(null? (filter (lambda (position)
(= (- k (position-col position))
(abs (- k-row (car position)))))
rest-of-positions))))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (queens 1) ;Value 2: (((1 1))) 1 ]=> (queens 2) ;Value: () 1 ]=> (queens 3) ;Value: () 1 ]=> (queens 4) ;Value 3: (((2 1) (4 2) (1 3) (3 4)) ((3 1) (1 2) (4 3) (2 4))) 1 ]=> (queens 5) ;Value 4: (((1 1) (3 2) (5 3) (2 4) (4 5)) ((1 1) (4 2) (2 3) (5 4) (3 5)) ((2 1) (4 2) (1 3) (3 4) (5 5)) ((2 1) (5 2) (3 3) (1 4) (4 5)) ((3 1) (1 2) (4 3) (2 4) (5 5)) ((3 1) (5 2) (2 3) (4 4) (1 5)) ((4 1) (1 2) (3 3) (5 4) (2 5)) ((4 1) (2 2) (5 3) (3 4) (1 5)) ((5 1) (2 2) (4 3) (1 4) (3 5)) ((5 1) (3 2) (1 3) (4 4) (2 5))) 1 ]=> (queens 8) ;Value 5: (((1 1) (5 2) (8 3) (6 4) (3 5) (7 6) (2 7) (4 8)) ((1 1) (6 2) (8 3) (3 4) (7 5) (4 6) (2 7) (5 8)) ((1 1) (7 2) (4 3) (6 4) (8 5) (2 6) (5 7) (3 8)) ((1 1) (7 2) (5 3) (8 4) (2 5) (4 6) (6 7) (3 8)) ((2 1) (4 2) (6 3) (8 4) (3 5) (1 6) (7 7) (5 8)) ((2 1) (5 2) (7 3) (1 4) (3 5) (8 6) (6 7) (4 8)) ((2 1) (5 2) (7 3) (4 4) (1 5) (8 6) (6 7) (3 8)) ((2 1) (6 2) (1 3) (7 4) (4 5) (8 6) (3 7) (5 8)) ((2 1) (6 2) (8 3) (3 4) (1 5) (4 6) (7 7) (5 8)) ((2 1) (7 2) (3 3) (6 4) (8 5) (5 6) (1 7) (4 8)) ((2 1) (7 2) (5 3) (8 4) (1 5) (4 6) (6 7) (3 8)) ((2 1) (8 2) (6 3) (1 4) (3 5) (5 6) (7 7) (4 8)) ((3 1) (1 2) (7 3) (5 4) (8 5) (2 6) (4 7) (6 8)) ((3 1) (5 2) (2 3) (8 4) (1 5) (7 6) (4 7) (6 8)) ((3 1) (5 2) (2 3) (8 4) (6 5) (4 6) (7 7) (1 8)) ((3 1) (5 2) (7 3) (1 4) (4 5) (2 6) (8 7) (6 8)) ((3 1) (5 2) (8 3) (4 4) (1 5) (7 6) (2 7) (6 8)) ((3 1) (6 2) (2 3) (5 4) (8 5) (1 6) (7 7) (4 8)) ((3 1) (6 2) (2 3) (7 4) (1 5) (4 6) (8 7) (5 8)) ((3 1) (6 2) (2 3) (7 4) (5 5) (1 6) (8 7) (4 8)) ((3 1) (6 2) (4 3) (1 4) (8 5) (5 6) (7 7) (2 8)) ((3 1) (6 2) (4 3) (2 4) (8 5) (5 6) (7 7) (1 8)) ((3 1) (6 2) (8 3) (1 4) (4 5) (7 6) (5 7) (2 8)) ((3 1) (6 2) (8 3) (1 4) (5 5) (7 6) (2 7) (4 8)) ((3 1) (6 2) (8 3) (2 4) (4 5) (1 6) (7 7) (5 8)) ((3 1) (7 2) (2 3) (8 4) (5 5) (1 6) (4 7) (6 8)) ((3 1) (7 2) (2 3) (8 4) (6 5) (4 6) (1 7) (5 8)) ((3 1) (8 2) (4 3) (7 4) (1 5) (6 6) (2 7) (5 8)) ((4 1) (1 2) (5 3) (8 4) (2 5) (7 6) (3 7) (6 8)) ((4 1) (1 2) (5 3) (8 4) (6 5) (3 6) (7 7) (2 8)) ((4 1) (2 2) (5 3) (8 4) (6 5) (1 6) (3 7) (7 8)) ((4 1) (2 2) (7 3) (3 4) (6 5) (8 6) (1 7) (5 8)) ((4 1) (2 2) (7 3) (3 4) (6 5) (8 6) (5 7) (1 8)) ((4 1) (2 2) (7 3) (5 4) (1 5) (8 6) (6 7) (3 8)) ((4 1) (2 2) (8 3) (5 4) (7 5) (1 6) (3 7) (6 8)) ((4 1) (2 2) (8 3) (6 4) (1 5) (3 6) (5 7) (7 8)) ((4 1) (6 2) (1 3) (5 4) (2 5) (8 6) (3 7) (7 8)) ((4 1) (6 2) (8 3) (2 4) (7 5) (1 6) (3 7) (5 8)) ((4 1) (6 2) (8 3) (3 4) (1 5) (7 6) (5 7) (2 8)) ((4 1) (7 2) (1 3) (8 4) (5 5) (2 6) (6 7) (3 8)) ((4 1) (7 2) (3 3) (8 4) (2 5) (5 6) (1 7) (6 8)) ((4 1) (7 2) (5 3) (2 4) (6 5) (1 6) (3 7) (8 8)) ((4 1) (7 2) (5 3) (3 4) (1 5) (6 6) (8 7) (2 8)) ((4 1) (8 2) (1 3) (3 4) (6 5) (2 6) (7 7) (5 8)) ((4 1) (8 2) (1 3) (5 4) (7 5) (2 6) (6 7) (3 8)) ((4 1) (8 2) (5 3) (3 4) (1 5) (7 6) (2 7) (6 8)) ((5 1) (1 2) (4 3) (6 4) (8 5) (2 6) (7 7) (3 8)) ((5 1) (1 2) (8 3) (4 4) (2 5) (7 6) (3 7) (6 8)) ((5 1) (1 2) (8 3) (6 4) (3 5) (7 6) (2 7) (4 8)) ((5 1) (2 2) (4 3) (6 4) (8 5) (3 6) (1 7) (7 8)) ((5 1) (2 2) (4 3) (7 4) (3 5) (8 6) (6 7) (1 8)) ((5 1) (2 2) (6 3) (1 4) (7 5) (4 6) (8 7) (3 8)) ((5 1) (2 2) (8 3) (1 4) (4 5) (7 6) (3 7) (6 8)) ((5 1) (3 2) (1 3) (6 4) (8 5) (2 6) (4 7) (7 8)) ((5 1) (3 2) (1 3) (7 4) (2 5) (8 6) (6 7) (4 8)) ((5 1) (3 2) (8 3) (4 4) (7 5) (1 6) (6 7) (2 8)) ((5 1) (7 2) (1 3) (3 4) (8 5) (6 6) (4 7) (2 8)) ((5 1) (7 2) (1 3) (4 4) (2 5) (8 6) (6 7) (3 8)) ((5 1) (7 2) (2 3) (4 4) (8 5) (1 6) (3 7) (6 8)) ((5 1) (7 2) (2 3) (6 4) (3 5) (1 6) (4 7) (8 8)) ((5 1) (7 2) (2 3) (6 4) (3 5) (1 6) (8 7) (4 8)) ((5 1) (7 2) (4 3) (1 4) (3 5) (8 6) (6 7) (2 8)) ((5 1) (8 2) (4 3) (1 4) (3 5) (6 6) (2 7) (7 8)) ((5 1) (8 2) (4 3) (1 4) (7 5) (2 6) (6 7) (3 8)) ((6 1) (1 2) (5 3) (2 4) (8 5) (3 6) (7 7) (4 8)) ((6 1) (2 2) (7 3) (1 4) (3 5) (5 6) (8 7) (4 8)) ((6 1) (2 2) (7 3) (1 4) (4 5) (8 6) (5 7) (3 8)) ((6 1) (3 2) (1 3) (7 4) (5 5) (8 6) (2 7) (4 8)) ((6 1) (3 2) (1 3) (8 4) (4 5) (2 6) (7 7) (5 8)) ((6 1) (3 2) (1 3) (8 4) (5 5) (2 6) (4 7) (7 8)) ((6 1) (3 2) (5 3) (7 4) (1 5) (4 6) (2 7) (8 8)) ((6 1) (3 2) (5 3) (8 4) (1 5) (4 6) (2 7) (7 8)) ((6 1) (3 2) (7 3) (2 4) (4 5) (8 6) (1 7) (5 8)) ((6 1) (3 2) (7 3) (2 4) (8 5) (5 6) (1 7) (4 8)) ((6 1) (3 2) (7 3) (4 4) (1 5) (8 6) (2 7) (5 8)) ((6 1) (4 2) (1 3) (5 4) (8 5) (2 6) (7 7) (3 8)) ((6 1) (4 2) (2 3) (8 4) (5 5) (7 6) (1 7) (3 8)) ((6 1) (4 2) (7 3) (1 4) (3 5) (5 6) (2 7) (8 8)) ((6 1) (4 2) (7 3) (1 4) (8 5) (2 6) (5 7) (3 8)) ((6 1) (8 2) (2 3) (4 4) (1 5) (7 6) (5 7) (3 8)) ((7 1) (1 2) (3 3) (8 4) (6 5) (4 6) (2 7) (5 8)) ((7 1) (2 2) (4 3) (1 4) (8 5) (5 6) (3 7) (6 8)) ((7 1) (2 2) (6 3) (3 4) (1 5) (4 6) (8 7) (5 8)) ((7 1) (3 2) (1 3) (6 4) (8 5) (5 6) (2 7) (4 8)) ((7 1) (3 2) (8 3) (2 4) (5 5) (1 6) (6 7) (4 8)) ((7 1) (4 2) (2 3) (5 4) (8 5) (1 6) (3 7) (6 8)) ((7 1) (4 2) (2 3) (8 4) (6 5) (1 6) (3 7) (5 8)) ((7 1) (5 2) (3 3) (1 4) (6 5) (8 6) (2 7) (4 8)) ((8 1) (2 2) (4 3) (1 4) (7 5) (5 6) (3 7) (6 8)) ((8 1) (2 2) (5 3) (3 4) (1 5) (7 6) (4 7) (6 8)) ((8 1) (3 2) (1 3) (6 4) (2 5) (5 6) (7 7) (4 8)) ((8 1) (4 2) (1 3) (3 4) (6 5) (2 6) (7 7) (5 8)))
問題 2.43
上記の問題 2.42のflatmapの写像の入れ子の順だとqueen-colsが再帰的に呼び出される回数はboarder-size回、Reasonerのflatmapの写像の入れ子の順を変えたのだと、queen-colsが再帰的に呼び出される回数はboarder-size^border-size回となるから、flatmapの写像の入れ子の順を入れ替えたLouis Reasonerのプログラムの実行が遅くなる。元の問題2.42のプログラムがパズルを解く時間をTとすると、flatmapの写像の入れ子の順を入れ替えたLouisのプログラムがエイトクィーンパズルを解く時間は約T * border-size^(border-size - 1)、T * 8^7 (8^7 = 2097152)になる。
0 コメント:
コメントを投稿