Lab 4: Pascal's Triangle

Due by the end of class

Introduction

This week, we will get practice with recursion and formatting data. In this lab you will also begin checking for valid input. In the previous labs, you were guaranteed that the user input was valid, but you cannot make this assumption in general.

We will be constructing Pascal's Triangle. You have probably seen it before in the context of raising binomials to powers. Carefully read its definition below before trying to implement anything.

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 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Obviously, this triangle of numbers follows a specific pattern. Each number is the sum of the two directly above it. There is also a formula (called the binomial formula) which allows you to calculate any number in the triangle without determining its ancestors. The formula below calculates the value of term k on row n. In our triangle, the first row is row 0, corresponding to raising a binomial to the zero^th power. Likewise, the first term in each row is term zero. Thus, both the rows and the columns of Pascal's Triangle use the zero-based numbering system we frequently employ in computer science.

T [n, k ] = n ! / (( n - k )! k ! )

In this formula, n! means n factorial, given by the definition n! = n(n - 1) ... 1, and 0! = 1.

Lab Exercise

As in Lab 3, you will be reading in integers. We are providing you and updated readInt() that can read positive and negative numbers. You should use this readInt() function in your main function to read user input.

/**
 * Function: 	readInt
 * Returns: 	an int, read from standard input. 
 **/
int readInt()
{
	int c = 0;
	int i = 0;
	int sign = 1;
  
	while ((c = getchar ()) != EOF && c != '\n' && c != ' ')
	{
		if (c == '-')
			sign = -1;
		else if( c >= '0' && c <= '9')	
			i = i * 10 + (c - '0');	
	}

	return sign*i;
}

The user will enter an integer, and your program should print to standard output that number of rows of Pascal's Triangle. For example, if the input value was 8, your code should print the following.

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

To aid you in printing out the triangle, you should implement a recursive factorial function, and its return value should be long long.

You must also include a makefile with a clean command in it. The name of the executable generated by running make should be pascal.

You should limit the input to the numbers between 0 and 20 inclusive. If the number is not between 0 and 20 inclusive, print the error message Invalid input and newline and return from the main() function. You do not need to worry about non-integer input.

Remember to use the long long data type in the calculation of the factorials since they will become large.

Turn In

Zip the contents of your lab directory, including the makefile and the source C file. Upload this zip file to Brightspace. Do not include any object files or executables. Running the make command must compile the required C source code file and generate an executable named pascal.

All work must be done individually. Never look at someone else's code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.