読者です 読者をやめる 読者になる 読者になる

勉強ノート - SICP(6)

 問題1.16〜1.19まで解きましたよー。
 解いたって言うか、挫折しましたよー(涙
 出来るかぁこんな問題><;
 おかげでだんだんSchemeのコツが掴めてきたぞ。

問題1.16

 対数的ステップ数の反復的べき乗手続きを設計しなさい。

(define (fast-expt b n)
    (fe-iter b n 1))

(define (fe-iter b n a)
    (cond ((= n 0) 1)
          ((even? n) (fe-iter (* b b) (/ n) a))
          (else (fe-iter b (- n 1) (* b a)))))

 この問題はやられたわ・・・・。

状態の移り変わりで積ab^2が普遍であるように状態遷移を定義する.

 とか書いてあるから、てっきり a だけ変えて b は変えちゃいけないもんかと思った。答えはみたけど、内容は把握した。

問題1.17

 この問題は解けた!

(define (double n) (* n 2))
(define (halve n) (/ n 2))

(define (* a b)
    (cond ((= b 0) 0)
          ((even? b) (double (* a (halve b))))
          (else (+ a (* a (- b 1))))))

 これは余裕でした。
 でもこれが対数的かどうかはしらね。

問題1.18

 1.17の問題を反復的プロセスに書き直す問題。
 比較的楽に解けた!

(define (kake a b)
    (kake-iter a b))

(define (kake-iter a b n)
    (cond ((= b 0) n)
          ((even? b) (kake-iter (double a) (halve b) n))
          (else (kake-iter a (- b 1) (+ n a)))))

問題1.19

 全然分からなかった・・・。悔しい><;
 とりあえず、フィボナッチ数列を2個飛ばし、3個飛ばし・・・って感じに出せるように式を組んで、そこから二乗飛ばしの式を求めようと思ったんだけど、挫折した。
 えーと、つまり、

0 1 1 2 3 5 8...

 っていうのを

0 1 3 8 (2個飛ばし
0 2 8 34 (3個飛ばし

 って出せるようにしたわけ。
 そしたら式の中にフィボナッチ数列が現れるようになっちゃって、アウト。仕方がないので答えを検索。
 どうやら
p' = p^2+q^2
q' = p^2+2pq
 となるらしい。
 詳しく解説しているブログはこちら

どんどん難しく

 まだまだ基礎中の基礎なんだろうけども、先へ進むにつれて数学の知識が必要になってくるっぽい。
 ああもう、学生時代に勉強しておけば良かった。