Transcript comp104 notes

Programming
Loops (continued)
COMP104 Lecture 9 / Slide 2
The for Statement


Syntax
for (ForInit; ForExpression; PostExpression)
Action
How it works:


Execute ForInit statement
While ForExpression is true
– Execute Action
– Execute PostExpression

Example
int i;
for(i=1; i<=20; i++)
cout << "i is " << i << endl;
COMP104 Lecture 9 / Slide 3
Iteration Using
the for Statement
ForInit
ForExpression
true
Action
PostExpression
false
COMP104 Lecture 9 / Slide 4
N! (for)
int number, factorial, n;
cout << "Enter number: ";
cin >> number;
factorial = 1;
for(n=1; n<=number; n++)
factorial *= n;
cout << "The factorial of " << number
<< " is " << factorial << endl;
COMP104 Lecture 9 / Slide 5
2N (for)
int number, result, n;
cout << "Enter number: ";
cin >> number;
result = 1;
for(n=1; n<=number; n++)
result *= 2;
cout << "Two raised to the " << number
<< " power is " << result << endl;
COMP104 Lecture 9 / Slide 6
Iteration
 Key
Points
 [stopping
criterion] Make sure there is
a statement that will eventually stop
the loop
 [initialization]Make sure to initialize
loop counters correctly
 [side effect] Loop counters should not
be modified in the loop
COMP104 Lecture 9 / Slide 7
The Lazy Student Problem




Four students working together on HW1
Problem will take 200 hours of work that can be done
over the next few weeks
The laziest student convinces the other three students
to draw straws
Each straw is marked with an amount


The amount represents both the number of days and the
numbers of hours per day that the student would work
Example
– If the straw was marked three then the student who drew it
would work for three hours per day for three days

What are the best markings of the straws for a clever,
lazy student?
COMP104 Lecture 9 / Slide 8
Observations

Need to find sets of numbers a, b, c, and d such that




a2 + b2 + c2 + d2 = 200
Maximal legal number is 14 as 152 equals 225
which is greater than 200
Minimal legal number is 1
No advantage to listing the combinations more than
once

Implication
– Generate the solutions systematically

We will make sure that a <= b <= c <= d
COMP104 Lecture 9 / Slide 9
Method

Generate all possibilities for a where for each
a possibility

Generate all possibilities of b where for each b
possibility
– Generate all possibilities for c where for each c possibility
 Generate all possibilities for d where for each d
possibility
 Determine whether the current combination is a
solution
COMP104 Lecture 9 / Slide 10
Nested For Loop Solution
int a, b, c, d;
for(a=1; a<=14; a++) {
for(b=a; b<=14; b++) {
for(c=b; c<=14; c++) {
for(d=c; d<=14; d++) {
if(a*a + b*b + c*c + d*d == 200)
cout << a << " " << b << " " << c
<< " " << d << endl;
}
}
}
}
COMP104 Lecture 9 / Slide 11
The Do-While Statement


Syntax
do Action
while (Expression)
How it works:




Execute Action
if Expression is true then
execute Action again
Repeat this process until
Expression evaluates to
false
Action is either a single
statement or a group of
statements within braces
Action
true
Expression
false
COMP104 Lecture 9 / Slide 12
N! (do-while)
int number, factorial, n;
cout << "Enter number: ";
cin >> number;
factorial = 1;
n = 1;
do{
factorial *= n;
n++;
}while(n <= number);
cout << "The factorial of " << number
<< " is " << factorial << endl;
COMP104 Lecture 9 / Slide 13
2N (do-while)
int number, result, n;
cout << "Enter number: ";
cin >> number;
result = 1;
n = 1;
do{
result *= 2;
n++;
}while (n <= number);
cout << "Two raised to the " << number
<< " power is " << result << endl;
COMP104 Lecture 9 / Slide 14
Maximum (do-while)
int value;
int max=0;
//input value
//maximum value
do{
cout << "Enter a value (-1 to stop): ";
cin >> value;
if(value > max)
max = value;
}while(value!=-1);
cout << "The maximum value found is "
<< " is " << max << endl;
COMP104 Lecture 9 / Slide 15
Waiting for a Reply
char reply;
do{
cout << "Continue(y/n): ";
cin >> reply;
//do something
}while(reply!='n');
COMP104 Lecture 9 / Slide 16
Which Loop to Use?

For loop


While loop




Best for calculations that are repeated a fixed number of
times using a value that is changed by an equal amount
(usually 1) each time through the loop.
You want to repeat a segment of code without knowing
exactly how many times it will be repeated.
You are working with user input
There are situations when the code segment should not be
executed at all.
Do-while loop


