Chapter 4

Building Programs and Solving Problems

Page 107

4.2 If any string other than ``yes'' is entered, the else clause is executed (and the string ``De gustibus non Disputandum'' is printed).

4.3 

    if ("yes" == response)
    {
	cout << ...;
    }
    else if ("no" == respone)
    {
	cout << ...;
    }
    else
    {
	cout << "sorry, only responses of yes and no are recognized" << endl;
    }

4.4 One code fragment that could be used is shown below. There are lots of others. 

    int grade;
    cout << "enter a grade: ";
    cin >> grade;

    if (grade > 90)
    {
        cout << "excellent score" << endl;
    }
    else if (grade > 80)
    {
        cout << "good work, keep it up" << endl;
    }
    else if (grade > 70)
    {
        cout << "ok, keep working on the material" << endl;
    }
    else if (grade > 60)
    {
        cout << "be sure to ask questions when things are hard" << endl;
    }
    else
    {
        cout << "you need to work very hard" << endl;
    }
Each else clause is necessary. If they're left out a grade of 100 would cause all the messages to be printed. In the code above a grade of 75 will cause the guard (grade > 70) to be true, and that's the only guard that will be evaluated as true.

4.5 When a string is used, the user can enter any characters from the keyboard. When an int is used, only digits can be entered, 0,1, ..., 9 (and +/- signs). By using strings, the program is more robust , that is less prone to crash if the user enters something unexpected.

Using a string ensures that anything entered by the user is processed, the string will always have a value. If an int is used, and the user enters "one", the int will have no value, the characters 'o', 'n', and 'e' will remain unprocessed on the input stream.

4.6 One variable is sufficient because only one value is needed at a time. The answer to any single question determines what action to take next, but because there is no reason to "remember" choices during the exection of the program one variable suffices.

Page 115

4.7 Here's a program for BTU's to Joules, the other programs are similar. 

   double btu;
   cout << "enter BTU's ";
   cin >> btu;
   cout << btu << " BTU's = " << btu/1054.8 << " Joules";
To use an assignment operator, use: 
    double joule;
    ...
    joule = btu/1054.8;
    cout << btu << " BTU's = " << joule << " Joules";
4.8 The output of cout << 9 * 3 < 4 * 5 << endl is 0 because the expression evaluates to 27 < 20 , which evaluates to false, which is 0.

The expression 9 * (3 < 4) * 5 evaluates to 9 * 1 * 5 because (3 < 4) is true which is 1. This is why 45 is output. 4.9 The statement cout << 9 * 5 < 45 << endl generates 0 as output because it is false and false corresponds to 0 for output (on most current systems).

The statement cout << 9*5 < 45 < 30 << endl evaluates to 45 < 45 < 30 which evaluates to 0 < 30 which is 1 (true). This depends on the associativity of the < operator.

4.10 The average of three values can be output using the statement below. 

    cout << (a + b + c)/3.0 << endl;
The parentheses are necessary because / has higher precedence than +. If the type of a,b,c is changed to double then the average will be a double as well. However, in the statement above a double value will be calculated even if a,b,c are int's because of the 3.0. The operator >> is left associative. The statement cout >> a >> b >> c is treated like ((cout >> a) >> b) >> c .

4.11 There are many possibilities, one is shown below. 

    string grade;
    int score;
    cout << "enter score: ";
    cin >> score;

    if (score > 100)
    {
        cout << "score too high, between 0 and 100" << endl;
    }
    else if (score >= 80)
    {
        grade = "High Pass";
    }
    else if (score >= 60)
    {
        grade = "Pass";
    }
    else{
        grade = "Fail";
    }
Page 125

