※ 引述《me5119 (the end~~~)》之銘言:
: x+2y+3z=13
: 的非負整數解
: 可以用H來算嗎?
: THX
因為 x 前面係數是 1
這題可以想成:2y+3z≦13的非負整數解
所以 z≦4
z=0 : y≦6 ,7種
z=1 : y≦5 ,6種
z=2 : y≦3 ,4種
z=3 : y≦2 ,3種
z=4 : y≦0 ,1種
因此共有 21 種
=========================================
雖然看起來好像只比土法練鋼快一點,
沒什麼大不了的。
但當 n 大了以後呢?
例如 x+2y+3z=100 的非負整數解有幾種?
一樣的,我們想成 2y+3z≦100
因此 z≦33
z=0 : 2y≦100, y≦50,有51種
z=1 : 2y≦ 97, y≦48,有49種
z=2 : 2y≦ 94, y≦47,有48種
z=3 : 2y≦ 91, y≦45,有46種
z=4 : 2y≦ 88, y≦44,有45種
z=5 : 2y≦ 85, y≦42,有43種
.
.
.
z=32: 2y≦ 4, y≦ 2,有 3種
z=33: 2y≦ 1, y≦ 0,有 1種
發現了嗎?
其實可以拆成2個等差數列,
而且兩個數列的公差都是3,
把兩個數列的級數值算出來並相加就是答案。
結論:
x+py+qz=n 的非整數解的數量,
(p,q,n 皆為自然數,且 p < q)
可以想成 py+qz≦n 的非整數解的數量,
並進一步化成 p 個公差為 q 的級數和相加。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.89.133
→
03/23 16:07, , 1F
03/23 16:07, 1F
→
03/23 16:08, , 2F
03/23 16:08, 2F
→
03/23 16:08, , 3F
03/23 16:08, 3F
推
03/23 18:01, , 4F
03/23 18:01, 4F
推
03/23 23:23, , 5F
03/23 23:23, 5F
推
03/24 00:17, , 6F
03/24 00:17, 6F
討論串 (同標題文章)