作者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
推 Hseuler:有很多種算法 暴力用程式算出來和你答案一樣 12/02 23:38
推 Hseuler:H(6,5)-H(2,5) 也可以得到答案 12/03 00:32
→ prag222:離散數學嗎?嗯嗯雖然看不懂但還是多謝了~!! 12/05 17:46
→ prag222:也有人是用排列組合的方式去算 12/05 17:47
→ prag222:我暴力法算過1000000~9999999符合我的算法,所以應該是ok的 12/05 17:48
推 b60624563:恩.. 這個可以用小小的程式來做~ 12/13 09:34
推 b60624563:樓上答案是210媽?? 12/13 09:37
推 Hseuler:高中的排列組合 12/14 12:39
→ prag222:是210沒錯,其實也有人是用排列組合的做法~謝囉 01/12 22:00