home—info—lects—labs—exams—hws
tutor/PIs—breeze (snow day)
Object120 + its docs—java.lang docs—java.util docs
lect10a
from `while` to `for`
(We'll divide the class into groups, w/ a pair of representatives at the board.)
Complete the following table,
for each of the following
code snippets.
int i = 8;
int resultSoFar = 0;
while (i > -4) {
if (i % 2 == 0) {
resultSoFar = resultSoFar + i;
}
i = i - 3;
}
return resultSoFar;
|
|
int i = 8;
int resultSoFar = 0;
while (i > -4) {
if (i % 2 == 0) {
resultSoFar = i + resultSoFar;
}
i = i - 3;
}
return resultSoFar;
|
|
int i = 8;
String resultSoFar = "";
while (i > -4) {
if (i % 2 == 0) {
resultSoFar = resultSoFar + Integer.toString(i);
}
i = i - 3;
}
return resultSoFar;
|
|
int i = 8;
String resultSoFar = "";
while (i > -4) {
if (i % 2 == 0) {
resultSoFar = Integer.toString(i) + resultSoFar;
}
i = i - 3;
}
return resultSoFar;
|
|
When writing a while-loop, keep these things in mind:
-
Work through an example by hand.
What “so-far” information do you accumulate?
(Make a local-variable to store that info, which will change over time.)
-
What corresponds to the new-information-looking-at-right-now?
(Make a local-variable to store that info, which will change over time.)
-
For each of these two pieces of info,
how do they change from one iteration to the next?
That is,
how do you construct the new values out of the pieces available to you?
We'll apply these steps to the following problem(s).
Starting-code
Exercise
In bowling, pins are arranged in a triangle with four layers;
there are a total of 10 pins.
You might be inspired on the weekends to make up your own
bowling formats, lining up empty bottles of Grape Nehi,
and realizing that you aren't confined to only four rows;
you might have 5 rows (requiring 5 more empties, for a total of 15),
or 6 rows (requiring yet 6 more empties, for a total of 21).
Of course, such home-grown bowling is only interesting for so long,
and then you start wondering,
in general, how many pins are needed for bowling-variants with other
numbers of rows?
o ( 1 pin in a 1-high triangle)
o o ( 3 pins in a 2-high triangle)
o o o ( 6 pins in a 3-high triangle)
o o o o (10 pins in a 4-high triangle)
o o o o o etc.
o o o o o o
That is, for a triangle with n rows, how many pins are needed?
Write the method triangularNumber,
which
returns the nth triangular number
Before launching into the code, let's compute some examples/test-cases
by hand, paying attention to our own thought process;
that will give us a clue as to how to compute the general case.
/** Return the nth triangular number.
* @param n The number of rows in a triangle.
* @return The number of pins needed to set up a n rows of pins,
* each row containing one more pin than the previous.
* That is, return 1+2+3+...+(n-1)+n.
*/
/** Some automated test cases for functions in this file.
*/
void testLoops() {
testEqualInts( triangularNumber(4), 10 );
testEqualInts( triangularNumber(6), 10 );
testEqualInts( triangularNumber( ), );
testEqualInts( triangularNumber( ), );
}
|
When computing this myself, I find that I am keeping track
of two pieces of information:
the total number of pins needed so far,
and
which row-number I'm currently working on.
(There is also the parameter n, given to me.)
teaching note:
Be sure to run a couple of
live tests of this, to set up triangularPyramid,
which will call this method.
Solution
Exercise
Consider stacking oranges.
This isn't two-dimensional like bowling pins sitting on the floor;
oranges get stacked in pyramids.
Every pyramid begins with a single orange at its peak,
but there are several ways to extend the pyramid.
-
You could have square pyramids (like the Egyptian and Mayan tombs),
one peak orange (layer 1) is supported by
four oranges (layer 2), which is supported by
nine oranges (layer 3), which is supported by
sixteen oranges (layer 4), etc..
The cross-section of the nth layer is an n×n square.
Write a program to compute the number of oranges in a square pyramid of height n.
-
If you want your stack to look tall, then you might instead use
triangular pyramids (tetrahedra):
The top layer has one orange,
the next has three oranges,
the next has a triangle of six oranges,
the next has a triangle of ten oranges,
etc..
What is the general pattern, for the number of oranges on the nth layer?
Hint: if the general case involves a triangularNumber,
then your code should call that previous function!
(Unless you are clever enough to find a
closed-form formula for tetrahedral numbers.)
Write a program to compute the number of oranges in a triangular pyramid of height n,
using a while-loop.
-
We will re-write some of the above while-loops
using a for-loop instead.
You can use either loop to do the same thing,
but for-loops are particularly idiomatic
when you have a number as your index variable.
More generally, you might wonder:
“Why does Java provide a for-loop,
when a while-loop already does everything I need?”.
The reason is that the for-loop provides us with
a nice trait:
it puts all the index-variable manipulation on a single line,
and leaves all details of
updating the SoFar-variable (the accumulator)
to the body of the loop.
It is helpful to be able to think of those tasks separately,
and helpful to have a language feature which lets us
make our
thought-patterns manifest.
-
In-class exercise, for for:
Re-write
countOccurrences(String,char)
using a for-loop.
If we finish these examples,
we will talk about:
- Read numbers from keyboard (as long as hasNextInt()),
and compute the min and max.
(What do our test cases tell us,
about the fewest number of times our loop might happen?
One — because the max of zero items isn't defined!)
-
Walking through characters in a string — find
the largest character.
-
Loops which might stop “early”:
Does a string contain the letter 'X'?
Note that we still have an accumulator “so-far” variable
and an index variable — but we can get fancier in our condition
if we want.
Does the program run much quicker, when we are fancy and stop earlier?
(For what inputs is it a big win?)
The syntax of a while loop is what you'd expect from
the above example:
- while-loop ::=
statementinit...
while (expressionboolean-condition) {
statementmay-alter-loop-condition...
}
When writing a while-loop, keep the same things in mind as when
writing a for-each loop.
However, we have a couple of new steps, because the for-each had
managed our index variable for us; now we need to do that
ourselves:
-
Work through an example by hand.
What “so-far” information do you accumulate?
(Make a local-variable to store that info, which will change over time.)
-
How to keep track of where you are in the loop?
-- or, keep track of the particular item you're
considering as you go through the loop another time.
Declare and initialize an index variable
to keep track of this.
(E.g., t, or even a Scanner).
- Write the loop, which uses the index-variable to
figure out when the loop ends.
-
Each time through the loop, how will you update your accumulator?
-
Each time through the loop, how will you update your index?
What does the following method return?
/** Announce a countdown, starting at 10.
* @return A countdown starting at 10.
* That is, "10...9...8... [etc] 2...1...Liftoff!"
*/
public String countdown() {
String chantSoFar = ""; /* A local variable, to accumulate the answer. */
int t = 10; /* The next number to count down. */
while (t >= 0) {
chantSoFar = chantSoFar + (t + "...");
t = t-1;
}
return (chantSoFar + "Liftoff!");
}
|
In order to walk through this, we need to keep track
of what chant and t are, in the environment.
- Fix the bug about including 0.
- Change the function so that it starts the countdown from
a specified point, not just 10.
style tip:
Don't just make the parameter named t and then assign to it
(but mention that approach).
Keeping the parameter untouched segues well into the next problem.
Cool Computer Science idea:
The crystal structure of graphite consists of layers of a hexagonal mesh -- strong connection within
the a single layer, but the layers just kinda nestle on top of each other (similar to our oranges).
(This is why graphite writes: the layers are sheeting off of each other, laying down onto the paper.)
But when you stack the layers, there are actually two possibilities:
a layer can be directly above the layer two levels down (as pictured),
or it can be offset by half a hexagon.
[When adding a new layer, you have two ways to offset the new hexagons — offset the same
way as the preceding one, or differently.]
Thus, each layer can be viewed as a 0 (directly above the two-layer-below version),
or as a 1 (offset half a hexagon from two layers below).
A computer scientist wants to construct a chunk graphite layer-by-layer, so that
it has a message in it!
A spy can give a pencil to their contact,
and the message is not written down anywhere — it is already encoded in the pencil's graphite!
(Moreover, the message could be encrypted — so even if interecepted, and even if
the interceptor looked at the crystal's graphite structure, it would look random.
The art of hiding messages inside innocuous files/objects is called
“steganography”.)
home—info—lects—labs—exams—hws
tutor/PIs—breeze (snow day)
Object120 + its docs—java.lang docs—java.util docs