中國剩余定理(孫子問題)

1、流 程 圖算法的描述算法自然語言順序結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)輸 語句偽 代 碼循環(huán)語句賦值語句條件語句入出中國剩余定理中國剩余定理 (孫子問題孫子問題)“孫子問題孫子問題”記載在孫子算經(jīng)中，記載在孫子算經(jīng)中，原文是：原文是：“今有物不知其數(shù)，三三今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？之剩二，問物幾何？” 孫子問題的現(xiàn)代數(shù)學描述孫子問題的現(xiàn)代數(shù)學描述“孫子問題孫子問題”相當于求關于相當于求關于x,y,z的方程組的方程組的正整數(shù)解。的正整數(shù)解。 273523zmymxm解題分析解題分析（1）如何依次檢索正整數(shù)？）如何依

2、次檢索正整數(shù)？ （采用循環(huán)結(jié)構(gòu)）（采用循環(huán)結(jié)構(gòu)） （2）該循環(huán)何時結(jié)束？）該循環(huán)何時結(jié)束？ （找到滿足條件的整數(shù)為止）（找到滿足條件的整數(shù)為止） （3）一個正整數(shù)）一個正整數(shù)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 2While Mod (m,3)2 )2 or Mod (m,5)3

3、)3 or M or Mod (m,7)2)2 m m1End WhilePrint m例1 有3個連續(xù)的自然數(shù)，其中最小的能被15整除，中間的能被17整除，最大的能被19整除，求滿足要求的一組三個連續(xù)的自然數(shù)。 分析：本題的其實就是求下面不定方程組的正整數(shù)解分析：本題的其實就是求下面不定方程組的正整數(shù)解. 15 ,117 ,219 .mxmymz 算法S1 取取m1；S2 當當m不能被不能被15整除，或整除，或m1不能被不能被17整除，或整除，或m 2不能被不能被19整除，則整除，則mm1，轉(zhuǎn)，轉(zhuǎn)S2；否則輸；否則輸 出出m，m1，m2，算法結(jié)束，算法結(jié)束. 流程圖 m 1While Mod (m,15)2_)2_ or Mod (m1,17)0_ )0_ orM orMod (m2,19)0)0 m m1End WhilePrint m，m+1，m+2偽代碼偽代碼思考：以下偽代碼是否可行？思考：以下偽代碼是否可行？ k1a15kWhile Mod(a1,17)0 or_ Mod(a2,19)0 kk1 a15kEnd While Print a,a1,a2本課小結(jié)本課小結(jié)1韓信點兵孫子問題的求解算法；韓信點兵孫子問題的求解算法； 2利用循環(huán)結(jié)