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