Hunter Liu's Website

9.1. Some Worksheet Solutions

Below, you’ll find partial solutions and explanations for the first five problems on the week 5 Tuesday worksheet! For the “predict the output” problems, you should check your answer by copying the code into your IDE and running it.

I’ve chosen to omit the solutions to the coding problems for now, but I may come back and add them in closer to the midterm. If you’re stuck on one of those four problems, I encourage you to search for help online! There is an art to getting assistance with programming through the internet. Often, our goals with coding are too specific or too sensitive (particularly in research) to carelessly Google, but there are often ways to phrase your issues or problems in a more general sense that others may have run into. For instance, with the pencil lead problem, you may have wondered how to compare a character to a single quotation mark. This specific issue is something Google-able, but the problem itself probably isn’t.

Predict the Output

In each of the following examples, predict the output of the code snippet provided.

 1#include <iostream> 
 2
 3using namespace std; 
 4
 5int main() {
 6    int a = 0; 
 7    int c = 1; 
 8    for(int b = 1; b <= 7; b += 3) {
 9        a += b; 
10        c *= b; 
11    } 
12
13    cout << a << " " << c << endl; 
14    return 0; 
15}

Something to be aware of with this first problem is that the variable b is counting up by 3’s. That is to say, the loop runs through the values b = 1, 4, 7 instead of all of the consecutive numbers between 1 and 7.

 1#include <iostream>
 2
 3using namespace std; 
 4
 5int main() {
 6    int a = 0; 
 7    int b = 837264; 
 8
 9    for(int i = a; i <= b; i++) {
10        a += 1; 
11        b /= 2;
12    }
13
14    cout << a << " " << b << endl; 
15    return 0; 
16}

The numbers are rather unmanageable here, but it gets a bit better if you write it out. An important thing to realise is that the first part of the for loop int i = a; only runs once before the loop begins. Then, it checks i <= b at the end of each iteration of the loop, and it uses the current value of b. So, i will not range over all of the numbers between 0 and 837264; it will range over far fewer.

Something one could realise is that i is the first integer such that \(i > b \cdot 2^{-i}\). This inequality can then be solved through the use of a graphing calculator, though one must be careful with the integer division that occurs on each iteration of the loop!

 1#include <iostream>
 2
 3using namespace std; 
 4
 5int main() {
 6    int a = 180; 
 7    int n = 2; 
 8    while(a > 1) {
 9        if(a % n != 0) {
10            n++; 
11            continue; 
12        }
13
14        int j = n; 
15        while(a % j == 0) {
16            j *= n; 
17        }
18
19        j /= n; 
20        a /= j; 
21        cout << j << endl; 
22
23        if(n > a) {
24            break; 
25        }
26    }
27
28    return 0; 
29}

We discussed this problem in class. The idea is that once n is a divisor of a, the code from lines 14 through 21 identifies the largest power of n that divides a, then prints it out.

In greater detail, we can consider the first iteration of the “outer” while loop, when a = 180 and n = 2. Since 180 is divisible by 2, it skips over the if statement on line 9 and jumps down to line 14, where it sets j = 2. Then, while 180 is divisible by j, it multiplies j by 2. j ranges over the values 2, 4, 8, and since 180 is no longer divisible by 8, it exits the while loop on line 15. 8 is actually not a divisor of 180, as we’ve “overshot” the highest power of 2 that divides 180; line 19 corrects for this, and line 20 removes the factor of 4 from 180. 4 is then printed to the screen.

Try writing out the contents of the variables a, n, j throughout the program!

For the follow-up question, the if statement on line 23 is actually unnecessary. The code essentially processes all of the prime divisors of a in order until they’ve all been divided away. a will eventually equal 1, and that will always coincide with when a becomes less than n.

Spot the Error

In each of the following examples, identify all of the errors in the code provided:

• For syntax errors, explain why the code has improper syntax, then correct the code so that it compiles.
• For other errors, identify which circumstances cause the program’s output to be incorrect. If applicable, provide an example of a user input that would cause such behaviour.

 1#include <iostream>
 2#include <string> 
 3
 4using namespace std; 
 5
 6int main() {
 7    // obtain input from the user 
 8    string input; 
 9    getline(cin, input); 
10
11    // for each character in the string, test if the 
12    // character is a digit (between '0' and '9'). 
13    // if it is, change it to a '*'. 
14    for(int i = 1; i <= input.length(); i++) {
15        char current_char = input.at(i); 
16        if('0' <= current_char && current_char <= '9') {
17            current_char = '*'; 
18        }
19    }
20
21    // print out the modified input 
22    cout << input << endl; 
23    return 0; 
24}

We discussed this problem in class as well. The first issue, of course, is that strings are indexed by 0 while the for loop in this problem starts from 1. In the sample string abc123, the only valid indices are 0, ..., 5. Since the for loop ranges over i = 1, ..., 6, this will crash when i = 6.

The second issue is more subtle. On line 17, we are replacing the contents of current_char with an asterisk, not the original string! Any changes to current_char are not reflected in the variable input.

We therefore need exactly two modifications: one on line 14 to correct the bounds on the for loop, and one on line 17 to make the changes to the string permanent. This is the corrected code:

 1#include <iostream>
 2#include <string> 
 3
 4using namespace std; 
 5
 6int main() {
 7    // obtain input from the user 
 8    string input; 
 9    getline(cin, input); 
10
11    // for each character in the string, test if the 
12    // character is a digit (between '0' and '9'). 
13    // if it is, change it to a '*'. 
14    for(int i = 0; i < input.length(); i++) {
15        char current_char = input.at(i); 
16        if('0' <= current_char && current_char <= '9') {
17            input.at(i) = '*'; 
18        }
19    }
20
21    // print out the modified input 
22    cout << input << endl; 
23    return 0; 
24}

 1#include <iostream> 
 2
 3using namespace std; 
 4
 5int main() {
 6    // get two string inputs from the user 
 7    string first, second; 
 8    cin >> first >> second; 
 9
10    // if the two strings have different lengths, 
11    // they cannot be the same. exit immediately. 
12    if(first.length() != second.length()) {
13        cout << "Different" << endl; 
14        return 0; 
15    }
16
17    // keep track of how many differences there are 
18    int different = 0; 
19
20    // count the number of different characters 
21    for(int i = 0; i < first.length(); i++) { 
22        if(first.at(i) = second.at(i)) {
23            different++; 
24        }
25    }
26
27    // if the # of differences is <= 1, we are good 
28    // otherwise, they are different. 
29    if(different <= 1) {
30        cout << "Close" << endl; 
31    } else {
32        cout << "Different" << endl; 
33    }
34
35    return 0; 
36}

The logic of this code is completely intact. It first checks if the two inputted strings are the same length; if not, we immediately know that they’re not “close”. Assuming they are the same length, we check every character of the string, one index at a time, and count how many times they differ.

first   H   e   l   l   o
second  H   a   l   l   o
index   0   1   2   3   4
            *

In this example, the code will identify exactly one difference at index 1.

However, there are two very subtle mistakes. First and foremost, the code uses string variables, but fails to include the string library. We must add #include <string> on line 2 to correct this. Second, when it compares two characters within the two strings on line 22, it uses = instead of ==. This is a fatal bug that is very difficult to catch, and this is a very common mistake!