while loops and loop patterns

A deceptive problem...
8 Write a method printNumbers that prints
each number from 1 to a given maximum,
separated by commas.

For example, the call:

printNumbers(5)

should print:
1, 2, 3, 4, 5

2
 Flawed solutions
8 void printNumbers(int max) {
for (int i = 1; i <= max; i++) {
cout<<i << ", ";
}
cout<<endl;// to end; the line of output
}
– Output from printNumbers(5): 1, 2, 3, 4, 5,

8 void printNumbers(int max) {

for (int i = 1; i <= max; i++) {
cout<<", " << i;
}
cout<<endl;// to end the line of output
}
– Output from printNumbers(5): , 1, 2, 3, 4, 5

3
 Fence post analogy
8 We print n numbers but need only n - 1 commas.
8 Similar to building a fence with wires separated by
posts:
– If we use a flawed algorithm that repeatedly places a post
+ wire, the last post will have an extra dangling wire.

for (length of fence) {

place a post.
place some wire.
}

4
 Fencepost loop
8 Add a statement outside the loop to place the
initial "post."
– Also called a fencepost loop or a "loop-and-a-
half" solution.

place a post.
for (length of fence - 1) {
place some wire.
place a post.
}
5
 Fencepost method solution
void printNumbers(int max) {
cout<<1;
for (int i = 2; i <= max; i++) {
cout<<", " << i;
}
cout<<endl; // to end the line
}

8 Alternate solution: Either first or last "post" can be taken out:

void printNumbers(int max) {
for (int i = 1; i <= max - 1; i++) {
cout<<i << ", ";
}
cout << max;// to end the line
}
6
 Fencepost question
8 Modify your method printNumbers into a
new method printPrimes that prints all
prime numbers up to a max.
– Example: printPrimes(50) prints
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47

– If the maximum is less than 2, print no output.

8 To help you, write a method countFactors

which returns the number of factors of a
given integer.
– countFactors(20) returns 6 due to factors 1, 2, 4, 5, 10, 20.
7
 Fencepost answer
// Prints all prime numbers up to the given max.
void printPrimes(int max) {
if (max >= 2) {
cout<<"2";
for (int i = 3; i <= max; i++) {
if (countFactors(i) == 2) {
cout<<", " << i;
}
}
cout<<endl;
}
}
// Returns how many factors the given number has.
int countFactors(int number) {
int count = 0;
for (int i = 1; i <= number; i++) {
if (number % i == 0) {
count++; // i is a factor of number
}
}
return count;
}

8
while loops

reading:

9
 Categories of loops
8 definite loop: Executes a known number of times.
– The for loops we have seen are definite loops.
• Print "hello" 10 times.
• Find all the prime numbers up to an integer n.
• Print each odd number between 5 and 127.
8 indefinite loop: One where the number of times its
body repeats is not known in advance.
• Prompt the user until they type a non-negative
number.
• Print random numbers until a prime number is printed.
• Repeat until the user has typed "q" to quit.
10
 The while loop
8 while loop: Repeatedly executes its
body as long as a logical test is true.
while (<test>) {
<statement(s)>;
}

8 Example:
int num = 1; // initialization
while (num <= 200) { // test
cout<<num << " ";
num = num * 2; // update
}
// output: 1 2 4 8 16 32 64 128 11
 Example while loop
// finds the first factor of 91, other than 1
int n = 91;
int factor = 2;
while (n % factor != 0) {
factor++;
}
cout<<"First factor is " << factor;
// output: First factor is 7

12
 Quick check
8 What is output by the following code?
int x = 1;
int limit = 60;
int val = 1;
while(val < limit) {
x *= 2;
}
cout<<x;
A. 1 B. 32 C. 64
D. No output due to syntax error
E. No output due to some other reason
13
 Sentinel values
8 sentinel: A value that signals the end of user input.
– sentinel loop: Repeats until a sentinel value is
seen.
8 Example: Write a program that prompts the
user for text until the user types nothing, then
output the total number of characters typed.
– (In this case, the empty string is the sentinel
value.)

Type a line (or nothing to exit): hello

Type a line (or nothing to exit): this is a line
Type a line (or nothing to exit):
You typed a total of 19 characters. 14
 Solution?
int sum = 0;
string response = "dummy"; // "dummy" value, anything
but ""
while (response != "") //while(response.compare(""))
{
cout << "Type a line (or nothing to exit): ";
getline(cin, response);
sum += response.length();
}
cout << "You typed a total of " << sum <<"characters.";

15
 Changing the sentinel value
8 Modify your program to use "quit" as the
sentinel value.
– Example log of execution:
Type a line (or "quit" to exit): hello|
Type a line (or "quit" to exit): this is a line
Type a line (or "quit" to exit): quit
You typed a total of 19 characters.

16
 Changing the sentinel value
8 Changing the sentinel's value to "quit" does
not work!
int sum = 0;
string response = "dummy";// "dummy" value, anything
but ""
while (response != "quit") {
cout << "Type a line (or \"quit\" to exit): ");
getline(cin, response);
sum += response.length();
}
cout << "You typed a total of " << sum << "
characters.";

8 This solution produces the wrong output.

Why? 17
You typed a total of 23 characters.
 The problem with the code
8 The code uses a pattern like this:
sum = 0.
while (input is not the sentinel) {
prompt for input; read input.
add input length to the sum.
}

18
 problem with code
8 On the last pass, the sentinel’s length
(4) is added to the sum:
prompt for input; read input ("quit").
add input length (4) to the sum.

8 This is a fencepost problem.

– Must read N lines, but only sum the
lengths of the first N-1.

19
 A fencepost solution
sum = 0.
prompt for input; read input. // place a "post"

while (input is not the sentinel) {

add input length to the sum. // place a "wire"
prompt for input; read input. // place a "post"
}

8 Sentinel loops often utilize a fencepost "loop-

and-a-half" style solution by pulling some
code out of the loop.
20
 Correct code
int sum = 0;
string response ;
cout << "Type a line (or \"quit\" to exit): ";
getline(cin, response);
while (response != "quit")
{
sum += response.length();
cout << "Type a line (or \"quit\" to exit): ";
getline(cin, response);
}
cout << "You typed a total of " << sum << "
characters.";

21
 Sentinel as a constant
int sum = 0;
string response ;
const string SENTINEL="quit";
cout << "Type a line (or "<<SENTINEL<<" to exit): ";
getline(cin, response);
while (response != SENTINEL) {
sum += response.length();
cout << "Type a line (or \"quit\" to exit): ";
getline(cin, response);
}
cout << "You typed a total of " << sum << "
characters.";

22
 examples
8 write a method to improve checking if a
number is prime or not
– when can we stop?
8 Write a method that flips a coin until there is
a run of 10 flips of the same side in a row
– how many flips were there before 10 in a row?
– repeat the experiment 1000 times, what is the
average number of flips

23