Project Euler31解けた!!
いやー時間かかりました。Project Euler31の両替問題。
なかなか上手くいかなくて悩みに悩んだ末に解けました。
実はこの両替問題、SICPにも同様の問題があるんですね。
SICP挫折者としては、本に載っているソースを眺めたい要求にかられましたが、自分の頭で考えるというルールを破りたくなかったんで、見ずに解きました。
相変わらずソースは汚いです。
しかし、ハッカーと呼ばれる人たちはこれらの問題をちょいちょいと解いてしまうんだろうか?どこの世界にも天才はいるんですねー。
私はソフトウェアを作るという大それたことは出来ないと諦めているので、せめてこういった問題をプログラミングで解くと言う事を楽しんでいます。
以下ソース
;イギリスでは硬貨はポンド£とペンスpがあり,一般的な流通ではこれらの8つの硬貨がある.;1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
;以下の方法で£2を作ることが可能である.
;1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
;いくらかの硬貨を使って2ポンドを作る方法はいくつあるでしょうか?
(define (200p n)
(define (200p-iter n ans)
(if (< n 200)
(+ ans (100p n))
(200p-iter (- n 200) (+ ans (100p n)))))
(200p-iter n 0))(define (100p n)
(define (100p-iter n ans)
(if (< n 100)
(+ ans (50p n))
(100p-iter (- n 100) (+ ans (50p n)))))
(100p-iter n 0))(define (50p n)
(define (50p-iter n ans)
(if (< n 50)
(+ ans (20p n))
(50p-iter (- n 50) (+ ans (20p n)))))
(50p-iter n 0))(define (20p n)
(define (20p-iter n ans)
(if (< n 20)
(+ ans (10p n))
(20p-iter (- n 20) (+ ans (10p n)))))
(20p-iter n 0))
(define (10p n)
(define (10p-iter n ans)
(if (< n 10)
(+ ans (5p n))
(10p-iter (- n 10) (+ ans (5p n)))))
(10p-iter n 0))(define (5p n)
(define (5p-iter n ans)
(if (< n 5)
(+ ans (2p n))
(5p-iter (- n 5) (+ ans (2p n)))))
(5p-iter n 0))(define (2p n)
(define (2p-iter n ans)
(if (< n 2)
(+ ans (1p n))
(2p-iter (- n 2) (+ ans (1p n)))))
(2p-iter n 0))(define (1p n)
1)(200p 200) ;73682