秋兰吧 关注:74贴子:237
  • 1回复贴,共1

基本练习题:一道华为的面试题。

只看楼主收藏回复

1分2分5分的硬币,组成1角,共有多少种不同组合?


1楼2011-09-17 20:54回复

    我把比较经典的解法整理出来,一般的for循环解法有空在整理
    思路分析:
    设1分个数为x,2分个数为y,5分的硬币个数为z,则1*x+2*y+5*z=10;
    5*z=10-x-2*y;即:
    z x对应可能的取值
    z=0 时x=10 8 6 4 2 0(6个)
    z=1 时x=5 3 1(3个)
    z=2时x= 0(1个)
    总共个数为6+3+1=10.
    因此,按照规律,本题目组合总数为10以内的偶数+5以内的奇数+0以内的偶数
    某个偶数m以内的偶数个数(包括0)可以表示为m/2+1=(m+2)/2
    某个奇数m以内的奇数个数也可以表示为(m+2)/2
    所以,求总的组合次数可以编程为:
    number=0;
    for (int m=0;m<=10;m+=5)
    {
    number+=(m+2)/2;
    }
    cout<<number<<endl;
    这样程序是不是简单多了(只需要累加3次,而上面的3层循环呢?大家自己想想)。别人考你肯定不是考你会不会编这个程序,是考你如何去使程序的复杂度降低。
    C语言代码:
    #include <stdio.h>
    void main(void) {
    int number=0,m;
    // 因为5*z=10-x-2*y<=10;z的取值范围为0、1、2(注意5*z),所以m的步长是5啊
    for (m=0;m<=10;m+=5) {
    number += (m+2)/2;
    }
    printf("组合数的个数为:%d\n",number);
    }
    该算法对本题没问题,能否提炼出通用算法。
    如果6分、4分、2分组成100分怎么处理呢?
    和先前一样的道理,2分为x,4分为y,6分为z。则6*z=100-2*x-4*y,可化简为:
    3*z=50-x-2*y
    z可能的取值为0、1、2···16,
    当z=0时,x可以为50 48 46···2 0(26个)
    当z=1时,x可以为47 45 43···3 1(24个)
    当z=2时,x可以为44 42 40···2 0(23个)
    当z=3时,x可以为41 39 37···3 1(21个)
    ·
    ·
    ·
    当z=15时,x可以为5 3 1(3个)
    当z=16时,x可以为2 0(2个)
    因此,按照规律,本题目组合总数为50以内的偶数+47以内的奇数+44以内的偶数+···+5以内的奇数+2以内的偶数
    某个偶数m以内的偶数个数(包括0)可以表示为m/2+1=(m+2)/2
    某个奇数m以内的奇数个数也可以表示为(m+2)/2
    所以,求总的组合次数可以编程为:
    number=0;
    for (int m=0;m<=50;m+=3)
    {
    number+=(m+2)/2;
    }
    cout<<number<<endl;
    是不是可以看出规律了呢?实际上就是看表达式(这里是3*z=50-x-2*y),就是把最大乘数(这里是3)放在一边,这也是m增加的步长。而m的最大取值也就是表达式中的这个常数。


    2楼2011-09-17 20:56
    回复