Transcript Loops

Announcements
 First Midterm
 On November 22nd Tuesday at 19:40am (~ 100 minutes)
 This week recitations, we will solve sample midterm questions.
 I will also send previous years’ exams this week.
 Exam classes and a detailed email will be announced in email this week.
 Homework 4 is due on Wednesday, November 16th at 19:00
 Input Entry and Input Check
 Menu choice MUST be one of {1, 2, 3}. Any other digits or strings are invalid input.
 Source string
MUST NOT be empty
 MUST NOT contain ‘?’
 Other than these two input checks above, you MAY ASSUME the source string will ONLY
have lowercase letters

 Search string
MUST NOT be empty,
 MUST NOT be longer than the source string,
 MUST NOT be ONLY ‘?’s
 Other than these 3 input checks above, you may ASSUME the search string will ONLY have
lowercase letters and ‘?’

Example: Print a string backwards
(revstring.cpp)
 Determine the index of the last character of the string,
and then access each character backwards
 How many times should the loop iterate ?
string s; int k;
cout << "enter string: ";
cin >> s;
cout << s << " reversed is ";
k = s.length() - 1; // index of last character in s
while (k >= 0)
{
cout << s.substr(k,1);
k -= 1;
}
cout << endl;
 What could we use instead of s.substr(k,1) ?
s.at(k)
Reverse String as a function
 First step, what is the prototype?
string revstring(string s)
// pre: s = c0c1c2…cn-1
// post: return cn-1…c2c1c0
 Second step, how do we build a new string?
 Start with an empty string, ""
 Add one character at each iteration using concatenation, +
rev = rev + s.substr(k,1);
 Use revstring to determine if a string is a palindrome
See palindrome.cpp for full program
string revstring(string s)
// post: returns reverse of s, that is "stab" for "bats“
{
int k = s.length() – 1;
string rev = "";
// start with empty string
while (k >= 0)
{
rev = rev + s.substr(k,1);
k -= 1;
}
return rev;
}
bool IsPalindrome(string word)
// post: returns true if and only word is a palindrome
{
return (word == revstring(word));
}
Bad loops
1. for (int i = 10; i < 5; i++)
{
cout << "How many times do I print?";
}
2.for (int i = 10; i >= 1; i++)
{
cout << "How many times do I print?";
}
3. int i = 1;
while (i < 20)
{
cout << "How many times do I print?";
}
Bad loops
 Never executes
 Never stops (infinite loops)
 Example: consider the following modified code from sum10nums
 What’s the problem in the loop below? What is missing?
sum = 0;
count = 1;
while (count <= 10)
{
cin >> num;
sum += num;
}
 count never reaches 10, because count is not updated in the loop
Infinite loops
 Infinite loop is something that must be avoided
 happens when the loop condition is always true
 same loop body iterates forever
 sometimes you see an output, sometimes you don’t
 press Ctrl-C to stop
 could be because of a wrong or missing update statement
 could be because of a wrong condition; could be another
reason
Infinite loops
 What is the problem with the code below?
 cannot say infinite loop, depends on input number
 for example, if num is an odd number, then the loop is infinite
cin >> num;
int start = 0;
while (start != num)
{
start += 2;
cout << start << endl;
}
 How to fix?
 You can check whether num is even before starting the loop.
if (num % 2 == 0)
{
while (start != num)
{ start += 2;
cout << start << endl;
}
}
Other Common Problems
 Easy to iterate one more or one less times
 Test each loop with the inputs that cause:
 zero iterations of the loop body
 one iteration of the loop body
 maximum number of iterations
 one less than the maximum number of iterations
 Use the debugger and watch the variables.
Developing Loops
 Some loops are easy to develop, others are not
 Sometimes the proper loop test and body are hard to
design
 Practice helps, but remember:
 Good design comes from experience, experience comes
from bad design
Number Crunching
 Number crunching is a CS term that means a computing
operation that requires several (and sometimes
complex) arithmetic operations
 It was the job of early computers
 Numeric Analysis
 classical sub-discipline of computer science
 Today
 implicitly or explicitly, all operations are numeric
 Now we will see some mathematical applications
 factorial calculation
 prime number testing
Factorial
 n! = 1x2x…xn is “n factorial”; used in math, statistics
long factorial(long n)
// pre: 0 <= n
// post: returns n! (1 x 2 x … x n)
 Similar to sum, but this time we will calculate a product
within the loop. At the end we will return the final
product.
 The loop will iterate n times, multiplying by 1, 2, …, n
 Suppose we use a variable called product to hold the result,
then product is n! when the loop terminates. Then we will
return it at the end.
Factorial
long Factorial(int num)
// precondition: num >= 0
// postcondition returns num! (1 x 2 x … x num)
{
long product = 1;
int count = 0;
while (count < num)
{
count += 1;
product *= count;
}
return product;
}
 Issues
 Why did we use long? What happens if we use int instead?
 What happens if we initialize count to 1?
 Let’s see fact.cpp
