Cracking the coding interview--Q8.7

January 14, 2013
作者:Hawstein
出处:http://hawstein.com/posts/8.7.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。



题目

原文:

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

译文:

我们有25分,10分,5分和1分的硬币无限个。写一个函数计算组成n分的方式有几种?

解答

一开始,我觉得使用递归不断地累加四种币值的硬币,当累加到n分,组成方式就加1。 最后就能得到一共有多少种组合方式,听起来挺正确的,然后写了以下代码:

int cnt = 0;
void sumn(int sum, int n){
    if(sum >= n){
        if(sum == n) ++cnt;
        return;
    }
    else{
        sumn(sum+25, n);
        sumn(sum+10, n);
        sumn(sum+5, n);
        sumn(sum+1, n);
    }
}```

但,这是错误的。问题出在哪?有序与无序的区别!这个函数计算出来的组合是有序的,
也就是它会认为1,55,1是不一样的,导致计算出的组合里有大量是重复的。
那要怎么避免这个问题?1,55,1虽然会被视为不一样,但如果它们是排好序的,
比如都按从大到小排序,那么就都是5,1了,这时就不会重复累计组合数量。
可是我们总不能求出答案来后再搞个排序吧,多费劲。这时我们就可以在递归上做个手脚,
让它在计算的过程中就按照从大到小的币值来组合。比如,
现在我拿了一个25分的硬币,那下一次可以取的币值就是25,10,5,1;如果我拿了一个
10分的,下一次可以取的币值就只有10,5,1了;这样一来,就能保证,同样的组合,
我只累计了一次,改造后的代码如下:

```cpp
int cnt = 0;
void sumN(int sum, int c, int n){
    if(sum >= n){
        if(sum == n) ++cnt;
        return;
    }
    else{
        if(c >= 25)
            sumN(sum+25, 25, n);
        if(c >= 10)
            sumN(sum+10, 10, n);
        if(c >= 5)
            sumN(sum+5, 5, n);
        if(c >= 1)
            sumN(sum+1, 1, n);
    }
}

有个全局变量总觉得看起来不好看,于是我们可以把这个全局变量去掉, 让函数来返回这个组合数目,代码如下:

int sum_n(int sum, int c, int n){
    int ways = 0;
    if(sum <= n){
        if(sum == n) return 1;
        if(c >= 25)
            ways += sum_n(sum+25, 25, n);
        if(c >= 10)
            ways += sum_n(sum+10, 10, n);
        if(c >= 5)
            ways += sum_n(sum+5, 5, n);
        if(c >= 1)
            ways += sum_n(sum+1, 1, n);
    }
    return ways;
}

CTCI原文中给出的解法如下:

int make_change(int n, int denom){
    int next_denom = 0;
    switch(denom){
    case 25:
        next_denom = 10;
        break;
    case 10:
        next_denom = 5;
        break;
    case 5:
        next_denom = 1;
        break;
    case 1:
        return 1;
    }
    int ways = 0;
    for(int i=0; i*denom<=n; ++i)
        ways += make_change(n-i*denom, next_denom);
    return ways;
}

也是从币值大的硬币开始,每次取i个(i乘以币值要小于等于n), 然后接着去取币值比它小的硬币,这时就是它的一个子问题了,递归调用。 具体来怎么来理解这个事呢?这样,比如我要凑100分,那我先从25分开始, 我先取0个25分,然后递归调用去凑100分;再然后我取1个25分,然后递归调用去凑100-25 =75分;接着我取2个25分,递归调用去凑100-25*2=50分……这些取了若干个 25分然后再去递归调用,取的就是10分了。一直这样操作下去,我们就会得到, 由若干个25,若干个10分,若干个5分和若干个1分组成的100分,而且, 这里面每种币值的数量都可以为0。

完整代码如下:

#include <iostream>
using namespace std;

int cnt = 0;
void sumN(int sum, int c, int n){
    if(sum >= n){
        if(sum == n) ++cnt;
        return;
    }
    else{
        if(c >= 25)
            sumN(sum+25, 25, n);
        if(c >= 10)
            sumN(sum+10, 10, n);
        if(c >= 5)
            sumN(sum+5, 5, n);
        if(c >= 1)
            sumN(sum+1, 1, n);
    }
}
int sum_n(int sum, int c, int n){
    int ways = 0;
    if(sum <= n){
        if(sum == n) return 1;
        if(c >= 25)
            ways += sum_n(sum+25, 25, n);
        if(c >= 10)
            ways += sum_n(sum+10, 10, n);
        if(c >= 5)
            ways += sum_n(sum+5, 5, n);
        if(c >= 1)
            ways += sum_n(sum+1, 1, n);
    }
    return ways;
}
int make_change(int n, int denom){
    int next_denom = 0;
    switch(denom){
    case 25:
        next_denom = 10;
        break;
    case 10:
        next_denom = 5;
        break;
    case 5:
        next_denom = 1;
        break;
    case 1:
        return 1;
    }
    int ways = 0;
    for(int i=0; i*denom<=n; ++i)
        ways += make_change(n-i*denom, next_denom);
    return ways;
}
int main(){
    int n = 10;
    sumN(0, 25, n);
    cout<<cnt<<endl;
    cout<<make_change(n, 25)<<endl;
    cout<<sum_n(0, 25, n)<<endl;
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview