Thread: Better algorithm for finding diagnols

  1. #1
    meow nbk's Avatar
    Join Date
    Jul 2004
    Posts
    45

    Better algorithm for finding diagnols

    I have made a program I created a couple months ago(December). I just opened it up again. I noticed it takes a very long time to calculate higher sided polygons(of course). What algorithm would you use?

    (Mine = s += n; n += 1, looped, s being sides, and n = added to it. 4 = 2, 5 = 5, 6 = 9.

    s+= n; n+= 1;
    2+=3;n+=1;
    5+=4;n+=1;
    9+=5;n+=1....)

    Thanks(by the way, if you want to see it, just ask).
    "When you're as strong as us, it's like taking baby from a candy." -Spopovitch

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I'm confused, what exactly are you calculating?

    Since s just seems to be the sum of the first n integers - 1 (ie 9 is the sum of 1+2+3+4-1)you can use the handy dandy equation where the sum of the first n integers is equal to (n*(n+1))/2.

  3. #3
    People Love Me
    Join Date
    Jan 2003
    Posts
    412
    Law of cosines, honey.

  4. #4
    meow nbk's Avatar
    Join Date
    Jul 2004
    Posts
    45
    PJ, the number of diagnols in a polygon. My description wasn't clear enough. Here >>

    Code:
    #include <iostream>
    
    int findNumber(int);
    
    int main()
    {
        int noOfSides;
        std::cout << "How many sides does the polygon have?\n";
        std::cin >> noOfSides;
        //int noOfDiagnols = findNumber(noOfSides);
        std::cout << "The polygon has " << findNumber(noOfSides) << " diagnols\n";
        system("PAUSE");
    }
    
    int findNumber(int nos)
    {
        std::cout << "In findNumber"
                  << "\n\n";
        int newNOS = nos - 3;
        int n = 2;
        std::cout << "\n";
        /*for( n = 2; newNOS <= 0; newNOS-- )
        {
             n += 1;
             std::cout << "in for()";
        }
        */
        int nOfDiag = 0;
        while(newNOS != 0)
        {
             std::cout << "In while()..\n"
                       << newNOS
                       << " steps to go;\n";
             
             nOfDiag += n;
             n += 1;
             newNOS--;
        }
        return nOfDiag;
    }
    (I realize I have the OS specific system("PAUSE"), comments, and other stuff I should have cleared out)

    I don't think that what you said would work, PJ, as n has to get incremented(another thing I should have used) each time.
    "When you're as strong as us, it's like taking baby from a candy." -Spopovitch

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    No, it doesn't have to increase every time, you wouldn't even need n.

    The number of diagonals for a shape with s sides is the same as the sum of the first (s-2) integers minus 1.

    So for example, number of diagonals for a square is 1+2-1=2.
    Pentagon: 1+2+3-1=5.
    Hexagon: 1+2+3+4-1=9.
    etc etc

    So to calculate for any value, use my above equation and subtract 1.
    For example, number of diagonals for a shape with 200 sides is:

    ((198*199)/2)-1=19700

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM