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