Transcript CSE / ENGR 142 Programming I

University of Washington
Computer Programming I
Lecture 9:
Iteration
© 2000 UW CSE
H1-1
Overview
Concepts this lecture
Iteration - repetitive execution
Loops and nested loops
while statements
for statements
H1-2
Chapter 5
Read Sections 5.1-5.6, 5.10
5.1 Introduction
5.2-5.3 While statement
5.4 For statement
5.5-5.6 Loop design
5.7 Nested Loops
5.11 Common errors
H1-3
An Old Friend:
Fahrenheit to Celsius
#include <stdio.h>
int main(void)
{
double fahrenheit, celsius;
printf("Enter a Fahrenheit temperature: ");
scanf("%lf", &fahrenheit);
celsius = (fahrenheit - 32.0) * 5.0 / 9.0;
printf("That equals %f degrees Celsius.",
celsius);
return 0;
}
H1-4
What’s “Wrong” with
Fahrenheit/Celsius Program?
User has to rerun the program for every
new temperature
Wouldn’t it be nice if the program
could process repeated requests?
Program ends immediately if user types a
bad input
Wouldn’t it be nice the program
politely asked the user again (and
again, etc. if necessary)?
H1-5
One More Type of Control Flow
Sometimes we want to repeat a block of code.
This is called a loop.
H1-6
Loops
A “loop” is a repeated (“iterated”) sequence of
statements
Like conditionals, loops (iteration) give us a huge
increase in the power of our programs
Alert: loops are harder to master than if statements
Even experienced programmers often make
subtle errors when writing loops
H1-7
Motivating Loops
Problem: add 4 numbers entered at the keyboard.
int sum;
int x1, x2, x3, x4;
printf(“Enter 4 numbers: ”);
scanf(“%d%d%d%d”, &x1, &x2, &x3, &x4);
sum = x1 + x2 + x3 + x4;
H1-8
Motivating Loops
Problem: add 4 numbers entered at the keyboard.
int sum;
int x1, x2, x3, x4;
printf(“Enter 4 numbers: ”);
scanf(“%d%d%d%d”, &x1, &x2, &x3, &x4);
sum = x1 + x2 + x3 + x4;
This works perfectly!
But... what if we had 14 numbers? or 40? or 4000?
H1-9
Finding Repeated Code
The key to using loops to solve a problem is to
discover steps that can be repeated
Our first algorithm for adding four numbers had no
repeated statements at all
But it does have some repetition buried in it.
Let’s rework the algorithm to make the repetition
more explicit
H1-10
Add 4 Numbers, Repetitively
int sum, x;
sum = 0;
printf(“Enter 4 numbers: “);
scanf(“%d”, &x);
sum = sum + x;
scanf(“%d”, &x);
sum = sum + x;
scanf(“%d”, &x);
sum = sum + x;
scanf(“%d”, &x);
sum = sum + x;
H1-11
Loop to Add 4 Numbers
int sum, x;
sum = 0;
printf(“Enter 4 numbers:”);
int sum, x;
int count;
scanf(“%d”, &x);
sum = sum + x;
sum = 0;
printf(“Enter 4 numbers:”);
scanf(“%d”, &x);
sum = sum + x;
count = 1;
while (count <= 4) {
scanf(“%d”, &x);
sum = sum + x;
count = count + 1;
}
scanf(“%d”, &x);
sum = sum + x;
scanf(“%d”, &x);
sum = sum + x;
H1-12
More General Solution
int sum, x, count;
int number_inputs;
/* Number of inputs */
sum = 0;
printf(“How many numbers? “);
scanf(“%d”, &number_inputs);
printf(“Enter %d numbers: “, number_inputs);
count = 1;
while ( count <= number_inputs ) {
scanf(“%d”, &x);
sum = sum + x;
count = count + 1;
}
H1-13
while Statement Syntax
Loop
condition
while ( condition ) {
statement1;
Loop body:
Any statement,
statement2;
or a compound
statement
...
}
H1-14
Compute 7!
What is 1 * 2 * 3 * 4 * 5 * 6 * 7? (“seven factorial”)
x = 1 * 2 * 3 * 4 * 5 * 6 * 7;
printf ( “%d”, x ) ;
H1-15
Compute 7!
What is 1 * 2 * 3 * 4 * 5 * 6 * 7? (“seven factorial”)
x = 1 * 2 * 3 * 4 * 5 * 6 * 7;
printf ( “%d”, x ) ;
Bite size pieces:
More Regular:
As a loop:
x = 1;
x = 1;
x = 1;
x = x * 2;
x = x * i; i = i + 1;
i = 2;
x = x * 3;
x = x * i; i = i + 1;
while ( i <= 7 ) {
x = x * 4;
x = x * i; i = i + 1;
x = x * i;
x = x * 5;
x = x * i; i = i + 1;
i = i + 1;
x = x * 6;
x = x * i; i = i + 1;
x = x * 7;
x = x * i; i = i + 1;
i = 2;
}
H1-16
while Loop Control Flow
x=1;
i=2;
i <= 7 ?
yes
x=x*i;
i=i+1;
no
H1-17
Tracing the Loop
/* What is 1 * 2 * 3 * ...*7 */
line i
x
x=1;
i=2;
while ( i <= 7 ) {
x=x*i;
i=i+1;
}
printf ( “%d”, x ) ;
A
1
/* A */
/* B */
/* C */
/* D */
/* E */
/* F */
/* G */
?
H1-19
Tracing the Loop
/* What is 1 * 2 * 3 * ...*7 */
line i
x
x=1;
i=2;
while ( i <= 7 ) {
x=x*i;
i=i+1;
}
printf ( “%d”, x ) ;
A
B
1
1
/* A */
/* B */
/* C */
/* D */
/* E */
/* F */
/* G */
?
2
H1-20
Tracing the Loop
/* What is 1 * 2 * 3 * ...*7 */
line i
x
i7?
x=1;
i=2;
while ( i <= 7 ) {
x=x*i;
i=i+1;
}
printf ( “%d”, x ) ;
A
B
C
1
1
1
T
/* A */
/* B */
/* C */
/* D */
/* E */
/* F */
/* G */
?
2
2
H1-21
Tracing the Loop
/* What is 1 * 2 * 3 * ...*7 */
line i
x
i7?
x=1;
i=2;
while ( i <= 7 ) {
x=x*i;
i=i+1;
}
printf ( “%d”, x ) ;
A
B
C
D
E
1
1
1
2
2
T
/* A */
/* B */
/* C */
/* D */
/* E */
/* F */
/* G */
?
2
2
2
3
H1-22
Tracing the Loop
/* What is 1 * 2 * 3 * ...*7 */
line i
x
i7?
x=1;
i=2;
while ( i <= 7 ) {
x=x*i;
i=i+1;
}
printf ( “%d”, x ) ;
A
B
C
D
E
C
1
1
1
2
2
2
T
/* A */
/* B */
/* C */
/* D */
/* E */
/* F */
/* G */
?
2
2
2
3
3
T
H1-23
Tracing the Loop
/* What is 1 * 2 * 3 * ...*7 */
line i
x=1;
i=2;
while ( i <= 7 ) {
x=x*i;
i=i+1;
}
printf ( “%d”, x ) ;
A
?
1
B
2
1
C
2
1
D
2
2
E
3
2
C
3
2
......................
C
7 720
D
7 5040
E
8 5040
/* A */
/* B */
/* C */
/* D */
/* E */
/* F */
/* G */
x
i7?
T
T
T
H1-24
Tracing the Loop
/* What is 1 * 2 * 3 * ...*7 */
line i
x=1;
i=2;
while ( i <= 7 ) {
x=x*i;
i=i+1;
}
printf ( “%d”, x ) ;
A
?
1
B
2
1
C
2
1
D
2
2
E
3
2
C
3
2
......................
C
7 720
D
7 5040
E
8 5040
C
8 5040
/* A */
/* B */
/* C */
/* D */
/* E */
/* F */
/* G */
x
i7?
T
T
T
F
H1-25
Tracing the Loop
/* What is 1 * 2 * 3 * ...*7 */
line i
x=1;
i=2;
while ( i <= 7 ) {
x=x*i;
i=i+1;
}
printf ( “%d”, x ) ;
A
?
1
B
2
1
C
2
1
T
D
2
2
E
3
2
C
3
2
T
......................
C
7 720
T
D
7 5040
E
8 5040
C
8 5040
F
G
(Print 5040)
/* A */
/* B */
/* C */
/* D */
/* E */
/* F */
/* G */
x
i7?
H1-26
Double Your Money
/* Suppose your $1,000 is earning interest at 5%
per year. How many years until you double your
money? */
H1-27
Double Your Money
/* Suppose your $1,000 is earning interest at 5%
per year. How many years until you double your
money? */
my_money = 1000.0;
n = 0;
while ( my_money < 2000.0 ) {
my_money = my_money *1.05;
n = n + 1;
}
printf( “My money will double in %d years.”, n);H1-28
Average Inputs
printf ( “Enter values to average, end with -1.0 \n”) ;
sum = 0.0 ;
count = 0 ;
sentinel
scanf ( “%lf”, &next ) ;
while ( next != -1.0 ) {
sum = sum + next ;
count = count + 1;
scanf ( “%lf”, &next ) ;
}
if (count > 0)
printf( “The average is %f. \n”,
H1-29
sum / (double) count );
Printing a 2-D Figure
How would you print the following diagram?
    
    
    
