用条件合并法解决中国剩余定理有关问题

用条件合并法解决中国剩余定理问题
这种方法可以在小学生中运用。

解题过程

XML code

《孙子算经》一道问题：今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二。问物几何？解法：先列出条件，1）除以3余22）除以5除33）除以7余2求同时满足以上3个条件的数。条件合并法解法步骤：先看满足同时条件1）和2）的数。3和5的最小公倍数（3，5）为15，在15的所有余数1，2，3，4，5，6，…，13，14中，同时满足1）、2）条件的数为8。与8同类的数为：除以15余8的数。现在，将原题的3个条件合并为： 1）除以15余82）除以7余2求同时满足以上2个条件的数。15和7的最小公倍数（15，7）为105，在105的所有余数1，2，3，…，103，104中，同时满足1）、2）条件的数为23。与23同类的数为：除以105余23的数。结论：满足原题3个条件的数为除以105余23的数，最小的就是23。 再做一道：一个数，除以4少1，除以6余5，除以15余14，这个数在150~200之间，求这个数。列出条件：1）除以4余32）除以6余53）除以15余14先看满足同时条件1）和2）的数。4和6的最小公倍数（4，6）为12，在12的所有余数1，2，3，4，5，6，…，10，11中，同时满足1）、2）条件的数为11。与11同类的数为：除以12余11的数。现在，将原题的3个条件合并为：1）除以12余112）除以15余14求同时满足以上2个条件的数。 12和15的最小公倍数（12，15）为60，在60的所有余数1，2，3，…，58，59中，同时满足1）、2）条件的数为59。与59同类的数为：除以60余59的数。 结论：满足原题3个条件的数为除以60余59的数，最小的就是59。前面几项分别是：59，119，179，239，…。满足原题150~200之间的，就是179。

[解决办法]
有段时间没见版主，来就送分。
[解决办法]
学习了~~谢·
[解决办法]
不错。。。
有点意思。。
关注。。。
[解决办法]
up
[解决办法]
请问一下楼主，对于第一道题，我这样写有什么不妥：

Dim x As Long
Dim y As Long = 2
Dim z As Long = 3
Dim m As Long = 2
For x = 1 To 2147483647
If x Mod 3 = y And x Mod 5 = z And x Mod 7 = m Then
TextBox1.Text = x
MsgBox(x)
End If
Next
[解决办法]
了解,进来看看

[解决办法]
good

[解决办法]
学习了，帮顶
[解决办法]
11111111111111111111111111111111111
[解决办法]
不错，学习了
[解决办法]
学习一下啊
[解决办法]
这么牛呀
学习
[解决办法]
真的应该好好学习vb啦，向你们学习啊
[解决办法]
恩 不杂懂 得研究研究

[解决办法]

[解决办法]
帮顶~~~~~
[解决办法]
up 
JF
[解决办法]
路过，接分
[解决办法]
收藏

[解决办法]
up 学习
[解决办法]
这是在练内功，积蓄力量，适合于在校生、无业游民。

每天忙于项目者，有心练下，可都没时间研究这些了。


[解决办法]
版主的贴哦！学习了。
[解决办法]
帮顶

[解决办法]
好贴...
[解决办法]
帮顶
[解决办法]
好好
[解决办法]
学习了~~谢·
[解决办法]
学习了~~谢·
[解决办法]
合并体现在哪？

我只看出用了标准解法。。。。
[解决办法]
貌似可以做为演示用的课件....

而且可以对比暴力法培养小学生们的程序思维,呵呵
[解决办法]
水版主又开始研究算法啦！

顶下……
[解决办法]
fffff
[解决办法]
强细
[解决办法]
还好！很强大！
[解决办法]
up
[解决办法]
先记下
[解决办法]
收藏了,谢谢
小时候特喜欢这种应用题~
[解决办法]
这算是伪代码吗？看不懂
[解决办法]
先顶了，在好好琢磨一下
[解决办法]
学习了，顶
[解决办法]
学习了
[解决办法]
顶一下
[解决办法]
hao!
[解决办法]
帮顶
[解决办法]
bangding
[解决办法]
顶！
[解决办法]
学习学习.......
[解决办法]
ding
[解决办法]
up
[解决办法]
学习了 呵呵
[解决办法]
up
[解决办法]
试试看
[解决办法]
现在才开始学，要好好向各位学习。
[解决办法]
水之
[解决办法]
:)
印象中，类似的问题，与初等数论结合也很容易解决。
[解决办法]
不懂
[解决办法]
学习了
[解决办法]

探讨

请问一下楼主，对于第一道题，我这样写有什么不妥：

Dim x As Long
Dim y As Long = 2

Dim z As Long = 3
Dim m As Long = 2
For x = 1 To 2147483647
If x Mod 3 = y And x Mod 5 = z And x Mod 7 = m Then
TextBox1.Text = x
MsgBox(x)
End If
Next

[解决办法]
算法问题
很好
[解决办法]
用蒙的办法：
For i As Integer = 0 To 100
If i Mod 3 = 2 Then
If i Mod 5 = 3 Then
If i Mod 7 = 2 Then
Response.Write(i)
Exit Sub
End If
End If
End If
Next
[解决办法]
JF
[解决办法]
看一看感受不错
[解决办法]
up
[解决办法]
学习了~~
[解决办法]
将看似繁杂的条件进行合并，去繁就简，合理排除了很多无关数，效率更高。

ps:好久没来，这次刚来VB.NET版，曾经得到过楼主的帮助，又看到楼主，备感亲切。
[解决办法]
LZ的算法本质上还是穷举法，只不过用最小公倍数给穷举法设了一个循环上限。

如果这样的题目是保证有解的，LZ所设的循环上限就没有任何实际意义。

而且每一次合并条件后，要从头开始再来一次穷举，导致效率大大降低。

我认为10楼的办法才是正解。
[解决办法]
有意思。
[解决办法]
hao
[解决办法]
长知识了
[解决办法]
飘过
[解决办法]
学习了，
[解决办法]
自我评价水平超菜一直不敢露头
今发现版主给的题目很有特色，代码写的很亮
露头赞一个
[解决办法]
学习了啊
[解决办法]
牛，学习了
[解决办法]
数论的，怀念阿.....中国剩余定理
[解决办法]
help help !!!!
[解决办法]
支持一下啊
[解决办法]
好！！！鼓掌！！

查看更多 下一篇