作者superlori (衝刺吧!!(握拳))
看板Math
標題Re: [離散]聯立方程非負整數解
時間Wed Sep 5 11:35:10 2012
※ 引述《physmd (smd)》之銘言:
: 類似的問題在版上應該出現過很多次了,不過暫時爬文找不到。
: 有請各位版友提供建議,謝謝~
: 求下列聯立方程的非負整數解:
: x + y + z = n
: x + 2y + 3Z = m
: n, m 為已知正整數,並且給定良好使得上列方程有解。
: (譬如說 n = 15, m = 20 之類的)
: 顯然可以滿足此聯立方程的 (x, y, z) 有很多組。如果不能明確求出
: (x, y, z),是否可以至少算出解的個數?
: 跑程式來完全列出所有的解固然是一個方法,但是當 n 跟 m 比較大的
: 時候就不切實際了。譬如說 n = 100, m = 110 或是更大之類的。
: (我實際上應用到的情況 n 跟 m 只會到 300 或 400 左右,並不會更大啦)
: 我沒有念過離散數學,而高中程度的排列組合當然是不夠用的。純粹為了
: 要解這個問題,有哪些入門以及進階的好書呢?
: 另外,感覺上似乎可以用連續函數還有微積分的分析方法來估計.....
: 不知版友是否有任何線索?
: 謝謝
不知道你想要知道的是不是這個方式
先將聯立方程組視為兩平面交為一直線
x + y + z = n ---E_1
x + 2y + 3z = m ---E_2
(1)
│1 1│ │1 1│ │1 1│
兩平面交於直線L,L的法向量為 (│ │ │ │ │ │) = (1,-2,1)
│2 3│,│3 1│,│1 2│
(2)
由方程組求L的一交點,不失一般性y=0,
x + z = n
x + 3z = m
3n-m m-n
得到一組交點(------- , 0 , -------)
2 2
(3)
L上的每一點可表為參數式
3n-m m-n
(x,y,z)= ( ------- + t , -2t , ------- + t )
2 2
如果用你說的例子,n=300 , m=400代入
x= 250 + t
y= -2t
z= 100 + t
要求(x,y,z)的非負整數解的話,那麼 -100<=t<=0 即為所求
可以解出所有(x,y,z)解的組數以及所有解
不知道有沒有誤會題意?
--
★ superlori:今天的冰好吃嗎???
★ superlori 好吃好吃!!!(猛點頭中)
★ superlori:妳知道為什麼好吃嗎???
★ superlori 不知道耶!!!(笑笑地搖搖頭聳聳肩)
★ superlori因為有我在呀!!....哈哈...
★ superlori 討厭啦....(害羞中)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.21.38.253
推 physmd :水喔~~ 真是快捷漂亮阿 原來我想太多了 :P 多謝 09/05 11:44
→ superlori :如果你要做一般通式的話要再討論(3n-m)/2和(m-n)/2 09/05 11:46
→ superlori :的大小關係就可以得到一般式的通解 09/05 11:47