Factorial (Cont’d) – Using BigInt class
 What is the problem of the previous program?
 integer overflow
 even long is not sufficient (actually there is no difference between
long and int for 32-bit computers like ours)
 12! is 479,001,600 so what happens with 13! ?
 The type BigInt, accessible via #include "bigint.h" can
be used like an int, but gets as big as you want it to be
 Really arbitrarily large?
 No, limited to computer memory, but computers most likely run out of time
before running out of memory
 Disadvantages of using BigInt compared to int?
 processing speed is lower
 uses up more memory
 Use BigInt if you really need it
 Do not forget to add bigint.cpp to your project,
 BigInt is a Tapestry class
 Download wincode.zip file from http://cs.duke.edu/csed/tapestry
Factorial using BigInt class
 See bigfact.cpp
Determining if a number is prime
 Prime number is a natural number which has only two divisors:
1 and itself
 Some Cryptographic algorithms depend on prime numbers
 Determining if a number is prime must be “easy”
 Actually factoring a number must be “hard”
 “hard” in the sense that it must be computationally infeasible to factorize
in a reasonable amount of time
 RSA Cryptosystem
 Rivest, Shamir, Adleman
 based on the factorization problem of large numbers
 has been utilized by several security products and services
 PGP (Pretty Good Privacy) – e-mail security
 WWW security using SSL protocol
 Sophisticated mathematics used for fast prime-testing, we’ll do
basic prime testing
 Since our algorithm is based on factorization, it will be really slow
for large numbers
Determining Primeness (continued)
 1 is NOT prime, 2 is prime, 3 is prime, 5 is prime, 17 is prime, … 137,
193?
 We do not need to check even numbers other than 2 (2 is a special case)
 To check 193, divide it by 3, 5, 7, 9, 11, 13
 Note that 14x14 = 196, so 13 largest potential factor?
 We will use modulus operator to check divisibility
 We’ll check odd numbers as potential divisors
 Watch out for 2, it is a special case
 How far should we go to check potential divisors?
 up to and including sqrt(number) + 1
 If there was a bigger factor, a smaller factor would exist. And this smaller one
must have been checked before. So we do not need to go beyond this limit.
 +1 is there to make sure that there will be no problems with precision
 See primes.cpp for code
Primeness Check – Details
 Special even number check is added before the loop to
eliminate even numbers to be checked in the loop
 In order to make the code more efficient
int limit = int(sqrt(n) + 1);
 To assign a double value to an int, a typecast is used, to tell the
compiler that the loss of precision is intentional
 Make typecasts explicit to tell the compiler you know what you are doing
 Compiler warnings are avoided
 We will see typecast in more detail later
for loop compared with while
<initialization>
while (<test>)
{
<statement1>;
...
<statementN>;
<update>
}
for (<initialization>;
<test>;
<update> )
{
<statement1>;
...
<statementN>;
}
Example
 Rewrite the while loop of main of primes.cpp using for
k = low;
while (k <= high)
{
if (IsPrime(k))
{
cout << k << endl;
numPrimes += 1;
}
k += 1;
}
for (k = low; k <= high; k += 1)
{
if (IsPrime(k))
{
cout << k << endl;
numPrimes += 1;
}
}
Shorthand for increment/decrement
 Lots of code requires incrementing a variable by one
 Three methods, using = and +, using +=, and using ++
 effectively they are same
num = num + 1;
num += 1;
num++;
// post increment
 It is also possible to write ++num;
 pre-increment
 These differ on when the increment is performed, but this
difference doesn’t matter when used as an abbreviation for the
statement n += 1; in a single statement
 Similarly there are post-decrement (and pre-decrement)
num = num - 1;
num -= 1;
num--;
The do-while loop
 Similar to while loop, but the test is after the execution of the loop body
 The while loop may never execute, do-while loop executes at least
once
<initialization>
do
{
<statement1>;
...
<statementN>;
Don’t
forget
<update>
} while (<condition>);
 Example: Prompt for a number between 0 and 100, loop until such a
number is entered (user should enter at least one number)
do
{
cout << "enter number in range [0..100] ";
cin >> num;
} while (num < 0 || num > 100 );
Priming
 Priming: reading an initial value before the loop
 do not get confused with prime numbers; this is something else
 Problem: enter numbers, add them up, stop when -1 entered
int sum = 0;
int num;
cin >> num;
// prime the loop
while (num != -1)
{
sum += num;
cin >> num;
}
cout << "total = " << sum << end;
 Code duplication exists here: input (and perhaps prompt) code is
repeated before the loop and in the loop
Pseudo infinite solution using break
 To avoid repeating code, include it in the body of the loop only,
