SICPを読む(14) 問題1.17 - 1.19 変換がわからない・・・

Scheme

a <- b の変換がうまくいかない。

問題1.17

あっさり解けた。

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

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

問題1.18

1.17を反復にする問題。簡単だと思っていたのに、いくら考えても答えに辿り着かない。答えを見た。

SICP memo: 問題1.18
product ← product そのまま

なるほど。2で割り切れなくなるまで、合計をキャッシュしておけばよかったのか。

合計を足してたので答えに辿り着かなかった。悔しい。

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

Vim++MzScheme+traceを導入してみた。Gaucheより見やすい。

3 * 20の計算の場合、

|(iter 3 20 0)
|(iter 6 10 0)
|(iter 12 5 0)
|(iter 12 4 12)
|(iter 24 2 12)
|(iter 48 1 12)
|(iter 48 0 60)
|60
60
  • 3 * 20だと、
  • 2で割り切れなくなるまでaを2倍して、bを2分する。
  • 12 * 5になる。(この時点まで、足さないのがポイント!!)
  • 12 * 4 + 12として、
  • 繰り返す。

割り切れなくなったら、外に追い出す感じ。

僕の頭の中に、こういう発想は全然無かった。

後でもう一度解こうと思う。

問題1.19

変換がわからなくなってきたので、飛ばそうと思う。

解答も見ないことにする。

まとめ

  • 同類の問題は解けるけど、応用問題に弱いことが判明してきた。
  • バイナリサーチの初歩段階なんだけど、つまずいている自分がいて情けない。