codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; coin change, part 1 (define (count xs n) (let ((cs (make-vector (+ n 1) 0))) (vector-set! cs 0 1) (do ((xs xs (cdr xs))) ((null? xs) (vector-ref cs n)) (do ((x (car xs) (+ x 1))) ((< n x)) (vector-set! cs x (+ (vector-ref cs x) (vector-ref cs (- x (car xs))))))))) (define (coins xs n) (let ((cs (make-vector (+ n 1) (list)))) (vector-set! cs 0 (list (list))) (do ((xs xs (cdr xs))) ((null? xs) (vector-ref cs n)) (do ((i (car xs) (+ i 1))) ((< n i)) (vector-set! cs i (append (vector-ref cs i) (map (lambda (zs) (cons (car xs) zs)) (vector-ref cs (- i (car xs)))))))))) (display (count '(1 5 10 25) 40)) (newline) (for-each (lambda (x) (display x) (newline)) (coins '(1 5 10 25) 40))
Private
[
?
]
Run code
Submit