Pascal's triangle algorithm

This is a discussion on Pascal's triangle algorithm within the C++ Programming forums, part of the General Programming Boards category; Since I haven't learned enough C++, and ain't intelligent enough either, I want you to have a look at this: ...

  1. #1
    Registered User
    Join Date
    Dec 2001
    Posts
    367

    Pascal's triangle algorithm

    Since I haven't learned enough C++, and ain't intelligent enough either, I want you to have a look at this:


    ||||||||||||||||||1
    |||||||||||||||||1 1
    ||||||||||||||||1 2 1
    |||||||||||||||1 3 3 1
    ||||||||||||||1 4 6 4 1
    |||||||||||||1 5 10 10 5 1
    ||||||||||||1 6 15 20 15 6 1

    Get it? This is called Pascal's triangle. I want an algorithm in C++ which writes a specific number of lines of this triangle you enter.

    This is what I have come up with this far:


    int main()

    {
    int lines;

    std::cout << "Type in the amount of lines of Pascal's triangle you want to be shown: ";
    std::cin >> lines;

    char space[] = " ";

    for(int i=0; i=>lines/2; i++)
    {
    std::cout << space;
    }

    /*this loop creates the amount of space needed, so that the base of the triangle will get right. Else it might look something like:

    1
    1 1
    1 2 1
    1 3 3 1
    1 4 6 4 1

    and so on.....*/

    After that the space is created, I want the program to start writing the actual triangle, and this is why I'm asking you for help!

    If you already haven't noticed, the syntax of the triangle is that a number in it, is the result of the two numbers above it:

    1 2 1 - has:
    1 3(1+2) 3(2+1) 1 - below. And they have:
    1 4(3+1) 6(3+3) 4(3+1) 1 - below. And so on....... hope you've got it!



    system("PAUSE");
    return 0;
    }
    Last edited by Zewu; 05-02-2002 at 01:04 PM.

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Code:
        0 1 2 3 4 .. k
    
    0   1
    1   1 1
    2   1 2 1
    3   1 3 3 1
    4   1 4 6 4 1
    :
    n
    The number in the triangle is calculated from:

    (n over k) which is n! / (k! * (n - k)!)
    where n! is 1*2*3*4*...*n

    A loop like this will print the numbers:
    Code:
    for(int n=0; n<Depth; n++)
    {
       for(int k=0; k<=n; k++)
       {
          cout << Calculate_N_Over_K(n, k) << " ";
       }
       cout << endl;
    }
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Registered User
    Join Date
    Dec 2001
    Posts
    367
    Vad har du för betyg i matte?

  4. #4
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Zewu
    Vad har du för betyg i matte?
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  5. #5
    Registered User
    Join Date
    Feb 2002
    Posts
    591
    That means..""What grade do you have in math?""

  6. #6
    Registered User
    Join Date
    Dec 2001
    Posts
    367
    That's right!

    Even though I don't seem very good in maths in this thread, I can asure you of that my grade in it is good.

    Anyway, thanks for the help with the triangle.

  7. #7
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Inga problem...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  8. #8
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    For those of us less mathematically inclined here's one approach:

    declare a 2 dimensional array of int using dynamic memory. The size of the array will be based on user input

    assume user input = n

    # of columns = (n * 2) - 1
    # of rows = n

    initialize all elements of array to 0

    then fill in appropriate elements of array.

    to display use loop(s) and if array[][] = 0 then output space; otherwise output array[][].

    at end be sure to delete all the dynamic memory you declared.

    Example : asssume user input = 4

    array will look like this in the end
    0001000
    0010100
    0102010
    1030301



    To fill in the array at appropriate elements do this:

    First fill in the ones like this:
    in row 0 there is only a single 1, at column element = user input - 1
    if row > 0 there are two ones, call them f and s.
    in row 1 f is at element index user input - 2and s is at element index user input
    each row after that f -= 1 and s += 1 marks the location of the 1s.

    Then fill in the values > 1.
    the number of ints greater than 1 in each row is row - 1, if row > 1; and 0 if row <= 1.

    each int > 1 in each row is located at f + 2i where i is the ith number > 2.

    the value of each int > 1 in each row is:
    array[row][f + 2i] = array[row - 1][f + 2i - 1] + array[row - 1][f + 2i + 1];

    If you prefere to merge the above two steps, feel free to do so.



    Now would be a good time to try to write some pseudocode to give these english statements the first blush of C++.
    Last edited by elad; 05-03-2002 at 04:00 PM.

  9. #9
    Unregistered Leeman_s's Avatar
    Join Date
    Oct 2001
    Posts
    753
    i dont like doing pascals triangle, i like this method:

    ex.: (a+5)^5 -> (a+b)^n :

    start with a^n. (coeficient*a exponent)/term number = next coeficient.

    then, (a^(n-1))(b^(n-(n-1))) + (a^(n-2))(b^(n-(n-2)))...and so on, but you must put on the coeficients

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    This method is pretty good. You could make it faster by
    taking out the recursion and indexing a 2-d array.
    Writing it so that it offsets it with | perfectly seems a little
    tough because at some point your pascal coeff will mess up the offsets. The easiest way to do this looks like to calculate one row for example 1 6 15 20 15 6 1 and then the number of spaces it occupies 16.

    Code:
    #include <iostream>
    using std::cout;
    using std::endl;
    
    int pascal(int row, int col)
    {
        if (row == 0 || col == 0 || row == col + 1)
            return 1;
    
        return pascal(row - 1, col - 1) + pascal(row - 1, col);
    }
    
    int main(void)
    {
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < i; ++j)
                cout << pascal(i, j) << " ";
            cout << endl;
        }
    
        return 0;
    }

  11. #11
    Registered User
    Join Date
    Dec 2001
    Posts
    367
    I did it this way:

    Code:
    int rows, cols;
    cin >> rows, cols;
    
    int pascal[rows][cols];
    
    for(int n=0; n<rows; n++)
    {
       for(int k=0; k<=n; k++)
       {
          if(k==0)
          {pascal[n][k]=1;}
    
          else if(pascal[k]==pascal[n])
          {pascal[n][k]=1;}
    
          else if(k>0)
          {pascal[n][k] = pascal[n-1][k-1] + pascal[n-1][k];}
    
       cout << " " << pascal[n][k];
    
       }
       cout << endl;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. pascal's triangle
    By Priyank in forum C Programming
    Replies: 9
    Last Post: 01-14-2011, 09:25 AM
  2. 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
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Replies: 1
    Last Post: 01-30-2002, 12:04 PM

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