問題 2.1 consとcar, cdrが出てきた。なるほどリストか。ふむふむ、これはシンプルで強力そうだ。2章終わったらC++で書いた正規表現パーサをschemeで書き直してみようかな。どんな風になるやら。 (define (make-rat n d) (let ((g (gcd n d))) (let ((n-itr …

問題 1.45 n乗根を求めるのに y -> x/y^(n-1)のfixed-pointを計算していき差が少なくなった値を近似値とする方法において、y -> x/y^(n-1)にaverage dampingを何回行えばそれが収束するかという問題。 解析的に気になったのでSICP問題を解いているブログ界隈…

問題 1.43 fをn回作用させる手続きを書く問題 (define (repeated f count) (if (= count 1) (lambda (x) (f x)) (lambda (x) (f ((repeated f (- count 1)) x))))) (define (square x) (* x x)) (print ((repeated square 2) 5)) (print ((repeated square 3…

問題 1.40 fixed-pointを求めるのにを使うのではなくaverage dampingでを使う方法もあるがさらに収束が早い方法としてというNewton's methodを使おうという問題。 (define (close-enough? a b) (let ((tolerance 0.0001)) (< (abs (- a b)) tolerance))) (de…

問題 1.37.a k-term finite continued fraction N_1 ----------------- N_2 D_1 + ----------- ... N_K + ----- D_K Suppose that `n' and `d' are procedures of one argument (the term index i) that return the n_i and D_i of the terms of the continu…

問題 1.35 *Exercise 1.35:* Show that the golden ratio [phi] (section *Note 1-2-2::) is a fixed point of the transformation x |-> 1 + 1/x, and use this fact to compute [phi] by means of the `fixed-point' procedure. 解 golden ratioの定義はを…

問題 1.31 product(積)版を書いてを計算せよという問題 (define (product term a next b) (if (> a b) 1 (* (term a) (exact->inexact (product term (next a) next b))))) (define (getpi n) (define (pi-term x) (if (even? x) (/ (+ x 2) (+ x 1)) (/ (+ …

問題 1.29 Simpson's ruleを使ってintegralを求めよという問題 (define (integral f a b n) (define h 0) (define (i-term count x) (cond ((= count 0) (f a)) ((= count n) (f b)) ((even? count) (* 2 (f x))) (else (* 4 (f x))))) (define (i-next x) (…

問題 1.28 Fermat-testの欠点を補うMiller-Rabinテストを実装せよという問題。 そこでここで書かれている素数の性質についてちょっと見てみる。 ... ① かつ1 素数ではない。 証明 ①は上位の式と同義であり、x-1, x+1はそれぞれ [tex:0どうやら一般的なMiller…

SICPをemacs上で読めるようにしてみる。 neilvandyke.org - SICP in Texinfo Format ここからsicp.info.gzをDLし解凍したら makeinfo --no-split sicp.texi -o sicp.info でinfoファイルを生成し、/usr/local/info等へコピー あとはemacs上でM-x infoでSICP…

問題1.27 素数以外でfermatテストを通ってしまう整数が本当に通るか確かめろという問題。 (define (fake-fermat-test n) (define (try-it a) (cond ((= a 1) (display "This num is prime or fake prime") (newline)) ((= (expmod a n n) a) (try-it (- a 1)…

※Guileだと時間計測にまともな機能が無いのでGaucheに変更。Gaucheだとnanosecondまで計測出来るみたいだしいい感じ。 問題 1.24 素数のテストにFermatテストを使う Fermatテストの骨格となる以下のコードを見てみる (define (expmod base exp m) (cond ((= …

久々にSICPの問題を解きたくなったのでやってみる。 問題 1.23 問題1.22の素数テストを改良して検査時間が1/2倍になったかどうかを調べてなってなかったら理由を説明せよという問題。 改良の仕方は素数のテストにまでの2以上の整数を調べていたのに対し、2と…

問題 1.22 (define (search-for-primes n) (if (even? n) (search-for-primes-iter (+ n 1) 3) (search-for-primes-iter n 3))) (define (search-for-primes-iter x count) (if (> count 0) (begin (timed-prime-test x) (search-for-primes-iter (+ x 2) (i…

いま問題1.20か、、1年くらい掛かりそうなペースだなこりゃ。問題 1.20 (define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) a) gcdの正規順序評価での展開 (要は式を評価するまえに展開出来る所は全て展開） ※ifの条件部は#f、#tの判定に計算してい…

問題 1.19直感的に行列の変換だと思ったので以下のように解く ベクトル(a,b)に対して行列を作用させた後のベクトルを とするとは となる。 よって、(a, b)にを2回作用させると となるのでここで ... ① ... ② と置くと と書けるので求めるq'とp'は①、②の通り…

久々に問題を解こう。 数日空けると頭が再帰的じゃなくなって問題が意味不明に。。 (define (* a b) (define (*-iter x a b) (cond ((= b 0) x) ((even? b) (*-iter (if (= x 0) (double a) (double x)) a (halve b))) (else (*-iter (+ x a) a (- b 1))))) …

問題 1.17 (define (fast-* a b) (cond ((= b 0) 0) ((even? b) (double (fast-* a (halve b)))) (else (+ a (fast-* a (- b 1)))))) (define (even? x) (= (remainder x 2) 0)) (fast-* a b)の計算でbが偶数の場合はdoubleとhalveの演算により、 (+ a (* (-…

問題 1.16 (define (expr b n) (expr-iter 1 b n)) (define (expr-iter a b n) (cond ((= n 1) a) ((even? n) (expr-iter (* a (square b)) b (/ n 2))) (else (expr-iter (* a b) b (- n 1))))) (define (even? n) (= (remainder n 2) 0)) (define (square …

問題 1.14 木構造描く方法が無いんで普通に展開 (cc 11 5) (+ (cc 11 4) (cc -39 5)) (+ (+ (cc 11 3) (cc -4 4)) 0) (+ (+ (cc 11 2) (cc 1 3)) 0) 0) (+ (+ (+ (+ (cc 11 1) (cc 6 2)) (+ (cc 1 2) (cc -9 3)) ) 0) 0) (+ (+ (+ 1 (+ (cc 6 1) (cc 1 2)) (…

もはや数学問題1.11 再帰的プロセス (define (func n) (cond ((< n 3) n) (else (+ (func (- n 1)) (* 2 (func (- n 2))) (* 3 (func (- n 3)))) 反復的プロセス 思考 ３つの整数a, b, cを初期値をf(2), f(1), f(0)で初期化し、 a ← a + 2b + 3c b ← a c ← b…

今日も1問だけ解く 問題1.10 (define (A x y) (cond ((= y 0) 0) )((= x 0) (* 2 y))( ((= y 1) 2) (else (A (- x 1) (A x (- y 1)))))) (A 1 10) = (A 0 (A 1 9)) = 2(A 1 9) = (A 1 1) = = (A 2 4) = (A 1 (A 2 3)) = (A 1 (A 1 (A 2 2))) = (A 1 (A 1 (A …

問題 1.9 (define (+ a b) (if (= a 0) b (inc (+ (dec a) b)))) のパターン (+ 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)…

SICP勉強 1SICP（計算機プログラムの構造と解釈）本をついつい買ってしまったのでちょっとずつ読もうと思う。 ルール ・基本、問題を全部解く ・分からなかったらwebで答えを探して写経する ・あんまり気合を入れてやらない(はまると他の勉強が出来なくなる)…