Hatena::Groupcsnagoya-sicp

toyoshiのSICP宿題帖

2009-04-12

2.17

08:40 | はてなブックマーク - 2.17 - toyoshiのSICP宿題帖

なんかもっとエレガントな方法がありそう・・・

(define (last-pair l)
  (if (null? (cdr l))
      l
      (last-pair (cdr l))))

2009-04-11

2.17

| 03:10 | はてなブックマーク - 2.17 - toyoshiのSICP宿題帖

なんかもっとエレガントな方法がありそう・・・

(define (last-pair l)
  (if (null? (cdr l))
      (l)
      (last-pair (cdr l))))

2.12

| 23:53 | はてなブックマーク - 2.12 - toyoshiのSICP宿題帖

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))

(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

(define (percent i)
  (* (/ (width i) (center i)) 100))

(define (make-center-percent c p)
  (make-interval (+ c (* c (/ p 100))) (- c (* c (/ p 100)))))

2.11

| 22:23 | はてなブックマーク - 2.11 - toyoshiのSICP宿題帖

1回だけ2回計算するのは(-a,+b) (-c,+d)のとき

-a*+dと+b*-cのどちらが大きいかがわからないため

検証用のコードはhttp://csnagoya-sicp.g.hatena.ne.jp/clairvy/20090411/sicp_ex_2_11から拝借しました。

(define (make-interval a b) (cons a b))

(define (upper-bound i)
  (cdr i))

(define (lower-bound i)
  (car i))

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
		 (+ (upper-bound x) (upper-bound y))))


(define (mul-interval-org x y)
  (let* ((l1 (lower-bound x))
	(u1 (upper-bound x))
	(l2 (lower-bound y))
	(u2 (upper-bound y))
	(p1 (* l1 l2))
	(p2 (* l1 u2))
	(p3 (* u1 l2))
	(p4 (* u1 u2)))
    (make-interval (min p1 p2 p3 p4) (max p1 p2 p3 p4))))

(define (mul-interval x y)
  (let* ((l1 (lower-bound x))
	(u1 (upper-bound x))
	(l2 (lower-bound y))
	(u2 (upper-bound y))
	(p1 (* l1 l2))
	(p2 (* l1 u2))
	(p3 (* u1 l2))
	(p4 (* u1 u2)))
    (cond ((>= l1 0)
	   (cond ((>= l2 0) (make-interval p1 p4))
		 ((< u2 0) (make-interval p3 p2))
		 (else (make-interval p3 p4))))
	  ((< u1 0)
	   (cond ((>= l2 0) (make-interval p2 p3))
		 ((< u2 0) (make-interval p4 p1))
		 (else (make-interval p2 p1))))
	  (else
	   (cond ((>= l2 0) (make-interval p2 p4))
		 ((< u2 0) (make-interval p3 p1))
		 (else (make-interval (min p2 p3) p4)))))))
  
(define i1 (make-interval 1 2))
(define i2 (make-interval -1 1))
(define i3 (make-interval -2 -1))

