数学建模社区-数学中国
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！ [打印本页]
作者: ilikenba 时间: 2004-6-15 22:11
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！
解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
+ l8 x* G4 O* k11x-49y=1，求x% E" E$ H: X( S2 m
（a） 11 x - 49 y = 1 49%11=5 ->( y h* ~9 m2 G+ A8 g
（b） 11 x - 5 y = 1 11%5 =1 ->& p6 _! w- S# C# ^
（c） x - 5 y = 1
+ F- D3 D* g2 v) i: n2 m令y=0 代入（c）得x=10 [3 ], \* D. w$ W( t) p* i: K L
令x=1 代入（b）得y=2& a0 O. A3 [8 W
令y=2 代入（a）得x=9
作者: 风雨同行 时间: 2004-6-16 10:15
以下是引用ilikenba在2004-6-15 22:11:48的发言：, I$ ` ^. O6 n; }& B
解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：' {- n2 h' b6 g% W
11x-49y=1，求x9 R( s# E" S$ L
（a） 11 x - 49 y = 1 49%11=5 ->2 R2 f; e' m6 [' v4 Y8 o2 i% m# J" M
（b） 11 x - 5 y = 1 11%5 =1 ->
, X, ]) K/ C. x（c） x - 5 y = 1
- O7 E+ n& H: `令y=0 代入（c）得x=1+ Y( x7 @! a. \8 s4 |; u
令x=1 代入（b）得y=27 m( @# G, o1 y
令y=2 代入（a）得x=9& E$ T; |: u/ [5 e- l" L A+ Z
/ i) u4 P8 _. C7 `$ l* K
加个非负条件吧
8 v4 f$ N1 W' V9 j
这个解法倒着看就不难理解了. G9 A: w8 L. I
这个问题实际上可以先找通解，就很容易得到最小非负解了
& g6 {$ Y8 ]2 [
11x－49y＝1的通解是
0 {( D$ Y- q0 E2 C# ] ]
x＝9＋49t，y＝2＋11t （t是整数）8 |- C7 ~2 m2 v) V: B
取t＝0得到最小非负解
作者: 风雨同行 时间: 2004-6-16 10:19
至于找通解的方法
大家想想线性方程组的通解是怎么找的就知道了
只不过这里的这个“线性方程组”只有一个方程罢了
作者: wslzlf2008 时间: 2004-12-18 10:12
这个不就是辗转相除的最简单的一个例子！！
作者: fup 时间: 2004-12-21 20:37
有道理，是这样的
作者: wqysk07250731 时间: 2005-3-9 20:43
切记非负的条件
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |