Transcript Week10

CMP 131
Introduction to Computer
Programming
Violetta Cavalli-Sforza
Week 10
TODAY
• Finish loops (or almost)
• Homework #5 was posted on Monday
Don’t wait to start on it!!!
Equivalent Statements
• FOR loop
FOR Count := StartValue TO StopValue DO
BEGIN ... END {FOR}
• Equivalent WHILE
Count := StartValue;
WHILE Count <= StopValue DO
BEGIN ... ; Count := Count + 1; END {WHILE}
• Equivalent REPEAT
Count := StartValue;
IF StartValue <= StopValue THEN
REPEAT
...
Count := Count + 1;
UNTIL Count > StopValue
Simple Applications of FOR Lopps
• Printing patterns
– E.g. diagonal band
– E.g. tree
• Generating numbers (e.g. tables)
– E.g. table of powers of numbers
(sqr, sqrt, cubes)
– E.g. Fibonacci numbers
Task: Draw Diagonal Band
***
***
***
***
***
***
***
***
Program: Diagonal Band
PROGRAM DiagonalBand;
VAR J : integer;
BEGIN
FOR J := 1 TO 8 DO
writeln('***':J + 3);
readln
END.
Task: Draw Tree
*
* *
*
*
*
*
**** ****
* *
* *
***
Program: Tree
PROGRAM Tree;
VAR J : integer;
BEGIN
writeln('*':5);
FOR J := 1 to 3 DO
writeln('*':5 - J,'*':2 * J);
writeln('**** ****');
FOR J := 1 to 2 DO
writeln('* *':6);
writeln('***':6);
readln
END.
Task: Fibonacci Numbers
• Print the first 20 Fibonacci numbers
• Fibonacci numbers function:
Program: Fibonacci
PROGRAM Fibonacci;
CONST Number = 20;
VAR J ,
{counter variable}
N1, N2, N3
{counter variable}
: integer;
BEGIN
N1 := 0;
writeln('Fibonacci 0:', N1:5);
N2 := 1;
writeln('Fibonacci 1:', N2:5);
FOR J := 2 TO Number – 1 DO
BEGIN
N3 := N1 + N2;
writeln('Fibonacci',J:3,':',N3:5);
N1 := N2;
N2 := N3;
END;
readln
END.
Output: Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
Fibonacci
0:
0
1:
1
2:
1
3:
2
4:
3
5:
5
6:
8
7:
13
8:
21
9:
34
10:
55
11:
89
12: 144
13: 233
14: 377
15: 610
16: 987
17: 1597
18: 2584
19: 4181
Simple Applications of
WHILE/REPEAT loops
• Accumulators
– E.g. sums, means,
• Simulations
Loop Design
• Terminology
– Loop control:
• Making sure that the loop exits when it is supposed
to
– Loop processing:
• Making sure that the body performs the required
operations
• To formulate loop control & loop
processing, it is useful to list what we
know about the loop
Loop Design
• Loop design can be approached in two
ways:
– Analyze requirements:
• Determine needed initialization, testing, and
updating of the loop control variable
• Then formulate the loop control and loop
processing steps
– Develop templates:
• Make templates for frequently running forms
• Use these templates as the basis for the new loop
Sentinel-Controlled Loops
• Sentinel:
– An end marker that follows the last data item
• Frequently, you will not know exactly how many
data items a program will process before it
begins execution
• One way to handle this is to instruct the user to
enter a unique data value (sentinel value) as the
last data item. The program then tests each data
item and terminates when the sentinel value is
read.
• Sentinel value should be carefully chosen and
must be a value that could not normally occur as
data.
Sentinel-Controlled Loops
• Template:
Read the first value of input variable
WHILE input variable is not equal to sentinel do
BEGIN
...
Read next value of input variable
END
Sentinel-Controlled Loops
• Example: Collecting Exam Scores:
1.Initialize Sum to 0
2.Read the first score into Score
3.WHILE Score is not the sentinel (e.g. -1) do
BEGIN
4. Add Score to Sum
5. Read the next score into Score
END
Loops Controlled by Boolean Flags
• Flag: A Boolean variable whose value is
changed from False to True when a particular
event occurs
• Boolean Flags Template:
Initialize flag to false
WHILE flag is still false DO
BEGIN
...
Reset flag to true if event being monitored occurs
END
Loops Controlled by Boolean
Flags
• Example: Reading data characters and save the
first digit character read
DigitRead := false;
WHILE ( not DigitRead ) DO
BEGIN
write
('Enter
another
data
character >');
readln (NextChar);
DigitRead := ('0'<=NextChar) AND
(NextChar<='9')
END {WHILE}
Task: Dropping Objects
• Problem definition:
– Your physics professor wants you to write a
program that displays the effect of gravity on a
free-falling object. You should build a table
showing the height from a tower to every
second.
Analysis: Dropping Objects
• Observations:
– Assume
• time of free fall = t
– At t = 0.0
{initialization}
– While falling
{updating-loop body}
– Free fall ends
{testing -exit}
• object height = tower height
• object height =
tower height - distance traveled
• when height <= 0.0
Program Segment:
Dropping Objects
writeln ('Time' :10:2, 'Height' 10:2);
{initialization}
T := 0.0;
Height := Tower;
WHILE Height > 0.0 DO
BEGIN {body}
writeln (T : 10:2, Height :10:2);
T := T + DeltaT;
Height := Tower - 0.5 * G * Sqr(T)
END {WHILE}
writeln;
writeln ('SPLATT!!!');
Example: Dropping Objects
• Observations
– Before the loop is entered, a message
displaying the heading is printed.
– The number of lines in the table depends on
the time interval between lines (DeltaT) and
the tower height (Tower).
– During each loop iteration, the current
elapsed time, t, and the current object height
are displayed and new values are assigned to
these variables.
Simple Loops Summary
• Use FOR loop as a counting loop. The loop control
variable must belong to an ordinal type (not real).
• REPEAT and WHILE-loops are conditional loops. Their
number of iteration depends on whether the value of a
condition is true or false.
• WHILE loop is repeated as long as its loop repetition
condition is true.
• REPEAT loop is repeated until its loop-termination
condition becomes true.
• Usually a REPEAT loop can be written as a WHILE loop
by complementing the condition.
• Not all WHILE loops can be written as REPEAT loops,
because REPEAT loops executes at least once, whereas
a WHILE loop body may be skipped entirely.
• WHILE loop is preferred over a REPEAT loop unless you
are certain that at least one loop iteration must always
be performed.
Exercises
• Write a while loop that counts the number of
digits entered in a stream of characters. Exit
when the character ‘X’ is entered. Make sure
you don’t count the X
• Write a while loop that reads negative or positive
numbers, keeping track of the largest in absolute
terms. Exit when a zero is entered.
• Write a while loop that reads lines of text, and
counts the characters entered. Exit when the
string ‘Quit’ is entered. (Don’t count the
characters in ‘Quit’).
Nested Loops
• It is possible to nest loops
• Each time the outer loop is repeated, the inner
loops are reentered, their loop-control
parameters are reevaluated, and all required
iterations are performed
• Very useful in processing multi-dimensional
arrays
Task: Draw Isosceles Triangle
*
***
*****
*******
*********
Program: Isosceles Triangle
PROGRAM Triangle;
{Draw an isosceles triangle}
CONST
NumLines = 5;
{number of rows in triangle}
Blank = ' ';
{output character}
Star = '*';
{output character}
VAR
Row,
{control for outer loop}
LeadBlanks,
{control for first inner loop}
CountStars: integer; {control for 2nd inner loop}
{Continued}
Nested Loops Example
Isosceles Triangle
BEGIN {Triangle}
FOR Row := 1 TO NumLines DO {outer loop}
BEGIN
{Draw each row}
{first inner loop}
FOR LeadBlanks := NumLines - Row DOWNTO 1 DO
write (Blank);
{Print leading blanks}
{second inner loop}
FOR CountStars := 1 TO 2 * Row - 1 DO
write (Star); {Print asterisks}
writeln;
END {for Row}
end. {Triangle}