路漫漫其悠远
本资料来源
路漫漫其悠远
算法 S1 取m＝1； S2 当m不能被15整除，或m＋1不能被17整除，或m
＋2不能被19整除，则mm＋1，转S2；否则输 出m，m＋1，m＋2，算法结束.
路漫漫其悠远
流程图
路漫漫其悠远
伪代码
m1 While Mod (m,15)≠2_
or Mod (m＋1,17)≠0_ orMod (m＋2,19)≠0 m m＋1 End While Print m，m+1，m+2
解题分析 （1）如何依次检索正整数？
（采用循环结构） （2）该循环何时结束？
（找到满足条件的整数为止） （3）一个正整数m什么时候满足方程？
（m同时满足被3除余2，被5除余3，被7除余2）
引入记号：m被3除余2用符号表示为Mod(m，3)
＝2；m被5除余3用符号表示为Mod(m，5)＝3；m被 7除余3用符号表示为Mod(m，7)＝2
中国剩余定理(孙子问题)
路漫漫其悠远 2020/4/14
中国剩余定理
(孙子问题)
路漫漫其悠远
“孙子问题”记载在《孙子算经》中 ，原文是：“今有物不知其数，三 三数之剩二，五五数之剩三，七七 数之剩二，问物几何？”
孙子问题的现代数学描述 “孙子问题”相当于求关于x,y,z的方程组
的正整数解。
路漫漫其悠远
路漫漫其悠远
流程图
路漫漫其悠远od (m,5)≠3 or Mod (m,7)≠2 m m＋1 End While Print m
路漫漫其悠远
例1 有3个连续的自然数，其中最小的能被15整除，中 间的能被17整除，最大的能被19整除，求满足要求的 一组三个连续的自然数。 分析：本题的其实就是求下面不定方程组的正整数解.
路漫漫其悠远
思考：以下伪代码是否可行？
k1 a15k While Mod(a＋1,17)≠0 or_
Mod(a＋2,19)≠0 kk＋1 a15k End While Print a,a＋1,a＋2
路漫漫其悠远
本课小结 1．韩信点兵－孙子问题的求解算法； 2．利用循环结构实现整数的搜索； 3．利用逻辑运算符Or实现多条件的判断。