中国剩余定理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,流 程 图,算法的描述,算法,自然语言,顺序结构,条件结构,循环结构,顺序结构,条件结构,循环结构,输 语句,伪 代 码,循环语句,赋值语句,条件语句,入出,中国剩余定理,(孙子问题),“孙子问题”记载在孙子算经中，原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”,孙子问题的现代数学描述,“孙子问题”相当于求关于,x,y,z,的方程组,的正整数解。,解题分析,（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,流程图,伪代码,m,2,While Mod (,m,3,)2,or,Mod (,m,5,)3,or M,od (,m,7,)2,m,m,1,End While,Print,m,例1 有3个连续的自然数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，求满足要求的一组三个连续的自然数。,分析：本题的其实就是求下面不定方程组的正整数解.,算法,S1 取m1；,S2 当m不能被15整除，或m1不能被17整除，或m,2不能被19整除，则m,m1，转S2；否则输,出m，m1，m2，算法结束.,流程图,m,1,While Mod (,m,15,)2_,or Mod (,m,1,17,)0_,orM,od (,m,2,19,)0,m,m,1,End While,Print m，m+1，m+2,伪代码,思考：以下伪代码是否可行？,k,1,a,15,k,While Mod(,a,1,17)0 or_,Mod(,a,2,19)0,k,k,1,a,15,k,End While,Print,a,a,1,a,2,本课小结,1韩信点兵孙子问题的求解算法；,2利用循环结构实现整数的搜索；,3利用逻辑运算符Or实现多条件的判断。,