如何计算可以组成的三角形数量

Question

下面的代码应该计算出给定范围 1...N 中 3 个不同整数的每个三元组可以形成的三角形的数量。然而，当我输入 5 时，它给出的是 34，而正确答案是 3：唯一可能的三角形是 (2, 3, 4)、(2, 4, 5) 和 (3, 4, 5)。

 // C code to count the number of possible triangles using

  #include <stdio.h>
  int main()
  {   int N, count=0;
      setvbuf(stdout, NULL, _IONBF, 0);
      printf("Please input the value of N: \n");
      scanf("%d", &N );
      for (int i = 1; i < N; i++) {
          for (int j = 1; j < N; j++) {
              // The innermost loop checks for the triangle
              // property
              for (int k = 1; k < N; k++) {

                  // Sum of two sides is greater than the
                  // third
                  if (i + j > k && i + k > j && k + j > i)
                  {
                      count++;
                  }
              }
      }

  }
      printf ("Total number of triangles possible is %d ",count);
      return 0;
  }

Answer 1

您不能确保这些数字是不同的。

您可以通过正确选择循环限制来做到这一点：

      for (int i = 1; i <= N-2; i++) {
          for (int j = i+1; j <= N-1; j++) {
              for (int k = j+1; k <= N; k++) {

启动每个内循环，其值比外循环的当前计数器高一。将每个循环运行到 也没有任何意义N。如果它们必须不同，您可以停在N-2, N-1, N

这会产生三倍，其中数字不断增加。如果你考虑三角形(3,4,5)并且(4,3,5)是不同的，我们还必须考虑这些三元组的排列。由于所有值都是不同的，因此对于内部循环中找到的每个三元组，我们有 6 种可能的排列。