数学建模社区-数学中国
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！ [打印本页]
作者: ilikenba 时间: 2004-6-15 22:11
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！
解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：) D9 I, y5 \& g
11x-49y=1，求x
- V2 |0 ]4 G- Y0 s& E8 N0 D7 E（a） 11 x - 49 y = 1 49%11=5 ->! h4 h- i I | @: M' @. A; c
（b） 11 x - 5 y = 1 11%5 =1 ->" n- v( h0 Z2 P7 H1 S. w$ q
（c） x - 5 y = 1
6 |3 G# j: [+ }- d6 J: \令y=0 代入（c）得x=1" N3 L5 Q0 [7 H% D, r
令x=1 代入（b）得y=2
0 B) s# `- W; F0 A( }令y=2 代入（a）得x=9
作者: 风雨同行 时间: 2004-6-16 10:15
以下是引用ilikenba在2004-6-15 22:11:48的发言：
8 A$ x5 A4 C( U5 q解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
5 l8 e8 i' V* y- x; L$ R* b2 u11x-49y=1，求x
1 R5 Z% M h9 U（a） 11 x - 49 y = 1 49%11=5 ->
! T" R3 Y. ]8 `' s（b） 11 x - 5 y = 1 11%5 =1 -> J' Z5 p# d2 O2 v% V
（c） x - 5 y = 16 w5 | b3 P/ h
令y=0 代入（c）得x=1$ _" [6 P: o( |( b( T1 I
令x=1 代入（b）得y=2% w1 C/ t, ~" E" F( L- H
令y=2 代入（a）得x=96 R) H! r3 T8 F) I, W
. D. L! H" h' s+ B
加个非负条件吧
* R2 Y/ T+ J& D" ?# G+ L
这个解法倒着看就不难理解了/ p" q, _ e3 X
这个问题实际上可以先找通解，就很容易得到最小非负解了
; [5 y1 N0 x! ~8 A V3 a
11x－49y＝1的通解是
9 M! M0 O* a! V7 y8 p$ Q0 Z
x＝9＋49t，y＝2＋11t （t是整数）
; _# @1 L1 O1 Z" L! h
取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 |