作者prag222 (prag)
看板logic
标题[讨论] 在100到1,000,000间的整数值之中,共有多少个整数值，将其每
时间Tue Dec 2 22:27:38 2008
在100到1,000,000间的整数值之中,共有多少个整数值，将其每个位数的值加总等於 5？例如：104 , 1 + 0 + 4 = 5 算是一个。
以下是我的想法大家帮忙看看是否正确吧~!!谢谢罗
首先我们可以把题目看成100～999999，因为1000000很明显不符合条件
而100～999999我们又可以看成是100～500000，因为六位数中500001以上就都不符合条件
而100～500000所有符合的状况又可分为
100～500(iab) 符合条件的状况ｉ=1,2,3,4,5
1000～5000(iabc) 符合条件的状况ｉ=1,2,3,4,5
10000～50000(iabcd) 符合条件的状况ｉ=1,2,3,4,5
100000～500000(iabcde) 符合条件的状况ｉ=1,2,3,4,5
=>因为不同位数符合条件的组合都不会相同....故可以依此分类
就以iab的三位数
i=1,1ab,要符合位数相加等於五也就是a+b=4,我们先算出a+b=4有5种状况
i=2,2ab,要符合位数相加等於五也就是a+b=3,我们先算出a+b=3有4种状况
i=3,3ab,要符合位数相加等於五也就是a+b=2,我们先算出a+b=2有3种状况
i=4,4ab,要符合位数相加等於五也就是a+b=1,我们先算出a+b=1有2种状况
i=5,5ab,要符合位数相加等於五也就是a+b=0,我们先算出a+b=0有1种状况
就以iabc的四位数
i=4,4abc要符合题目就是要a+b+c=1,而a只有0,1这2种状况
也就是说0+b+c=1和1+b+c=1才符合题目
移项一下,就等於求b+c=1跟b+c=0的状况次数,这时我们看到
我们不是在iab算出a+b=1跟a+b=0的状况次数了
变数不同但他们是一样的东西,所以4abc符合条件的状况等於b+c=1(a+b=1)的状况次数加b+c=0(a+b=0)的状况次数=>总共有(2+1)种状况
i=3,3abc要符合题目就是要a+b+c=2,而a只有0,1,2这2种状况
............(依此类推)
------------------------------------------------------
100~999位数相加总合=5的次数等於
5+4+3+2+1=15
1000~9999位数相加总合=5的次数等於
15(1+2+3+4+5)+10(1+2+3+4)+6(1+2+3)+3(1+2)+1=35
10000~99999位数相加总合=5的次数等於
35(1+3+6+10+15)+20(1+3+6+10)+10(1+3+6)+4(1+3)+1=70
100000~999999位数相加总合=5的次数等於
70(1+4+10+20+35)+35(1+4+10+20)+15(1+4+10)+5(1+4)+1=126
=>15+35+70+126=246
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.167.118.151
1F：推 Hseuler:有很多种算法 暴力用程式算出来和你答案一样 12/02 23:38
2F：推 Hseuler:H(6,5)-H(2,5) 也可以得到答案 12/03 00:32
3F：→ prag222:离散数学吗?嗯嗯虽然看不懂但还是多谢了~!! 12/05 17:46
4F：→ prag222:也有人是用排列组合的方式去算 12/05 17:47
5F：→ prag222:我暴力法算过1000000~9999999符合我的算法,所以应该是ok的 12/05 17:48
6F：推 b60624563:恩.. 这个可以用小小的程式来做~ 12/13 09:34
7F：推 b60624563:楼上答案是210妈?? 12/13 09:37
8F：推 Hseuler:高中的排列组合 12/14 12:39
10F：→ prag222:是210没错,其实也有人是用排列组合的做法~谢罗 01/12 22:00