一道算法题，求最优解法？

liuke432

有一种数组(a,b,c)，满足条件: a*a+b*b=c*c和b=a+1。例如（3,4,5)。
用程序找出指定范围(1<a,b,c<N)内所有的这种数组,求最优算法。

1.普通的解法： 群举法

1. 
   
2.    for(i=2,i<N,i++)
   
3.        for(j=2,j<N,j++)
   
4.            for(k=2,k<N,k++)
   
5.              if((i*i+j*j==k*k)&&(j==i+1))
   
6.                  printf("%d,%d,%d\n",i,j,k);
   

复制代码

                 
2.优化一下，去掉一层for循环

1. 
   
2.    for(i=2,i<N,i++)
   
3.        for(k=i+1,k<N,k++)
   
4.              if(i*i+(i+1)*(i+1)==k*k)
   
5.                  printf("%d,%d,%d\n",i,i+1,k);
   

复制代码

                 
请问还有没有其它更优化的算法？  

[ 本帖最后由 liuke432 于 2008-4-17 13:36 编辑 ]

cugb_cat

还可以再去掉一层循环，知道a的值了，就知道c的值和b的值了，判断一下b和c是不是在范围内就行了。

LinuxKen

c 也是整数？

Smeagol

貌似LZ的第二种方法就可以了，如果单纯以循环判断优劣，可以用cugb_cat 斑竹的方法，但是同时也增加了很多运算和比较...

liuke432

原帖由 cugb_cat 于 2008-4-17 13:44 发表
还可以再去掉一层循环，知道a的值了，就知道c的值和b的值了，判断一下b和c是不是在范围内就行了。

写成程序是什么样的呢？c用a怎么表示呢，带根号的？   ：）

liuke432

原帖由 LinuxKen 于 2008-4-17 13:51 发表
c 也是整数？

a,b,c 都是整数

cugb_cat

符合勾股定理的数貌似不是很多，数论书上有介绍这个的，推荐陈景润的初等数论，上面有比较详细的讨论勾股数的内容，我感觉通过一些公式和定理，可以减少很多计算。

cjaizss

b^2-a^2=(b+a)(b-a)=a+b
只要a+b为平方数即可

liuke432

原帖由 cjaizss 于 2008-4-17 14:47 发表
b^2-a^2=(b+a)(b-a)=a+b
只要a+b为平方数即可

但这里是b=a+1, 是b和a有这样的关系。
如果是c和a有这样的关系，这个等式倒可以用。

wxycyel

有两个意见
1 第一层循环中I的值不用到N,最大到N除以2的平方根(取整)就可以了,因为再大的话, I^2 + (I+1)^2就大于N^2了;
2 一个循环就可以, 可以在这次循环中对I^2+(I+1)^2的值,进行检查,如果值小于N并且是一个整数的平方数就输出I

[ 本帖最后由 wxycyel 于 2008-4-17 16:18 编辑 ]