Lect#3_Loops
Download
Report
Transcript Lect#3_Loops
Control Structures II
Repetition
(Loops)
Why Is Repetition Needed?
How can you solve the following problem:
• What is the sum of all the numbers from 1 to
100.
• The answer will be
1 + 2 + 3 + 4 + 5 + 6 + … + 99 + 100.
Why Is Repetition Needed?
Here’s some sample Java code:
int sum=0;
sum = sum+1;
sum = sum +2;
sum = sum +3;
sum = sum +4;
…
sum = sum +99;
sum = sum +100;
System.out.println(“The sum from 1 to 100 = “
+sum);
Why Is Repetition Needed?
This solution has problems:
• It would take a long time to type in.
• There is a high risk of making an error while
typing it in.
• It doesn’t easily scale. This may work for 100
numbers but how would you handle having to
add from 1 to a 1000? Or to 1000000?Or to
1000000000?
Why Is Repetition Needed?
The Algorithm
1.
2.
3.
4.
5.
6.
7.
8.
9.
Create a variable to hold the sum.
Initialize the sum to zero.
Create a variable to hold a counter from 1 to 100.
Initialize the counter to 1.
While the counter is less-than-or-equal to 100
add the counter to the sum
add one to the counter
Now repeat
Print the sum
Why Is Repetition Needed?
We can use pseudo-code:
sum = 0
count = 1
loop while count <= 100
sum = sum + count
count++
endloop
print sum
Why Is Repetition Needed?
loop while condition
<body>
endloop
• This pseudo-code means: before executing the
statements in the body, evaluate the condition. If the
condition is true then execute the body once.
• Once you have executed the body statements once, go
back to the loop condition and re-evaluate it. If it is true,
execute the body code again. If the condition is not true
then the body will not be executed!
The while Looping (Repetition) Structure
• Infinite loop: is a loop that continues to execute
endlessly.
• So, expression is always true in an infinite loop.
• Statements must change value of expression to
false.
8
Example
i = 0
loop while (i <= 20)
print(i)
i = i + 5
end loop
0
Output
5
0
5
10
15
20
15
20
25
i = 0
i <= 20
i
10
start
Yes
Print i
i = i + 5
end
What will happen if you omit (i= i + 5) ?
No
While Loop Types
• Counter-Controlled Loop
• Sentinel-Controlled Loop
• Flag-Controlled Loop
Counter-Controlled Loop
• Used when exact number of data or entry pieces is
known.
• General form:
or
N=…
Read N
N = …
counter = 0
Loop while (counter < N)
.
.
.
counter = counter + 1
.
.
.
End loop
(1)
Initialization
stmt.
(2)
Loop condition
counter = 0
counter < N
Yes
do operation
counter = counter + 1
(3)
Update stmt.
No
Example
• Write a program to allow the user to enter a set
of integer numbers, then print the sum of these
numbers.
Start Program
Read setSize
counter = 0
sum = 0
Loop while (counter < setSize)
Read number
sum = sum + number
counter = counter + 1
End loop
Print sum
End Program
start
Start Program
Read setSize
counter = 0
sum = 0
Loop while (counter < setSize)
Read number
sum = sum + number
counter = counter + 1
End loop
Print Sum
End Program
setSize counter sum number
3
0
0
1
Output
1
1
10
2
11
4
3
1
10
4
15
3
15
Read setSize
counter = 0
sum = 0
counter <
setSize
Yes
Read number
sum = sum + number
counter = counter + 1
Print sum
end
No
Counter-Controlled Loop:
Another way
While loop
for expressing it N = …
counter = 0
Loop while (counter < N)
.
.
counter = counter + 1
End loop
For loop
N = …
For(counter = 1, counter <= N, counter = counter + 1)
.
.
Initialization
End For
Condition
counter = 1 to N
Increment \ Decrement
Step 1
Counter-Controlled Loop –For Loop
The for loop does not have a standard flowcharting method and you will find it done in
different ways.
N=…
or
Read N
Yes
do operation
counter = counter + 1
or
Read N
Can be
simplified
to:
counter = 1
counter
<= N
N=…
No
For counter = 1 to N,
step 1
do operation
Next counter
Example
1. Write down an algorithm and draw a flowchart
to find and print the largest of N (N can be any
number) positive numbers. Read numbers one
by one.
2. Verify your result by tracing the developed
algorithm. (Assume N to be 4 and the following
set to be the numbers {5 2 6 1})
start
Read N
max = 0
Solution
counter = 1
(1)
counter
<= N
Start Program
Read N
max = 0
For(counter = 1 to N, step 1)
Read number
if (number > max)
max = number
No
Yes
Read number
number >
max
Yes
End For
Print max
End Program
max = number
counter = counter + 1
end
Print max
No
start
(2) •
•
N
4
Trace the developed algorithm.
Assume N to be 4 and the following set
to be the numbers {5 2 6 1}
max counter
Read N
max = 0
number
counter = 1
0
1
5
5
2
2
counter
<= N
6
3
6
Yes
Read number
4
1
number >
max
Yes
5
max = number
Print max 6
counter = counter + 1
end
Print max
No
No
Sentinel-Controlled Loop
• Used when exact number of entry pieces is
unknown, but last entry (special/sentinel value) is
known.
• The idea of a sentinel controlled loop is that there is
a special value (the "sentinel") that is used to say when
the loop is done.
• General form:
Input the first data item into variable
Loop while (variable != sentinel)
.
.
.
input a data item into variable;
.
.
.
End loop
Example
• Write a program that adds up a list of positive
numbers entered by the user from the keyboard,
then prints the result.
• What is the number of iterations ??
▫ Unknown
• Since the input are positive integers, we can use
(-1) as the sentinel.
• Example of user input: 1 3 6 4 9 12 3 5 -1
Solution
Start Program
sum = 0
Read number
loop while (number != -1)
sum = sum + number
Read number
End loop
Print sum
End Program
sum
number
0
5
5
2
7
3
10
-1
start
sum = 0
Read number
number
!= -1
Yes
Input
5
2
3
-1
sum= sum+ number
Read number
Print sum
Print sum 10
end
No
Flag-Controlled Loop
• A flag is a boolean variable, used to indicate whether or
not a desired situation has occurred
▫ A value of FALSE indicates that the desired event has not
yet occurred
▫ TRUE indicates that it has occurred
• General form:
boolean found = false
Loop while (!found)
Initialization
Testing
.
.
if (expression)
found = true
.
.
End loop
Updating
Example: Number Guessing Game
• Write a program that generates a random number in the
range 0..100.
• Then the user tries to guess the number.
• If the user guessed the number correctly, then print the
message “You guessed the number correctly !”.
• Otherwise:
▫ If the guessed number is less than the random
number, print message “Your guess is lower than the
number”.
▫ Otherwise: print message “Your guess is higher than
the number”.
▫ The user enters another number.
• The user guesses until he\she enters the correct number.
Solution
Start Program
randomNumber = … will be discussed later
guessedRight = false
loop while (not guessedRight)
Read guess
if (guess = randomNumber)
guessedRight = true
Print “You guessed the number correctly !”
else
if (guess < randomNumber)
Print “Your guess is lower than the number”
else
Print “Your guess is higher than the number”
End loop
End Program
start
Solution
randomNumber = …
guessedRight = false
Yes
Read guess
Yes
guess =
randomNumber
Not
guessedRight
No
guessedRight = true
Print
“Correct Guess”
Yes
guess <
randomNumber
No
Print
“Guess is
Lower”
Print
“Guess is
Higher”
end
No
The do…while Loop
• Form:
do
statement(s)
while (expression)
• Statements are executed first and then
expression is evaluated.
• Statements are executed at least once and then
continued if expression is true.
Difference
while Loop
do…while
Loop
for Loop
Example
SECRET_CODE = 1234
do
Print "Type the secret code number to enter."
Read code
while (code!=SECRET_CODE)
Print "Well done,
you can now enter"
SECRET_CODE = 1234
Print input msg
Read code
code !=
SECRET_CODE
No
Print msg
Yes
Nested loop: loop in loop
Example:
Print the following using loops.
5 rows :
*
**
***
****
*****
Row 1 1 star
Row 2 2 stars
…
Row 5 5 stars
We need a loop for the rows
We need loops for columns
The number of stars in a row is equal to the row#
Need nested loop
Since the # of iterations are known for loops
Nested loop: loop in loop
Solution:
For (i = 1 to 5, step 1)
For (j = 1 to i, step 1)
print(" *")
End For
move cursor to next line
End For
Output:
*
**
***
****
*****
Chapter Summary
• Looping mechanisms:
▫ Counter-controlled while loop
for loop
▫ Sentinel-controlled while loop
▫ Flag-controlled while loop
▫ do…while loop
• Nested control structures