4.12 There are many ways of writing this code. In the function below I've used a return statement on a single line with an if statement (for February). In some situations it's convenient not to use a compound statement. In such situations I put all the code on one line as shown below. 

    in DaysInMonth(int month, int year)
    // precondition: month coded as 1 = january, ..., 12 = december
    // postcondition: returns # of days in month in year
    {

        // 30 days has september, april, june, and november
        if (9 == month || 4 == month || 
            6 == month ||11 == month)
        {
            return 30;
        }
        else if (2 == month)               // handle february
        {
            if (IsLeap(year)) return 29;
            return 28;
        }
        else
        {
            return 31;
        }

4.13 The parentheses are needed because the expression 

    TensPrefix(10 * num / 10)
when num == 22 evaluates to TensPrefix(10 * 22 / 10) which is TensPrefix(220/10) which is TensPrefix(22) because * and / have equal precedence so in the absence of parentheses the order of evaluation is left-to-right.

4.14 This function can be written in many ways, I've shown two below. The second version uses the same ``logic'' as the first, but returns the result of the expression testing for divisibility by 2 which is either 0 or 1 depending on whether num is odd or even, respectively. 

    int IsEven(int num)
    // precondition: returns 1 if num is even, else returns 0
    {
        if (num % 2 == 0)
        {
             return 1;
        }
        return 0;
    }

    int IsEven(int num)
    // precondition: returns 1 if num is even, else returns 0
    {
        return num % 2 == 0;
    }

4.15 In the function below I've used the one line form of an if statement again. In this case the code is clear and it probably won't be modified so this approach is justified. 

string DayName(int day)
// precondition: 0 <= day <= 6
// postcondition: returns string representing day with
//                0 = "Sunday", 1 = "Monday", ..., 6 = "Saturday"
{
    if (0 == day) return "Sunday";
    if (1 == day) return "Monday";
    if (2 == day) return "Tuesday";
    if (3 == day) return "Wednesday";
    if (4 == day) return "Thursday";
    if (5 == day) return "Friday";
    if (6 == day) return "Saturday";
}

4.16 (answer will appear soon)

4.17 There's room for improvement in the function below. It is possible, for example, to check for common abbreviations like nope, yeah, yup, etc. and return the string "yes" or "no" as appropriate. 

    string YesNo(string prompt)
    // postcondition: returns either "yes" or "no"
    //                depending on user's entered response
    {
        string response;
        cout << prompt << " [yes/no]";
        cin >> response;
        return response;
    }

4.18 This function is easier to write than the leap year function for our (Julian/Gregorian) calendar. 

    int IsIslamicLeap(int year)
    // postcondition: returns 1 if year is a leap year in the
    //                Islamic calendar, else returns 0
    {
        return ((11*y + 14) % 30) < 11;
    }

4.19 I used only 2 if statements in the function below by using the && operator. 

    int IslamicDaysInMonth(int month, int year)
    // postcondition: returns # of days in month/year
    {
        // odd numbered months have 30 days

        if (month % 2 == 1) return 30;

        if (12 == month && IsIslamicLeap(year)) return 30;
         
        return 29;  // even numbered months have 29 days
    }
page 133

4.20 Once again, there are many ways to do this. 


#include 

// draws fence/posts as entered by user

void
DrawFence(int numPosts);

main()
{
    int fencePosts;
    cout << "enter # of posts: ";
    cin >> 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;
    
}

4.21 

    num = 1;
    while (num < 30000)
    {
        cout << num << endl;
        num *= 2;                  // next power of two
    }

4.22 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.

4.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;

4.24 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.

page 142

4.25 

    int Factorial(int num)
    // postcondition: returns num! if num >= 0
    //                returns (-num)! if num is negative
    {
        num = Abs(num);
        // remaining code identical to fact.cc code
        int product = 1;
        int count = 1;

        while (count <= num)           // invariant: product == (count-1)!
        {
            product *= count;
            count += 1;
        }
        return product;        
    }

4.26 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.cc) the value returned is correct.

4.27 The code will never generate an error because of short-circuit evaluation. If the value of x is negative when 

    if (x >= 0 && sqrt(x) > 10)
is evaluated. Then the subexpression x >= 0 will be false, and the call to sqrt will NOT be made because the whole expression must be false. This is one of the nice things about short-circuit evaluation of boolean expressions.

4.28 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.

4.29 The call IsPrime(1) evaluates to false (the first if statement takes care of this, checking for numbers less than 2.

4.30 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).

4.31 The sqrt function yields approximations to square roots, not the exact square root. This is due to the finite precision of floating point numbers (the type double in C++). For numbers like 9.0, the square root will most likely be 3.0, but for larger numbers that are perfect squares the likelihood of small perturbations from the exact result increases. When these small differences are multiplied as in the code fragment from this problem, the differences are ``magnified''. In general, it's not a good idea to check for exact equality when comparing floating point (double) values, but to use some kind of tolerance. Fragments like the one below can be used to see if two values are ``close''. Choosing the correct tolerance is part of the study of numerical analysis , a branch of computer science we'll only briefly explore. 

    if (abs(root*root - num) <= TOLERANCE)
    {
        //... code here
    }

