How to calculate the number of triangles that can be formed-CodePudding

The code below should have calculated the number of triangles that can be made from every triplet of 3 integers from 1 to N. However, when I input 5, it gives me 34, while the right answer is 3: the only possible triangles are (2, 3, 4), (2, 4, 5) and (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;
  }

CodePudding user response：

You do not ensure that the numbers are distinct.

You can do this be chosing your loop limits correctly:

      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  ) {

Start each inner loop one higher than current counter of outer loop. It also does not make any sense to run each loop up to N. If they must be distinct, you can stop at N-2, N-1, N

This creates triples where numbers are increasing. If you consider triangles (3,4,5) and (4,3,5) to be different, we must also account for permuations of these triples. As all values are distinct, we have 6 possible permutations for each triple that was found in the inner loop.

CodePudding user response：

I'm sorry, I can't go for a comment so let's go for an answer. I don't really get what you wish to do. As I am understanding it, you wish to print this : 1, 2, 3, 4, 5-> [2, 3, 4], [2, 4, 5], [3, 4, 5] -> 3

Except, with your code, you'll never check your N since you go out of your loop when i turns into N.

Also, your "j" and "k" don't have to move starting 1 since you already tried that position with "i", so you'll only get doublons doing that.

EDIT : some changes for a smarter code (I removed my 1 but go check for "<=", which I personnaly dislike :) ):

// since [1, 2, 3] can't bring any triangle
if (N < 4) return 0; 

// since there is no possible triangle with 1 as a border, start at 2 
for (int i = 2; i <= N-2; i  ) {
          for (int j = i 1; j <= N-1; j  ) {
              // The innermost loop checks for the triangle
              // property
              for (int k = j 1; k <= N; k  ) {

                  // Sum of two sides is greater than the
                  // third
                  // simplified as suggested by S M Samnoon Abrar
                  if (i   j > k)
                  {
                      
                      count  ;
                  }
              }
      }

CodePudding user response：

You need to do the following:

run first loop through 1 to N, i.e.: 1 <= i <= N
don't start each nested loop from index 1. So, you need to run first nested loop in range i 1 <= j <= N and second nested loop in range j 1 <= k <=N.

Explanation

First, if you run all 3 loops from 1 to N, then you are not doing distinct counting because all numbers in the range will be iterated 3 times. So it would give an incorrect result.
Secondly, since we need to count distinct numbers only, it is efficient to count 1 from the previous outer loop each time. In this way, we are ensuring that we are not iterating over any number twice.

Check the following code:


 // 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 = i 1; j <= N; j  ) {
              // The innermost loop checks for the triangle
              // property
              for (int k = j 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;
  }

CodePudding user response：

Spot the extra line of code that enforces the constraint that the 3 numbers are "distinct" (read "unique"). Funny what a little "print debugging" can turn up...

    printf("Please input the value of N: ");
    scanf("%d", &N );
    for (int i = 1; i < N; i  ) {
        for (int j = 1; j < N; j  ) {
            for (int k = 1; k < N; k  ) {
                if (i   j > k && i   k > j && k   j > i) {
                    if( i != j && j != k && k != i ) {
                        printf( "%d %d %d\n", i, j, k );
                        count  ;
                    }
                }
            }
        }
    }
    printf ("Total number of triangles possible is %d ",count);

Output

Please input the value of N: 5
2 3 4
2 4 3
3 2 4
3 4 2
4 2 3
4 3 2
Total number of triangles possible is 6

The OP code was counting (1,1,1) or (2,3,3) in contravention of "distinct" digits.

AND, there is now ambiguity from the OP person as to whether, for instance, (4,2,3) and (4,3,2) are distinct.

printf() - the coder's friend when things don't make sense...