ilikenba 发表于 2004-6-15 22:11

在网上看到的问题，一时找不到原理在哪，大家看看！

解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
11x-49y=1，求x
（a） 11 x - 49 y = 1    49%11=5 ->
（b） 11 x -  5 y = 1    11%5 =1 ->
（c）    x -  5 y = 1
令y=0 代入（c）得x=1
令x=1 代入（b）得y=2
令y=2 代入（a）得x=9

风雨同行 发表于 2004-6-16 10:15

<DIV class=quote><B>以下是引用<I>ilikenba</I>在2004-6-15 22:11:48的发言：</B>
解释一下这个的原理，用欧几里德算法求二元一次方程的<FONT color=#ee11c2>最小整数解</FONT>：
11x-49y=1，求x
（a） 11 x - 49 y = 1    49%11=5 -&gt;
（b） 11 x -  5 y = 1    11%5 =1 -&gt;
（c）    x -  5 y = 1
令y=0 代入（c）得x=1
令x=1 代入（b）得y=2
令y=2 代入（a）得x=9
</DIV>
<P>加个非负条件吧
<P>这个解法倒着看就不难理解了
<P>这个问题实际上可以先找通解，就很容易得到最小非负解了
<P>11x－49y＝1的通解是
<P>x＝9＋49t，y＝2＋11t （t是整数）
<P>取t＝0得到最小非负解

风雨同行 发表于 2004-6-16 10:19

<P>至于找通解的方法</P><P>大家想想线性方程组的通解是怎么找的就知道了</P><P>只不过这里的这个“线性方程组”只有一个方程罢了</P>

wslzlf2008 发表于 2004-12-18 10:12

<FONT color=#99667b>这个不就是辗转相除的最简单的一个例子！！</FONT>

fup 发表于 2004-12-21 20:37

有道理，是这样的

wqysk07250731 发表于 2005-3-9 20:43

切记非负的条件
页: [1]
查看完整版本: 在网上看到的问题，一时找不到原理在哪，大家看看！