Earth has the Bermuda Triangle, Space has black holes, and humanity has my crazy mind. All of these things are largely unexplained phenomena and so I figured, why not throw out one for the programming world? If Bermuda can have a triangle, dangit we are going to have one too! Introducing Pascal’s triangle…. on this episode of the Programmer’s Underground!
Pascal’s triangle has been studied around the world for hundreds of years. Not primarily because of its mystique but because a simple arrangement of numbers can produce some interesting patterns. Each row starts and ends with one but the values in each row are the sum of the two numbers above it. But that is one way you could think of it. Another way is looking at the edges (diagonals) and working your way in you can see such patterns as natural numbering, triangular numbering, tetrahedral and even pentatope numbers. Each row moving in is said to be the next highest order of triangle. You can even find the Fibonacci number in it.
Below is a nice little graphic showing you the start of Pascal’s triangle (Compliments of Wikipedia.org)
As the studies continue more and more people find subtle little patterns. When expanded out, pascal’s triangle can even form little triangles in it (by shading out certain numbers). Could this triangle be some key to the universe? Will aliens from another planet know its true meaning and use it to open a dialog of mathematics with us? Perhaps. But here on this entry I am going to show you how to write your own.
I originally got the idea to do this example from people on the board asking about Pascal’s triangle as part of an assignment. I figured why not do one myself and throw it out there for our DIC members to read and use. Some people have been asking for it in various languages and some have wanted it in C/C++. To quell the masses and literally buckle under the pressure, I decided to do it in C/C++ to get to most of the students out there in high school/college land.
So here it is….
#include <iostream>
using namespace std;
int main() {
int rows = 0;
cout << "Please enter the number of rows: ";
cin >> rows;
// Formula: c = prevnum * ((row+1 - column) / column)
// Denominator increases and numerator decreases
for (int i = 0; i < rows; i++) {
// Lets prefix the appropriate number of spaces for each row
for (int space = (rows - i); space > 0; space--) {
cout << " ";
}
// First cell will always be one
double cell = 1.0;
cout << cell << " ";
// Starting with second column to the end, calculate the value.
for (int col = 1; col < (i + 1); col++) {
// First calculate the factor to multiply against previous number
double factor = ((double)((i + 1) - col) / (double)col);
// Multiply it against the previous cell and print.
factor = cell * factor;
cell = factor;
cout << cell << " ";
}
// We have finished a row, so drop to the next.
cout << endl;
}
return 0;
}
Your first impression might be “That is it?” and yeah, that would be it. Of course this program is meant to serve as a nice framework for those people who want to continue building onto it. As you can see it has no real error checking or anything against the user’s input and that was intentional. We do want you to think “a little” if at all possible.
As you can see we collect the number of rows to display and loop through each row building the columns as we go. The idea is that each column is based on a formula seen there in the example value = previous_column_value * (((row + 1) – column) / column) where you got to make sure that column is not zero (or else you would get a divide by zero error).
The tricky part is to make sure that your formula follows the precedence rules and that you start off each column with 1. Also making sure that you use the correct types for obtaining a faction on the back half of the numbers (using double to get decimal values for instance). Throwing it in a loop for the rest of the columns you can then calculate each row and print it. That’s all there is to it folks!
Now on a standard fixed width output the triangle starts out nice but the bigger numbers begin to distort it. This is just a formatting issue and really I didn’t want to go into all that. Here is the output with the first 10 rows. As you can see it distorts just a little and gets gradually worse because of the fixed width nature of the fonts and lack of the proper spacing to compensate.
Feel free to use the code above in your own projects. Just throw out some credit to DIC when possible. Maybe it can be a topic you have at the dinner table while you are picking at your peas. You can find many more topics like this on the DIC boards so if you haven’t already, be sure to drop by and let the DIC team answer your programming questions.
Thanks! 🙂
