Hunter Liu's Website

10. Week 5 Thursday: More Practise with Loops

≪ 9. Week 5 Tuesday: Practise with Loops and Strings | Table of Contents | 11. Week 6 Tuesday: Functions ≫

Happy Halloween! Unless you’re reading this when it’s not Halloween.

Today, we’re going to take a step back from new content and focus on practise problems. Our goal is to consolidate and reinforce the skills that we’ve been learning throughout the first month of the course.

There are three broad types of problems:

  1. Predict the output
    You are to read through a program or chunk of code and figure out what it does, typically by identifying the output it will produce.
  2. Spot the error
    Like the first type of problem, you’re given a program or chunk of code, but there may be something wrong with it. You are to identify the error and fix it so that it works as intended.
  3. Do it yourself
    You will be given a task or scenario, and you are to design and implement a program that performs said task.

These are loosely arranged in order of increasing difficulty. You need to be able to predict code output if you want to catch errors, and you need to be able to catch your own code’s errors and oversights if you’re going to write correct and robust code.

The following collection of problems are split into the above three categories, but the problems are not arranged in any particular order.

Predict the Output

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

Problem 1. 

 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}

Problem 2. 

 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}

Problem 3. 

 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}
Follow-up Question
Now that you (presumably) know what the program does, is the if statement on line 23 necessary? In other words, if lines 23-25 were deleted, would the behaviour of the program change?

Spot the Error

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

Problem 4. Censorship

This program intends to obtain a line of input from the user, then convert all digits into asterisks. For instance, if the input was abc123, the intended output is abc***.

 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}

Problem 5. Off by one

The following input accepts two string inputs from the user, each without any spaces. Then, it determines if the two string inputs differ by at most one character. For instance, “Hello” and “Hallo” are close, and “PIC10A” and “pic10a” are not. For this problem, “Hello” and “ello” are considered different.

 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}
Challenge
The variable different computes a version of the Hamming distance between two strings. Can you modify the code so that it works for strings of different lengths as well? For instance, “Hello”, “ello”, and “Hllo” are all a “distance” of 1 character apart.

Do it Yourself

Problem 6. Pencil Lead

You have a magical mechanical pencil that’s loaded with an infinitely long piece of pencil lead. Since you enjoy bullet journalling, you know exactly how much lead you use for each letter, number, and symbol you write:

  • Lowercase letters and numbers take 0.02 cm of lead.
  • Uppercase letters take 0.05 cm of lead.
  • Periods, commas, and quotation marks (both single and double) take 0.01 cm of lead.
  • Any other symbol takes 0.04 cm of lead.

Write a program that accepts a line of input from the user. Then, print out how much lead gets consumed when copying this line of input into your journal.

Sample Run: 
INPUT   Hello, World!
OUTPUT  0.31 cm

In the above example, there were 2 uppercase letters (0.1 cm), 8 lowercase letters (0.16 cm), a comma (0.01 cm), and an exclamation mark (0.04 cm).

Problem 7. A Spreading Illness

An infectious disease has broken out at UCLA, and it is threatening to infect all 46,430 students!

Each student is either Susceptible, Infected, or Recovered. Since the disease is very mild and completely non-lethal, infected students are only contagious for one day, after which they recover. However, since UCLA is so densely populated, every infected student will pass the pathogen on to five other students, who will become infected the following day. Recovered students are immune and cannot be reinfected.

On day one of the outbreak, only one student is infected. On day two, 5 students are infected, and one student is recovered. On day 3, 25 students are infected, and six students have recovered.

How long will it take for all 46,430 students to become immune?

Remark
This can, in fact, be solved without using a loop! What you will have implemented is a profoundly rudimentary discretised version of the SIR model of infectious disease spread. Nowadays, policymakers and epidaemiologists use computer simulations to predict the spread of infectious diseases. By tuning various parameters and reviewing how this impacts the population, they can determine appropriate courses of action.

Problem 8. Jack's Magic Beans

Jack has a magic bean, which was passed down through his family for generations. However, he has come across a time of great hardship, and he decides to plant the magic bean.

These beans take two days to mature. On the third day, they produce one magic bean every day, which can then be planted to grow even more beans.

Suppose Jack plants his magic bean at the start of day 1. On day 2, he will just have the one magic bean plant. On day 3, the magic bean plant matures and produces a new magic bean, which Jack plants immediately; he will thus have 2 bean plants at the end of day 3.

Write a program that asks the user for an integer \(n\), then determines how many bean plants Jack has at the end of day \(n\).

Challenge
Your solution will most likely involve loops. Is it possible to write a solution that doesn’t use loops at all?

Challenge Problem 9. Spirals

Write a program that asks the user for a positive integer \(n\), then prints out an \(n\times n\) spiral to the screen.

Sample run: 
INPUT   5
OUTPUT  #####
OUTPUT      #
OUTPUT  ### #
OUTPUT  #   #
OUTPUT  #####

INPUT   10
OUTPUT  ##########
OUTPUT           #
OUTPUT  ######## #
OUTPUT  #      # #
OUTPUT  # #### # #
OUTPUT  # #  # # #
OUTPUT  # #    # #
OUTPUT  # ###### #
OUTPUT  #        #
OUTPUT  ##########

Your output does not have to match the above sample perfectly. As long as you produce a spiral that resembles the above, that’s good enough for me. I don’t think it’s important that you precisely match the orientation, style, etc. of the above.