Java Reference
In-Depth Information
t[r][c] is called “ r choose c ” because it is the number of ways of choosing c
elements from a set of size r .
We give an example. Consider the set of integers {1, 2, 3, 4} . Its subsets
of size 2 are:
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
There are 6 subsets of size 2 in the set of 4 ,so 4 choose 2 is 6 , and 6 appears in
row 4 column 2 of Pascal's triangle.
Creating Pascal's triangle
Figure 9.6 contains a function that computes the first n rows of Pascal's tri-
angle as a ragged array. The first statement of the function body declares two-
dimensional array variable t , creates an array object of length n , whose elements
are initialized to null , and stores the name of the array in t . Note that if n is 0 ,
an array of size 0 is created; this is allowed in Java.
Each iteration of the loop creates one row of array elements and stores val-
ues in them. The repetend has two steps: first, create the array object of length
r+1 and store it in t[r] ; second, calculate the values of array t[r] .
Calculating the values for row r is straightforward. The first value is set to
1 ; the inner values of the row are calculated in a loop, using the formula given
earlier, and the last value is set to 1 . For row 0 , the single element will be calcu-
lated twice because it is both the first and the last element.
Get the method
from a footnote
on lesson page
9-4.
/** = the first n rows of Pascal's triangle ( for n >= 0) */
public static int [][] PascalTriangle( int n) {
int [][] t= new int [n][]; // Pascal's triangle
// invariant: rows 0..r-1 have been created
for ( int r= 0; r != t.length; r= r + 1) {
// Create array t[r] for row r of Pascal's triangle
t[r]= new int [r + 1];
// Calculate the values for row r
t[r][0]= 1;
// invariant: elements b[r][0..c-1] have been calculated
for ( int c= 1; c < r; c= c + 1)
{ t[r][c]= t[r - 1][c - 1] + t[r - 1][c]; }
t[r][r]= 1;
}
return t;
}
Figure 9.6:
A function to calculate n rows of Pascal's triangle
Search WWH ::

Custom Search