Transcript 08 Deterministic iteration

08 Deterministic iteration
CE00858-1:
Fundamental Programming Techniques
March 16
08 Deterministic iteration
1
Objectives
In this session, we will:
•
•
•
•
March 16
introduce repetition using a for loop
analyse problems involving repetition
consider loops within loops
implement solutions to problems involving both repetition
and selection
08 Deterministic iteration
2
Control structures
• any program only uses:
• sequence
• selection
• repetition
• so far only written programs using simple sequences
• each statement performed in order
• and selections
• different statements are performed dependent on some
condition
March 16
08 Deterministic iteration
3
Iteration
• doing the same actions repeatedly
loop condition
while there is more shopping in the basket, put an item on
the conveyor belt
action
• two types of iteration:
• deterministic – know before hand how many times to repeat
• non-deterministic – don’t know how many times to repeat
March 16
08 Deterministic iteration
4
Analysis of iteration
• when faced with a new specification we need to decide whether
actions are performed more than once
• if they are, there will normally be an iteration in the program
• if a program has an iteration in it, need to consider:
•
•
•
•
•
what data is used
what operations are done once before the loop?
how many times is loop repeated?
what operations are repeated inside the loop?
what operations are done once after the loop?
• to decide on how many times the loop is executed, need to
consider
• when the loop starts
• when the loop finishes
March 16
05 Simple selection
5
Deterministic iteration
• repeating a known number of times
dealing a hand of 7 cards to two players:
repeat 7 times
deal card to player 1
deal card to player 2
• also used to count number of repetitions
singing 10 green bottles
repeat 10 times from 10 down to 1
sing 1 verse
March 16
08 Deterministic iteration
6
For statement in Java
for (initial statement; condition; increment)
{
done just before end
of each repetition
statement;
}
done once before
loop starts
tested before starting
each repetition of loop:
if true, enter loop
if false, exit loop
braces are needed to block
more than one statement
March 16
08 Deterministic iteration
7
For loop example – Sum
• problem:
• input 10 integers
• calculate the sum and output it
March 16
08 Deterministic iteration
8
Sum analysis
• what data is used?
• num: integer input by user
• sum: integer total calculated in program
• what operations are performed?
• iteration needed to add up several numbers
• what operations are done once before the loop?
• create Scanner
• prompt user for number
• initialise sum to 0
• how many times is loop repeated?
• loop repeated 10 times
• what operations are repeated inside the loop?
• input num
• add num to sum
• what operations are done once after the loop?
• output sum
March 16
08 Deterministic iteration
9
Sum code
Sum.java
//calculate and output sum of 10 integers
Scanner myKeyboard = new Scanner(System.in);
System.out.print("Enter 10 integers: ");
int sum = 0;
loop repeated 10
int num;
times
//sum numbers entered by user
for (int i = 0; i < 10; i++)
{
num = myKeyboard.nextInt();
sum = sum + num;
}
could also put:
for (int i = 1; i <= 10; i++)
statements repeated
inside loop
System.out.println("Sum is: " + sum);
March 16
08 Deterministic iteration
10
Sum loop explanation
• initially i is set to 0
• as i is less than 10, the loop is entered
• the statements within the loop are executed
• the next number is entered
• the number is added to sum
• the value of i is incremented to 1 (i++)
• i is now 1 which is still less than 0, the loop is
entered
• this continues until i is not less than 10 when the test
will be false
• the loop terminates
March 16
08 Deterministic iteration
11
Using counter example – Squares
• the variable declared in the for statement can be
used within the loop
• problem:
• to output the squares of numbers from 1 to 10
March 16
08 Deterministic iteration
12
Squares analysis
• what data is used?
• i: integer counter to control number of repetitions, used inside loop
• what operations are performed?
• iteration needed to calculate square of several numbers
• what operations are done once before the loop?
• none
• how many times is loop repeated?
• loop repeated 10 times, i = 1 to 10
• what operations are repeated inside the loop?
• square = i * i
• output square
• what operations are done once after the loop?
• none
March 16
08 Deterministic iteration
13
Squares code
Squares.java
//calculate and output squares
for (int i = 1; i <= 10; ++i )
{
System.out.println ( i + " squared is " + (i * i));
}
March 16
08 Deterministic iteration
14
Count back example – CountDown
• the loop counter can start and end at any value
• problem:
• count down from a number entered by the user
• when count down finished, "Lift off" should be output
March 16
08 Deterministic iteration
15
CountDown analysis
• what data is used?
• start: positive integer input by user
• count: integer counter to control number of repetitions, used inside
loop
• what operations are performed?
• iteration needed to count down from starting value
• what operations are done once before the loop?
• create Scanner
• prompt user for start
• input start
• how many times is loop repeated?
• loop repeated start times, count = start down to 0
• what operations are repeated inside the loop?
• output count
• what operations are done after the loop?
• output "Lift off"
March 16
08 Deterministic iteration
16
CountDown code
CountDown.java
//count down for lift off
Scanner myKeyboard = new Scanner(System.in);
System.out.print("Enter start value for count down: ");
int start = myKeyboard.nextInt();
//count back from starting point
for (int count = start; count >= 0; count --)
{
System.out.println(count);
}
//lift off
System.out.println("Lift off!");
March 16
08 Deterministic iteration
17
Common mistake 1
for (i = 0; i <= 10; i++)
System.out.print("i is: ");
System.out.println(i);
• problem...
March 16
08 Deterministic iteration
18
Common mistake 2
for (i = 0; i <= 10; i++);
{
System.out.print("i is: ");
System.out.println(i);
}
• problem...
March 16
08 Deterministic iteration
19
Common mistake 3
for (i = 0; i >= 10; i++)
{
System.out.print("i is: ");
System.out.println(i);
}
• problem...
March 16
08 Deterministic iteration
20
Common mistake 4
for (i = 0; i >= 10; i--)
{
System.out.print("i is: ");
System.out.println(i);
}
• problem...
March 16
08 Deterministic iteration
21
Nested loops example – BlockOfFlats
• iteration within an iteration
• inner loop completed each time outer loop executes
• problem:
• output address of each flat in a block:
• four floors, each containing 3 flats
• output as a table
March 16
08 Deterministic iteration
22
BlockOfFlats analysis
• what data is used?
• floor: integer counter to count 4 floors, used inside loop
• flat: integer counter to count 3 flats, used inside loop
• what operations are performed?
• iteration needed as there are 4 floors
• nested iteration needed as there are 3 flats on each floor
• what operations are done once before loop to process floors?
• none
• how many times is loop to process floors repeated?
• loop repeated 4 times, floor = 4 down to 1 as we deal with top
floor first
• what operations are repeated inside loop to process floors?
• process flats on floor – needs to be expanded
• output newline
• what operations are done once after loop to process floors?
• none
March 16
08 Deterministic iteration
23
• process flats on floor analysis:
• how many times is loop to process flats repeated?
• loop repeated 3 times, flat = 1 to 3
• what operations are repeated inside loop to process flats?
• output floor and flat number
March 16
08 Deterministic iteration
24
BlockOfFlats
BlockOfFlats.java
//process floors
for (int floor = 4; floor >= 1; floor--)
{
//process flats on floor
for (int flat = 1; flat <= 3; flat++)
{
System.out.println("Floor: " + floor + ", flat: " + flat);
}
System.out.println();
}
March 16
08 Deterministic iteration
25
Sequence of loops example – Triangle
• problem:
• output triangle of stars:
****
***
**
*
March 16
08 Deterministic iteration
26
Triangle analysis
Row
Pattern
Spaces
Stars
1
****
0
4
2
-***
1
3
3
--**
2
2
4
---*
3
1
row – 1
5 - row
General case:
March 16
08 Deterministic iteration
27
Triangle analysis continued
•
what data is used?
•
what operations are performed?
•
what operations are done once before row loop?
•
how many times is row loop repeated?
•
what operations are repeated inside row loop?
•
• row: integer loop counter to count 4 rows, used inside loop
• space: integer loop counter to count number of spaces on row, used inside loop
• star: integer loop counter to count number of stars on row, used inside loop
• iteration needed as there are 4 rows
• nested iteration as there are several spaces on each row
• followed by second nested iteration as there are several stars on each row
• none
• loop repeated 4 times, row = 1 to 4
• process spaces on row – needs to be expanded
• process stars on row – needs to be expanded
• output newline
what operations are done once after row loop?
• none
March 16
08 Deterministic iteration
28
• process spaces on row analysis:
• how many times is spaces loop repeated?
• loop repeated row – 1 times, space = 1 to row - 1
• what operations are done inside spaces loop?
• output single space
• process stars on row analysis:
• how many times is stars loop repeated?
• loop repeated 5 – row times, star = 1 to 5 - row
• what operations are done inside the stars loop?
• output single star
March 16
08 Deterministic iteration
29
Triangle code
Triangle.java
//process rows
for (int row = 1; row <= 4; row++)
{
//process spaces on row
for (int space = 1; space <= row - 1; space++)
{
System.out.print(" ");
}
//process stars on row
for (int star = 1; star <= 5 - row; star++)
{
System.out.print("*");
}
System.out.println();
}
March 16
08 Deterministic iteration
30
Selection in iteration example - Smallest
• can also perform tests within iteration
• problem:
• read in 10 integers
• output smallest number read in
March 16
08 Deterministic iteration
31
Smallest analysis
•
what data is used?
•
what operations are performed?
•
what operations are done once before loop?
•
how many times is loop repeated?
•
what operations are repeated inside the loop?
•
• num: integer input by user
• smallest: integer to hold smallest value, determined in program
• iteration needed to find smallest of 10 integers input
• nested selection needed as smallest number needs to be stored
• create Scanner
• prompt user for input
• read first number and store in smallest
• 9 times as first integer read outside loop, i = 1 to 9
• read number
• check if smallest number – needs to be expanded
what operations are done once after the loop?
• output smallest
March 16
08 Deterministic iteration
32
• check if smallest number:
• what operations are done if num less than smallest?
• store num in smallest
• what operations are done if num not less than smallest?
• none
March 16
08 Deterministic iteration
33
Smallest.java
Smallest code
//output smallest number in a list of 10
Scanner myKeyboard = new Scanner(System.in);
System.out.println("Enter 10 integers: ");
int smallest = myKeyboard.nextInt();
for (int i = 1; i < 10; i++)
{
int num = myKeyboard.nextInt();
if (num < smallest)
{
smallest = num;
}
}
//output smallest
System.out.println("Smallest number: " + smallest);
March 16
08 Deterministic iteration
34
Summary
In this session we have:
• covered the for loop and how it is used when the number of
repetitions is known in advance
• analysed problems involving deterministic iteration
• implemented the for loop
• seen how loops can contain nested loops and other control
structures
In the next session we will:
• consider non-deterministic iteration
March 16
08 Deterministic iteration
35