数学建模社区-数学中国
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！ [打印本页]
作者: ilikenba 时间: 2004-6-15 22:11
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！
解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
! g& X! x7 Q7 |9 s11x-49y=1，求x9 F7 A& H( G2 |6 v
（a） 11 x - 49 y = 1 49%11=5 -># }9 M* e/ D& ~" ~( U
（b） 11 x - 5 y = 1 11%5 =1 ->
5 R; w% ]+ W: e" a2 ~& P% i$ W（c） x - 5 y = 1/ A+ Z5 k" R. G7 v, D" S+ `
令y=0 代入（c）得x=1
5 n# s( n0 Z2 O! m N" Q6 Y/ G令x=1 代入（b）得y=2/ ^* ?4 b# b" X5 }; U
令y=2 代入（a）得x=9
作者: 风雨同行 时间: 2004-6-16 10:15
以下是引用ilikenba在2004-6-15 22:11:48的发言： X1 l+ P# w9 c2 @# ]2 k, ? ]
解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：- y, x0 F+ V+ `; A. P; \
11x-49y=1，求x
* [7 J9 ?- e, d7 Z（a） 11 x - 49 y = 1 49%11=5 ->
; ]4 x! Z. d7 @（b） 11 x - 5 y = 1 11%5 =1 ->4 h+ z1 W. b2 W3 D7 ]3 S
（c） x - 5 y = 1
# Y5 f) j, _! f! R7 I0 z令y=0 代入（c）得x=1
5 U+ J2 I6 M( q. E令x=1 代入（b）得y=2- N- T# K( y7 Z' G- q5 p
令y=2 代入（a）得x=9
+ E0 i) f1 V M; y# e
) {) _: D/ N& q加个非负条件吧 F* y. h5 X1 u* v
这个解法倒着看就不难理解了0 D/ F/ L/ C/ d( s4 p" l
这个问题实际上可以先找通解，就很容易得到最小非负解了2 d0 w2 E4 w9 P$ t S7 _
11x－49y＝1的通解是' N) t! b7 }8 r
x＝9＋49t，y＝2＋11t （t是整数）
% ^5 F! `2 F" J
取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 |