Prev <<
>> On to the next chapter: Guess My Number.
Pascal's Triangle
What sort of math can you do on a computer?
The following program computes Pascal's triangle
(about Pascal's triangle):
An overview of the code:
- The page lays out
a centered button
at the top of the page and puts an empty array in a
global variable row.
- Each time the
button is pressed,
we do the
following:
- Run a computation to
figure out the next row of Pascal's triangle and
- Append it into the
<center>...</center> element as a new line.
Handling Clicks and Adding Text with jQuery
Again we are using the
jQuery library.
In this program we are using two jQuery idioms:
The official jQuery
documentation is excellent if you are impatient to read more.
Javascript Array Manipulation
To compute each row of Pascal's triangle, we are using Javascript
Arrays. Things to know about arrays in this example:
- row = [] means "Set row to be an empty array." The []
is just an array with no items. We could have chosen any
starting array such as [1, 2, 1].
- row.push(1) means "Push the number 1 onto the end of
the array." If row used to be [1, 2, 1],
now it will be [1, 2, 1, 1].
- row.length is just the length of the array. If row is
[1, 2, 1, 1], then row.length is 4.
- row[j] += row[j - 1] updates the jth item of the array
by adding to it the value of the j-1th item of the array.
- row.join(' ') means "Make a big string joining all the elements
of the array with a space between each element."
Looping and the Four "for" Parts
The computation of a row is done using a
for loop.
Here you can read the loop as follows: "Begin
j at
row.length-2, and as long as
it is no smaller than 1,
run the body of the loop and then
decrease j by 1".
Let us take that apart in some more detail. The "for" statement
expresses all this by providing a place for the four pieces of code
you usually need for any loop:
- The initalizer statement
runs only once, at the very beginning of the loop. Here the initializer
sets up the variable j at row.length-2.
- The loop test expression
is checked each time we are about to begin looping again, including the
first time through. If the expression is false, the body of the loop
is skipped and the loop is done. For example, when we are making the
first row of Pascal's triangle, row.length will be 1,
which means that j will start off as -1, so the
test expression j>=1 will start off false, and the
body of the loop will not execute at all.
1 from the j variable.
- The loop body within
{curly braces} is the main piece of code that you want to run
repeatedly. It runs right after the test succeeds.
- The loop advance statement
runs after the body each time we are getting ready to make
another loop. Here the loop advances by subtracting 1 from
j.
What is the loop actually doing? Here is a diagram of the contents
of row right after we have computed row #4 (the length
of the array is 5, and the items are indexed from 0 to 4):
| i |
0 |
1 |
2 |
3 |
4 |
| row[i] |
1 |
4 |
6 |
4 |
1 |
|
When the button is clicked, first we push a "1" onto the end of the array,
extending its length by one item, so now the array has six items.
| i |
0 |
1 |
2 |
3 |
4 |
5 |
| row[i] |
1 |
4 |
6 |
4 |
1 |
1 |
| j |
|
|
|
|
j=4 |
|
The loop variable j starts out at row.length-2,
which is 4.
| i |
0 |
1 |
2 |
3 |
4 |
5 |
| row[i] |
1 |
4 |
6 |
4 |
5 |
1 |
|
|
|
|
→ |
j=4 |
|
The loop body row[j] += row[j - 1] finds the number 4
in slot #3 and then adds it into slot #4, writing a 5 into that slot.
Then the loop advance statement decreases j by 1
and the loop is repeated several times:
| i |
0 |
1 |
2 |
3 |
4 |
5 |
| row[i] |
1 |
4 |
6 |
10 |
5 |
1 |
|
|
|
→ |
j=3 |
|
|
|
| i |
0 |
1 |
2 |
3 |
4 |
5 |
| row[i] |
1 |
4 |
10 |
10 |
5 |
1 |
|
|
→ |
j=2 |
|
|
|
|
| i |
0 |
1 |
2 |
3 |
4 |
5 |
| row[i] |
1 |
5 |
10 |
10 |
5 |
1 |
|
→ |
j=1 |
|
|
|
|
|
| i |
0 |
1 |
2 |
3 |
4 |
5 |
| row[i] |
1 |
5 |
10 |
10 |
5 |
1 |
|
j=0 |
|
|
|
|
|
Finally, after j is decreased to 0, the loop test
j >= 1 is no longer true, and the loop exits instead of running
the loop body again.
We are left with row #5 of Pascal's triangle in the array.
Things to Try
- Try changing the program so that the first row of the triangle
starts as "[1, 100, 100, 1]".
- Try changing the program so that it adds a row if you click anywhere
in the body of the document - so you don't need to click on the button.
Prev <<
>> On to the next chapter: Guess My Number.