勾股数问题分析与解答 - 苗苗的日志 - 网易博客

勾股数问题分析与解答 - 苗苗的日志 - 网易博客
勾股数问题分析与解答
默认分类 2008-08-21 07:57 阅读79 评论0
字号： 大大 中中 小小

[定义]如果直角三角形三条连长均为整数,这三个整数组成的数组就称为勾股数组,对于勾股数组(a,b,c),根据定理有关系式:a*a+b*b=c*c.

[问题]有一种勾股数组(a,b,c)使得b=a+1,例如:20*20+21*21=29*29;用程序找出指定范围(1
输入数据文件IN.TXT

只有一行为整数N,表示指定的范围,1
输出数据文件OUT.TXT

分行列出所有结果,数组间用","分隔,从小到大排列.


分析

本期问题收到很多读者的解答,解答的思路大致分为三类:

一.遍历求解:这类算法最简单,也最耗时,两个遍历条件得到结果的算法复杂度是O(n*n),显然不是好的算法.

二.约束条件:很多读者意识到,当a确定后,通过c/sqrt(2)-1
三.递归算法:应用这种方法解答的只有三位读者:马苏宏,郝文辉,邓敏.以下是马苏宏的推理:

设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

解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外,所有其他勾股数组均可逆向使用上述公式,由另一组比较小的勾股数推出.

总结递推公式如下:

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).

郝文辉的解答用到了一些数论知识,解答也是正确的,这种方法在数论中被称为无穷递降法,是Fermat(法国数学家,以Fermat大定理而闻名)首次发明使用的.


按照上述第三种分析的思路,编程非常容易:

#include

const int NORMAL=0;

const int ERROR1=-1;

const int ERROR2=-2;

int main(void)

{

FILE *fp;

long a=3,c=5;

long n;

if(!(fp=fopen("IN.TXT","r"))) return ERROR1;

fscanf(fp,"%d",&n);

fclose(fp);

if(!(fp=fopen("OUT.TXT","w"))) return ERROR2;

while(c
{

fprintf(fp,"%d,%d,%d\n",a,a+1,c);

c+=a+1;

a+=c*2-1;

c+=1;

}

fclose(fp);

return NORMAL;

}