The numbers in the graphic below form the first five rows of Pascal's Triangle. The first row consists of a single number 1. In subsequent rows, each of which is has one more number than the previous, values are calculated by adding the two numbers above left and above right. For the first and last values in each row we just take the single value above, therefore these are always 1.
Pascal's Triangle in its conventional centred layout
(If you do an image search for Pascal's Triangle you will find plenty more, most frequently in a honeycomb grid, sometimes animated, but always nicer than mine. I'm a software engineer, not a graphic designer!)
At first glance you might think Pascal's Triangle is of little interest or use other than perhaps teaching very young children to add up. Nothing could be further from the truth - as with so many areas of mathematics this simple idea has spawned a large area of study and overlaps with even more. The Wikipedia article on the subject is fairly comprehensive but I am writing this article as a precursor to another on the subject of a contraption called a Galton Board, which takes us into the area of statistics and specifically the normal distribution. If you look at the last row of numbers you might be able to discern the first inklings of a normal distribution.
To that end, note that each number represents the number of possible paths to it from the top, asuming we travel downwards and either to the left or right. For example, the second number in the third row is 3, and there are three possible paths to it from the top:
- left, left, right
- left, right, left
- right, left, left
The Data Structure
Let's start of by considering the kind of data structure we need to represent Pascal's Triangle. For this purpose it might be simpler to show it left-aligned rather than centred.
Pascal's Triangle in a left aligned form
Looking at the layout above it becomes obvious that what we need is a jagged array, or an array of arrays. In a Pascal's Triangle the rows and columns are numbered from 0 just like a C array so we don't even have to bother about adding or subtracting 1.
Program Requirements
The purpose of this program is simply to print out Pascal's Triangle to the number of rows which will be specified as a command line argument. The steps to do this, which will roughly correspond to functions called from main, are as follows:
- Retrieve and validate the command line argument
- Create an empty data structure of the required size
- Calculate all values
- Print out the values in a left-aligned format
- Print out the values in a centred format
Step 3, calculating values, doesn't present any obvious problems as it is simply the addition of two numbers. However, calculating the indexes of the two numbers in the previous row to add is fiddly so I'll use the following formula, where n is the row number and k is the column number, both 0-based:
Calculating values for Pascal's Triangle
value(n,k) = n!/(k!*(n-k)!)
(The exclamation mark ! represents the factorial of a number, ie the number multiplied by all its preceding integers down to 1. For example 5! = 5*4*3*2*1. A while ago I wrote a post on memoizing factorials - pre-calculating and storing them for future use - but for this project I will write a function to calculate them on the fly.)
Starting to Code
Create a new folder and within it create a file called pascalstriangle.c. As this is a short and simple program I will keep all the source code in one file. You can download it from as a zip or download/clone from Github if you prefer.
Source Code Links
pascalstriangle.c (part 1)
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//--------------------------------------------------------
// FUNCTION PROTOTYPES
//--------------------------------------------------------
long int factorial(long int n);
int get_rowcount(int argc, char* argv[]);
bool pascalstriangle_create(long int* pt[], int rowcount);
void pascalstriangle_populate(long int* pt[], int rowcount);
void pascalstriangle_print_left(long int* pt[], int rowcount);
void pascalstriangle_print_centre(long int* pt[], int rowcount);
void pascalstriangle_free(long int* pt[], int rowcount);
//--------------------------------------------------------
// FUNCTION main
//--------------------------------------------------------
int main(int argc, char* argv[])
{
puts("---------------------");
puts("| codedrome.com |");
puts("| Pascal's Triangle |");
puts("---------------------");
int rowcount = get_rowcount(argc, argv);
if(rowcount > 0)
{
long int* pt[rowcount];
if(pascalstriangle_create(pt, rowcount))
{
pascalstriangle_populate(pt, rowcount);
pascalstriangle_print_left(pt, rowcount);
pascalstriangle_print_centre(pt, rowcount);
pascalstriangle_free(pt, rowcount);
}
}
else
{
printf("Error - row count must be specified as argument\n");
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
After the #defines and function prototypes we have our main function. This firstly calls the get_rowcount function which I'll describe later but basically retrieves the rowcount from command line parameters. If it's a valid number > 0 we declare an array which is passed to pascalstriangle_create along with the rowcount. This function uses malloc so could possibly fail and return false which we need to check for. However, if all goes well we call a set of functions to populate and print a Pascal's Triangle, and then free the memory.
pascalstriangle.c (part 2)
//--------------------------------------------------------
// FUNCTION get_rowcount
//--------------------------------------------------------
int get_rowcount(int argc, char* argv[])
{
if(argc == 2)
{
return atoi(argv[1]);
}
else
{
return 0;
}
}
Next comes the get_rowcount function, its arguments being the argc and argv arguments straight from main. The first argument is always the name of the executable so the one we want is at index 1. We therefore check there are two arguments - if not we return 0. Even if there are the correct number of arguments the second might not be a valid number so we call atoi which returns 0 if it cannot convert the supplied number to an int. As you saw in main, we checked the return value before continuing with creating the triangle.
pascalstriangle.c (part 3)
//--------------------------------------------------------
// FUNCTION pascalstriangle_create
//--------------------------------------------------------
bool pascalstriangle_create(long int* pt[], int rowcount)
{
int columncount = 1;
for(int row = 0; row < rowcount; row++)
{
pt[row] = malloc(sizeof(long int) * columncount);
if(pt[row] == NULL)
{
return false;
}
columncount++;
}
return true;
}
Now let's move on to pascalstriangle_create, which takes an array of long int pointers and a rowcount, and dynamically allocates memory to each element of the array to create a 2D array looking like the graphic in the Data Structure section above. This is perfectly straightforward but note that each row has one more element than the one before. The function therefore uses a columncount variable which is initialized to 1 and incremented on each iteration of the loop.
pascalstriangle.c (part 4)
//--------------------------------------------------------
// FUNCTION pascalstriangle_populate
//--------------------------------------------------------
void pascalstriangle_populate(long int* pt[], int rowcount)
{
int columncount = 1;
int column;
for(int row = 0; row < rowcount; row++)
{
for(column = 0; column < columncount; column++)
{
pt[row][column] = factorial(row) / (factorial(column) * factorial(row - column));
}
columncount++;
}
}
The next function is pascalstriangle_populate which takes the newly created empty data structure and fills in the missing values using the formula above.
The columncount and for loop match the pascalstriangle_create function above and I could easily have combined the two. However, they are two separate processes and I therefore decided to put each in its own function. (You have probably heard of the Single Responsibility Principle. It's usually applied to classes in OOP but is equally if not more relevant to individual functions. Creating and populating a data structure are most certainly not a "single responsibility", even if merging them would save a loop.)
pascalstriangle.c (part 5)
//--------------------------------------------------------
// FUNCTION pascalstriangle_print_left
//--------------------------------------------------------
void pascalstriangle_print_left(long int* pt[], int rowcount)
{
int columncount = 1;
int column;
for(int row = 0; row < rowcount; row++)
{
for(column = 0; column < columncount; column++)
{
printf("%-4ld", pt[row][column]);
}
printf("\n");
columncount++;
}
printf("\n");
}
//--------------------------------------------------------
// FUNCTION pascalstriangle_print_centre
//--------------------------------------------------------
void pascalstriangle_print_centre(long int* pt[], int rowcount)
{
int columncount = 1;
int column;
int inset = (int)((((rowcount * 2) - 1) / 2) * 3);
int insetindex;
for(int row = 0; row < rowcount; row++)
{
for(insetindex = 0; insetindex < inset; insetindex++)
{
printf(" ");
}
for(column = 0; column < columncount; column++)
{
printf("%-3ld ", pt[row][column]);
}
printf("\n");
columncount++;
inset-= 3;
}
}
Next up we have a couple of print functions. Again they could have been combined (arguably without violating the Single Responsibilty Principle) with an additional argument to specify whether to print left or centred, but I decided to avoid several untidy "if" statements at the expense of a certain amount of duplication.
The second of these functions centres the triangle by calculating an offset and printing that number of spaces before the actual numbers, the offset being reduced at each iteration.
pascalstriangle.c (part 6)
//--------------------------------------------------------
// FUNCTION pascalstriangle_print_free
//--------------------------------------------------------
void pascalstriangle_free(long int* pt[], int rowcount)
{
for(int row = 0; row < rowcount; row++)
{
free(pt[row]);
}
}
//--------------------------------------------------------
// FUNCTION factorial
//--------------------------------------------------------
long int factorial(long int n)
{
if(n == 0)
{
return 1;
}
else
{
long int f = n;
for(int i = n - 1; i > 1; i--)
{
f*= i;
}
return f;
}
}
Lastly we have a couple of utility functions, pascalstriangle_free to free the memory and factorial to (obviously!) calculate factorials.
There are a couple of points to note in the factorial function:
- 0! is 1 (check it on your calculator if you don't believe me...)
- The condition in the for loop is i > 1, NOT i >= 1. This cuts out the superfluous (but mathematically correct) final stage of multiplying by 1.
We have now finished the code so can compile and run it using these commands . . .
Compile and Run
gcc pascalstriangle.c -std=c11 -lm -o pascalstriangle
./pascalstriangle 8
. . . which will give you the following output.
Program Output
---------------------
| codedrome.com |
| Pascal's Triangle |
---------------------
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
1 7 21 35 35 21 7 1
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
1 7 21 35 35 21 7 1
You can of course change the command line argument to another value if you like.