The code segment should always be executed at least once.
Otherwise, the situations when do-while loops are used are
very similar to those when while loops are used.
COMP104 Lecture 9 / Slide 17
A simpler lazy student problem














three straws: a, b, c
minimum value = 1
maximum value = 3
a <= b <= c
1
1
1
1
1
1
2
2
2
3
1
1
1
2
2
3
2
2
3
3
1
2
3
2
3
3
2
3
3
3
for (a=1; a<=3; a++)
for (b=a; b<=3; b++)
for (c=b; b<=3; c++)
cout << a << b << c << endl;
COMP104 Lecture 9 / Slide 18
How to Stop a Loop

Known number of iterations before the loop
stops (for)

Test for a user-controlled condition before
or after each iteration (while, do-while)

Use the break command.
COMP104 Lecture 9 / Slide 19
break

The break command is the same as the
one used previously in switch.

break leaves the current loop immediately.
It is recommended that break be used for
situations where the loop needs to be
terminated immediately (e.g., due to user
intervention or if a fatal error occurs).
COMP104 Lecture 9 / Slide 20
Maximum (while with break)
int value=0;
int max=0;
while(true){
//input value
//maximum value
cout << "Enter a value (-1 to stop): ";
cin >> value;
if(value > max)
max = value;
if(value==-1)
break;
}
cout << "The maximum value found is "
<< " is " << max << endl;
COMP104 Lecture 9 / Slide 21
Common Loop Errors
while(balance != 0.0);
{
balance = balance - amount;
}

This will lead to an infinite loop!
for(n=1; n<=count; n++);
{
cout << "hello" << endl;
}

"hello" only printed once!
COMP104 Lecture 9 / Slide 22
Common Loop Errors
(with correct indentation and curly braces)
while(balance != 0.0) {
;
// do nothing infinitely !!
}
balance = balance - amount;

This will lead to an infinite loop!
for(n=1; n<=count; n++) {
;
// do nothing n times!!
}
cout << "hello" << endl;

"hello" only printed once!
COMP104 Lecture 9 / Slide 23
Common Loop Errors
while(balance != 0.0){
balance = balance - amount;
}

balance may not become equal zero due to numerical
inaccuracies
int power;
while(power <= 1000){
cout << "Next power of N is " << power << endl;
power *= n;
}


Be sure to initialize to 0 a variable used for sums
Be sure to initialize to 1 a variable used for products
COMP104 Lecture 9 / Slide 24
Nested Loops

Nested loops are loops within loops. They are
similar in principle to nested if and if-else
statements.

Many applications require nested loops.
COMP104 Lecture 9 / Slide 25
Nested Loops
// Find the average score on 8 lab assignments
int n, lastlab=8;
double avg, score, tscore;
char resp;
do{
tscore = 0;
for(n=1; n<=lastlab; n++){
cout << "Enter student’s score for lab " << n << ": ";
cin >> score;
tscore += score;
}
avg = tscore/double(lastlab);
cout << "The average score is " << avg << endl;
cout << "Enter another student (y/n)? ";
cin >> resp;
}while(resp=='y' || resp=='Y');
COMP104 Lecture 9 / Slide 26
Diamond Pattern

Print out the following diamond pattern
*
* *
* * *
* *
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
* *
* * *
* *
*
COMP104 Lecture 9 / Slide 27
Diamond Pattern

Subproblem:



Print out upper half:






print out the upper half
print out the lower half
row 1: print 4 spaces, 1 star;
row 2: print 3 spaces, 3 stars;
row 3: print 2 spaces, 5 stars;
row 4: print 1 space, 7 stars;
row 5: print 0 spaces, 9 stars;
Algorithm Refinement:





row 1: print (5-row) spaces, (2*row - 1) stars;
row 2: print (5-row) spaces, (2*row - 1) stars;
row 3: print (5-row) spaces, (2*row - 1) stars;
row 4: print (5-row) spaces, (2*row - 1) stars;
row 5: print (5-row) spaces, (2*row - 1) stars;
COMP104 Lecture 9 / Slide 28
Diamond Pattern
int row, space, star; // loop
for(row=1; row<=5; row++){
for(space=1; space<=5-row;
cout << " ";
for(star=1; star<=2*row-1;
cout << "*";
cout << endl ;
}
for(row=4; row>=1; row--){
for(space=1; space<=5-row;
cout << " ";
for(star=1; star<=2*row-1;
cout << "*";
cout << endl ;
}
counters
//top half
space++)
star++)
//bottom half
space++)
star++)
COMP104 Lecture 9 / Slide 29
Multiplication Table
// Program to output the
// multiplication table
int i;
//Outer loop counter
int j;
//Inner loop counter
for(i=1; i<=10; i++){
for(j=1; j<=10; j++)
cout << i*j << " ";
cout << endl;
}