c - 毕达哥拉斯三元组

Question

我尝试解决 this problem

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

我使用欧几里得公式:

我的解决方案是:

int a = 0, b = 0, c = 0, m = 0, n = 0;
int abort = 0;

 while(abort == 0)
 {
      m++;
      while(abort == 0 && n < 10000)
      {
          n++;
          if(m > n)
          {
              a = (m*m) - (n*n);
              b = 2*m*n;
              c = (m*m) + (n*n);

              if(a+b+c == 1000 && a > 0 && b > 0 && c > 0 /*&& a < b && b < c*/)
              {
                   exit = 1;
              }
          }
      }
      n = 0;
 }

如果我运行它，我得到 a = 375 b = 200 和 c = 425。这是错误的，因为它应该是 a < b < c但是如果我使用你在我的代码中看到的检查(被注释掉的部分)，我的代码将永远运行。

那么我的错误是什么？

Answer 1

您使用的公式集有一个典型错误:并非所有毕达哥拉斯三元组都可以用它来描述(但所有基本 个)； 正确的公式集是

  a = k * (m * m - n * n)
  b = k * (2 * m * n)
  c = k * (m * m  + n * n)

例如，tiplet (9 12 15) 需要 k = 3；但是，提供的集合过多:一些三元组出现两次或更多次，因此您将不得不使用HashMap 或其他东西。在您的确切问题中，所需的三元组 (375 200 425) 是由 (m = 20, n = 5, k = 1) 生成的，因此在this Project Euler 问题中可以使用缩短的公式，但是在其他情况下，您必须使用正确的方法。