本文部分信息来源于 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中,可以有多少个偶数。故产生的结果就如上所示了。