素数計算を高速化し、そのパフォーマンスを測定せよnextを使い高速化したバージョン (define (prime? n) (= n (smallest-divisor n))) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-div…

1000の場合 guile> (search-for-primes 1000 30) 1001 1003 1005 1007 1009 *** 62 1011 1013 *** 63 1015 1017 1019 *** 62 1021 *** 63 1023 1025 1027 1029 1031 *** 63 1033 *** 47 1035 1037 1039 *** 62 1041 1043 1045 1047 1049 *** 46 1051 *** 63 …

さあ面白くなってきた。素数を求めるのに必要な時間を調べ、考察せよC言語なら単純なforループになるコードだが、Lispだと末尾再帰を使って解く必要がある。 残念ながら自力で書くことは出来なかっので、AnswerBookをコピーしてコード読み。 (define (search…

199, 1999, 19999の最小除数を求めよ (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor …

ちょっと挫折しました...余力があれば後で戻ってくるかも。 AnswerBook一応、作用的順序評価はやってみた。 ; 作用的順序評価 (if (= 40 0) 206 (gcd 40 (remainder 206 40))) (if (= 40 0) 206 (if (= 6 0) 40 (gcd 40 (remainder 40 6)))) (if (= 40 0) 20…

逐次平方の反復的プロセスバージョンを求めよ発想の転換が必要。 b^n = (b^(n/2))^2 = (b^2)^(n/2) b^n = b * b^(n-1) [普通の逐次平方ならばこんな感じ] 2^6 = (2^3)^2 = 8^2 = 8 * 8 = 64 [反復プロセスで行うならばこうする] 2^6 = (2^3)^2 = (2^2)^3 -->…

sinの近似と増加量の計算 (define (cube x) (* x x x)) (define (p x) (- (* 3 x) (* 4 (cube x)))) (define (sine angle) (if (not (> (abs angle) 0.1)) angle (p (sine (/ angle 3.0))))) a. (sine 12.5) の評価で、手続きpは何回作用させられたか？5回 (…

木構造を手で書けうおー、しんどい・・・。 でも練習にはちょうどいいか。 ; 11の場合 (cc 11 5) (cc 11 4) (cc 11 3) (cc 11 2) (cc 11 1) (cc 11 0) -> 0 (cc 10 1) (cc 10 0) -> 0 (cc 9 1) (cc 9 0) -> 0 (cc 8 1) (cc 8 0) -> 0 (cc 7 1) (cc 7 0) -> 0…

Fib(n)が φ^n /√5 に最も近い整数であることを、帰納法を用いて証明せよ。 φ = (1 + √5)/2 ≒ 1.61803398874989 φ^2 = φ + 1 いわゆる黄金比のこと。証明なんて何年ぶりだろう...、自力で解くのは正直無理でしたm(__)m。 AnswerBookを写経しながら、自分の言…

Pascal三角形を計算する関数を作成せよ関数自体は簡単に出来た。 ; 1〜n行, 1〜n列 目のパスカル三角形の値を返す ; 範囲外の場合は0を返す (define (pascals-triangle row col) (cond ((> col row) 0) ((= col 1) 1) ((= row col) 1) (else (+ (pascals-tri…

フィボナッチ数計算の対数ステップ版を作れ 答えを見ながら証明してみましたが、正直理解しきれていないなあ...。 a = bq + aq + ap b = bp + aq a' = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p = bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2…

1.17の反復プロセス版を作れ (define (fast-mul2 a b) (define (iter a b total) (cond ((= b 0) total) ((even? b) (iter (double a) (halv b) total)) (else (iter a (- b 1) (+ total a))))) (iter a b 0)) (define (double x) (ash x 1)) (define (halv …

掛け算、割り算の無い世界で、足し算を使って掛け算を定義せよ逐次平方はべき乗の高速化だったが、 これは同じような考えで掛け算を定義する。なんとなく、doubleとhalvはシフト演算で定義してみた。 (define (fast-mul a b) (cond ((= b 0) 0) ((even? b) (…

再帰関数を、再帰的プロセス、反復的プロセスで記述せよ ; 答え合わせ用にトレース ; (f 3) ; ==> (+ (f 2) (* 2 (f 1)) (* 3 (f 0))) ; ==> (+ 2 (* 2 1) (* 3 0)) ; ==> (+ 2 2 0) ; ==> 4 ; (f 4) ; ==> (+ (f 3) (* 2 (f 2)) (* 3 (f 1))) ; ==> (+ 4 4 …

Ackermann関数についてそもそもAckermann関数ってなんだ？って話なので、Wikipediaで調べてみる。 アッカーマン関数 - Wikipedia今ひとつ分からないので実際に書いて動かしてみる。 (define (A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else …

下記の2つの手続きを、置き換えモデルを用いて図示せよ そのプロセスは反復的か再帰的か？ プロセスを図示することが大切。プロセス1 (plus 3 3) ==> (inc (plus 2 3)) ==> (inc (inc (plus 1 3))) ==> (inc (inc (inc (plus 0 3)))) ==> (inc (inc (inc 3))…

立方根を求める手続きを作成せよ improveのみ、立方根の手続きに変更すれば良い せっかくなので、good-enough?等はAnswerBook1.7を参考に作ることにした 共通関数は別ファイルにまとめることにした(sicp-lib.scm - おんがえしの日記) (load "sicp-lib.scm") …

1.1.7節で作成した、sqrtの弱点を解析せよ また、その弱点を改良せよ とりあえず、検証用手続きを作る (define (sqrt-test x) (/ (square (sqrt x)) x)) 非常に小さい数の場合、閾値よりも小さい数になると精度が悪くなる。 再帰が少ない回数で終了してしま…

通常版では (sqrt 2) ==> 1.41421568627451 new-if版では ==> ERROR: Stack overflow ==> ABORT: (stack-overflow) ifでは述語がtrueにならない限りelse節が評価されないが、 new-ifはただの手続きのため、呼び出されてすぐにthen節、else節が評価されてしま…

(define (p) (p)) (define (test x y) (if (= x 0) 0 y)) 作用的順序の場合 無限ループする (test 0 (p)) => (test 0 (p)) => (test 0 (p (p (p) (p))))... 正規順序の場合 まず関数testを展開する (test x y) => (if (= x 0) 0 y) ;xを代入する(yはまだ) =>…

とりあえず関数を動かしてみて、どのような振る舞いをするか確かめる a-plus-abs-b は a + abs(b) のことだということは動かせば分かる。 (define (a-plus-abs-b a b) ((if (> b 0) + -) a b)) (a-plus-abs-b 1 2) ; 3 (a-plus-abs-b 1 -2) ; 3 (a-plus-abs-…

三つの数を引数として取り、大きい二つの数の二乗の和を返す手続きを定義せよ。 テキストで出てきた、square, sum-of-squaresを使いまわす ソートする必要は無い、一番小さい数が分かればよい (define (square x) (* x x)) ;(square 5) (define (sum-of-squa…

次の式を前置記法に翻訳せよ とりあえず書いてみる。 実行してみて、動くことを確認。 回答集を見て、同じ答えなことを確認 細かいことだけど、guileは有理数で出力されて、gaucheは小数で出力されるのね (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2)…

式の列がある。それぞれの式が印字する結果は何か。列は示した順に評価するものとする問題1.1はインタプリタの使い方を覚えるのがメイン。 問題を正しく打ち込み、結果を考え記入。インタプリタで結果を答え合わせ。 10 ; 10 (+ 5 3 4) ; 12 (- 9 1) ; 8 (/ …