SICPを読む(10) 問題1.9 - 1.10 指数的爆発

Scheme

問題1.9

紙の上で展開した。散々悩んだので、あっさり解けた。

問題1.10

数学的帰納の問題。

プログラムを見て、数学的定義を述べよ。

(define (A x y)
 (cond ((= y 0) 0)
       ((= x 0) (* 2 y))
       ((= y 1) 2)
       (else (A (- x 1) (A x (- y 1))))))

xに大きな値を取ると大変な事になることだけわかった。x = 3以降の動きが異常すぎるのだ。尋常じゃない。僕の少ない頭では、数学的定義がわからなかった。

丁寧な解説がありました。

なるほど・・・指数的爆発を起こすはずです・・・。後でもう一度解きたい問題。

追加問題

ひげぽん OSとか作っちゃうかMona- - 関数型言語の勉強にSICPを読もう - (7) 1章 - 反復をマスターしたいけど・・・

ひげぽんの問題もやってみた。

1からnまで数えよう!

; 再帰版
(define (sum n)
 (if (= n 1)
     1
     (+ n (sum (- n 1)))))
(sum 10) ; 55

; 反復版
(define (sum n)
 (define (iter s i)
  (if (> i n)
      s
      (iter (+ s i) (+ i 1))))
 (iter 0 1))
(sum 10) ; 55

おぉぉぉ。スムーズに解けた。先人がいるというのはありがたい。

  • 再帰のポイントは(n - 1)で考える。
  • 反復のポイントは、+の位置。

しかし、1からnまで計算するのに繰り返しは要らない。

(define (sum n)
 (/ (* (+ n 1) n) 2))
(sum 10) ; 55