一.问题描述
如果直角三角形三条边长均为整数,这三个整数组成的数组就称为勾股数组,对于勾股数组(a,b,c),根据定理有关系式:a^2 + b^2=c^2
问题: 有一种勾股数组(a,b,c),使得b=a+1.例如: 3^2+4^2=5^2;
用程序找出指定范围(1 二. 分析 1.遍历求解:这类算法最简单,也最耗时.两个遍历条件得到结果的算法复杂度是0(n^2),显然这不是好算法. 2.递归算法: 设 a,b,c为一组勾股数, 设 m= c--a,有 a^2+(a+1)^2=(a+m)^2; 视m 为常数,解得: a= m--1+sqrt(2*m*(m-1)) 因a是整数,故2*m*(m-1)是完全平方数,有整数n>=0,使得: 2*m*(m-1)=(m+n)^2; 1 解m得: m ==n+1+sqrt((n+1)^2+n^2); 因为m是整数,故(n+1)^2+n^2是完全平方数. 当n=0时,代入得到a=3,b=4,c ==5. 当n<>0时,n,n+1,sqrt((n+1)^2+n^2)构成一组勾股数. 可见,除3,4,5外,所有其他勾股数组均可逆向使用上述公式,由另一组比较小的勾股数推出. 由 1 得: m^2 =n^2 +2m+2mn 2m(m-1) = n^2+m^2+2mn=(m+n)^2. 所以: a = m-1+n+m=n+2*m-1=n + 2*b(n) +2*c(n) --1; 总结递推公式如下: a(0)=3 b(0)=4 c(0)=5 a(n+1) = a(n) +2*b(n) +2*c(n) -1 b(n+1)=a(n+1) +1; c(n+1)=a(n+1) +b(n) +c(n) 本文来自CSDN博客，转载请标明出处：http://www.nigeriaembassy.cn/fisher_jiang/archive/2006/04/20/671018.aspx
