如何求出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楼的效率好很多，改了下数据类型，防止溢出

1. 
   
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. }
    
16. 
    
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;
    
22. 
    
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. }
    
22. 
    
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