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

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

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