本文部分信息来源于 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
Hey, that’s pwoefrul. Thanks for the news.
难道做程序猿数学一定要学号!!