数学建模社区-数学中国
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！ [打印本页]
作者: ilikenba 时间: 2004-6-15 22:11
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！
解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：8 b) l( a1 G/ b c: B m
11x-49y=1，求x0 G. M5 q3 C9 n# M8 \$ C+ _
（a） 11 x - 49 y = 1 49%11=5 ->0 v: Z5 D6 X, q
（b） 11 x - 5 y = 1 11%5 =1 ->
# L$ N; B7 c' \8 a5 \0 \. X# ]（c） x - 5 y = 1' k$ H; c* z/ {, ^
令y=0 代入（c）得x=1& B% f3 u; A9 N* e: v9 n
令x=1 代入（b）得y=2
8 C$ Z! \7 @5 | D# C令y=2 代入（a）得x=9
作者: 风雨同行 时间: 2004-6-16 10:15
以下是引用ilikenba在2004-6-15 22:11:48的发言：
* e8 V/ U, ]3 G( @5 U解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：2 {( m2 }9 @2 E$ B0 e" L
11x-49y=1，求x2 ~0 n3 O2 R% ], K6 B- i
（a） 11 x - 49 y = 1 49%11=5 ->
9 [3 d" d0 U3 e! M: t（b） 11 x - 5 y = 1 11%5 =1 ->9 ~) }1 e3 d4 W5 C* }: Y
（c） x - 5 y = 1
?1 V- i; o+ y n0 _( Y7 j/ Y令y=0 代入（c）得x=12 S+ ]: S/ M+ W
令x=1 代入（b）得y=2
7 P O/ q1 g' Z" Y5 B令y=2 代入（a）得x=9
1 t; l8 H7 ^6 }; p8 v
; {1 p+ R+ n. _8 c
加个非负条件吧
( Y4 |0 U1 S! b" ?' m
这个解法倒着看就不难理解了# h- Y+ D) Y v/ _! P/ ?
这个问题实际上可以先找通解，就很容易得到最小非负解了$ H6 E- u* T% J" f' o
11x－49y＝1的通解是
. x: ~7 ^ n$ R& F5 g( y" y: M
x＝9＋49t，y＝2＋11t （t是整数）
) f) o4 k" P/ _9 @: v
取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 |