算法案例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
用现代符号表示为:
N≡2[mod3]≡3[mod5]≡2[mod7],其最小正数解是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还有其它的解吗

下一页