can u please find alternate solution for this code ?

[Umakant]

hi guys...
i am UMAKANT...

problem is ....
input will be N (integer)....and output shud be...a,b and c ...all less than N...and satisfying equation ... (a*a)+(b*b)=(c*c)
and we r not supposed to use BRUTE FORCE APPROACH...
{in brute force ....we check ....whether condition is true or false ...or every possible combinations of a,b,c}

i wrote following code...which is working...but ...my professor wants it in some other way...he thinks its brute force approach ...may be...

 
#include<stdio.h>

 main()
{
   int a,b,c,n;
   printf("Enter Value fr n: ");
   scanf("%d",&n);

   for(a=1;a<n;a++)
           for(b=1;b<n;b++)
                   for(c=1;c<n;c++)
                           if(((a*a)+(b*b))==(c*c))
                                   printf("a : %d , b : %d, c : %d\n",a,b,c);
}

SAMPLE RESULT : (for N=30)

Enter Value fr n: 30
a : 3 , b : 4, c : 5
a : 4 , b : 3, c : 5
a : 5 , b : 12, c : 13
a : 6 , b : 8, c : 10
a : 7 , b : 24, c : 25
a : 8 , b : 6, c : 10
a : 8 , b : 15, c : 17
a : 9 , b : 12, c : 15
a : 10 , b : 24, c : 26
a : 12 , b : 5, c : 13
a : 12 , b : 9, c : 15
a : 12 , b : 16, c : 20
a : 15 , b : 8, c : 17
a : 15 , b : 20, c : 25
a : 16 , b : 12, c : 20
a : 20 , b : 15, c : 25
a : 20 , b : 21, c : 29
a : 21 , b : 20, c : 29
a : 24 , b : 7, c : 25
a : 24 , b : 10, c : 26

so please help me..by giving me alternate solution to this...i wil be really thankful to youu

cheers,
Umakant.

[redhead]

In order to understand what is going on here, you need to fully understand the math involved, for this I would suggest you read up on the Pythagorean Theorem aswell as the Law of cosines, basicaly know what lies behind the Pythagorean triple construction.

True your bruteforce will enventualy provide the needed result, but I'm sure your teacher is more intersted in how far you've gone into the math involved, like I am, than just producing somethign which will give a correct result.

[redhead]

Or if you're too lazy to read through all that, take a look at this code

#include <stdio.h>
#include <math.h>

int SQR( int num ){ return num*num; }
int found( int , int*, int );

int main()
{
  int range,i,j,sum=1,count=0;
  int *squares;
  printf("Enter upper limit:");
  scanf("%d",&range );
  if( range < 1 )
    {
      printf("Range too low\n");
      return -1;
    }
  /* make room for what we need, no restrictions here */
  squares = (int*) malloc( sizeof(int)*range);
  if( ! squares )
    {
      printf("Not enough memory!\n");
      return -2;
    }
  /* since it is based on a triangle,
   * first make a list of all possible n^2
   */
  for( i=0; i<range; i++ )
    {
      squares[i] = SQR(i+1);
    }
  /* search through all possible combinations */
  for( i=1; i<range; i++ )
    {
      for( j=1; j<range; j++ )
        {
          sum = SQR(i) + SQR(j);
          /* if our current sum is part of the n^2 list
           * it is a damned valid number
           */
          if( found( sum, squares, range ))
            {
              printf("(%d %d %0.0f)\n",i,j,sqrt(sum));
              count++;
            }
        }
    }
  printf("%d triplets found\n",count );
  free(squares);
  return 0;
}

int found( int num, int* a, int range )
{
  int i;
  for( i=0; i<=range-1; i++ )
    {
      if( a[i] == num )
        return 1;
    }
  return 0;
}

But keep in mind, your teacher will probably ask how you came up with it.. What are you going to say.. I can imagine the conversation

Teacher: > Hmmm quite interesting code you produced there, I must say..
Student: > yeah, what do you think of it ?
Teacher: > it's pretty sleek, I must say, but how did you come up with the algorithm for searching through a list of matching sqaures within our accepted range ?
Student: > you see, I search the web, and up came this brilliant community, where they were gullible enough to correct my previus bruteforce algorithm, which you turned down to begin with...
Teacher: > BZZZZ... you lose, heres your deserved F, now go cry in the corner untill you've figured out why I'm giving you this F...

Now wouldn't it be more K-cool (or how you youngsters put it these days) to walk up to the teacher and announce...

Student: > Hey, I see why you made me take a second look at my algorithm.. now I see that behind it all lies the Pythagorean Theorem, where it's all based on a right angled triangle in which the right angled is placed between the sides of lengths A and B. Here the connecting side of length C will allways be the sum of length A and B squared.
Teacher: > Yes, you're showing some knowledge in the area, but how come you came up with the idear of searching through the possible squares of any number in your range ?
Student: > Well, you see, it's like this.. Since we're working with an available range, where any of the length A, B or C mustn't exceed the range in any way, it is more convenient to simply search for our squared C in that range, since that number will allways be hte largest of the three, so naturaly our length A and B will remain within the provided range at all times..
Teacher: > yes, by gully you do have an idear of how this is connected, you deserve your B+ (since I would never give an A+, and you did start out with a typical bruteforce algorithm)

Isn't my latest scenario a better way to end this exercise ?

Oh no, I just gave you the solution to what to tell your professor..
Ah, anyway, you know what is the right thing(tm) to do ? right ??