SICPを読む(47) 問題 2.17 - 2.20 一発で解けた。

Scheme

一発で解けた。スゲー嬉しい!!

問題 2.17

リストの最後の要素をリストで返す。

(define odds (list 1 3 5 7))

(define (last-pair items)
    (if (null? (cdr items))
        items
        (last-pair (cdr items))))

(last-pair odds) ; (7)

(null? (cdr items))で一個先読みしてるのがポイント。

問題 2.18

リストの逆順を返す問題。

反復を使った。

(define (reverse items)
  (define (iter i j)
    (if (null? i)
        j
        (iter (cdr i) (cons (car i) j))))
  (iter items `()))

(reverse odds) ; (7 5 3 1)

cdrダウンする感覚を掴んできたぞぉ〜。

問題 2.19

コインの両替問題。

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define no-more? null?)
(define except-first-denomination cdr)
(define first-denomination car)

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
          (+ (cc amount (except-first-denomination coin-values))
             (cc (- amount (first-denomination coin-values)) coin-values)))))

(cc 100 us-coins) ; 292
(cc 100 uk-coins) ; 104561

難しそうだったけど、car,cdr,null?置き換えれば良いだけ。coin-valuesの順を変えても影響はない。

「ccを作れ」という問題じゃなくて良かった。

uk-coinsはめちゃめちゃ時間がかかる。計算結果をキャッシュ出来たらなぁ・・・先は長い・・・。

問題 2.20

ドット末尾記法を使う。最初の引数を見て、偶数リスト、奇数リストを作る問題。

(define (same-parity . items)
  (let ((parity? (if (even? (car items)) even? odd?)))
    (define (iter i)
      (cond ((null? i) `())
            ((parity? (car i))
             (cons (car i) (iter (cdr i))))
            (else
              (iter (cdr i)))))
    (iter items)))

(same-parity 1 2 3 4 5 6 7) ; (1 3 5 7)
(same-parity 2 3 4 5 6 7)   ; (2 4 6)

parity?してみて、評価が#tなら、リストに追加。そうでなければ空読みするだけ。

(define parity? ...)と書くと、毎回(even? (car items)が呼ばれることになってしまうのでかなり無駄なので、letを使って計算回数を減らしてみた。奇数を評価する場合、even?は1度しか呼ばれない。

まとめ

  • cdrダウンの感覚重要
  • cdrダウン+consアップでリストのコピーが作れる。間に処理を加えれば任意のリストが出来上がる。
  • 再帰だと正順、反復だと逆順になるっぽい。
  • リストの末尾に値を加えたいとき、先頭からnull?を探さなければならないのだろうか?ポインタが欲しい!!
    • 追記:リスト末尾に要素を加えたい時はキューを使えばいい3.3.2を参照。