【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))

参考

計算機プログラムの構造と解釈

【SICP】1.2.1~1.2.2

1.2.1 線形再帰と反復

• 線形再帰プロセス：プロセスを実行するごとに、実行する演算が線形に成長する再帰プロセスのこと

• 線形反復的プロセス：プロセスに必要なステップ数が線形に成長していく反復的プロセスのこと

6!の線形再帰プロセスの例

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

(factorial 6)

6!の線形反復的プロセスの例

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

(factorial 6)

1.2.2木構造再帰

フィボナッチ数列

(define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1))
                   (fib (- n 2))))))

パスカルの三角形

   1
  1 1
 1 2 1
1 3 3 1

n行目k個目の数を(n, k)とすると、 (n, k) = (n-1, k-1) + (n-1, k) さらに、 k=1, k=nのとき、(n, k)=1

(define (pascal n k)
        (if (or (= k 1) (= k n))
            1
            (+ (pascal (- n 1) (- k 1))
               (pascal (- n 1) k))))

参考

計算機プログラムの構造と解釈

【Lisp】Land of Lisp 2章

グローバル変数の定義

トップレベル変数（グローバルにて意義される変数）を定義するためにdefparameterを使う。 **はローカル変数と区別するためにつけておくと良い。

> (defparameter *small* 1)
*SMALL*

同じ名前でトップレベル変数を定義すると上書きされる。

> (defparameter *small* 1)
> *small*
1

> (defparameter *small* 2)
> *small*
2

ただし、defvarを使うと上書きされない。

> (defvar *foo* 1)
> *foo*
1

> (defvar *foo* 2)
> *foo*
1

グローバル関数の定義

defunを使う。

(defun function_name (arguments)
 ...)

バイナリサーチ

;ゲームの初期化
(defun start-over ()
  (defparameter *small* 1)
  (defparameter *big* 100)
  (guess-my-number))

;数の推測
(defun guess-my-number()
    (ash (+ *small* *big*) -1))

;想定している数値よりも大きい時のコマンド
(defun bigger()
    (setf *small* (1+ (guess-my-number)))
        (guess-my-number))

;想定している数値よりも小さい時のコマンド
(defun smaller()
    (setf *big* (1- (guess-my-number)))
        (guess-my-number))

再帰をつかっていますね。

ローカル変数の定義

letを使う。

(let (変数定義)
   ...本体...)

letでは複数の変数を定義できる。その変数はletコマンドの本体内でだけ使える。

(let ((a 5)
      (b 6))
      (+ a b))

ローカル関数の定義

fletを使う。

(flet ((関数名 (引数)
       …関数本体…))
    …本体…)

(flet ((f (n)
        (+ n 10)))
    (f 5))

ローカル関数内で同じスコープのローカル関数名を使いたいときはlabelsを使う。

(labels ((a(n)
            (+ n 5))
         (b (n)
            (+ (a n) 6)))
         (b 10))

参考

Land of Lisp

【SICP】勉強用の環境を整える(DrRacket)

Sublime Text2でGaucheを実行させる環境をつくろうとしたのだが、.scmファイルを読み込んで実行させる方法がわからなかった。

なので、DrRacketをインストールすることにした。

インストール方法は「計算機プログラムの構造と解釈」のためのプログラミング環境 | 林檎生活100 にとても詳しく書かれているので参考にさせてもらった。

【SICP】「計算機プログラムの構造と解釈」を読み始める

計算機プログラムの構造と解釈

魔術師本はじめました。

目的

• コンピューターサイエンスの基礎を学ぶ

読み始めたきっかけ

• 文系プログラマなので、コンピューターサイエンスの基礎がない。プログラマとして働き初めて今年で3年目になるが、今後基礎を知らないことで 思わぬところで躓きそうだから。

• 技術力を上げたい。この本は読んですぐに技術力が上がるようなものではないと思う。しかし、後々「SICP読んどいて良かった」となる類の本だと思う。

大きな理由は、自分にコンピューターサイエンスの基礎が無いことによる将来への不安である。

このままエンジニアとして働き続けたいので、そろそろ基礎を固めないとなあと。

「Lispを勉強する」に加えて、「SICPを読み切る」も今年の目標にも挙げているので最後まで読み切ろう。