SICP（計算機プログラムの構造と解釈 第二版）を読む会 #yomukai

概要

yomukai.connpass.com

Slackで

前回

www.shigemk2.com

今回

http://sicp.iijlab.net/fulltext/x121.html

1.2.1 線形再帰と反復

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

往路と復路の線形再帰的プロセス。

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

展開の線形反復的プロセス。(末尾再帰)

1.2.2 木構造再帰

フィボナッチが代表例。

同じ結果を計算するより効率的な手続きに変換する「スマート翻訳系」

1.2.3 増加の程度

プロセスが入力が大きくなるにつれて必要とする資源を, 粗く見積る 増加の程度(order of growth)

計算量の例のアレ。

1.2.4 べき乗

普通の再帰。

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- 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)))) 

1.2.5 最大公約数

最大公約数(GCD)

• GCDの計算法はEuclidのアルゴリズムが使える
• Euclidのアルゴリズムの手続き
• Euclidのアルゴリズムが必要とするステップ数が、対数的に増加するという事実は、Fibonacci数と面白い関係にある

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

remainderは余りを求める関数。 https://www.shido.info/lisp/scheme2.html

1.2.6 例: 素数性のテスト

(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 1)))))


(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(prime? 1409)

• 確率的アルゴリズム エラーの機会が任意に小さくなることの証明出来るテスト

http://sicp.iijlab.net/fulltext/x126.html

計算機プログラムの構造と解釈[第2版]