查看: 4745|回复: 5

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

[复制链接]

字体大小: 正常放大

ilikenba

1万主题	49 听众	2万积分

TA的每日心情

	奋斗 2024-6-23 05:14

签到天数: 1043 天

[LV.10]以坛为家III

群组: 万里江山

群组: sas讨论小组

群组: 长盛证券理财有限公司

群组: C 语言讨论组

群组: Matlab讨论组

电梯直达

1^#

发表于 2004-6-15 22:11 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解：
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

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

风雨同行

4 主题	1 听众	63 积分

该用户从未签到

2^#

发表于 2004-6-16 10:15 |只看该作者 |招呼Ta 关注Ta

以下是引用ilikenba在2004-6-15 22:11:48的发言： 解释一下这个的原理，用欧几里德算法求二元一次方程的最小整数解： 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

加个非负条件吧- I) ^. C$ u' X) y3 n" x5 Z" z

这个解法倒着看就不难理解了 & I) E9 G" o- m3 z, e1 w. u9 R: P7 l

这个问题实际上可以先找通解，就很容易得到最小非负解了 s8 }! D9 ~0 v' B9 @

11x－49y＝1的通解是6 A) v+ e1 \2 k0 t) V/ s% y1 Q0 Q

x＝9＋49t，y＝2＋11t （t是整数） 8 i3 O- ~5 L6 ]' t' q

取t＝0得到最小非负解