素毕达哥拉斯三元数组.doc

素毕达哥拉斯三元数组满足的正整数组(a,b,c)称为“毕达哥拉斯数组”，在中国又称“勾股数组”，代表一个直角三角形的三条边长。其中，较短的直角边称为“勾”，较长的直角边称为“股”，斜边称为“弦”。原理分析1、 表达式记则问题转化为：寻找有理数x和y使得，设（u、v为正整数，0tu的正整数u和v，若u和v没有公因子且不同时是奇数，则公式可产生全部的素毕达哥拉斯三元数组。2、 计算方法（1） 输入：数值m（不小于3的正整数）、位置代号location（“1”表示长度为奇数的直角边，“2”表示长度为偶数的直角边、“3”表示斜边）（2） 输出：输出结果为满足输入的边长和位置的全部素毕达哥拉斯三元数组，若输入错误则输出为空。（3） 计算过程（首先求出u和v，进而可算出a、b和c。以下仅为求u和v的过程）输入“1”号位，即当m为偶数时，设v=u+x（x为正整数）,则对于所有不大于的正整数x，分别计算若u和v均为整数，则记录数组(u,v)。输入“2”号位，即当m为偶数时，对所有不大于的正整数u，计算若v为整数且u、v互质，则记录数组(u,v)。输入“3”号位，即当m为奇数时，对所有不大于的正整数u，计算若v为整数，则记录数组(u,v)。3、 时间复杂度根据算法原理，可见在最不利的情况下抛物线法的时间复杂度为。参考资料1 R.柯朗,H.罗宾.什么是数学（第三版） MATLAB程序注：函数GreatestCommonDivisor(u,v)的计算结果为u和v的最大公约数function Z=Pythagoras(m,location)U=;V=;if m2 & ceil(m)=m switch location case 1 if ceil(m/2)=m/2 for x=1:floor(sqrt(m)-1) u=(m-x2)/2/x; v=sqrt(m+u2); if floor(u)=u & floor(v)=v U(length(U)+1)=u; V(length(V)+1)=v; end; end; end; case 2 if ceil(m/4)=m/4 for u=1:floor(sqrt(m/2) v=m/2/u; if floor(v)=v & GreatestCommonDivisor(u,v)=1 U(length(U)+1)=u; V(length(V)+1)=v; end; end; end; case 3 if ceil(m/2)=m/2 for u=1:floor(sqrt(m-1)/2) v=sqrt(m-u2); if floor(v)=v U(length(U)+1)=u; V(length(V)+1)=v; end; end; end; end;end;A=V.2-U.2;B=2.*U.*V;C=V.2+U.2; Z=A,B,C;计算实例输入输出mlocationZ=Pythagoras(m,location)25125, 312, 313362323, 36, 325;77, 36, 8549335131135131, 617093580, 617093581;35131, 1709220, 1709581;35131, 332820, 334669432602467856899, 43260, 467856901;116964221, 43260, 116964229;51984091, 43260, 51984109;18714251, 43260, 18714301;12995989, 43260, 12996061;9548051, 43260, 9548149;4678469, 43260, 4678669;2386829, 43260, 2387221;2079139, 43260, 2079589;1060459, 43260, 1061341;518941, 43260, 520741;380699, 43260, 383149;263461, 43260, 2669