解决1分2分5分硬币组合的数学问题

    本文部分信息来源于 http://topic.csdn.net/u/20110913/21/54ef3c9d-6e86-4a4e-8359-cc8f0d728770.html
    问题的提出如下:1分2分5分的硬币,组成1角,共有多少种组合,如果是组成1块,又有多少种组合。

    这个问题看似很简单,答案为10种。但如果要真正去算,或者写程序来实现。想必大多数的人都会使用3层for循环来实现。即分别令i=0(表示1分),j=0(表示2分),k=0(表示5分),然后循环条件为3者之和小于10,得出的结果为三者之和大于10。即实现算术 x+2y+5z=10,然后求x,y,z的组合。
    然而,问题在于提出的问题并没有问具体的组合方式,而是只问了究竟有多少种,那么如果再使用这种算法就有点得不偿失了。

    文中有一个叫tsx86的解法,将此题变成了纯粹的数学题,如下所示:

如果这个和越大,那相应的复杂度会很高。所以
因此,本题目组合总数为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;
}

这样程序简单太多了。

    以上文的原理就在于,将x+y*2+5*z=10转换成为10-5z=x+y*2,当z从0到2时,就转换成了求1和2的组合了,实际上就变成了10-5z中,可以有多少个偶数。故产生的结果就如上所示了。

    另外,文中提到了一个 求 如果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的最大取值也就是表达式中的这个常数。

    看来,数学还是很重要的。不然,不光是笔试过了不,连面试这种考思考方式的也过不了了。

转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/life/201110090001.html

相关文章:

作者: flym

I am flym,the master of the site:)

《解决1分2分5分硬币组合的数学问题》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注