素毕达哥拉斯三元数组
素毕达哥拉斯三元数组
满足a +b =c 的正整数组(a , b , c ) 称为“毕达哥拉斯数组”，在中国又称“勾股数组”，代表一个直角三角形的三条边长。其中，较短的直角边称为“勾”，较长的直角边称为“股”，斜边称为“弦”。
2
2
2
原理分析
1、表达式
记
⎧a ⎪c =x ⎨b ⎪=y
⎩c
则问题转化为：寻找有理数x 和y 使得
x 2+y 2=1，x , y ∈(0, 1) y 2=1-x 2=(1-x )(1+x )
设
y 1-x u
==t =（u 、v 为正整数，0
则
⎧1-t 2⎧y =t ⋅(1+x ) ⎧t ⋅x -y =-t ⎪⎪x =1+t 2
⇒⎨⇒⎨ ⎨2t 1-x =t ⋅y x +t ⋅y =1⎩⎩⎪y =
⎪1+t 2⎩
因此
⎧u 2
⎪a 1-2v 2-u 2
=2⎪=2u c v +u 2⎪1+2
⎪v ⎨u ⎪2⋅b =2⋅u ⋅v ⎪=⎪c u 2v 2+u 2
1+2⎪
v ⎩
⎧a =(v 2-u 2) ⋅r ⎪
⎨b =(2⋅u ⋅v ) ⋅r ⎪c =(v 2+u 2) ⋅r ⎩
对于任意v >u 的正整数u 和v ，若u 和v 没有公因子且不同时是奇数，则公式
⎧a =v 2-u 2⎪
⎨b =2⋅u ⋅v ⎪c =v 2+u 2⎩
可产生全部的素毕达哥拉斯三元数组。
2、计算方法
（1）输入：数值m （不小于3的正整数）、位置代号location （“1”表示长度为奇数的直角边，“2”表示长度为偶数的直角边、“3”表示斜边）
（2）输出：输出结果为满足输入的边长和位置的全部素毕达哥拉斯三元数组，若输入错误则输出为空。
（3）计算过程（首先求出u 和v ，进而可算出a 、b 和c 。以下仅为求u 和v 的过程）
①输入“1”号位，即m =a =v -u 当m 为偶数时，设v =u +x （x 为正整数）, 则
2
2
m =v 2-u 2=(u +x ) 2-u 2=x 2+2⋅u ⋅x
对于所有不大于m -1的正整数x ，分别计算
⎧m -x 2⎪u =
2x ⎨
⎪v =m +u 2⎩
若u 和v 均为整数，则记录数组(u , v ) 。
②输入“2”号位，即m =b =2⋅u ⋅v
当m 为偶数时，对所有不大于
m
的正整数u ，计算 2
v =
m 2⋅u
若v 为整数且u 、v 互质，则记录数组(u , v ) 。
③输入“3”号位，即m =c =v +u
2
2
当m 为奇数时，对所有不大于
m -1
的正整数u ，计算 2
v =m -u 2
若v 为整数，则记录数组(u , v ) 。
3、时间复杂度
根据算法原理，可见在最不利的情况下抛物线法的时间复杂度为O (n ) 。
参考资料
[1] R.柯朗,H. 罗宾. 什么是数学（第三版）
MATLAB 程序
注：函数GreatestCommonDivisor(u,v)的计算结果为u 和v 的最大公约数 function Z=Pythagoras(m,location) U=[]; V=[];
if m>2 & ceil(m)==m switch location case 1
if ceil(m/2)~=m/2
for x=1:floor(sqrt(m)-1) u=(m-x^2)/2/x; v=sqrt(m+u^2);
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-u^2);
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'];
计算实例