算法案例1孙子问题.ppt

算法案例1,中国剩余定理 孙子问题,人们在长期的生活，生产和劳动过程中，创造了整数、分数、小数、正负数的概念及其运算，在代数学、几何学等方面，我国在宋，元之前也都处于世界的前列。我们在小学、中学学到的算术，代数，从记数到多元一次联立方程的求根方法，都是我国古代数学家最先创造的。更为重要的是我国古代数学的发展有着自己鲜明的特色，也就是“寓理于算”，即把解决的问题“算法化”。,今有物不知数，三三数之剩二，五五数之剩三，七七数之剩二， 问物几何？,孙子算经,翻译：一个数除以3余2，除以5余3，除以7余2，问这个数是几?,三三数之剩二: 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,用现代符号表示为: N2mod33mod52mod7，其最小正数解是23,这一类问题的解法可以推广成解一次同余式组的一般方法奏九韶给出了理论上的证明，并将它定名为“大衍求一术”。这个问题的通用解法称为“中国剩余定理”,秦九韶 （公元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,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还有其它的解吗？,因为357=105,23+105 23+2105 23+3105都是本问题的解。,韩信何以很快知道队伍的人数？,23+22105=2333,算法设计结构：（自然语言）,S1：输入一个初始值m； S2：下述条件之一不满足，使m的值增加1后，再返回S2，直到都满足为止： （1）m被3除后余2； （2）m被5除后余3； （3）m被7除后余2； S3：输出m。,算法设计结构：（流程图）,输出m,ma,Mod(m,3)2,mm+1,结束,开始,Mod(m,3)2,Mod(m,3)2,算法设计语句：（伪代码）,10 m8 20 While Mod(m,3)2,or Mod(m,5)3,or Mod(m,7)2 30 mm+1 40 End While Print m,巩固运用,1写出下列符号的结果 int(2) int(3.2) int(-0.2) mod(1,2) mod(3,2),2一个三位数,如果每一位数字的立方和等于它本身，则称之为“水仙花数”设计一个算法，找出所有的水仙花数，用伪代码表示,回顾反思,解决不定方程问题其实并不难，只要使用循环，从小到大搜索即可