【SICP】1.2.3~1.2.6
1.2.3 増加の程度
増加の程度:プロセスが入力が大きくなるにつれて必要とする資源のこと
1.2.4 べき乗
(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1)))))
上記は線形再帰的プロセスでθ(n)のステップと、θ(n)のスペースを必要とする。
しかし、以下のように書くとθ(n)のステップとθ(1)のスペースで済む。
(define (expt b n) (expt-iter b n 1)) (define (expt-iter b counter product) (if (= counter 0) product (expt-iter b (- counter 1) (* b product))))
逐次平方を使うと以下のように書ける。
(define (fast-expt b n) (cond ((= n 0) 1) ((even? n) (square (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1)))))) (define (even? n) (= (remainder n 2) 0)) (define (square n) (* n n))
1.2.5 最大公約数
ユークリッド互除法
(define (gcd a b) (if (= b 0) a (gcd b (remainder a b))))
1.2.6 除数の探索
最小でかつ整数の除数を見つける
(define (smallerst-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisior) (cond ((> (square test-divisior) n) n) ((divides? test-divisior n) test-divisior) (else (find-divisor n (+ test-divisior 1))))) (define (divides? a b) (= (remainder b a) 0)) (define (square n) (* n n))
参考
- 作者: ジェラルド・ジェイサスマン,ジュリーサスマン,ハロルドエイブルソン,Gerald Jay Sussman,Julie Sussman,Harold Abelson,和田英一
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/02
- メディア: 単行本
- 購入: 35人 クリック: 1,149回
- この商品を含むブログ (493件) を見る