use a test to break out of the loop
 break statement exits (inner-most) loop
 I don’t prefer this kind of loops (I’d prefer code duplication)
 Because the loop condition is not clear, hence prevents readability
 Try not to use break in this course
 Save it for later when you develop really complicated loops
int sum = 0;
int num;
while (true)
// seemingly infinite loop
{
cin >> num;
if (num == -1)
{ break;
// get out of loop
}
sum += num;
}
cout << "total = " << sum << end;
Fence Post Problem
 The problem that occurs when one or more operations of the loop
body are executed one less then the others.
 Example: Display integers between 1 and 10 separated by comma
1,2,3,4,5,6,7,8,9,10
 no comma after 10; no comma before 1.
for (n=1; n <= 10; n++)
{ cout << n << ",";
}
Problem: comma after 10
for (n=1; n < 10; n++)
{ cout << n << ",";
}
cout << n;
No problem, but code duplicates
 Think of other solutions! (see page 175 of Tapestry)
Downward-counting loop
 Calculate n to the power of m: nm=nxnx…xn
 Example: 25=2x2x2x2x2=32
int
int
cin
for
{
power = 1;
n, m;
>> n >> m;
(int i = m; i <= 1; i--)
power = power * n;
}
Nested loops
 Sometimes one loop occurs in another
 Generating 2-dimensional tabular data
 multiplication table
 Sorting vectors (which will be studied much later)
 Display some geometric figures using character * (or any other
character)
 display rectangles, triangles
 Although other loops can be nested as well, most of the
time, for loops are used in nested manner
Nested loops - Example
 Write a function to display a rectangle of stars (height and width are
parameters)
 e.g. if height is 4 and width is 7, the output should look like
*******
*******
*******
*******
for (i=1; i<= height; i++)
{
for (j=1; j<=width; j++) // inner loop prints 1 line of stars
{
cout << "*";
}
cout << endl;
// end of line is put to the end of each line
}
 See drawfigures.cpp for the complete function and its use in main
Nested loops - Example
 Write a function to display a perpendicular isosceles triangle of stars
(perpendicular side length is parameter)
 e.g. if side length is 6 , the output should look like
*
**
***
****
*****
******
for (i=1; i <= side; i++)
{
for (j=1; j<=i; j++)
// inner loop prints 1 line of stars
{
cout << "*";
}
cout << endl;
// end of line is put to the end of each line
}
 See drawfigures.cpp for the complete function and its use in main
Same loop: downward-counting
for (i=1; i <= side; i++)
{
for (j=1; j<=i; j++)
{
cout << "*";
}
cout << endl;
}
for (i=1; i <= side; i++)
{
for (j=i; j>=1; j--)
{
cout << "*";
}
cout << endl;
}
Drawfigures – Other Considerations
 What about having a function to display a line of stars (number
of stars is a parameter)
 useful for both rectangle and triangle
void PrintLine (int numstars)
// pre: numstars > 0
// post: displays numstars stars in one line
{
int i;
for (i=1; i<= numstars; i++)
{ cout << "*";
}
cout << endl; // end of line is put to the end of the line
}
 in rectangle function, inner loop is replaced by a function call
for (i=1; i<=height ; i++)
{
PrintLine(width);
}
 use of PrintLine in triangle function is similar
Example – Multiplication Table
 On ith line print, i*1, i*2, i*3, ... , i*i
 Total number of lines is an input. Display lines starting with 1.
 See multiply.cpp
#include <iostream>
#include <iomanip>
// for setw
using namespace std;
int main()
{
int i,k,numlines;
const int WIDTH = 4;
cin >> numlines;
}
for (i=1; i <= numlines; i++)
{
for (k=1; k <= i; k++)
{
cout << setw(WIDTH) << i*k;
}
cout << endl;
}
return 0;
Constants
 Sometimes very useful
 provides self documentation
 re-use the same value across the program
 avoid accidental value changes
 like variables, but their value is assigned at declaration
and can never change afterwards
 declared by using const before the type name (any type is OK)
const double PI = 3.14159;
const string thisclass = "CS201"
const int
WIDTH = 4;
 later you can use their value
cout << (PI * 4 * 4);
 but cannot change their value
PI = 3.14;
causes a syntax error
Formatting Output
 We use stream manipulator setw to specify the total number of
spaces that the next output will use
 setw(field length)
 written in cout and affects only the next output value
not the whole cout line
 output is displayed using field length spaces in right justified manner
(any empty space is on the left)
 defined in header file <iomanip>, so you have to have #include
<iomanip>
 Example
cout << setw(9) << "cs201";
 output shown is four blanks and cs201
Example using robot class (see rectangularscan.cpp)
 Write a program in which the robot starts at 0,0 and
searches a rectangular space that covers n*n cells
 n is input (in the example below, n is 8)
 during this journey the robot should pick or put things on the
cells so that all visited cells occupy one thing