Problem9

1.package com.shui.mu.yao.io.algorithm;  
2.  
3.import java.util.Arrays;  
4.  
5./** 
6. *  
7. * @author shuimuqinghua77 @date 2011-11-3下午03:31:30 
8. */  
9./** 
10. * A Pythagorean triplet is a set of three natural numbers, a b c, for which, a2 
11. * + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one 
12. * Pythagorean triplet for which a + b + c = 1000. Find the product abc. 
13. */  
14.public class Problem9 {  
15.    public static int[] PythagoreanTriplet(int seed) {  
16.          
17.        for (int i = 1; i < seed/2; i++)  
18.            for (int j = i + 1; j < seed/2; j++)  
19.                for (int k = j + 1; k < /** 2边之和大于第三边 */  
20.                i + j && k < seed; k++) {  
21.                    if (k - i > j)  
22.                        continue;  
23.                    if (threeSqrt(i, j, k, seed))  
24.                        return new int[] { i, j, k };  
25.  
26.                }  
27.        return new int[3];  
28.    }  
29.  
30.    private static boolean threeSqrt(int x, int y, int z, int seed) {  
31.        if (x + y + z == seed && x * x + y * y == z * z)  
32.            return true;  
33.        else  
34.            return false;  
35.    }  
36.  
37.    public static void main(String[] args) {  
38.        long start=System.currentTimeMillis();  
39.        int[] triplet = PythagoreanTriplet(1000);  
40.        System.out.println(Arrays.toString(triplet));  
41.        System.out.println(triplet[0] * triplet[1] * triplet[2]);  
42.        long end=System.currentTimeMillis();  
43.        System.out.println(end-start);  
44.        start=System.currentTimeMillis();  
45.        triplet=MathMethod(1000);  
46.        System.out.println(Arrays.toString(triplet));  
47.        System.out.println(triplet[0] * triplet[1] * triplet[2]);  
48.        end=System.currentTimeMillis();  
49.        System.out.println(end-start);  
50.}  
51.  
52.    private static int[] MathMethod(int seed) {  
53.        int a=0;  
54.        for(int b=1;b<seed/2;b++){  
55.            a=(seed*b-seed/2*seed)/(b-seed);  
56.            if(a*(b-seed)==(seed*b-seed/2*seed)&&a<b)  
57.                return new int[]{a,b,seed-a-b};  
58.        }  
59.        return new int[3];  
60.    }  
61.  
62.}