[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[jfriends:00248] 「計算機プログラムの構造と解釈第二版」を読む会 第5回議事録
まなみ：たまには豪勢なホテルとか旅館でのんびりしたいなー...
紀香 ：あなた『一休.COM 』知らないの〜？ 会員も１０万人突破したのよ。
亜希子：なにそれ、一休さんとホテルとどう関係あるのよ？
美穂 ：高級ホテル・旅館の格安予約サイト！今入会するとプレゼント一杯よ。
＿早く登録してね＿ http://www.ikyu.com/present/present_ci.asp?cp=041 ＿
------------------------------------------------------------------------
やました です。
おそくなりすみません。
第5回 SICP読書会議事録です。
-- ここから -----------------------------------------------------
「計算機プログラムの構造と解釈第二版」を読む会 第5回議事録
出席者(敬称略)
金山 二郎
横山 晴庸
えんどう やすゆき
Nobuo Yamashita
読み手：金山
書記：Yamashita
p.71 から p73 まで
写像の入れ子
対の並びをつくる
「(enumerate-interval 1 n) で並びを生成し」、
「この並びの各iに対し、並び (enumerate-interval 1 (- i 1))
を写像する」
「後者の並びの各jについて対 (list i j) を生成する」
(accumulate append
nil
(map (lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
ひとつの種から並びを生成する手続きで proc を種のならびを写像すると
並びの並びができるので、これを繋いで、ひとつのならびにする。
これが flatmap
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))
順列を生成する
簡単のようで、0 から考えるとチョット考えこんでしまう？
でも再帰で考えれば簡単^^;
「S の順列を生成する計画はこうだ: S の各要素 x に対し、S - x の順列の
並びを再帰的に生成し、その前に x を連結する。すべての x についてこの
並びを組合せると、S のすべての順列ができる。」
プログラムは再帰だよなやっぱ。
(define (permutations s)
(if (null? s)
(list '())
(flatmap (lambda (x)
(map (lambda (p) (cons x p))
(permutations (remove x s))))
s)))
(define (remve item sequence)
(filter (lambda (x) (not (= x item)))
sequence))
問題2.40
「与えられた整数 n に対し、1 ≦ j ＜ i ≦ n の対 (i,j) の並びを生成する
手続き unique-pairs を定義せよ。unique-pairs を使って、上の
prime-sum-pairs の定義を簡単にせよ。
答
(define (unique-pairs n)
(flatmap (lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
(define (prime-sum-pairs n)
(map make-pair-sum
(filter prime-sum?
(unique-pairs n))))
問題2.41
「与えられた整数 n に対し、n より小さいか等しい相異る正の整数 i,j,k の
順序づけられた三つ組で、和が与えられた整数 s になるものをすべて求めよ。」
答
(define (unique-triples n)
(flatmap (lambda (i)
(flatmap (lambda (j)
(map (lambda (k) (list i j k))
(enumerate-interval 1 (- j 1))))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
(define (ex2.41 n s)
(filter (lambda (ls) (= s (accumulate + 0 ls))) (unique-triples n)))
この問題を変形して、「9 より小さいか等しい相異る n 個の正の整数の
順序づけられた組で、和があたえられた整数 s になるものをすべて
求めよ」としてプログラムを作ると、カックロというペンシルパズルを
解くときの便利なツールが作れます。ちょっとした演習問題ですねえ。
問題2.42
エイトクィーンパズル
この問題がなかなか解けませんでした。というか時間切れになってしまったので
もういちどやりなおしました。
(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 empty-board '())
(define (adjoin-position row col rest-of-queens)
(cons (list col row) rest-of-queens))
(define (safe? col positions)
(let* ((k-pair (car positions))
(rests (cdr positions))
(row (car (cdr k-pair))))
(accumulate both #t (map (lambda (pos)
(let ((rw (car (cdr pos)))
(cl (car pos)))
(and (not (= rw row))
(not (= (+ cl rw) (+ col row)))
(not (= (- cl rw) (- col row))))))
rests))))
(define (both p q)
(and p q))
-- ここまで -----------------------------------------------------
今回はコードを熟読し、その場で問題を解いてみたので、
あまり進みませんでしたが、こういうやりかたも良いではないか
との意見もありました。
--nobsun