(define (display-interval-org-and-new x y)
  (define (display-interval-2d i)
    (format #t "[~@d, ~@d]" (lower-bound i) (upper-bound i)))
  (define (display-prompt x y)
    (display-interval-2d x)
    (display " * ")
    (display-interval-2d y)
    (display " = "))
  (let ((org-result (mul-interval-org x y))
        (new-result (mul-interval x y)))
    (display-prompt x y)
    (display-interval-2d new-result)
    (if (equal? org-result new-result)
        (display " org and new result are same"))
    (newline)))

(display-interval-org-and-new i1 i1)
(display-interval-org-and-new i1 i2)
(display-interval-org-and-new i1 i3)
(display-interval-org-and-new i2 i1)
(display-interval-org-and-new i2 i2)
(display-interval-org-and-new i2 i3)
(display-interval-org-and-new i3 i1)
(display-interval-org-and-new i3 i2)
(display-interval-org-and-new i3 i3)

2.9

19:19 | はてなブックマーク - 2.9 - toyoshiのSICP宿題帖

二つの区間を(L1,U1),(L2,U2)とした場合

それぞれの区間の幅は

\frac{(U1-L1)}{2} + \frac{(U2-L2)}{2} = \frac{U1+U2-L1-L2}{2}

区間の和の計算はAlyssaの定義より

( (L1 + L2),(U1 + U2))なので、これの幅を計算すると

\frac{(U1+U2)-(L1+L2)}{2} =  \frac{U1+U2-L1-L2}{2}

となり、二つの区間の和は区間の幅だけの関数であるといえる

乗算、除算が上記にあてはまらない例は

(1,1),(2,2)のときなど

2.6 チャーチ数

| 18:32 | はてなブックマーク - 2.6 チャーチ数 - toyoshiのSICP宿題帖

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one
  (lambda (f) (lambda (x) (f x))))

(define two
  (lambda (f) (lambda (x) (f(f x)))))

(define (+ n1 n2)
  (lambda (f) (lambda (x) ((n1 f) ((n2 f) x)))))

加算はできないとおもったけど、add-1は1を足してるってことから、それを変形することでできました。

2008-11-19

1.20 GCDのやつ

| 02:09 | はてなブックマーク - 1.20 GCDのやつ - toyoshiのSICP宿題帖

(gcd 206 40)
(gcd 40 (remainder 206 40)))
(gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))

正規順序で実際に実行されるremainderは・・・

(gcd (remainder T (ST))) (remainder (ST) (remainder T (ST)))))

4種類なので4回ですね。

作用的順序の場合はGCDが呼ばれた回数と同じなので、これも4回ですね。

2008-11-18

1.18 乗算の反復的プロセス

| 05:17 | はてなブックマーク - 1.18 乗算の反復的プロセス - toyoshiのSICP宿題帖

id:clairvyさんのと少し違うけど、たぶんこれも反復的になってるはず。

なんとか一人で考えられてほっとした

(define (* a b)
  (*-iter a b a))

(define (*-iter product b a)
  (cond ((= b 1) product)
	((even? b) (*-iter (+ a product) (halve b) (double a)))
	(else (*-iter (+ a product) (- b 1) a))))


(define (even? n)
  (= (remainder n 2) 0))

(define (double x)
  (+ x x))

(define (halve x)
  (/ x 2))

1.17 *の再帰的実装

03:58 | はてなブックマーク - 1.17 *の再帰的実装 - toyoshiのSICP宿題帖

再帰プロセスの方はわかるんだけどなー

1.18が不安

(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 x)
  (+ x x))

(define (halve x)
  (/ x 2))

clairvyclairvy2008/11/19 06:13product + (b x a) が不変量だとすると.
(a + product) + {(b / 2) x (a x 2)} と,
(a + product) + {(b - 1) x a} は,両方とも不変量?
それともただのtypo?

2008-11-09

1.12 パスカルの三角形

00:42 | はてなブックマーク - 1.12 パスカルの三角形 - toyoshiのSICP宿題帖

(define (pascal x y)
  (cond ((= x 1) 1)
	((= x y) 1)
	(else (+ (pascal (- x 1) (- y 1)) (pascal x (- y 1))))))

再帰プロセスって書きはじめると、こんな簡単でいいんだろうかって思う。

今回なら「一個左上と、一個真上を足した数」みたいに文章がそのままコードにできるのが不思議。

1.11

| 23:57 | はてなブックマーク - 1.11 - toyoshiのSICP宿題帖

なぜか動かないけど、こういうこと。

あとから見直す

再帰プロセス

(define (func n) 
	(if (< n 3) 
		n 
		((>= n 3) (+ (func (- n 1)) (* 2 (func (- n 2))) (* 3 (func (- n 3)))))))

反復的プロセス

(define (func n)
	(func-iter 2 1 0 n))

(define (func-iter x-1 x-2 x-3 n)
	(if (= n 0)
		x-3 
		(func-iter ((+ x-1 (* 2 x-2) (* 3 x-3)) x-1 x-2 (- n 1)))))