作者netsphere ()
看板Prob_Solve
標題Re: [問題] 有關於歐基里德擴展演算法
時間Sat Aug 14 13:05:08 2010
※ 引述《linkone (小豆豆)》之銘言：
: 給定一個方程式 ax+by=d 其中 d為 a,b 的最大公因數
: 要求出 |x|+|y| 的最小值...
: 上網看了很多的推導過程都看不太懂.....
: 只知道要用歐基里德求公因數的遞回觀念
: 不知道有無較簡潔的解釋方法?
: 麻煩各位了
我也有一個類似的問題想問
給定一個方程式 ax+by=d a,b,d為任意整數
要求出 |x|+|y| 的最小值 或 顯示無解
看起來沒辦法用擴充歐基里德的方式
有什麼比較好得方式來解呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.205.55.104
※ 編輯: netsphere 來自: 123.205.55.104 (08/14 13:05)
推 scwg:Extended Euclidean Algorithm 本來就可以知道是不是無解啊.. 08/15 05:23
推 yzugsr:為什麼會無解? 沒說x,y一定要是整數 08/15 14:27
→ yzugsr:這不就是條直線嗎? 08/15 14:27
→ kytu:恩...原PO的意思應該是x,y隸屬於整數 08/15 18:31
→ kytu:也就是不定方程式有整數解。 08/15 18:42
推 suhorng:一直搞不懂的是|x|+|y|最小, 之前沒找到證明Orz 08/15 19:10