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.}