Hatena::Groupcsnagoya-sicp

toyoshiのSICP宿題帖

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.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))

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.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)))))

2008-11-08

1.10 Ackermann関数

| 03:18 | はてなブックマーク - 1.10 Ackermann関数 - toyoshiのSICP宿題帖

Ackermann関数を知らないので、たらいまわし関数みたいなもんだったらサドすぎるなと思いながら手計算した。

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)
(A 0 (A 0 (A 0 (A 0 (A 0 32)
(A 0 (A 0 (A 0 (A 0 64)
(A 0 (A 0 (A 0 128)
(A 0 (A 0 256)
(A 0 512)
1024

たらいまわし系じゃねえか!

(A 1 y)

は2^yってことなんですね

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4)))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
65536

(A 1 16)は1個目のやつから2^16とわかっているので省略

これは(A x y)のとき

2^x^yかな、たぶん

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
4294967296

これも途中で省略

つまり

f・・・2n

g・・・2^n

h・・・2^(2n)

ということかな

1.9 反復的プロセスと再帰的プロセス

| 02:39 | はてなブックマーク - 1.9 反復的プロセスと再帰的プロセス - toyoshiのSICP宿題帖

一個目のコードを置き換えモデルにすると

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc (5))))
(inc (inc (inc (6))))
(inc (inc (7)))
(inc (8))
9

二個目を置き換えもデルにすると

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
0

というわけで前者が再帰的プロセス、後者が反復的プロセス。

二個目のアルゴリズムは面白いなー