Chapter 5, Pause Reflect

• 5.1--5.5

  5.6--5.17

  5.18 -- 5.23

  5.24 -- 5.27

  5.28 -- 5.31

  5.32 -- 5.38

  5.39 -- 5.44

5.1 -- 5.5

• 5.1: Here's a program to print all values from 1 to the value entered by the user. int main() { int last; cout << "enter last number: "; cin >> last; int counter = 1; while (counter <= last) { cout << counter << endl; counter += 1; } return 0; } To print down to one, change the loop as shown below. The variable counter isn't needed: while (1 <= last) { cout << last << endl; last -= 1; }

• 5.2: The loop below prints powers of two: num = 1; while (num < 30000) { cout << num << endl; num *= 2; // next power of two }

• 5.3: The loop guard uses the value of num, but this variable is not modified in the loop body. Hence the loop body, if it executes once, will execute "forever". If the user enters a number greater than or equal to 100 the loop body won't execute at all.

• 5.4: To find the first vowel in a string we can use a few approaches. One is to loop over each character in the string stopping when we find a vowel (or run out of characters). Since a string may have no vowels, we need identify this case. We'll use string::npos for this purpose.

  Although the question doesn't ask for a function to help, using a function will be easier. Here's a complete program listing. There are many other ways of doing this task.

  #include <iostream> #include <string> using namespace std; bool IsVowel(string letter) // post: return true if and only if letter is a vowel: a,e,i,o,u // note: only works for lowercase letters { return "a" == letter || "e" == letter || "i" == letter || "o" == letter || "u" == letter; } int VowelIndex(string word) // post: return index of first occurrence of a vowl in word // return string::npos if no vowel occurs { int len = word.length(); int index=0; while (index < len && ! IsVowel(word.substr(index,1))) { index ++; } //DeMorgan's law helps to assert: // index >= len OR IsVowel(s.substr(index,1) if (index >= len) { return string::npos; } else { return index; } } int main() { string word; int index; cout << "enter word "; cin >> word; index = VowelIndex(word); if (index == string::npos) { cout << "no vowels found" << endl; } else { cout << "first vowel is " << word.substr(index,1) << endl; } return 0; }

• The functions are shown below #include <string> using namespace std; string revstring(string s) // post: returns reverse of s, that is "stab" for "bats" { int len = s.length(); string rev = ""; // start with empty string int k=0; while (k < len) { rev = rev + s.substr(k,1); k++; } return rev; } bool IsPalindrome(string word) // post: returns true if and only word is a palindrome { return word == revstring(word); }

• 5.6: The function below will work. There is an absolute value function fabs() for floating point numbers defined in <cmath> but not one for integer values. int Factorial(int num) // postcondition: returns num! if num >= 0 // returns (-num)! if num is negative { if (num < 0) num = -1 * num; // make it positive // remaining code identical to fact.cpp code int product = 1; int count = 1; while (count <= num) // invariant: product == (count-1)! { product *= count; count += 1; } return product; }

• 5.7: The call Factorial(-7) evaluates to 1 in the original factorial program because the while loop body in the function Factorial never executes, so the value of product returned is 1.

• 5.8: Assuming the existence of Factorial: long Factfact(int num) // post: returns n!! which is (n!)! { return Factorial(Factorial(n)); }

• Assuming the function Factorial from bigfact.cpp is used (which returns a BigInt value): BigInt NFact(int x, int n) // pre: 1 <= n // post: return x(!)^n, which is x !!!...!! where there are n !'s // assume that { int k = 0; BigInt result = x; while (k < n) { result = Factorial(result); k += 1; } return result; }

• 5.10: This code does pass a black-box test. The only difference is that the value of count starts at 0 instead of 1 (and the loop test compensates for this). Because count is incremented before the value of product is updated (in contrast to the loop in fact.cpp) the value returned is correct.

  A good invariant is product == (count-1)! This is true the first time the loop test is evaluated since count is 1, and 0! (zero factorial) is 1, the value of count.

  When the loop terminates, we konw count == num + 1 because the loop increments count by one. This means that product == [(num + 1) - 1]! by the invariant, or num!, the desired answer.

• 5.11: Yes, if divisor += 2 is changed to divisor += 1 the function IsPrime will still return the correct values. However, it will test many more divisors than necessary since it will now test all numbers between 3 and limit rather than just odd numbers. Since even numbers have already been checked before the loop, checking even divisors is not necessary.

• 5.12: The call IsPrime(1) evaluates to false (the first if statement takes care of this, checking for numbers less than 2. This is correct, 1 is not considered prime. The first (and only even) prime number is 2.

• 5.13: If the loop below is used in IsPrime, some method is needed for determining why the loop exits, i.e., which of the conjuncts divisor <= limit and n % divisor is false. while (divisor <= limit && n % divisor != 0) { divisor += 2; } If the loop exits because a divisor was found, then false should be returned.

      if (n % divisor == 0)
      {
          return false;
      }
      else
      {
          return true;
      }
  

  This can be shorted considerably to

      return ! (n % divisor = 0);
  

  You should think about this; the expresion n % divisor == 0 is either true or false. If it is true, then n has a divisor so IsPrime should return false. Hence the use of !. The expression could be written as n % divisor != 0 but this is hard to think about (at least for me it is).

• 5.14: If the values of expo is 1,024 originally then it has the values (in order)

  1024
  512
  256
  128
  64
  32
  16
  8
  4
  2
  1
  0
  

  If expo starts at 1,000, it has the values (in order)

  1000
  500
  250
  125
  62
  31
  15
  7
  3
  1
  0
  

• 5.15: Since the value of divisor is initially 3, the invariant is true because n isn't even, so 2 doesn't divide it. The range in the invariant: [2..3) is an open interval, so the last number is NOT included in the open interval. Thus the range is the same as [2..2].

  When divisor divides n evenly, the function returns false, which is correct since a divisor is found. If the loop terminates because the loop test is false, then the invariant tells us there are no divisors in the interval [2..divisor). Since divisor > limit when the loop terminates, all numbers up to the square root of n have been checked -- since none divide n, it must be prime.

• 5.16: The order of the statements cannot be changed because if base is squared first, then result will be multiplied by a much larger number than it is when the statements are in the order shown in the code.

• 5.17: To work with negative exponents, we'll need to return a double value instead of an int. We'll rename Power to be PosPower, then write Power: double Power( double base, int expo) // pre: 0 <= expo // post: returns base^expo (base to the power expo) { double result = 1.0; // invariant: result * (base^expo) = answer bool negPower = false; // assume expo is positive if (expo < 0) { expo = -1 * expo; // absolute value negPower = true; } while (expo > 0) { if (expo % 2 != 0) // exponent is odd { result *= base; } expo /= 2; // 4/2 == 2, 5/2 == 2 base *= base; // (a*a)^(b/2) == a^b } if (negPower) { return 1/result; } return result; }

• 5.18: Once again, there are many ways to do this. #include <iostream> using namespace std; // draws fence/posts as entered by user void DrawFence(int numPosts); main() { int fencePosts; cout << "enter # of posts: "; cin >> fencePosts; DrawFence(fencePosts); DrawFence(fencePosts); } void DrawFence(int numPosts) //precondition: numPosts > 0 //postcondition: draws one line of fences/posts, # of posts = numPosts { // draw first fence post outside loop cout << "|"; // draw remaining posts int k = 1; // already drew one post while (k < numPosts) { cout << "---|"; k += 1; } cout << endl; }
• 5.19: To put a space between each number, the last number is treated differently, after the loop. It's possible to solve this problem in other ways. Spaces are added before a new digit within the loop, this is effectively between digits since, for example, 352 will yield " two", " five two", and then after loop (note, no space): "three five two". string StringOut(long number) // precondition: 0 < number // postcondition: returns string formed from digits written in English // e.g., 123 -> "one two three" { string s = ""; int digit; while (number >= 10) { digit = number % 10; s = " " + DigitToString(digit) + s; number /= 10; } s = DigitToString(number % 10) + s; return s; }

• 5.20:

• 5.21: The function below counts digits. Zero can be tricky in certain situations so it's treated as a special case in the code below. int NumDigits(int n) // postcondition: returns # characters in n, accounting // for - sign, e.g., -23 -> return 3 { int digits = 0; if (0 == n) return 1; // treat zero as special case if (n < 0) // account for '-', then make positive { digits += 1; n = -1 * n; } while (n > 0) { digits += 1; // count the digit and n /= 10; // chop off the digit } return digits; }

• 5.22: This can be done with one loop, using the value of the number being printed to determine when a new line of output should be started (multiples of 10). In the loop below, a space is printed after every number rather than between numbers. The next loop shows a solution to the fencepost problem of only printing a space between numbers. // space after every number num = 1; while (num <= 100) { cout << num << " "; if (num % 10 == 0) { cout << endl; // new line on multiple of 10 } num += 1; // next number } // space between numbers only int num = 1; while (num <= 100) { if (num % 10 != 1) // NOT first number on line { cout << " "; // so has space before it } cout << num; if (num % 10 == 0) { cout << endl; // new line } num += 1; } A nested-loop can be used for this problem too. One loop for each line, and an outer loop for the number of lines. In general, it's a good idea to try to write code without nested loops if possible. Nested loops are usually hard to get right. int numLines = 0; // # of lines printed while (numLines < 10) // more lines of output? { int num = numLines*10 + 1; // first number on line int count = 0; // count # of numbers printed while (count < 10) { cout << num; num += 1; // next number to print count += 1; // another number printed } cout << endl; // new line of output numLines += 1; } The code in the inner loop doesn't need both num and count . Since both are incremented by one each time through the loop, one of them is superfluous. Defining and using both is ok, but it's possible to dispense with count and use a test of while (num <= numLines*10 + 10) as the guard. It might be useful to use a variable with the value numLines*10+ 10 so that this isn't recalculated everytime through the loop. Smart compilers can ``optimize'' this kind of recomputation away, however.

• 5.23: This loop effectively calculates the base 2 logarithm of a number (actually one more than the base 2 log). If log_2(X) = Y then the relationship 2^Y = X holds. Thus log_2(32) = 5 since 2^5 = 32.
  int num; cout << "enter a number "; cin >> num; int count = 0; while (num > 0) { num /= 2; count += 1; } cout << "base 2 log + 1 of " << num << " = " << count;

5.24 -- 5.27

• 5.24: A for loop is used in the code below. long Factorial(int num) // precondition: num >= 0 // postcondition returns num! { long product = 1; int count; // invariant: product == (count-1)! for(count=1; count <= num; count += 1) { product *= count; } return product; }

• 5.25: The while loop below is equivalent. double total = 0.0; double val = 1.0 while (val < 10000) { total += val; val *= 1.5; }

• 5.26: The for loop below is equivalent int sum = 0; int k; for(k=1; k <= num; k += 2) { sum += k; }

• 5.27: The output of the loop is shown after it: for(k=1024; k >= 0; k /= 2) { cout << k << endl; }

  Output (one number per line):

     1024 512 256 128 64 32 16 8 4 2 1 0 0 0 0 0 0 0 0 ...
  

  This is an infinite loop since 0/2 == 0, so the once k becomes zero, it remains zero forever (until the user stops the program).

• 5.28: A do-while loop is used below since the user must enter at least one number. int pos = 0; int neg = 0; int number; cout << "enter numbers, zero to exit: "; do { cin >> number; if (number < 0) neg++; else if (number > 0) pos++; } while (number != 0); cout << "# positive = " << pos << endl; cout << "# negative = " << neg << endl;

• 5.29: The loops below use a field-width for all but the first number which is printed before the loop (so has no leading spaces). The inner loop prints spaces between numbers by using a fieldwidth of 4. for(j=1; j <= limit; j++) { cout << j; for(k=2; k <= j; k++) { cout.width(4); cout << k*j; } cout << endl; }

• 5.30: The function LeftStars prints the left-justified star pattern. The function CenterStars prints the center-justified pattern. (note that both functions print a space AFTER each '*' rather than between --- this makes the code simpler). The centered pattern is created by adding a single use of width() before the first asterisk printed. void LeftStars(int n) // precondition: 0 < n // postcondition: print **** pattern, k stars in row k { int j,k; for(j=1; j <= n; j++) { for(k=1; k <= j; k++) { cout << "* "; } cout << endl; } } void CenterStars(int n) // precondition: 0 < n // postcondition: print centered **** pattern, k stars in row k { int j,k; for(j=1; j <= n; j++) { cout.width(40-j); for(k=1; k <= j; k++) { cout << "* "; } cout << endl; } }

• 5.31:

           const int FEET_PER_MILE = 5280;
           const int OUNCES_PER_LB = 16;
           const double E = 2.718;
           const double GRAMS_PER_POUND = 453.59;
           const double FT_LBS_PER_ERG =  1.356e7;
        

• 5.32: Oops, this is the same as Pause/Reflect 4.25, see that solution.

• 5.33: #include <iostream> using namespace std; #include "date.h" int main() { int m,d,y; cout << "enter month day year "; cin >> m >> d >> y; Date theDate(m,d,y); Date today; cout << "you have been alive " << today - theDate << " days" << endl; return 0; }

• 5.34: This is a repeat of 4.24, see that solution.

• 5.35: It's extremely unlikely that we need to worry about programs using the Date class being used in 2738, which is day one million. The value of a long is roughly two billion if 32-bit numbers are used (which is the smallest long, longs sometimes use 64 bits). A date constructed using Date d(2000000000L); will print as January 6, 5475815 which is after the year five million. I, Owen Astrachan, will give any one $500.00 if a Date program is still around in that year (time travel to check is acceptable as a means of verification.)

• 5.36: To write a program using the Date class in canada you'll need to prompt the user for day, month, year (as the user would expect), but construct dates using the United States convention. To the user, the program appears to be using dates in the Canadian format, but the regular Date class is used in the program.

• There are many ways to find Thanksgiving (fourth Thursday). Here's one, this method finds the first Thursday, then adds 21 to find the fourth Thursday (which is three weeks after the first).
  Date Thanksgiving(int year) //post: returns date of thanksgiving in year { Date d(11,1,year); // november 1 while (d.DayName() != "Thursday") { d += 1; } // d is now the first Thursday, fourth is 21 days later return d + 21; }

  Most people try to find the fourth Thursday using a loop, this is trickier. It's trickier because of initialization of the Date object used, if it's initialized to November 1, getting the code right is tricky (use an invariant and try).

  Date Thanksgiving(int year) //post: returns date of thanksgiving in year { Date d(10,31,year); // october 31 int thursdays = 0; // # thursdays before d // invariant: thursdays is number of thursdays before(including) d while (thursdays != 4) { d += 1; // increment d if (d.DayName() == "Thursday") { thursdays += 1; } } return d; }

• 5.38: Here's one approach, this looks at every day of the month. bool MoreFridays(int month, int year) // post: returns true if there are more Fridays than Mondays // in month of year { int mondays = 0; // count # of Mondays int fridays = 0; // count # of Fridays; Date d(month, 1, year); // first of the month while (d.Month() == month) // still in same month? { if (d.DayName() == "Friday") { fridays += 1; } else if (d.DayName() == "Monday") { mondays += 1; } } return fridays > mondays; }

  Alternatively, you could find the number of days in a month, and loop that way:

  Date d(month, 1, year); // first of the month int days = d.DaysIn(); int k; for(k=0; k < days; k++) { if (d.DayName() == "Friday") { fridays += 1; } else if (d.DayName() == "Monday") { mondays += 1; } d++; } return fridays > mondays;

  In either case, to find the every month in a year, just call MoreFridays in a loop:

  int main() { int year; int k; cout << "enter year "; cin >> year; for(k=1; k <= 12; k+= 1) { if ( MoreFridays(k,year)) { Date d(k,1,year); cout << d.MonthName() << " has more fridays" << endl; } } return 0; }

5.39 -- 5.44

• 5.39: Here's a modified RollTest, local variables r1 and r2 store the dice rolls so that they can be printed and added together. You must store dice rolls in int variables to print and check, you can't call Roll() once to print and again to check, different rolls will result. double RollTest(int target, int trials) // precondition: 2 <= target <= 12, 0 < trials // postcondition: returns average # of rolls needed to obtain target // trying 'trials' times { Dice d1(6); Dice d2(6); int total = 0; int k; for(k=0; k < trials; k++) { int numRolls = 1; //first time through loop is 1 roll int r1 = d1.Roll(); int r2 = d2.Roll(); cout << "rolling .. " << r1 << " " << r2 << endl; while (r1 + r2 != target) { numRolls += 1; } total += numRolls; } return double(total)/trials; }
• 5.40: Here's a function that returns the number of times two N-sided Dice are rolled before doubles occur. The value of N is a parameter to the function. Only one Dice variable is defined, it is rolled twice. It's possible to use no integer variables at all (like count). Instead, the member function Dice::NumRolls() could be used to determine how many times d was rolled (don't forget to divide by two!). int RollsForDoubles(int n) // precondition: 0 < n // postcondition: returns # times two N-sided Dice rolled // before doubles obtained { Dice d(n); // n-sided dice int count = 1; // first time rolled in loop test while (d.Roll() != d.Roll()) { count += 1; } return count; }

• 5.41: Here's one approach int Heads(int flips) // post: return # times heads flipped in n attempts { int headCount = 0; Dice coin(2); int k; for(k=0; k < flips; k++) { if (coin.Roll() == 1) // could use 2, simulated anyway { headCount += 1; } } return headCount; }
• 5.42: The functions below return the number of times three six-sided dice are rolled before all three show the same number. The second function, Triples uses a "real" test in the while loop. The test is the negation of the if statements checked in Triples2 int Triples2() // postcondition: return # of rolls until three 6-sided // die return the same number { int count = 0; Dice d(6); int r1, r2, r3; while (true) { r1 = d.Roll(); r2 = d.Roll(); r3 = d.Roll(); count++; // rolled them all one more time if (r1 == r2 && r2 == r3) { return count; } } } int Triples() // postcondition: return # of rolls until three 6-sided // die return the same number { Dice d(6); int count = 1; int r1 = d.Roll(); int r2 = d.Roll(); int r3 = d.Roll(); while (r1 != r2 || r2 != r3) { count++; r1 = d.Roll(); r2 = d.Roll(); r3 = d.Roll(); } return count; }

• 5.43: Here's some code that does the job, it can be cleaned up, but it's straightforward: int main() { Dice monthDice(12); // for random month Dice day30(30); // for random day of the month (30 days) Dice day31(31); // 31 days Dice day28(28); // 28days Dice day29(29); // leap years int month = monthDice.Roll(); int year; int day; cout << "enter year "; cin >> year; Date d(month,1,year); if (d.DaysIn() == 30) { day = day30.Roll(); } else if (d.DaysIn() == 31) { day = day31.Roll(); } else if (d.DaysIn() == 28) { day = day28.Roll(); } else { day = day29.Roll(); } Date randomDate(day,month,year); cout << "random date is " << randomDate << endl; return 0; }

• 5.44: DeMorgan's law is used as follows: when the loop terminates we want all three values (r1, r2, r3) to be different, i.e.,
  • r1 is different from r2
  • r1 is also different from r3
  • r2 must be different from r3

  Since all of these must be true (and) when the loop terminates, the negation of the conjunction yields a disjunction (use OR).

  int Triples() // postcondition: return # of rolls until three 6-sided // die roll different numbers { Dice d(6); int count = 1; int r1 = d.Roll(); int r2 = d.Roll(); int r3 = d.Roll(); while (r1 == r2 || r2 == r3 || r1 == r3) { count++; r1 = d.Roll(); r2 = d.Roll(); r3 = d.Roll(); } // demorgan says r1 != r2 && r2 != r3 && r1 != r3 return count; }