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

liuke432

原帖由 wxycyel 于 2008-4-17 15:02 发表
有两个意见
1 第一层循环中I的值不用到N,最大到N除以2的平方根(取整)就可以了,因为再大的话, I^2 + (I+1)^2就大于N了;
2 一个循环就可以, 可以在这次循环中对I^2+(I+1)^2的值,进行检查,如果值小于N并且是一个 ...

Thanks!
对于（2），I^2+(I+1)^2的值应该是小于N^2, 怎样判断这个数是平方数，还得用循环？

wxycyel

可以不用循环,标准math库中应该有求平方根的函数(你最好查一下,我也不是很清楚),改造一下应该可以用的.
判断小于N是我对I的最后一个值等到的结果是否一定小于N没有把握,如果可以肯定小于的话可以不比较.

scutan

原帖由 liuke432 于 2008-4-17 15:12 发表


Thanks!
对于（2），I^2+(I+1)^2的值应该是小于N^2, 怎样判断这个数是平方数，还得用循环？

1. 
   
2.         if ((floor(sqrt(a)) * floor(sqrt(a))) == a)
   
3.         {
   
4.                 printf("yes\n");
   
5.         }
   
6.         else
   
7.         {
   
8.                 printf("no\n");
   
9.         }
   

复制代码

cjaizss

个人怀疑，除了0^2+1^2=1^2
3^2+4^2=5^2
不存在别的b=a+1

scutan

原帖由 cjaizss 于 2008-4-17 15:43 发表
个人怀疑，除了0^2+1^2=1^2
3^2+4^2=5^2
不存在别的b=a+1

还是有其它的.

如是:
a=3,b=4,c=5
a=20,b=21,c=29
a=119,b=120,c=169
a=696,b=697,c=985

liuke432

原帖由 cjaizss 于 2008-4-17 15:43 发表
个人怀疑，除了0^2+1^2=1^2
3^2+4^2=5^2
不存在别的b=a+1

还有，比如 20,21,29

liuke432

综合上面各位的提示，得到如下算法：

1. 
   
2.               for(i=2,i<(N/(sqrt(2))),i++)
   
3.         {
   
4.                 k=i*i+(i+1)*(i+1);
   
5.                  if((k < N*N)&&((floor(sqrt(k)) * floor(sqrt(k))) == k))
   
6.                                 printf("%d,%d,%d\n",i,i+1,sqrt(k));
   
7.                 }
   

复制代码

谢谢大家！

scutan

原帖由 liuke432 于 2008-4-17 15:53 发表


还有，比如 20,21,29

刚刚写的, 不知道有错没得.

1. 
   
2. #include<stdio.h>
   
3. #include<stdlib.h>
   
4. #include<math.h>
   
5. 
   
6. #define N 1000000000
   
7. 
   
8. int main()
   
9. {
   
10.         int tmp = (int)sqrt(N);
    
11.         int count = 0;
    
12. 
    
13.         int a, c;
    
14. 
    
15.         for (a = 0; a < tmp; a++)
    
16.         {
    
17.                 c = a*a + (a+1)*(a+1);
    
18.                 if ((int)sqrt(c) > N)
    
19.                         break;
    
20.                 if ((floor(sqrt(c)) * floor(sqrt(c))) == c)
    
21.                 {
    
22.                         count++;
    
23.                         printf("a=%d,b=%d,c=%d\n", a, a+1, (int)sqrt(c));
    
24.                 }
    
25.         }
    
26.         printf("done\n");
    
27.         return 0;
    
28. }
    
29. 
    

复制代码

结果:

a=0,b=1,c=1
a=3,b=4,c=5
a=20,b=21,c=29
a=119,b=120,c=169
a=696,b=697,c=985
a=4059,b=4060,c=5741
a=23660,b=23661,c=33461
done

real    0m0.015s
user    0m0.016s
sys     0m0.000s

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

wxycyel

tmp的值取得有问题,应该是 N/sqrt(2);

ypxing

大家应该探讨有没有低于O(n)的算法