Thread: Brute Force

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    27

    Unhappy Brute Force

    This is a little exercise I'm having trouble with. To be quite frank, I don't really completely understand the problem.
    I've asked my teacher for some help and he has given me the accompanying code as a guild.

    (Pythagorean Triples) A right triangle can have sides that are all integers. The set of three intger values for the sides of a right triangle is called a Pythagorean triple. These three sides must satisfy the relationship that the sum of the squares of two of the sides is equal to the square of the hypotenuse. Find all Pythagorean triples for side1, side2 and hypotenuse all no larger than 100. Use a triple-nested for loop that tries all possibilities.


    #include <iostream>

    int main()
    {
    int count = 0;
    long hyptSquared, sidesSquared;

    for ( /* write header for side1 */ ) {

    for ( /* write header for side2 */ ) {

    for ( /* write header for hyptSquared */ ) {
    /* calculate hyptSquared */
    /* calculate the sum of the sides squared */

    if ( hyptSquared == sidesSquared ) {
    cout << side1 << "\t" << side2 << "\t"
    << hypt << "\n";
    ++count;
    }
    }
    }
    }
    cout << "A total of " << count << " triples were found."
    << endl;
    return 0;
    }


    I've gone through all my text books and tutorials on the net but I'm still stuck. PLEASE HELP!!!!! PLEASEEEEEEEEEEE

    Guys I know this is asking a bit too much and I hate having
    to ask but if I don't than I won't learn anything and I really want to learn. Thanks heaps

  2. #2
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    WHat this does is finds the triplets .. That is the sides of a triangle... a2=b2+c2 (Note 2 means square) Where a b and c are the sides of a triangle.... The three numbers must satisy the above equation... Then it is called a pyth.... triplet.. The program finds the number of such tripltes that can be formed within a given number.. SO that's it

  3. #3
    Unregistered
    Guest
    The algorhythm:

    side1 can range from 1 to 100
    side2 can range from 1 to 100
    side3 can range from 1 to 100

    if side3*side3 = (side1*side1) + (side2 * side2);
    display all sides.

    =================================
    to start thinking about the way it would work think about how you might do this using pencil and paper and setting up individual cases representing all the different possibilities:

    case1:
    let side1 = 1
    let side2 = 1
    let side3 = 1
    1*1 != 1*1 + 1*1;

    case2:
    let side1 = 1
    let side2 = 1
    let side3 = 2
    2*2 != 1*1 + 1*1

    etc for every possible case of side3 from 1 - 100 and side1 and side2 both being 1. Then change side2 to 2 and run side three from 1-100 all over again

    case101:
    let side1 = 1
    let side2 = 2
    let side3 = 1
    1*1 != 1*1 + 2*2

    case102
    let side1 = 1
    let side2 = 2
    let side3 = 2
    2*2 != 1*1 + 2*2
    etc for every case of side2 from 3-100. then when you've checked all 10000 cases for side2 and side3 ranging from 1-100 you can change side1 to 2 and check all 1000 of those:

    case10001
    let side1 = 2
    let side2 = 1
    let side3 = 1
    1*1 != 2*2 + 1*1

    case 1002
    let side1 = 2
    let side2 = 1
    let side3 = 2
    2*2 != 2*2 + 1*1
    etc etc etc

    Essentially the computer will do 100*100*100 different cases and do it much much faster than you could ever possibly try to do it. All you have to do to have the computer create all the different cases is to set up the nested loops, enter the appropriate code indicating the minimal length of the sides, the maximal length of the sides, and the increment for each separate case. If you then tell the computer what calculations to make, what comparison to make, and what to do if the comparison turns out a given way; you've got your program.

  4. #4
    Registered User
    Join Date
    Feb 2002
    Posts
    589

    Barjor

    Hey Unregistered. That was one of the best answears I have seen in a long time..

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > for ( /* write header for side1 */ ) {

    for ( side1 = 0 ; side1 < 100 ; size1++ ) {

  6. #6
    Registered User
    Join Date
    Feb 2002
    Posts
    27

    Question Getting there... Help still needed

    I understand the problem, and I understand I somehow have to implement 3 nested for loops (3 that's right, right?) to test all the possibilities...

    I am not sure what are ther ranges I have to input into the 3 nested for loops though. Can anyone help me out with this?

    Greatly appreciated if you can

  7. #7
    Unregistered
    Guest

    rough idea

    im still learning C++ syntax(2days in now), so dont bug me about syntax errors, but i would solve like this(if using 3 nested for loops)

    for {a=1;a<100; a++}
    {for {b=1;b<100; b++}
    {for {c;c<100; c++}
    {if (c*c==a*a+b*b) //check to see if its a triple
    {cout << c,a,b;} //print the triple
    };
    };
    };


    hope u get the idea...i guess u could make it faster by putting breaks in at the 3rd for loop...doesn't really matter though


    anyone else, how was my syntax? close? i tried doing it without my book

  8. #8
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    Please use tags. It makes your code more readable.

    If a, b and c are all integers and a^2 + b^2 = c^2, then (a, b, c) is a Pythagorean tripple.

    Perhaps this is what you want.

    Code:
    #include <stdio.h>
    #include <math.h>   
    
    int main (void)
    {
        int a, b, c2, c;
        
        for (a = 0; a < 100; a++)
        {
            /* start with a, to avoid duplicates */
            for (b = a; b < 100; b++)
            {
                c2 = a * a + b * b;
                
                c = (int) sqrt (c2);
                
                /* sqrt returns a float value, so if c2 == 5,
                   then (int) sqrt (5) == 2 and (c * c) == 4 */               
                if ((c * c) == c2)
                {
                    printf ("%d^2 + %d^2 = %d^2\n", a, b, c);
                }
            }
        }         
                        
        return 0;
    }

  9. #9
    Registered User
    Join Date
    Feb 2002
    Posts
    27

    Causes Unwanted Repetition :(

    I can see where you are getting the idea from but just so that I can try to explain things easier... we will say the range is 1-3 only, for simplicity sake.

    OK, u have the following loops above...

    (a=1; a<3; a++){
    (b=1; b<3; b++){
    (c=1; c<3; c++){
    }
    }
    }


    Working this out on pen and paper I found I got unwated repetition occuring, let me explain...

    When A=1 (a=1 is < 3), so the 2nd loop will be excuted,
    B=1 (b=1 < 3), so the third loop will be excuted.
    C=1 (c=1 < 3) The third loop will continue to repeat itself until C=5 (c=3 is !< 3) that is when it stops.

    Right now we have...
    A = 1
    B = 1
    C = 1, C = 2

    After the 3rd loop has stopped it will go back to the 2nd loop,
    B=2 (b=2 < 3) the condition is true, so the 3rd loop is excuted until C=3 (c=3 !< 3) that is when it stops.


    Right now we have...
    A = 1
    B = 2
    C = 1, C = 2
    -------------------------FIRST FULLY COMPLETED LOOP-----------------

    When A=2 (a=2 is < 3), so the 2nd loop will be excuted,
    B=1 (b=1 < 3), so the third loop will be excuted.
    C=1 (c=1 < 3) The third loop will continue to repeat itself until C=5 (c=3 is !< 3) that is when it stops.


    After this it will go back to the 2nd loop,
    B=2 (b=2 < 3) the condition is true, so the 3rd loop is excuted until C=3 (c=3 !< 3) that is when it stops.




    Basically this is all the possibilities you will get....

    A B C(Hypothenous)
    1 1 1
    1 1 2
    1 2 1
    1 2 2
    2 1 1
    2 1 2
    2 2 1
    2 2 2

    The problem is that there is repetition happening,
    FOR EXAMPLE: 1 2 1 (isn't this the same is as)
    2 1 1 (The only difference here is sides a and b
    has been swapped around)

    I don't want this to happen! PLEASEEEEEEEE HELP!!!
    PLEASEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE!!!

    Thank-You

  10. #10
    Registered User
    Join Date
    Feb 2002
    Posts
    27

    Red face Replying to SHIRO

    This message is intended for SHIRO who has replied to my call for help.

    First let me say thanks for having an input and trying to help out, Thank-You!

    The only thing wrong with your suggestion Shiro is that side3(hypothenous) is not going through all the possibilities. Only side1 and side2 are. I hope u understand what I'm trying to say...
    If u have anymore suggestion or the answer (the code itself) it would be great.

  11. #11
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    Variables a and b run from 0 to 100. So the maximum value of a^2+b^2 = 100^2+100^2 = 20.000. The variable c runs from 0 to 100, so the maximum value of c^2 = 10.000. This implies that when you let a and b run from 0 to 100 and create the Pythagorean tripples, you don't need to run c from 0 to 100.

    When running only a and b from 0 to 100, the largest Pythagorean tripple is (80, 84, 116). This is the same as letting c run from 0 to 116!

    By the way, you have a lot of non-Pythagorean tripples in your example. For example, (2, 1, 1) is no Pythagorean tripple.

    But after all, you can do

    (a=1; a<3; a++){
    (b=a; b<3; b++){
    (c=1; c<3; c++) {
    }
    }
    }

    Letting b start from a prevents from duplications. If you write it down, you'll get:

    a b c
    1 1 1
    1 1 2
    1 2 1
    1 2 2
    2 2 1
    2 2 2

  12. #12
    Registered User
    Join Date
    Feb 2002
    Posts
    27

    Talking A little Thanks

    Thanks for that Shiro.

    Your right about not getting duplicates if I set A=B or B=A.
    It took me awhile to work the logic out on that one, why is it that I don't get any duplicates if I initialize that for my for loop.

    Thanks heaps

  13. #13
    Unregistered
    Guest
    Since the sides represent physical entities they can't be zero length or you wouldn't have a triangle, although to the compiler it wouldn't matter.

    Code:
    struct triad
    {
    int x;
    int y;
    int h;
    };
    
    int side1;
    int side2;
    int side3;
    int index = 0;
    
    //unknown number of triples could be found so declare a large 
    //array of triples on the heap;
    triad * triples = new triad[100000];
    
    //find all valid triples
    for(side1 = 1; side1 < 101; side1++)
    {
      for(side2 = 1; side2 < 101; side2++)
     {
       for(side3 = 1; side3 < 101; side3++) 
       {
          if(side3*side3 = side1*side1 + side2*side2)
          {
            //store the data in the next available index
            triples[index].x = side1;
            triples[index].y = side2;
            triples[index++].h = side3;
         }
        }
      }
    }
    
    //find unique triples
    int k = 0, s, t;
    char found;//a flag indicating duplicate value
    
    //create large array to hold unique triads
    triad *uniqueTriples = new triad[1000000];
    
    //the first element of triples must be unique by definition
    //so copy elements to the first element of uniqueTriples
    uniqueTriples[k].x = triples[0].x;
    uniqueTriples[k].y = triples[0].y;
    uniqueTriples[k++].h = triples[0].h;
    
    //now check each element of triples
    for(s = 1; s < index; s++)
    {
      //set the flag each time through
      found = 'n';
    
      //check each element of triples against each element of 
      //uiniqueTriples
      for(t = 0; t < k; t++)
      {
          //if the hypotenuses are the same then the sides are too    
          if(triples[s].h == uniqueTriples[t].h)
          {
             //so change the flag to indicate duplicate
             found = 'y';
    
             //and stop this loop
             t = k;
          }
       }
    
       //when done with the comparisons for this element of triples
       if(found == 'n')
       (
          //then this element of triples is also unique so copy to 
          //uniqueTriples
          uniqueTriples[k].x = triples[s].x;
          uniqueTriples[k].y = triples[s].y;
          uniqueTriples[k++].h = triples[s].h;
        }
    }
    
    //now display the unique triples
    for(t = 0; t < k; t++)
    {
      cout << uniqueTriples[t].x << ' ' << uinqueTriples[t].y << ' ' 
              << uniqueTriples[t].h << endl;
    }
    
    //and delete the dynamic memory
    delete [] triples;
    delete [] uniqueTriples;
    or some such algorhythm.

  14. #14
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    You are right from a geometrical point of view, but Pythagorean tripple is also a term from number theory.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Running a Brute Force Attack Simulation...
    By Junior89 in forum C++ Programming
    Replies: 31
    Last Post: 02-13-2011, 08:52 PM
  2. 2d array Brute force test
    By grimuth in forum C++ Programming
    Replies: 5
    Last Post: 04-08-2010, 10:01 AM
  3. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 01:41 AM
  4. Replies: 2
    Last Post: 03-21-2004, 08:21 PM
  5. Help : Brute Force String KeyGen
    By Tangy in forum C++ Programming
    Replies: 11
    Last Post: 03-11-2002, 09:01 PM