repeat 3 times
print a row of 5 stars
repeat 5 times
print

It seems as if a loop within a loop is needed.
H1-30
Nested Loop
#define ROWS
3
#define COLS
…
5
row = 1;
while ( row <= ROWS ) {
/* print a row of 5 *’s */
…
row = row + 1;
}
H1-31
Nested Loop
row = 1;
while ( row <= ROWS ) {
/* print a row of 5 *’s */
col = 1;
while (col <= COLS) {
printf(“*”);
outer
loop:
print 3
rows
col = col + 1;
}
printf( “\n” );
inner
loop:
print
one
row
H1-32
row = row + 1;
}
Trace
row: 1
col:
2
3
1 2 34 5 6 1 2 34 5 6
output: * * * * *
*****
*****
4
1 2 34 5 6
row = 1;
while ( row <= ROWS ) {
/* print a row of 5 *’s */
col = 1;
while (col <= COLS) {
printf(“*”);
col = col + 1;
}
H1-33
printf( “\n” );
row = row + 1;
}
Print a Multiplication Table
1
2
3
1
2
3
1
1
2
3
1 1*1
1*2 1*3
2
2
4
6
2 2*1
2*2 2*3
3
3
6
9
3 3*1
3*2 3*3
4
4
8
12
4 4*1
4*2 4*3
H1-34
1
2
3
1
1
2
3
2
2
4
6
3
3
6
9
4
4
8
12
Print Row 2
col = 1;
while (col <= 3) {
printf(“%4d”, 2 * col );
col = col + 1;
}
printf(“\n”);
row number
H1-35
Nested Loops
Print 4 rows
row = 1;
Print one row
while (row <= 4) {
col = 1;
while (col <= 3) {
printf(“%4d”, row * col );
col = col + 1;
}
printf(“\n”);
row = row + 1;
}
H1-36
Loop Trace
row col
1 1 print 1
2 print 2
3 print 3
print \n
2 1 print 2
2 print 4
3 print 6
print \n
row col
3
1 print 3
2 print 6
3 print 9
print \n
4
1 print 4
2 print 8
3 print 12
print \n
H1-37
Notes About Loop Conditions
They offer all the same possibilities as
conditions in if-statements
Can use &&, ||, !
Condition is reevaluated each time through
the loop
A common loop condition: checking the
number of times through the loop
H1-38
Counting Loops
A common loop condition: checking the
number of times through the loop
Requires keeping a “counter”
This pattern occurs so often there is a
separate statement type based on it: the
for-statement
H1-39
A for Loop
/* What is 1 * 2 * 3 * ... * n ? */
x=1;
i=2;
while ( i <= n ) {
x=x*i;
i = i+1;
}
printf ( “%d”, x ) ;
x=1;
for ( i = 2 ; i <= n ; i = i+1 ) {
x=x*i;
}
printf ( “%d”, x) ;
H1-40
for Statement Syntax
for ( initialization;
condition;
update expression) {
statement1;
statement2;
...
}
H1-41
for Loop Control Flow
Initialization
Condition yes
no
For Loop Body
Update Expression
H1-42
for Loops vs while Loops
Any for loop can be written as a while loop
These two loops mean exactly the same thing:
for (initialization; condition; update)
statement;
initialization;
while (condition) {
statement;
update;
}
H1-43
Counting in for Loops
/* Print n asterisks */
for ( count = 1 ; count <= n ; count = count + 1 ) {
printf ( “*” ) ;
}
/* Different style of counting */
for ( count = 0 ; count < n ; count = count + 1 ) {
printf ( “*” );
}
H1-44
“3 Rows of 5” as a Nested for Loop
#define ROWS
3
#define COLS
5
...
inner
loop:
print
one
row
for ( row = 1; row <= ROWS ; row = row + 1 ) {
for ( col = 1 ; col <= COLS ; col = col + 1 ) {
outer
loop:
print 3
rows
printf( “” );
}
printf( “\n” );
}
H1-45
Yet Another 2-D Figure
How would you print the following diagram?






 
  
   
For every row ( row = 1, 2, 3, 4, 5 )
Print row stars
H1-46
Solution: Another Nested Loop
#define ROWS 5
...
int row, col ;
for ( row = 1 ; row <= ROWS ; row = row + 1 ) {
for ( col = 1 ; col <= row ; col = col + 1) {
printf( “” ) ;
}
printf( “\n” );
}
H1-47
Yet One More 2-D Figure
How would you print the following diagram?
    
   
  
 

