Transcript 05-LoopingConstructs

Today’s Material
• Flowchart notation and loops
• Implementation of loops in C
– while loops
– do-while loops
– for loops
• Auxiliary Statements used inside the loops
– break
– continue
– goto
1
The Need For Loops
• Often you would need to repeatedly execute
some statements as long as a condition is true
• Consider computing “an“, where “a” is a real
number and “n” is an integer >= 0
– E.g., Compute 35
– 35 = 3*3*3*3*3
2
How to compute an?
• Keep a running power, initialized to 1
– power = 1 (a0=1)
• Multiply power with “a”, and count the number
of times we have multiplied “power” with “a”
– Initially count = 0
• When “count” reaches “n”, that is, when we have
multiplied “power” with “a” “n” times, we are
done
3
Algorithm for Computing an
1. Prompt the user and get “a” and “n”
2. Set count to 0
3. Set power to 1 /* power = a0 = 1 */
4. repeat while (count < n)
4.1. power = power * a;
4.2. count++;
/* power = acount now */
5. Print power
4
Flowchart for Computing an
Start
Prompt the user and
get “a” and “n”
count = 0
power = 1
count < n?
no
Print power
yes
power *= a;
count++;
End
5
C Looping Constructs
•
•
•
Clearly, we need to repeatedly execute steps
4.1 and 4.2 until “count” reaches “n”
That is, we need to loop around steps 4.1, 4.2
as long as a condition is true
C provides 3 looping constructs
–
–
–
while loops
do-while loops
for loops
6
while Statement
• The while loop keeps repeating an action until an
associated test returns false
• Useful when the programmer does not know in advance
how many times the loop will be iterated
• Syntax:
while(expression)
{
statement1;
statement2;
...
}
expression
N
Y
statement 1
statement 2
...
7
Code for Computing an
int count;
int n;
double a;
double power;
Start
Prompt the user and
get “a” and “n”
printf(“Enter a: “);
scanf(“%lf”, &a);
printf(“Enter n: “);
scanf(“%d”, &n);
count = 0
power = 1
count < n?
no
Print power
End
yes
power *= a;
count++;
count = 0;
power = 1; /* power = a0 */
while (count < n){
power *= a;
count++;
} /* end-while */
printf(“a^n: %lf\n”, power);
8
Trace of the Code for a = 3, n = 5
int count;
int n;
double a;
double power;
printf(“Enter a: “);
scanf(“%lf”, &a);
printf(“Enter n: “);
scanf(“%d”, &n);
count = 0;
power = 1;
while (count < n){
power *= a;
count++;
} /* end-while */
printf(“a^n: %lf\n”,
power);
a
3
n
5
Test: 0 < 5?  True
Test: 1 < 5?  True
Test: 2 < 5?  True
Test: 3 < 5?  True
Test: 4 < 5?  True
Test: 5 < 5?  False
count
0
power
1
3
2
9
3
27
4
81
5
243
1
9
Computing an: Alternative Code
int i;
int n;
double a;
double power;
printf(“Enter a: “);
scanf(“%lf”, &a);
printf(“Enter n: “);
scanf(“%d”, &n);
i = 0;
power = 1;
while (i < n){
power *= a;
i++;
} /* end-while */
printf(“a^n is: %lf\n”,
power);
int i;
int n;
double a;
double power;
printf(“Enter a: “);
scanf(“%lf”, &a);
printf(“Enter n: “);
scanf(“%d”, &n);
i = 0;
power = 1;
while (i++ < n)
power *= a;
printf(“a^n is: %lf\n”, power);
10
Computing 1+2+3+..+N
1. Prompt the user and get “n”
2. Set i to 1
/* Iteration variable */
3. Set sum to 0
/* Running sum */
4. repeat while (i <= n)
4.1. sum += i;
4.2. i++;
5. Print sum
11
Flowchart and Code for
Computing 1+2+3+..+N
Start
int i;
int n;
int sum = 0;
Prompt the user and
get “n”
i=1
printf(“Enter n: “);
scanf(“%d”, &n);
sum = 0
i <= n?
no
Print sum
yes
sum += i;
i++;
i = 1;
while (i<= n){
sum += i;
i++;
} /* end-while */
printf(“Sum is: %d\n”, sum);
End
12
Trace of the Code for n=5
n
5
int i;
int n;
int sum = 0;
Test: 1 <= 5?  True
printf(“Enter n: “);
scanf(“%d”, &n);
Test: 2 <= 5?  True
i = 1;
while (i<= n){
sum += i;
i++;
} /* end-while */
printf(“Sum is: %d\n”,
sum);
Test: 3 <= 5?  True
Test: 4 <= 5?  True
Test: 5 <= 5?  True
Test: 6 <= 5?  False
i
sum
1
0
2
1
3
3
4
6
5
10
6
15
13
Computing 1+2+3+..+N: Alternative Code
int i;
int n;
int sum = 0;
printf(“Enter n: “);
scanf(“%d”, &n);
i = 1;
while (i<= n){
sum += i;
i++;
} /* end-while */
int i;
int n;
int sum = 0;
printf(“Enter n: “);
scanf(“%d”, &n);
i = 1;
while (i<= n)
sum += i++;
printf(“Sum is: %d\n”, sum);
printf(“Sum is: %d\n”, sum);
14
Printing a Table of Squares
• We want to print a table of squares for
numbers 1, 2, 3, 4, .., n for some number “n”
• Here is how the table should look like for n = 6
+-----+-----+
| i | i*i |
+-----+-----+
|
1|
1|
|
2|
4|
|
3|
9|
|
4|
16|
|
5|
25|
|
6|
36|
+-----+-----+
15
Code for Printing a Table of Squares
int i;
int n;
Start
Prompt the user and
get and “n”
printf(“Enter n: “);
scanf(“%d”, &n);
Print the heading
printf(“+-----+-----+\n”);
printf(“| i | i*i |\n”);
printf(“+-----+-----+\n”);
i=1
i <= n?
no
Print bottom line
of the table
End
yes
print (i, i*i)
i++;
i = 1;
while (i <= n){
printf(“|%5d|%5d|\n”,
i, i*i);
i++;
} /* end-while */
printf(“+-----+-----+\n”);
16
Trace of the code for n=4
printf(“+-----+-----+\n”);
printf(“| i | i*i |\n”);
printf(“+-----+-----+\n”);
i = 1;
while (i <= n){
printf(“|%5d|%5d|\n”,
i, i*i);
i++;
} /* end-while */
printf(“+-----+-----+\n”);
+-----+-----+
| i | i*i |
+-----+-----+
|
1|
1|
|
2|
4|
|
3|
9|
|
4|
16|
+-----+-----+
n
4
Test: 1 <= 4?  True
Test: 2 <= 4?  True
Test: 3 <= 4?  True
Test: 4 <= 4?  True
i
1
2
3
4
5
Test: 5 <= 4?  False
17
Another while Example
int i = 0;
printf(“How do you like C programming?\n”);
while(i < 10){
printf(“Programming is fun!\n”);
i++;
} /* end-while */
• Repeats 10 times (for i from 0 to 9)
• Prints the same message 10 times
18
Yet Another while Example
int i = 20;
printf(“How do you like C programming?\n”);
while(i < 10){
printf(“Programming is fun!\n”);
i++;
} /* end-while */
• Repeats 0 times (i is 20, not less than 10)
• Does not print any "... is fun" messages.
19
do while Statement
• While loop tests the loop condition at the beginning
of the loop, before the first iteration begins
• Sometimes you want to test the loop condition at
the end of the loop. In such cases do-while loops
are used
– This ensures that the loop body is run at least once
• Syntax:
do
{
statement 1
statement1;
statement2;
...
} while(expression);
statement 2
...
expression
Y
N
20
Asking for a Password(1)
• Assume you want to repeatedly ask the user
for the password until the user enters the
password correctly
/* Implementation using while */
#define PASSWORD 123456
int passwd;
printf(“Enter the password: “);
scanf(“%d”, &passwd);
while (passwd != PASSWD){
printf(“Enter the password: “);
scanf(“%d”, &passwd);
} /* end-while */
printf(“Password is OK\n”);
• Clearly you want
to ask for the
password at
least once!
– Using a while
loop, we have to
repeat
printf/scanf
statements 21
Asking for a Password(2)
• Here is the same loop with do-while
#define PASSWORD
int passwd;
123456
do {
printf(“Enter the password: “);
scanf(“%d”, &passwd);
} while(passwd != PASSWD);
printf(“Password is OK\n”);
• This is cleaner compared to while loop
22
do while Example
• Asking for a positive integer
int no;
do {
printf(“Enter a positive integer: “);
scanf(“%d”, &no);
} while(no <= 0);
23
Another do while Example
char option = 'x';
do{
printf("Select an option: \n");
printf("(a) Calculate grades \n");
printf("(b) Calculate class average \n");
printf("(c) Print grades \n");
printf("(q) Quit \n");
option = getchar();
getchar(); /* Skip ‘\n’ */
if (option == 'a') ...
else if (option == 'b') ...
else if (option == 'c') ...
} while(option != ‘q’);
24
Another do while Example
int i = 0;
printf(“How do you like C programming?\n”);
do {
printf(“Programming is fun!\n”);
i++;
} while(i < 10);
• Repeats 10 times (for i from 0 to 9)
• Prints the same message 10 times
25
Yet Another do while Example
int i = 20;
printf(“How do you like C programming?\n”);
do {
printf(“Programming is fun!\n”);
i++;
} while(i < 10);
• Repeats once (for i == 20)
• Prints the same message once
26
What are the differences between
the while and the do while
statements?
while
do while
Entry control structure
Exit control structure
Loop may or may not be executed
Loop is executed at least once
27
for Statement
• More frequently used
• Ideal for loops that have a “counting” variable
– i.e., We need to loop a fixed number of times
• Is general enough to be used by other kinds of
loops as well
• Syntax:
for (initializing list; expression; altering list)
{
statement1;
statement2;
...
}
28
for Statement Flowchart, and Equivalent
while Statement
for(initialize; check; modify)
{
statement1;
statement2;
...
}
initialize;
while(check)
{
statement1;
statement2;
...
modify;
}
initialize
check
N
Y
statement 1
statement 2
...
modify
29
Another for Example
• Problem: Print numbers from 1 to 10
int count;
for(count = 1; count <= 10; count++){
printf("%d ",count);
} /* end-for */
printf("\n");
Printed output:
Start
count = 1
count <= 10
N
1 2 3 4 5 6 7 8 9 10
Y
Display
count
count++
End
30
Using for Statement
• For statement is usually the best choice for loops that
“count up” (increment a variable) or “count down”
(decrement a variable)
for (i=0; i<N; i++) …
• Counting up from 0 to N-1
for (i=1; i<=N; i++) …
• Counting up from 1 to N
for (i=N-1; i>=0; i--) …
• Counting down from N-1 to 0
for (i=N; i>=1; i--) …
• Counting down from N to 1
31
for Example: Compute an
power = 1;
for(i=1; i<=N; i++){
power *= a;
} /* end-for */
i=1
N
Display
power
n
5
Test: 1 <= 5?  True
Test: 2 <= 5?  True
Start
i <= N
a
3
Test: 3 <= 5?  True
Y
power *=a;
i++
Test: 4 <= 5?  True
Test: 5 <= 5?  True
End
Test: 6 <= 5?  False
i
1
power
2
3
3
9
4
27
5
81
6
243
1
32
Printing a Table of Squares
printf(“+-----+-----+\n”);
printf(“| i | i*i |\n”);
printf(“+-----+-----+\n”);
for (i=1; i <= n; i++){
printf(“|%5d|%5d|\n”, i, i*i);
} /* end-while */
printf(“+-----+-----+\n”);
+-----+-----+
| i | i*i |
+-----+-----+
|
1|
1|
|
2|
4|
|
3|
9|
|
4|
16|
|
5|
25|
|
6|
36|
+-----+-----+
Output for n=6
33
Another for Example
• Problem: Compute 1+2+3+4+…+N
sum = 0;
for(i=1; i<=N; i++){
sum += i;
}
• Initialize (i=1), check(i<=N) and modify(i++)
statements are all optional and can be omitted
sum=0;
i=1;
for(; i<=N; i++){
sum += i;
}
sum=0;
for(i=1; i<=N;){
sum += i++;
}
sum=0;
i=1;
for(; i<=N;){
sum += i++;
}
34
Nested Loops
•
It is possible to nest loops inside each other
–
•
Many applications require nesting of loops
Example: Print the multiplication table
+---+---+---+---+---+---+---+---+---+---+---+
| * | 1| 2| 3| 4| 5| 6| 7| 8| 9| 10|
+---+---+---+---+---+---+---+---+---+---+---+
| 1| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10|
| 2| 2| 4| 6| 8| 10| 12| 14| 16| 18| 20|
| 3| 3| 6| 9| 12| 15| 18| 21| 24| 27| 30|
| 4| 4| 8| 12| 16| 20| 24| 28| 32| 36| 40|
| 5| 5| 10| 15| 20| 25| 30| 35| 40| 45| 50|
+---+---+---+---+---+---+---+---+---+---+---+
35
Printing the Multiplication Table
int i, j;
/* Print the header */
printf(“+---+---+---+---+---+---+---+---+---+---+---+\n”);
printf(“| * |”);
for (j=1; j<=10; j++) printf(“%3d|”, j);
printf(“\n+---+---+---+---+---+---+---+---+---+---+---+\n”);
/* Print the table. i goes over the rows, j over the columns */
for (i=1; i <= 10; i++){
printf(“|%3d:|“, i);
/* Print 1 row of the table for i */
for (j=1; j <= 10; j++){
printf(“%3d|”, i*j);
} /* end-for-inner */
printf(“\n”);
} /* end-for-outer */
/* Print the bottom line of the table */
36
printf(“+---+---+---+---+---+---+---+---+---+---+---+\n”);
break & continue in loops
•
We have seen that “break” transfers the
control out of switch statements
•
Similarly, when used within loops, “break”
transfers the control out of the current loop
code block
37
Code for Computing the sum of a
series of numbers
int sum = 0;
int n;
while (1){ /* Infinite loop */
printf("Enter an int or -1 to stop: ");
scanf("%d", &n");
if (n == -1) break;
sum += n;
} /* end-while */
/* Get out of the loop */
printf("Sum is %d\n", sum);
38
Code for Checking if a number “n”
is prime or not
int d;
int n;
printf(“Enter an integer: “);
scanf(“%d”, &n);
for (d=2; d<n; d++){
if (n%d == 0) break;
} /* end-for */
if (d<n) printf(“n=%d is divisible by %d\n”, n, d);
else printf(“n=%d is prime\n”, n);
39
break (cont)
•
break is particularly useful if the escape
point is somewhere in the middle of the loop
rather than at the beginning or at the end
while (1){
printf(“Enter a number or 0 to stop: “);
scanf(“%d”, &n);
if (n == 0) break;
printf(“n=%d, n*n*n*=%d\n”, n, n*n*n);
} /* end-while */
40
break (cont)
•
break transfers the control out of the
innermost enclosing code block.
–
Thus when you have a nested loop, break only
escapes one level of nesting
while (…){
…
switch(…){
…
…
break; /* takes us out of switch to (A) */
…
}
(A)
}
(B)
41
continue
•
•
•
Transfers the control to the end of the loop
Note that we are still inside the loop
“continue” simply skips the rest of the statements in
the loop body, and moves the control to the end
int i;
int n = 0;
int sum = 0;
while (n<10){
scanf(“%d”, &i);
if (i == 0) continue; /* takes us to (B) */
n++; sum += i;
/*(B)*/
} /* end-while */
42
goto
•
Transfers the control to an arbitrary point in
the code designated by a label
–
–
goto is strictly discouraged as it leads to spaghetti
code, which is hard to understand and maintain
But it may be useful in certain situations
while (…){
…
switch(…){
…
…
goto loop_done; /* break won’t work here, as it takes */
…
/* us out of switch only */
} /* end-switch */
} /* end-while */
loop_done:
43
Infinite Loops
• A loop that iterates forever
while (1){
…
}
do{
…
} while (1);
for (;;;){
…
}
• How do we get out of these loops then?
– Simply have a “break” somewhere within the loop
while (1){
printf(“Enter a number or 0 to stop: “);
scanf(“%d”, &n);
if (n == 0) break;
printf(“n=%d, n*n*n*=%d\n”, n, n*n*n);
} /* end-while */
44
Comma Operator
•
Occasionally we may want to combine several
expressions together into a single statement
–
•
This is where we use the comma operator
Syntax
expr1, expr2, …, exprN;
•
•
•
•
expr1 is evaluated, its value discarded
expr2 is evaluated, its value discarded
…
exprN is evaluated, its value becomes the value of
the statement
45
Comma Operator Example (1)
i=1, j=2, k=i+j;
•
•
is equivalent to
((i=1), (j=2), (k=i+j));
Evaluation proceeds left to right
The result of the statement is k=i+j; which is 3
46
Comma Operator Example (2)
• Problem: Compute 1+2+3+4+…+N
sum=0;
for(i=1; i<=N; i++)
sum += i;
for(sum=0, i=1; i<=N; i++)
sum += i;
for(sum=0, i=1; i<=N; sum+=i, i++)
;
Empty statement: Loop body is empty
47