The deadline for this lab is Wednesday 09 November 2005, 13:45 hours. Strictly no submissions will be accepted after the deadline.
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. We will be looking specifically at Sierpinski
Triangles that are found within Pascal's Triangle. Look at the diagram. 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 triangle form as shown in the diagram, we can show the first 14 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 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
Each number in Pascal's triangle is given a coordinate in the form of (r,c) where r is the row number and c 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.
To keep things simple, we assume that we have exactly 25 rows of Pascal's triangle.
* * * * . * * * * * * . . . * * * . . * * * . * . * . * * * * * * * * * * . . . . . . . * * * . . . . . . * * * . * . . . . . * . * * * * * . . . . * * * * * . . . * . . . * . . . * * * . . * * . . * * . . * * * . * . * . * . * . * . * . * * * * * * * * * * * * * * * * * * . . . . . . . . . . . . . . . * * * . . . . . . . . . . . . . . * * * . * . . . . . . . . . . . . . * . * * * * * . . . . . . . . . . . . * * * * * . . . * . . . . . . . . . . . * . . . * * * . . * * . . . . . . . . . . * * . . * * * . * . * . * . . . . . . . . . * . * . * . * * * * * * * * * . . . . . . . . * * * * * * * * * . . . . . . . * . . . . . . . * . . . . . . . *
Notice that the full-stops (even numbers) form triangles within Pascal's triangle. Such triangles are called Sierpinski Triangles.
What we want to do is to be able to find the area of a Sierpinski triangle at a particular coordinate. For example, the Sierpinski triangle at (2,1) has area 1. The Sierpinski triangle at (4,1) has area of 6, because the triangle is formed by 6 dots. The Sierpinski triangle at (6,1) has an area of 1. The Sierpinski triangle at (10,5) has an area of 28. The Sierpinski triangle at (5,1) has an area of 0, because (5,1) contains an asterisk and there is no Sierpinski triangle there.
Since our Pascal's triangle only has 25 rows, the Sierpinski triangle at (24,3) has an area of 7 because it is a partial triangle.
You are not allowed to use any special mathematical formula to calculate the area of any of the Sierpinski triangles. You should derive the area directly from the dots and asterisks in Pascal's triangle.
2 1 3 1 4 1 5 1 6 1 10 5 24 3
This says that we should find the area of Sierpinski's Triangle at coordinates (2,1), (3,1), and so on, until (24,3). There are an unknown number of lines in the text file.
You may assume that the coordinates always specify a point within the first 25 rows of Pascal's triangle. No error checking is required.
Area of Sierpinski's triangle at (2,1): 1 Area of Sierpinski's triangle at (3,1): 0 Area of Sierpinski's triangle at (4,1): 6 Area of Sierpinski's triangle at (5,1): 0 Area of Sierpinski's triangle at (6,1): 1 Area of Sierpinski's triangle at (10,5): 28 Area of Sierpinski's triangle at (24,3): 7You are reminded to follow the sample output exactly; else marks will be deducted.
Remember to submit your program using the submit pascal.c command, and check your submission using the check command.
All the best!