Problem with Pythagorean triple etc.

This is a discussion on Problem with Pythagorean triple etc. within the C Programming forums, part of the General Programming Boards category; You can probably tell by the title of the topic that this is basically a homework problem. Anyway, for some ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    13

    Problem with Pythagorean triple etc.

    You can probably tell by the title of the topic that this is basically a homework problem. Anyway, for some reason I am having a brain fart or something because I am not able to work it out. Specifically this is what I have to do:

    (Pythagorean Triples) A right triangle can have sides that are all integers. The set of three integer 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 the hypotenuse all no larger than 500. Use a triple-nested for loop that simply tries all possibilities.

    If someone could just point me in the right direction and slap me across the face while you do that, that would be great thanks!
    Code:
    #include <stdio.h>
    
    void main()
    {
    	int result;
    	int tenuse;
    	for (int side1 = 0; side1 < 500; side1++)
    	{
    		for (int side2 = 0; side2 < 500; side2++)
    		{
    			for (int hypo = 1; hypo <= 500; hypo++)
    			{
    				result = side1 * side1 + side2 * side2;
    				tenuse = hypo * hypo;
    				if(result == hypo)
    					printf("%d %d %d", side1, side2, hypo);
    				printf("\n");
    			}
    		}
    	}
    }

  2. #2
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    1) A triangle cannot have a 0 length side.
    2) You are checking for a^2 + b^2 = c. Look.
    3) Why print a newline if you don't even find one?

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    13
    Geez... all I needed was a good wakeup and I got it. Thanks Tonto. I got it to work now, but I have no idea why I used 0 for the sides (lol); and thanks for the other tips.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    void main - see faq -
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    Why would you want a triple nested loop? Having the two sides of a right triangle automatically gives you the hypotenuse. All you have to do is sum the square of the two sides and if the result is an integer print all three values. What a crazy piece of homework.

  6. #6
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    SKeane: But then again, they aren't really expected to know the math... what a sham society it is nowadays.

    This will generate and print all triples {a^2 + b^2 == c^2} for c < 100 million using fast "m-n" algorithm. Have fun turning it in.

    Code:
    #include <stdio.h>
    
    size_t gcd(size_t m, size_t n)
    {
    	if(m == n) return m;
    	else if(m < n) return gcd(n - m, m);
    	else return gcd(m - n, n);
    }
    int main(void)
    {
    	size_t max = 10000, k, m, n;
    	for(m = 1; m < max; ++m)
    		for(n = m+1; n < max; n += 2)
    			if(gcd(m, n) == 1)
    				for(k = 1; (n*n + m*m)*k < max*max; ++k)
    					printf("%d^2 + %d^2 = %d^2\n", (n*n - m*m)*k, 2*m*n*k, (n*n + m*m)*k);
    	return 0;
    }
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by jafet
    This will generate and print all triples [...] for c < 100 million using fast "m-n" algorithm. Have fun turning it in.
    It seems to miss things like (5,12,13) or (7,24,25).
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  8. #8
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    Using your original code (amended slightly)

    Code:
    #include <stdio.h>
    
    #define MAX_SIDE 500
    
    int main()
    {
        int result;
        int side1, side2, hypo;
    
        for (side1 = 1; side1 < MAX_SIDE; side1++)
        {
            for (side2 = 1; side2 < MAX_SIDE; side2++)
            {
                for (hypo = 1; hypo < MAX_SIDE; hypo++)
                {
                    result = (side1 * side1) + (side2 * side2);
    
                    if( result == (hypo * hypo) )
                    {
                        printf("%d %d %d\n", side1, side2, hypo);
                    }
                }
            }
        }
    
        return(0);
    }
    But it's still a dumb assignment.

  9. #9
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    I tinkered with this, just because, and found a couple ways to help speed up and make safer the brute force method. FWIW.
    Code:
    /**
     * Display Pythagorean triples up to 'size'.
     * @param  size  the maximum length of a side
     * @return the number of Pythagorean triples found
     * @example <code>unsigned int count = pythagorean_triples(500);</code>
     * @Notes  Being brute force, this gets very slow for large values of size.
     * @Notes  This code <i>does</i> check for integer overflow with the squared
     *         values.
     */
    unsigned int pythagorean_triples(unsigned int size)
    {
        unsigned int a, b, c, len = 0, count = 0;
        for ( a = 1; a < size && a < UINT_MAX / a; ++a )
        {
            for ( b = a + 1; b < size && b < UINT_MAX / b; ++b )
            {
                for ( c = b + 1; c < size && c < UINT_MAX / c; ++c )
                {
                    unsigned int lhs = a * a + b * b;
                    unsigned int rhs = c * c;
                    if ( lhs < rhs )
                    {
                        break; /* rhs will only get bigger */
                    }
                    else if ( lhs == rhs )
                    {
                        if ( ++count == UINT_MAX )
                        {
                            goto done;
                        }
                        len += printf("(%u,%u,%u),", a, b, c);
                        if ( len >= 60 )
                        {
                            len = 0;
                            putchar('\n');
                        }
                        fflush(stdout);
                        break; /* no reason to continue checking more c's */
                    }
                }
            }
        }
        done:
        if ( len )
        {
            putchar('\n');
        }
        return count;
    }
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  10. #10
    and Nothing Else Matters
    Join Date
    Jul 2006
    Location
    Philippines
    Posts
    117
    ok SKeane, what is your idea of a good assignment? well, not for experts, but for those still learning the language. can you give examples on: (not the overly complicated ones)

    1.) loops and nested loops
    2.) pointers
    3.) arrays and multidimensional arrays
    4.) strings
    5.) linear linked lists
    6.) a combination of some or all of this.

    hehehe! so when a classmate or friend of mine asks me to help them, i'd have sumthin to let them solve.
    It is not who I am inside but what I do that defines me.

  11. #11
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    It seems to miss things like (5,12,13) or (7,24,25).
    Or maybe you just aren't patient enough (It prints the first aforementioned pair at least 20,000 lines down.) I could try print them out in sorted order, but it might get a little messy.


    sangken: Try a tic-tac-toe AI. Study minimax trees, alpha-beta pruning and (very effective for this game) transposition tables. It's not very hard once you get the hang of it.

    Learns you: most conventional C/C++ constructs, recursion, hash tables, arrays (if you use conventional board representation) or bitwise operators (if you use bitboards). You can practise making a simple GUI, and you can show off your work to non-programmers too.


    ok SKeane, what is your idea of a good assignment?
    Presumably something which allows a student to practise programming in a useful and constructive way, instead of imposing stupid restrictions and forcing students to turn to inefficient practices, like coming to this board for trivial help.
    Last edited by jafet; 10-14-2006 at 01:58 AM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. beginner problem
    By The_Nymph in forum C Programming
    Replies: 4
    Last Post: 03-05-2002, 04:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21