Problem9

package com.shui.mu.yao.io.algorithm;

import java.util.Arrays;

/**
 * 
 * @author shuimuqinghua77 @date 2011-11-3下午03:31:30
 */
/**
 * A Pythagorean triplet is a set of three natural numbers, a b c, for which, a2
 * + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one
 * Pythagorean triplet for which a + b + c = 1000. Find the product abc.
 */
public class Problem9 {
	public static int[] PythagoreanTriplet(int seed) {
		
		for (int i = 1; i < seed/2; i++)
			for (int j = i + 1; j < seed/2; j++)
				for (int k = j + 1; k < /** 2边之和大于第三边 */
				i + j && k < seed; k++) {
					if (k - i > j)
						continue;
					if (threeSqrt(i, j, k, seed))
						return new int[] { i, j, k };

				}
		return new int[3];
	}

	private static boolean threeSqrt(int x, int y, int z, int seed) {
		if (x + y + z == seed && x * x + y * y == z * z)
			return true;
		else
			return false;
	}

	public static void main(String[] args) {
		long start=System.currentTimeMillis();
		int[] triplet = PythagoreanTriplet(1000);
		System.out.println(Arrays.toString(triplet));
		System.out.println(triplet[0] * triplet[1] * triplet[2]);
		long end=System.currentTimeMillis();
		System.out.println(end-start);
		start=System.currentTimeMillis();
		triplet=MathMethod(1000);
		System.out.println(Arrays.toString(triplet));
		System.out.println(triplet[0] * triplet[1] * triplet[2]);
		end=System.currentTimeMillis();
		System.out.println(end-start);
}

	private static int[] MathMethod(int seed) {
		int a=0;
		for(int b=1;b<seed/2;b++){
			a=(seed*b-seed/2*seed)/(b-seed);
			if(a*(b-seed)==(seed*b-seed/2*seed)&&a<b)
				return new int[]{a,b,seed-a-b};
		}
		return new int[3];
	}

}