逐次平方の反復的プロセスバージョンを求めよ発想の転換が必要。 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回 (…

両替問題は面白かった。 理屈は分かるけど、解けてしまうことがやっぱり不思議。 せっかくなので日本硬貨での両替計算も作ってみました。 (define (count-change amount) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= k…

木構造を手で書けうおー、しんどい・・・。 でも練習にはちょうどいいか。 ; 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) (…