换零钱问题

刚刚看了欧拉计划31题.一下就想起了sicp上的练习2.19了,由于时间隔的太久,一下子想不起当时写的解法了=.=

只记得是一个简单的递归….感觉智商一直在下降啊

思路如下:

假设有N种硬币,那么换零钱方式的数目,等于完全不使用第一种硬币的方式的数目,加上使用第一种硬币的方式的数目.

scheme的一种解法如下

(define (cc amount coin-values)
(define (no-more? a) (null? a))
(define (except-first-demonination list) (cdr list))
(define (first-demonination list) (car list))
    (cond ((= amount 0) 1)
    ((or (< amount 0) (no-more? coin-values)) 0)
    (else
        (+ (cc amount
                (except-first-demonination coin-values))
            (cc (- amount
                (first-demonination coin-values))
            coin-values)))))

对应可以写出C语言的递归解法

#include 
static int pence[] = {1, 2, 5, 10, 20, 50, 100, 200};
static int total_amount = 200;
int findallpos(int amount, int i)
{
    if(amount == 0)
        return 1;
    else if(i>7 || amount < 0)
        return 0;
    return(findallpos(amount - pence[i], i) +
    findallpos(amount, i+1));
}

int main()
{
    printf("%d\n",findallpos(total_amount, 0));
    return 0;
}