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;
}

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;
}

Vad har du för betyg i matte?

Originally posted by Zewu
Vad har du för betyg i matte?

That means..""What grade do you have in math?""

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.

Inga problem...

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++.

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

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;
}

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;
}