1

我正在尝试解决Project Euler 问题 9：

毕达哥拉斯三元组是三个自然数的集合，a < b < c，其中，a2 + b2 = c2

例如，32 + 42 = 9 + 16 = 25 = 52。

恰好存在一个毕达哥拉斯三元组，其 a + b + c = 1000。求积 abc。

我在Wikipedia上查找了找到毕达哥拉斯三元组的公式，并试图将其翻译成代码。问题是代码输出了错误的答案，但我认为代码是正确的。

var a, b, c;
var pos1, pos2, pos3;
var ans1, ans2, ans3;

for(var n=2; n<=20000; n++) {
  a = 2 * n + 1;
  b = 2 * n * (n +1);
  c = 2 * n * (n +1) + 1;
  if(a<b<c) {
  if(a^2 + b^2 === c^2) {
      pos1 = a;
      pos2 = b;
      pos3 = c;
  }
  if(a + b + c ===1000) {
      ans1 = a;
      ans2 = b;
      ans3 = c;
  }
}
}
console.log(ans1 + " " + ans2 + " " + ans3);
4

5 回答 5

8

这是一个解决方案

var a;
var c;

for (var b = 1; b < 1000; b += 1) {
    a = (500000 - 1000 * b) / (1000 - b);

    if (Math.floor(a) === a) {
        c = 1000 - a - b;

        break;
    }
}

console.log(a, b, c);

结果是 375 200 425

在jsfiddle上

毕达哥拉斯
a 2 + b 2 = c 2

我们还有
a + b + c = 1000

代数，将 c 重新排列到左边
c = 1000 - (a + b)

将 c 插入毕达哥拉斯
a 2 + b 2 = (1000 - (a + b)) 2

乘以
a 2 + b 2 = 1000000 - 2000 * (a + b) + (a + b) 2

乘以
a 2 + b 2 = 1000000 - 2000 * (a + b) + a 2 + 2 * a * b + b 2

重新排列 a 2 + b 2以简化
0 = 1000000 - 2000 * (a + b) + 2 * a * b

将未知数重新排列到左边
2000 * (a + b) - 2 * a * b = 1000000

简化，/2
1000 * (a + b) - a * b = 500000

分解
a(1000 - b) + 1000 * b = 500000

重新排列
a(1000 - b) = 500000 - 1000 * b

a = (500000 - 1000 * b) / (1000 - b)

现在输入 b，计算 a 并测试 a 是否为Pythagorean Triples要求的整数

于 2013-04-22T09:35:59.383 回答
5

TGarr，这是对 Xotic750 答案的解释。

我真的不明白你是如何创建算法的。为什么 a = 到 (500000 - 1000 * b) / (1000 - b) ...

他从 a^2 + b^2 = c^2 和 a + b + c = 1000 开始，并将它们结合起来，因为 projecteuler 上的问题指出只有一组数字，这两个陈述都是正确的。这是他如何将它们结合起来的。他将第二个方程解为 c = 1000 - (a + b)。然后他将其代入第一个等式，使其变为 a^2 + b^2 = (1000 - (a + b))^2。他继续，直到他能够解出整个方程的 a。一旦他能够做到这一点，他就能够制作一个for增加 b 的循环，这比许多其他选项更简单、更优雅。

为什么 if 语句的条件设置为 Math.floor(a) === a？

这只是意味着“是a，向下舍入到最接近的整数，与a？相同” 换句话说，是a整数吗？（复制他的代码，并console.log ( a );在语句上方添加if。这可能有助于您理解那段代码）既然他能够解出 a 的方程，他所要做的就是为 b 插入不同的数字，并且只要结果是一个整数，他会有答案。或者至少他会知道什么a并b c = 1000 - a - b;告诉他 c 是什么，而这就是她所写的全部内容。

于 2013-07-06T04:23:01.207 回答
3

这是另一种代码较少的解决方案：

for(var a = 1; a < 500; a++){
  for(var b = a; b < 1000; b++){
    var c = Math.sqrt(a * a + b * b);
    if(c > b && Number.isInteger(c) && a + b + c == 1000){
      console.log(a * b * c);
    }
  }
}

结果是：31875000 :)

于 2017-10-02T18:00:03.237 回答
2

你不能这样计算幂。

用于Math.pow(a,2)计算 a^2

var a, b, c;
var pos1, pos2, pos3;
var ans1, ans2, ans3;

for(var n=2; n<=20000; n++) {
  a = 2 * n + 1;
  b = 2 * n * (n +1);
  c = 2 * n * (n +1) + 1;
  if(a<b<c) {
  if(Math.pow(a,2) + Math.pow(b,2) === Math.pow(c,2)) {
      pos1 = a;
      pos2 = b;
      pos3 = c;
  }
  if(a + b + c ===1000) {
      ans1 = a;
      ans2 = b;
      ans3 = c;
  }
}
}
console.log(ans1 + " " + ans2 + " " + ans3);
于 2013-04-22T09:22:54.523 回答
2

等式 1：a 2 + b 2 = c 2

方程 2：a + b + c = 1000

从 eq 1 和 eq 2 我们可以有

方程 3：c = 1000 - a - b

将 eq 3 中的 c 值代入 eq 1 我们得到：

方程 4：a 2 + b 2 = (1000 - a - b) 2

eq 4 的 RHS 是三项式平方。我们知道这种三项式的平方是

(a - b - c) 2 = a 2 + b 2 + c 2 – 2ab + 2bc – 2ca

我们得到：

a 2 + b 2 = 1000 2 + a 2 + b 2 – 2*1000*a + 2*a*b – 2*b*1000

现在我们简化到 LHS

a = (1000 2 - 2*1000*b)/(2*1000*b)

现在我可以用它来找出 a 的值，它是一个整数，然后使用 Math.sqrt( a a + b b ) 来计算 c 的值。然后我可以检查 a+b+c==1000 是否成立。

我的解决方案：

public class ProjectEuler9 {
    public static void main(String[] args) {
        long start = System.nanoTime();
        double a;
        for(int b=1; b<1000; b++){
            a = ( (Math.pow(1000, 2) - 2000*b ) / (2000- 2*b) );
            if(Math.floor(a) == a) {
                // a is an integer
                double c = Math.sqrt((a*a + b*b));
                System.out.println("a : " + a + " b :" + b + " c : " + c);
                long product = (long) (a*b*c);
                System.out.println("product abc : " + product);
                break;
            } else {
               //a is not an integer.
            }
        }
        long stop = System.nanoTime();
        System.out.println("\nTime: " + (stop - start) / 1000 + " ns");
    }
}

输出 ：

a : 375.0 b :200 c : 425.0
product abc : 31875000

Time: 3714 ns
于 2017-03-20T03:38:19.750 回答