Transcript Introduction

Lesson 7
COP1006
McManus
1






Flowchart Symbols
The Loop Logic
Structure
Incrementing/
Decrementing
Accumulating
While/WhileEnd
Repeat/Until





AutomaticCounter Loop (For)
Nested Loops
Indicators
Algorithm
Instructions
Recursion
COP1006
McManus
2

Decision
◦ True/False/Else


Decision
Process
Assign
Process
Assign
COP1006
McManus
3

Allows the programmer to specify that an
action is to be repeated based on the truth
or falsity of some condition.
While there are more timecards to be processed
Obtain time from each card and calculate pay
As long as there are items still remaining on the
list the loop will continue.
◦ Otherwise known as iteration.
COP1006
McManus
4


Known as definite because the number of
iterations to be performed at runtime is
known.
Also known as Counter-controlled Repetition
◦ Uses a variable called a counter to control the
number of times a set of statements should
execute.
COP1006
McManus
5

Known as indefinite because the number of
iterations at runtime is not known before
the loop begins executing.
◦ Uses a sentinel value (signal value, a flag value,
or a dummy value to indicate “end of data entry.”
 When using a sentinel
 Choose a sentinel that will not naturally exist within the range
of data being used.
 Ex. 999-99-9999 for Social Security Numbers
COP1006
McManus
6

one of the three types of program control
structures
◦ Sequence
◦ Selection
◦ Repetition
COP1006
McManus
7




Initialization
Condition (the test)
Increment (or Decrement)
The Accumulator, although used in frequently
in loops, is NOT part of the generic looping
process
COP1006
McManus
8

The Initialization

set to an initial value
◦ usually zero but not all the time

Examples:
◦ Count = 0
◦ Count = 1
◦ Count = 100
COP1006
McManus
9

The Test or Condition

Examples:
◦ tested before the start of each loop repetition,
called the iteration or pass.
◦
◦
◦
◦
Count
Count
Count
Count
<3
<= 3
>5
>= 5
Count = 10
Count <> 10
COP1006
McManus
10

The Increment (or Decrement)
◦ updates the variable during each iteration
◦ must be part of the loop body (usually the last line)

Examples:
◦ Count = Count + 1
◦ Count = Count - 1
COP1006
McManus
11


Variables used to store values being
computed in increments during the
execution of a loop.
Not part of the Looping Process
◦ But quite often an integral addition to the process
◦ Very often looks like an increment, which is part of the
looping process

Examples:
◦ Sum = Sum + 1
◦ TotalGrade = TotalGrade + CurrentGrade
COP1006
McManus
12

The Three Most Common Loop-control
statements:
◦ the while,
◦ the for, and
◦ the repeat

But there are lots of other loop variations
dependent on the language.
COP1006
McManus
13

The while statement
◦ The most versatile of the loops
◦ The loop body contains the instructions to be
repeated.
◦ The loop-repetition condition is the Boolean
expression after the reserved word while which is
evaluated before each repetition of the loop body.
COP1006
McManus
14
Set counter To 0
While counter < final_value
statements
Increment counter by 1
While-end
Init
true
?
Stmt
false
Stmt
COP1006
McManus
15
x = 3;
How many times does the
Count = 0;
loop execute?
while Count < 3 do
begin
What is displayed?
X = X * 2;
6
Print (X);
12
Count = Count + 1
24
end; {while Count}
Pascal Code
COP1006
McManus
16
x=3
Count = 0
While Count < 3
X=X*2
Print X
Count = Count + 1
End While
VB Code
COP1006
McManus
17
int X = 3;
int count = 0;
While (count < 3)
{
X=X*2
cout << X << endl;
Count = Count + 1;
}
Print statement
C++ Code
COP1006
McManus
18
A
Sentinel-Controlled Loop
◦ Controlled by a sentinel value.
◦ Examples
end-of-file marker (EOF)
end-of-line marker (EOL)
999999999 for SSN
999999 for date
COP1006
McManus
19

A Sentinel-Controlled Loop
◦ Pseudocode Template
Initialize Sum to 0
Read the first value into counter variable
While counter variable is not sentinel do
Add counter value to Sum
Read next value into counter value
While-end; {while}
COP1006
McManus
20

Boolean Flag-Controlled Loops
◦ Executes until the event being monitored occurs.
 A program flag, or flag, is a Boolean variable whole
value (True or False) signals whether a particular event
occurs.
 The flag should initially be set to False and reset to
True when the event occurs.
COP1006
McManus
21

Boolean Flag-Controlled Loops
◦ Pseudocode Template
Initialize flag to False
while not flag
statements..
Reset flag to True if the event being monitored
occurs
while-end;
{while}
COP1006
McManus
22


Logical Opposite of the
While Loop
Unlike the While/WhileEnd, the Do/Until tests for
falsity.
◦ Should be used when the
question being asked is
more naturally asked
in the negative.
Init
false
Counter
<5
Stmt
true
Stmt
COP1006
McManus
23
x=3
Count = 3
Do Until Count < 1
X=X*2
Print X
Count = Count - 1
Loop
COP1006
McManus
24

Similar to the While/While-End structure
◦ In the While Loop
 loop-continuation is tested at the beginning of the
loop before the body of the loop is performed.
◦ In the Repeat Until Loop
 loop-continuation is tested after the loop body is
performed, thus executing the loop body at least once.
COP1006
McManus
25

Pseudocode Template
Repeat
statements
increment counterVariable
Until testCondition
 Notice that the
statements are
executed before the
condition to end the loop
counter = 1
Action
occurs
before
Test
statements
True
counter
<5
False
COP1006
McManus
26


Combines all of the Loop Process
components into one statement.
Notes on the Counter:
◦ Can be used non-destructively but must not be
modified (destructively) within the loop body.
◦ Should be a local variable.

The loop body will not be executed if initial
is greater than the final value, unless the
increment value is negative.
COP1006
McManus
27

Pseudocode Example
For counter = initialvalue To finalvalue Step 1
statements…
‘to increment
Next counter
For counter = finalvalue To initialvalue Step -1
statements…
‘to decrement
Next counter
COP1006
McManus
28

Note that the “To” is equivalent to “while less than or
equal to”
For counter = 1 to 5 Step 1
Print counter
Next counter
counter = 1
(implicit)
counter
<= 5
True
counter =
counter + 1
(implicit)
Print counter
(implicit)
False
COP1006
McManus
29

Loops can be nested just as if statements.
◦ Cannot use the same counter-control variable for
the inner loop as is used for the outer loop.
x True
False
y True
False
COP1006
McManus
30
Initialize outer loop
While outer loop test {while}
statements...
Initialize inner loop
While inner loop test {while}
Inner loop processing and
Update inner loop variable
while-end {inner while}
statements...
Update outer loop variable
while-end {outer while}
COP1006
McManus
31
Dim outercounter As Integer
Dim innercounter As Integer
outercounter = 1
While outercounter <= 3
innercounter = 1
While innercounter <= 3
innercounter = innercounter + 1
Wend ‘innercounter
outercounter = outercounter + 1
Wend ‘outercounter
COP1006
VB Code
McManus
32


Assertions about the characteristics of a loop
that always must be true for a loop to execute
properly.
The assertions are true on loop entry, at the
start of each loop iteration, and on exit from
the loop.
◦ They are not necessarily true at each point within
the body of the loop.
COP1006
McManus
33




when the loop is skipped entirely (zero
iteration loop)
when the loop body is executed just once
When the loop executes some normal number
of times
When the loop fails to exit (infinite loop)
COP1006
McManus
34

Verify the Algorithm
◦ Test the value of the algorithm
 before the loop
 during the loop, and
 after the loop.
COP1006
McManus
35


Beware of infinite loops
Beware of off-by-one Loop Errors
◦ Executes the loop one too many times
◦ Executes the loop one too few times
COP1006
McManus
36
Or twisted tails
COP1006
McManus
37



Occurs when a function calls itself from
within the body of the function
Also known as “procedural iteration”
Classic Examples of Recursion
◦ Factorial
◦ Fibonacci
COP1006
McManus
38

How it works:
If X = 3, the chain of recursive calls would be as
follows:
Factorial(3)
3 * Factorial(2)
3 * (2 * Factorial(1) )
Precondition x  0
Postcondition
Returns the product 1 * 2 * 3 * …* x for x > 1
Returns 1 when X is 0 or 1.
COP1006
McManus
39
Private Function Factorial(ByRef y As Double) _
As Double
‘2nd double defines Factorial
If y <= 1 Then
Factorial = 1
' Base case
Else
Factorial = y * Factorial(y - 1) ' Recursive step
End If
End Function
The Base Case is also known as the Stopping Case.
COP1006
McManus
40




Investigated (in the year 1202)
was about how fast rabbits could
breed in ideal circumstances.
Suppose a newly-born pair of
rabbits, one male, one female,
are put in a field. Rabbits are
able to mate at the age of one
month so that at the end of its
second month a female can
produce another pair of rabbits.
Suppose that our rabbits never
die and that the female always
produces one new pair (one
male, one female) every month
from the second month on.
The puzzle that Fibonacci posed
was...
How many pairs will there be in
one year?




At the end of the first month,
they mate, but there is still one
only 1 pair.
At the end of the second month
the female produces a new pair,
so now there are 2 pairs of
rabbits in the field.
At the end of the third month,
the original female produces a
second pair, making 3 pairs.
At the end of the fourth month,
the original female has produced
yet another new pair, the female
born two months ago produces
her first pair also, making 5
pairs.
COP1006
McManus
41
Female
Male
COP1006
McManus
42



We can make another
picture showing the
Fibonacci numbers
1,1,2,3,5,8,13,21
If we start with two
small squares of size
1 next to each other.
On top of both of
these draw a square
of size 2 (=1+1).
COP1006
McManus
43

The number of clockwise spirals and the
number of counterclockwise spirals formed
by the seeds of certain varieties of flowers
COP1006
McManus
44
COP1006
McManus
45

Fibonacci Numbers
Each Fibonacci number is the sum of the two
preceding Fibonacci numbers.
 The Fibonacci series defined recursively:
Fibonacci(0)
Fibonacci(1)
Fibonacci(2)
Fibonacci(n)
=
=
=
=
0
1
1
Fibonacci(n-1) + Fibonacci(n - 2)
A Shortened Form:
Fib (1) = 1
Fib (2) = 1
Fib (n) = Fib (n - 1) + Fib (n - 2)
Fib(3) = Fib(2) + Fib(1) = 1 + 1 = 2
Fib(4) = Fib(3) + Fib(2) = 2 + 1 = 3
Fib(5) = Fib(4) + Fib(3) = 3 + 2 = 5
Fib(6) = Fib(5) + Fib(4) = 5 + 3 = 8
COP1006
McManus
46
Chapter 8
COP1006
McManus
47


Used for menu-driven programs and
event-driven programs
Menu
◦ A list of options that a program based on case
logic can perform

Event-driven
◦ Order is dictated by the user, not the
programmer, by which button is clicked on
COP1006
McManus
48

The Setup
List1.AddItem
List1.AddItem
List1.AddItem
List1.AddItem
“England”
“Germany”
“Spain”
“Italy”
‘adds items to a
‘Windows list box
VB Code
COP1006
McManus
49
Label3.Text = List1.Text
‘Sets the caption for the Label
‘above the output textbox
‘Next, the appropriate language phrase is displayed in
the textbox based on the Country selected.
VB Code
COP1006
McManus
50
Select Case List1.ListIndex
Case 0
Label4.Caption = “Hello, programmer”
Case 1
Label4.Caption = “Hallo, programmierer”
Case 2
Label4.Caption = “Hola, programador”
Case 3
Label4.Caption = “Ciao, programmatori”
End Select
VB Code
COP1006
McManus
51
Select Case Age
Case 16
LabelAge.Caption = “You can drive now! Parents Beware!”
Case 18
LabelAge.Caption = “You can vote now!”
Case 21
LabelAge.Caption = “You can drink wine with your meals.”
Case 65
LabelAge.Caption = “Time to retire and have fun!”
Case Else
LabelAge.Caption = “You’re a great age! Enjoy it!
End Select
COP1006
McManus
52
COP1006
McManus
53