数学建模社区-数学中国
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！ [打印本页]
作者: ilikenba 时间: 2004-6-15 22:11
标题: 在网上看到的问题，一时找不到原理在哪，大家看看！
解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
n3 _6 K ^6 \9 L+ N( O11x-49y=1，求x: e1 J# C# H' B1 @ n
（a） 11 x - 49 y = 1 49%11=5 ->- O) R7 K5 B" ~- k, v
（b） 11 x - 5 y = 1 11%5 =1 ->
) u2 Y0 |/ } Z3 J. w（c） x - 5 y = 1
; g; K5 j" r, g; o5 s令y=0 代入（c）得x=1
. h/ q, b0 [, \4 k. m; p令x=1 代入（b）得y=25 M+ Q3 \5 m; K
令y=2 代入（a）得x=9
作者: 风雨同行 时间: 2004-6-16 10:15
以下是引用ilikenba在2004-6-15 22:11:48的发言：- p; _! ~ C, K$ w# O, d- L
解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
9 R1 S0 k5 [3 n' U11x-49y=1，求x+ t0 f9 V7 l9 K& a0 q! i1 Z* i
（a） 11 x - 49 y = 1 49%11=5 -> ]% ^8 S$ p' O1 X/ R7 ^7 B2 X
（b） 11 x - 5 y = 1 11%5 =1 ->
9 J- _6 ]/ h6 z9 ?$ ^$ v（c） x - 5 y = 1
# ]' i R$ f! C, z令y=0 代入（c）得x=1
8 \( k! e2 s/ ~# I( U# o令x=1 代入（b）得y=2
# ?* M8 `6 y2 ^* E令y=2 代入（a）得x=9 X4 }) a2 s2 F9 p- E' b
9 }) g5 C# a/ ?7 \" z
加个非负条件吧
( S& W/ W. f9 u2 ~
这个解法倒着看就不难理解了1 ]- L$ D6 b7 X% h0 b
这个问题实际上可以先找通解，就很容易得到最小非负解了- T M u) F- W# `# R
11x－49y＝1的通解是0 }1 l. e& g, S& ]
x＝9＋49t，y＝2＋11t （t是整数）
. u; i. ?8 z8 j7 A0 S
取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 |