如何求出1-n以内勾股数之和

〇〇

上面2楼的答案貌似都不太对 D:\lt\dl>ggs1 10 1: 3 4 5 2: 8 6 10 total:10 36 D:\lt\dl>ggs1 15 1: 3 4 5 2: 8 6 10 3: 5 12 13 total:15 66 漏了 9 12 15

〇〇

但你们的答案都是一致的，10楼的效率好很多，改了下数据类型，防止溢出

2. #include <stdio.h>
3. typedef unsigned int DW;
4. DW Test(DW n)
5. {
6. DW t,sum=0,c=0;
7. DW a,b;
8. for(b=1;b*b<n/2.0;b++)
9. for(a=b+1;a*a<=n;a++)
10. { c++;t=a*a+b*b;
11. if(t<=n)
12. /*printf("%d: %d\t%d\t%d\t\n",c,a*a-b*b,2*a*b,t),*/ sum+=2*a*(a+b);else break;
13. }
14. return sum;
15. }
17. DW main(int c ,char **v)
18. { if (c==2) {
19. printf("total:%s %u\n",v[1],Test(atoi(v[1])));
20. }
21. return 0;
23. }

复制代码

D:\lt\dl>ggs1 100 total:100 3864 D:\lt\dl>timer ggs1 1000000 Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31 total:1000000 3387036080 Kernel Time = 0.031 = 48% User Time = 0.015 = 24% Process Time = 0.046 = 72% Global Time = 0.064 = 100%

G-Spider

12# 〇〇 看来#6的转化与题目要求不等价。 勾股数 形如：{a^2+b^2 ,a^2-b^2 ,2ab} 5 3 4 2*2*1 (得到3) 15 9 12 2*6*1 2*3*2 (得不到9) 所以问题的实质就是，求所有满足a^2+b^2 <= n 的非平凡的正整数解。 还考虑看公因子，不知这样能不能完全包含。 3*（5 3 4） =（15 9 12）

wayne

12# 〇〇 打印非平凡的解。 统计的是所有的解：

1. #include <stdio.h>
2. typedef unsigned int DW;
3. inline DW gcd(DW m,DW n){DW t; while(m!=0) t=m,m=n%m,n=t;return n;}
4. DW Test(DW n)
5. {
6. DW t,s,ii,cnt=0,sum=0,c=0;
7. DW a,b;
8. for(b=1;b*b<n/2.0;b++)
9. for(a=b+1;a*a<n;a++)
10. { t=a*a+b*b;
11. if(t<=n){
12. if(gcd(a-b,2*b)==1){
13. s=1;
14. for(ii=1;ii<=s;ii++) printf("%5u:%10u\t%10u\t%10u\n",++cnt,ii*(a*a-b*b),2*ii*a*b,ii*t);
15. s=n/t;
16. sum+=s*(s+1)*a*(a+b);
17. }
18. } else break;
19. }
20. return sum;
21. }
23. int main(int c ,char **v)
24. {
25. if (c==2) {
26. printf("total of triples less than %s :\t%u\n",v[1],Test(atoi(v[1])));
27. }
28. return 0;
29. }

复制代码

wayne

12# 〇〇 发现答案还是不一样，能否把你的ggs1 100的全部的解打印出来 我的是：

1: 3 4 5 1: 6 8 10 1: 9 12 15 1: 12 16 20 1: 15 20 25 1: 18 24 30 1: 21 28 35 1: 24 32 40 1: 27 36 45 1: 30 40 50 1: 33 44 55 1: 36 48 60 1: 39 52 65 1: 42 56 70 1: 45 60 75 1: 48 64 80 1: 51 68 85 1: 54 72 90 1: 57 76 95 1: 60 80 100 2: 15 8 17 2: 30 16 34 2: 45 24 51 2: 60 32 68 2: 75 40 85 3: 35 12 37 3: 70 24 74 4: 63 16 65 5: 5 12 13 5: 10 24 26 5: 15 36 39 5: 20 48 52 5: 25 60 65 5: 30 72 78 5: 35 84 91 6: 21 20 29 6: 42 40 58 6: 63 60 87 7: 45 28 53 8: 77 36 85 9: 7 24 25 9: 14 48 50 9: 21 72 75 9: 28 96 100 10: 55 48 73 11: 9 40 41 11: 18 80 82 12: 33 56 65 13: 65 72 97 14: 11 60 61 15: 39 80 89 16: 13 84 85 total of triples less than 100 : 7016

〇〇

这次对了。 with a as(select level a from dual connect by level<=:m) ,t as(select /*+use_hash(a ,b)*/:m,a.a,b.a b,sqrt(a.a*a.a+b.a*b.a)c from a,a b where b.a>a.a and ceil(sqrt((a.a*a.a+b.a*b.a)))<=:m and instr(sqrt((a.a*a.a+b.a*b.a)),'.')=0 ) select * from t union all select :m,sum(a)+sum(b)+sum(c),null,null from t; :M A B C ----- ---------- ---------- ---------- 100 3 4 5 100 5 12 13 100 6 8 10 100 7 24 25 100 8 15 17 100 9 12 15 100 9 40 41 100 10 24 26 100 11 60 61 100 12 16 20 100 12 35 37 100 13 84 85 100 14 48 50 100 15 20 25 100 15 36 39 100 16 30 34 100 16 63 65 100 18 24 30 100 18 80 82 100 20 21 29 100 20 48 52 100 21 28 35 100 21 72 75 100 24 32 40 100 24 45 51 100 24 70 74 100 25 60 65 100 27 36 45 100 28 45 53 100 28 96 100 100 30 40 50 100 30 72 78 100 32 60 68 100 33 44 55 100 33 56 65 100 35 84 91 100 36 48 60 100 36 77 85 100 39 52 65 100 39 80 89 100 40 42 58 100 40 75 85 100 42 56 70 100 45 60 75 100 48 55 73 100 48 64 80 100 51 68 85 100 54 72 90 100 57 76 95 100 60 63 87 100 60 80 100 100 65 72 97 100 7016 53行。

wayne

16# 〇〇

Timer 9.01 : Igor Pavlov : Public domain : 2009-05-31

这个timer工具那可以下载呢

〇〇

Timer.rar (1.75 KB, 下载次数: 1)

2011-4-21 09:53 上传

点击文件名下载附件

wayne

18# 〇〇 thanks，有源代码吗，不是说属于Public domain 了吗

G-Spider

17# wayne 903版，包括源码。 7bench903.zip