Skip to content

Instantly share code, notes, and snippets.

@esehara

esehara/money.rb

Last active Apr 17, 2016
Embed
What would you like to do?
SICP P.22 両替の問題について
def exchange x
exchange_node x, 50
end
# proto exchange node example
def proto_exchange_node x, coin
return 1 if x == 0
return 1 if x < 5
return 0 if x < 0
sum_coin = 0
case coin
when 10
sum_coin += exchange_node(x - 5, 5)
end
sum_coin += exchange_node(x - coin, coin) + 1
return sum_coin
end
# bad exchange node
def bad_exchange_node x, coin
return 1 if x == 0
return 1 if x < 5
return 0 if x < 0
sum_coin =
if coin >= 50
exchange_node(x - 50, 50)
else
0
end +
if coin >= 25
exchange_node(x - 25, 25)
else
0
end +
if coin >= 10
exchange_node(x - 10, 10)
else
0
end +
if coin >= 5
exchange_node(x - 5, 5)
else
0
end
end
$caches = {}
# better refactoring
COINS = [50, 25, 10, 5]
def exchange_node x, coin
return 1 if x == 0
return 1 if x < 5
return 0 if x < 0
return COINS.inject(1) do |sum, c|
sum + cache_exchange_coin(x, coin, c)
end
# return exchange_coin(x, coin, 50) +
# exchange_coin(x, coin, 25) +
# exchange_coin(x, coin, 10) +
# exchange_coin(x, coin, 5) + 1
end
def exchange_coin x, n, coin
if x - coin >= 0 && n >= coin
exchange_node(x - coin, coin)
else
0
end
end
def cache_exchange_coin x, n, coin
caches_key = "#{x}_#{n}_#{coin}"
if $caches[caches_key].nil?
if x - coin >= 0 && n >= coin
$caches[caches_key] = exchange_node(x - coin, coin)
else
$caches[caches_key] = 0
end
end
$caches[caches_key]
end
# --------------------TestCase
require 'minitest/unit'
require 'minitest/autorun'
class TestExchange < MiniTest::Unit::TestCase
def test_exchange_node_5
assert_equal 3, exchange_node(10, 5)
end
def test_exchange_node_10
assert_equal 4, exchange_node(10, 10)
end
def test_exchange_20
assert_equal 9, exchange(20)
end
def test_exchange_100
assert_equal 292, exchange(100)
end
def test_pef_exchange_1000
assert_equal exchange(1000), exchange(1000)
end
end
#lang racket
(require rackunit)
(define coins '(50 25 10 5))
(define (change-money x)
(change-money-p x (car coins)))
;; (if-check-coin-node x n 50)
;; (if-check-coin-node x n 25)
;; (if-check-coin-node x n 10)
;; (if-check-coin-node x n 5)
(define (change-money-p x n)
(if (= x 0) 1
(+
(foldl +
0
(map (lambda (coin) (if-check-coin-node x n coin)) coins))
1)))
(define (if-check-coin-node x n coin)
(if (check-coin? x n coin) (change-money-p (- x coin) coin) 0))
(define (check-coin? x n coin)
(and (>= (- x coin) 0)
(>= n coin)))
(check-equal? (change-money 4) 1)
(check-equal? (check-coin? 5 5 5) true)
(check-equal? (change-money 5) 2)
;; 10
;; 5 - 5
;; 5 - 1
;; 1
(check-equal? (change-money 10) 4)
;; 10 - 10
;; 10 - 5 - 5
;; 10 - 5 - 1
;; 10 - 1
;; 5 - 5 - 5 - 5
;; 5 - 5 - 5 - 1
;; 5 - 5 - 1
;; 5 - 1
;; 1
(check-equal? (change-money 20) 9)
(check-equal? (change-money 100) 292)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.