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