Pascal's Triangle was originally developed by the ancient Chinese, but
Blaise Pascal was the first person to discover the importance of all of
the patterns it contained.
Look at the diagram on the right. At the tip of Pascal's Triangle is the number 1, which makes up the zeroth row. The first row (1 & 1) contains two 1's, both formed by adding the two numbers above them to the left and the right, in this case 1 and 0 (all numbers outside the Triangle are 0's). Do the same to create the 2nd row: 0+1=1; 1+1=2; 1+0=1. And the third: 0+1=1; 1+2=3; 2+1=3; 1+0=1. In this way, the rows of the triangle go on infinitely.
Since it is difficult for us to show Pascal's Triangle in a triangular form as shown in the diagram, we can show the first 12 rows of Pascal's Triangle in the following format:
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 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1
Each number in Pascal's Triangle is given a coordinate in the form of (n,k) where n is the row number and k is the column number. Both row and column numbers start from zero. So, (0,0) is the very first top-left number 1, (4,2) is the number 6, and (7,5) is the number 21.
In this assignment, we shall look at several ways of constructing the Pascal's Triangle.
which can be expressed as a computation involving factorials where the factorial of n is defined as
As an example, the factorial of six is
A skeleton program is provided for you. Your task is to define the function constructPascal that outputs the Pascal Triangle for a user-specified number of rows (a value greater than 0). You are to define two other functions binomialCoefficient and factorial to modularize the computation of the binomial coefficient and factorial. The function prototypes are as follows.
void constructPascal(int numRows); int binomialCoefficient(int n, int k); int factorial(int n);
A number of sample run are given below. Your program should give the correct output for Pascal Triangles of rows ranging from 1 to 13 (both inclusive).
Enter the number of rows of the Pascal Triangle: 1 1 |
The name of your C program file must be called lab8q1.c, files with any other name will not be marked.
In this part of the assignment, you are required to think about how the computation of the binomial coefficient can be restructured to avoid the computation of large factorials. You are to redefine the binomialCoefficient function in question 1. Try expanding the factorials involved in computing the binomial coefficient and look at the terms that can be cancelled. Once again, you are encouraged to discuss this in the forum, without giving the solution directly. You might also find the following statement helpful.
The product of n consecutive integers is divisible by the factorial of n.You are not allowed to use any data type other than int. The function prototypes should remain the same as per question 1.
A number of sample run are given below. You can assume that for this and subsequent exercises, we will never exceed 23 rows when constructing the Pascal Triangle.
Enter the number of rows of the Pascal Triangle: 1 1 |
Do not worry about lines being automatically wrapped around by your console window. That's not your fault.
The name of your C program file must be called lab8q2.c, files with any other name will not be marked.
There is a much simpler way of constructing the Pascal Triangle which makes use of the following.
This involves storing the values of the current row in order to compute the values of the next row. As such an array is in order. Include the declaration of an appropriately sized array in the constructPascal function; this array should also be appropriately initialized. Once again, you are reminded that we will never exceed 23 rows when constructing the Pascal Triangle.
The sample run is exactly the same as per question 2.
The name of your C program file must be called lab8q3.c, files with any other name will not be marked.
If we are allowed only one step, then we have an equal probability of 0.5 ending up either at positions -1 or +1. Multiply these two probabilities by 21, and we get the two values of 1 in row n = 1 of the Pascal Triangle. If we are allowed two steps, then we either end up at positions -2, 0 or +2. The probabilities of ending up at these positions are 0.25, 0.5 and 0.25 respectively. By multiplying these three probabilities by 22, we obtain the numbers 1, 2 and 1 respectively, consistent with the values of row n = 2 of the Pascal Triangle. So in general, if we are allowed to take n steps, we would end up at n+1 different positions. The probabilities of landing at these positions multiplied by 2n, gives us the desired values of row n of the Pascal Triangle. You might also like to note that you will always end up in odd (even) positions if n is odd (even).
Your task is to write a program to simulate the drunkard's walk. At the start of your program, the user will be prompted for the number of trials R and the random seed, in addition to the number of rows of the Pascal Triangle. For each row, simulate the walk for a total of R trials, and determine the frequencies of landing at the different positions. Use this to approximate the values of the Pascal Triangle, and print out the values to 3 decimal places. Do this for the required number of rows. Re-declare the array in the constructPascal function of question 3 with an appropriate size such that it can be used to store the frequencies of landing at a particular position. Write a function randomWalk that takes in this array and simulates the walk for R trials. The function prototypes of constructPascal and randomWalk is given below.
void constructPascal(int numRows, int numTrials); void randomWalk(int walk[], int n, int numTrials);
You may define other helper functions to further modularize your program. The sample run is given below. Once again, due to the randomness of the program, your output might not be the same. However, as the number of trials increases, your values must converge to the values of the Pascal Triangle.
Enter the number of rows of the Pascal Triangle: 1 Enter number of trials: 10000 Enter seed: 123 1.000 |
The name of your C program file must be called lab8q4.c, files with any other name will not be marked.
A total of 43 different hosts have accessed this document in the last 444 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 7 times.
If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.