For every row ( row = 0, 1, 2, 3, 4)
H1-48
Print row spaces followed by (5 - row) stars
Yet Another Nested Loop
#define ROWS 5
...
int row, col ;
for ( row = 0 ; row < ROWS ; row = row + 1 ) {
for ( col = 1 ; col <= row ; col = col + 1)
printf( “ ” ) ;
for ( col = 1 ; col <= ROWS – row ; col = col + 1)
printf( “” ) ;
printf( “\n” );
}
H1-49
Some Loop Pitfalls
while ( sum < 10 ) ;
sum = sum + 2;
for ( i = 0; i <= 10; i = i + 1);
sum = sum + i ;
for ( i = 1; i != 10 ; i = i + 2 )
sum = sum + i ;
H1-50
Double Danger
double x ;
for ( x = 0.0 ; x < 10.0 ; x = x + 0.2 )
printf(“%.18f”, x) ;
Seems harmless...
H1-51
Double Danger
What you expect:
0.000000000000000000
0.200000000000000000
0.400000000000000000
...
9.000000000000000000
9.200000000000000000
9.400000000000000000
9.600000000000000000
9.800000000000000000
What you might get:
0.000000000000000000
0.200000000000000000
0.400000000000000000
...
8.999999999999999997
9.199999999999999996
9.399999999999999996
9.599999999999999996
9.799999999999999996
H1-52
9.999999999999999996
Use ints as Loop Counters
int i ;
double x ;
for ( i = 0 ; i < 50 ; i = i + 1 )
{
x = (double) i / 5.0 ;
printf(“%.18f”, x) ;
}
H1-53
Counting in Loops
Counting up by one or down by one:
for ( i = 1 ; i <= limit ; i = i+1 ) { . . . }
times_to_go = limit;
while ( times_to_go > 0 ) {
•••
times_to_go = times_to_go - 1;
}
H1-54
Counting Up or Down by 1
This pattern is so common there is special
jargon and notation for it
To "increment:" increase (often by 1)
To "decrement:" decrease (often by 1)
C operators:
Post-increment ( x++ ): add 1
Post-decrement ( x-- ): subtract 1
H1-55
Handy Shorthand x++
x--
Used by itself,
x++ means the same as x = x+1
x-- means the same as x = x-1
Very often used with loop counters:
for ( i=1 ; i <= limit ; i++ ) { . . . }
times_to_go = limit;
while ( times_to_go > 0 ) {
...
times_to_go--
H1-56
...
Iteration Summary
General pattern:
Initialize, test, do stuff, repeat . . .
“while” and "for" are equally general in C
Use “for” when initialize/test/update are
closely related and simple, especially
when counting
H1-58
Looking Ahead
We’ll talk more about how to design loops
We’ll discuss complex conditional
expressions
Can be used with loops as well as in
conditional statements
We’ll see “arrays”, a powerful new way of
organizing data
Very often used with loops
H1-59