算法的案例1孙子问题1.ppt

人们在长期的生活，生产和劳动过程中，创造了整数、分数、小数、正负数的概念及其运算，在代数学、几何学等方面，我国在宋，元之前也都处于世界的前列。我们在小学、中学学到的算术，代数，从记数到多元一次联立方程的求根方法，都是我国古代数学家最先创造的。更为重要的是我国古代数学的发展有着自己鲜明的特色，也就是“寓理于算”，即把解决的问题“算法化”。 三三数之剩二: 2,5,8,11,14,17,20,23,26,29,32,35,***,3x+2 五五数之剩三: 3,8,13,18,23,28,33,38,43,48,53,58,***,5y+3 七七数之剩二: 2,9,16,23,30,37,44,51,58,65,72,79,***,7z+2 这一类问题的解法可以推广成解一次同余式组的一般方法．奏九韶给出了理论上的证明，并将它定名为“大衍求一术”。这个问题的通用解法称为“中国剩余定理” 秦九韶 （公元1202-1261年）南宋，数学家。他在1247年（淳佑七年）著成『数书九章』十八卷．全书共81道题，分为九大类：大衍类、天时类、田域类、测望类、赋役类、钱谷类、营建类、军旅类、市易类。这是一部划时代的巨著，它总结了前人在开方中所使用的列筹方法，将其整齐而有系统地应用到高次方程的有理或无理根的求解上去，其中对「大衍求一术」﹝一次同余组解法）和「正负开方术」﹝高次方程的数值解法）等有十分深入的研究。其中的“大衍求一术”﹝一次同余组解法），在世界数学史上占有崇高的地位。 孙子问题相当于求关于x,y,z的不定方程组： 的正整数解. m被3除余2，即:m-int(m/3)×3=2 或mod(m,3)=2 m被5除余3,即:m-int(m/5)×5=3 或mod(m,5)=3 m被7除余2,即:m-int(m/7)×7=2 或mod(m,7)=2 * * 算法案例1 中国剩余定理 孙子问题 今有物不知数，三三数之剩二，五五数之剩三，七七数之剩二， 问物几何？ 《孙子算经》 翻译：一个数除以3余2，除以5余3，除以7余2，问这个数是几? 用现代符号表示为: N≡2[mod3]≡3[mod5]≡2[mod7]，其最小正数解是23 m=3x+2 m=5y+3 m=7z+2 几个有关整除问题的运算符号： Int(x)----表示不超过x的最大整数； Mod(a,b)----表示a除以b所得的余数，称b为模。 Int(9/5)=? Int(19/5)=? Int(29/5)=? Mod(9,5)=? Mod(19,5)=? Mod(29,5)=? 算法设计思想： 首先,让m=2开始检验条件,若三个条件中有一个不满足,则m递增1,一直到同时满足三个条件为止。 如m=8，被3除余2，5除余3，7除余1，不符； 如m=9，被3除余0，不符； 如m=10，被3除余1，不符； 如m=11，被3除余2，被5除余1，不符； 如m=12，被3除余0，不符； 如m=13，被3除余1，不符； 如m=14，被3除余2， 5除余4，不符； 可验证得：m=23 满足条件的m还有其它的解吗？ 因为3×5×7=105 23+105 23+2×105 23+3×105…都是本问题的解。 韩信何以很快知道队伍的人数？ 23+22×105=2333 算法设计结构：（自然语言） S1：输入一个初始值m； S2：下述条件之一不满足，使m的值增加1后，再返回S2，直到都满足为止： （1）m被3除后余2； （2）m被5除后余3； （3）m被7除后余2； S3：输出m。 算法设计结构：（流程图） 输出m m←a Mod(m,3)≠2 m←m+1 结束 开始 Mod(m,3)≠2 Mod(m,3)≠2 算法设计语句：（伪代码） 10 m←8 20 While Mod(m,3)≠2,or Mod(m,5)≠3,or Mod(m,7)≠2 30 m←m+1 40 End While Print m 巩固运用 1．写出下列符号的结果 int(2) int(3.2) int(-0.2) mod(1,2) mod(3,2) 2．一个三位数,如果每一位数字的立方和等于它本身，则称之为“水仙花数”．设计一个算法，找出所有的水仙花数，用伪代码表示． *