page 151

4.32 Think about these questions.

4.33 Soda machines are complicated. Next time one is being serviced, watch the person doing this fill the soda racks.

4.34 There are lots of comments so that users (or clients) of the class will be able to use the Dice class in programs. Comments are needed to understand what the class does (at least for client programs). The comments are like a manual for how to use the class.

4.35 There is a typo in the Fall 1995 version of the book, the line should read. 

    cout << "# of sides = " << tetra.mySides << endl;
The data field mySides is private and hence not accessible to client (user) programs. The member function NumSides() provides access to the value of the data. The line 
    cout << "# of sides = " << tetra.NumSides() << endl;
will compile successfully.

4.36 To allow the user to enter the number of sides of the dice the following could be used. 

    int sides;
    cout << "enter # of sides : ";
    cin >> sides;

    Dice die(sides);

    // ... continue with program

The number of rolls can be entered as well, a loop is needed for this to work.







 page 156 



 4.37 


long int Factorial(int num)
// precondition: num >= 0
// postcondition returns num!
{
    long int product = 1;
    int count;

    for(count=1; count <= num; count += 1) // invariant: product == (count-1)!
    {          
        product *= count;
    }
    return product;
}






 4.38 


   double total = 0.0;
   double val = 1.0
   while (val < 10000)
   {
      total += val;
      val *= 1.5;
   }



 4.39 


   int sum = 0;
   Dice die(12);
   int k;

   for(k=1; k <= num; k += 2)
   {
      sum += die.Roll();
   }






 page 167 



 4.40 

If the two lines below are the entire function Power, the
function won't work as intended.

    int value = Power(base,expo-1);
    return base * value;


In this case there is no  base case  for the chain of recursive
calls.  A call of Power(3,4) to compute 3^4 will generate a
recursive call Power(3,3).  This generates the chain of calls

    Power(3,2)     Power(3,1)     Power(3,0)     Power(3,-1)  ...


and nothing (except running out of memory) will stop the chain from
being extended each time another call to Power is made.



 4.41 

If the output statements are added, the call Power(25,6)
will generate output as shown below.  These are powers of 25 from
25^1, 25^2, ... , 25^5, 25^6.  On PC's and macs the return type for
the function Power should be long or long int or
the last ``correct'' value below will be 15625, the other values exceed
the maximum value of 16-bit integers.

    25
    625
    15625
    390625
    9765625
    244140625





The call Power(3,9) generates the output below (successive powers
of 3 from 3^1 to 3^9).

    3
    9
    27
    81
    243
    729
    2187
    6561
    19683






 4.42 

The loop iterates exactly expo times.




 4.43 
A ``good'' invariant is shown below.


    result = base^k




The first time the loop guard is evaulated this expression is true
because 1 = base^0 for any value of base.
Because both
result and k are upated each time the loop body is
executed, the relationship continues to hold.  This is true since
k is incremented by 1 and the value of result is
multiplied by base.



When the loop terminates, the value of k is expo so the
truth of the invariant indicates that 

   result = base^expo



which is what should be returned.



 4.44 

The addition of the output statement 
 cout << expo << endl 
 before  the if
statement will generate the output below (one number per line) for the
call Power(2,14)

    14 13 12 11 10 9 8 7 6 5 4 3 2 1 0


The call Power(3,9) will generate the output below, again one
number per line.

    9 8 7 6 5 4 3 2 1 0


Note that the output statement occurs before any recursive calls are
made. 



 4.45 

There is a typo in the Fall 1995 version of this code.  The function
body should be

    if (1 == expo)
    {
        return base;
    }



Reducing the number of multiplications by one isn't an important
savings in terms of efficiency.  Using 24 instead of 25 multiplications
for 2^{25} won't save significant time, nor will reducing the number
even for ``large'' exponents like 1,000.  For increased efficiency,
saving one multiplication isn't (usually) important.  In the next
section a much more efficient method saves many more multiplications.

In general, ``optimizing'' a program with such small savings doesn't
make sense until it can be determined that the savings will accrue large
benefits.  For example, if one billion powers were being calculated, the
savings would be beneficial.