|
9#
楼主 |
发表于 07-6-18 14:17:28
|
只看该作者
我来推推!
从表面上看似乎要用到组合(Combine),但仔细观察会发现情况太多,运用组合来求解将会很费力。因此我采用数学推导:
设1分,2分,5分的硬币枚数各为X,Y,Z,将得出公式:
X+2*Y+5*Z=100
(1)当Y,Z为0时,X=100,所以X的取值范围:[0,100]
(2)当X,Z为0时,Y=50,所以Y的取值范围:[0,50]
(3)当X,Y为0时,Z=20,所以Z的取值范围:[0,20]
并且X,Y,Z均为整数。
由于Z最小,因此我就以Z来枚举观察其规律:
(1)当Z=0时,X+2*Y=100---->Y=(100-X)/2
要使Y为整数,100-X必须为偶数,即X必须为偶数,0--100之间的偶数有:100/2+1=51个
(2)当Z=1时,X+2*Y=95---->Y=(95-X)/2:
要使Y为整数,95-X必须为偶数,即X必须为奇数,0---95之间的奇数有:94/2+1=48个
(3)当Z=2时,X+2*Y=90--->Y=(90-X)/2
要使Y为整数,90-X必须为偶数,即X必须为偶数,0--90之间的偶数有:90/2+1=46个(比(1)少了5个)
(4)当Z=3时,X+2*Y=85---->Y=(85-X)/2
要使Y为整数,85-X必须为偶数,即X必须为奇数,0---85之间的奇数有:84/2+1=43个(比(2)少了5个)
......
此时我们可以得出规律:
(1)当Z为偶数时,X必然为偶数.当Z为奇数时,X必然为奇数
(2)当Z从0--20递增时,偶数和奇数间隔出现,每当Z增加2时,X的偶数或奇数个数比上次减少了5
根据这一规律我们可以得出两组等差数列:
51,46,41,36,31,26,21,16,11,6,1
48,43,38,33,28,23,18,13,8,3
将其求和可以得出Z从0--20递增时,X的奇数及偶数的总和,该值即为换法的总数:
(51+46+....6+1)+(48+43+...+8+3)
=11*(51+1)/2+10*(48+3)/2
=541
这是我目前的思路.
有好的想法欢迎发言! |
|