Tags

, , , , ,

Pascal’s Triangle is mentioned in Berkeley’s CS61B lecture 5 (around ~39:00 and up). I just watched it and it inspired this post.

For details about Pascal’s triangle and it’s interesting properties, go to Wikipedia.

In lecture it is given as an example of an application of a 2D array. Along with an example of the triangle’s application in math:

row i represents the coefficients of the expansion of: (x+1)i

ie. for i=4.

(x + 1)4 = 1x4 = 4x3 + 6x2 + 4x + 1

The given source code also demonstrates a very powerful feature of Java, the run-time declaring nature of Arrays — The second dimension in the pascal’s triangle array has variable size.

Here’s something I put together that utilizes the sample code.


import java.util.*;

/**
 *
 * @author DM
 */
public class PascalTriangle {

	private static final int N_ROWS = 10;

	public static void main(String[] args) {
		//declare the array.
		int pt[][] = new int[N_ROWS][];
		//fill it with values.
		//This loop was given in CS61B lecture 5
		for (int i = 0; i < N_ROWS; i++) {
			pt[i] = new int[i + 1];			// Construct row i.
			pt[i][0] = 1;					// Leftmost value of row i.
			for (int j = 1; j < i; j++) {
				pt[i][j] = pt[ i - 1][j - 1] + pt[i - 1][j];	// Sum 2 entries above.
			}
			pt[i][i] = 1;					// Rightmost value of row i.
		}

		// pretty-print the triangle.

		System.out.println("Created pascal triangle with " + N_ROWS + " rows.");
		//need to know the max length beforehand.
		int maxlength = Arrays.toString(pt[ pt.length - 1]).length();

		for (int i = 0; i < pt.length; i++) {
			int rowAr[] = pt[i];
			String rowText = java.util.Arrays.toString(rowAr);

			int offset = maxlength / 2 + rowText.length() / 2;
			String format = "%" + offset + "s\n";

			System.out.printf(format, rowText);
		}
	}
}

You can change the N_ROWS constant to higher values to get more rows.
Here’s a sample output with N_ROWS = 10:

Created pascal triangle with 10 rows.
                 [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]

If you have a bit of imagination you can see how this concept and its 3D cousin, Pascal’s Pyramid, could be (customized and) applied in a game to implement a form of difficulty in movement through some resistant medium; ie air, water, mud, force-field, -some other imaginary resisting medium-…

Advertisements