Skip to main content

How To Think Like a Computer Scientist C++ Edition The Pretext Interactive Version

Barbara Ericson, Allen B. Downey, Jason L. Wright (Editor)

Exercises 13.14 Coding Practice

1.

Create the enumerated type Planet, which maps the planets in our solar system to integers starting at 1. Make sure to list the planets out in order! (Sadly, Pluto is not a planet :( )
🔗
Solution.
Below is one way to implement the program. The planets in our solar system are Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, and Neptune.
🔗
#include <iostream>
using namespace std;

enum Planet { MERCURY = 1, VENUS, EARTH, MARS, JUPITER, SATURN, URANUS, NEPTUNE };
🔗
🔗

2.

How long is a year on other planets? Let’s write a program that prints out the number of days in a year on each planet using a switch statement. These values are, in planetary order, 88 days, 225 days, 365 days, 687 days, 4333 days, 10759 days, 30687 days, and 60190 days. Print out this information in the following format: Planet planet has numDays number of days in a year! Check the hint below for help with the construction of the code.
🔗
Hint.

Activity 13.14.1.

How long is a year on other planets? Let’s write a program that prints out the number of days in a year on each planet using a switch statement. These values are, in planetary order, 88 days, 225 days, 365 days, 687 days, 4333 days, 10759 days, 30687 days, and 60190 days. Print out this information in the following format: Planet planet has numDays number of days in a year! Use the lines to construct the code, then go back to complete the Activecode.
🔗
🔗
🔗
🔗

3.

A Bingo board has 25 Spaces in a matrix-like grid. A Space has a number value randomly selected from 1 to 75 and can either be filled or not. Write the struct definitions for Space and BingoBoard.
🔗
Solution.
Below is one way to implement the program. We declare the Space and BingoBoard struct and create the instance variables in order. Make sure to set is_filled to false!
🔗
#include <iostream>
#include <vector>
using namespace std;

struct Space {
    int value;
    bool is_filled;
};

struct BingoBoard {
    vector<vector<Space> > board;
};
🔗
🔗

4.

Now let’s generate a BingoBoard! We want to fill the 25 Spaces on the BingoBoard with random values from 1 to 75 without repititon. To do this, we’ll make a vector of numbers from 1 to 75 and shuffle it using the same method as shown in this chapter. Then we will select the first 25 values for the 25 spaces on the BingoBoard. We will do this entire process in multiple steps. First, write the function randomInt, which generates a random value between low and high, inclusive. Be sure to include the relevant libraries! Check the hint below for help with the construction of the code.
🔗
Hint.

Activity 13.14.2.

Now let’s generate a BingoBoard! We want to fill the 25 Spaces on the BingoBoard with random values from 1 to 75 without repititon. To do this, we’ll make a vector of numbers from 1 to 75 and shuffle it using the same method as shown in this chapter. Then we will select the first 25 values for the 25 spaces on the BingoBoard. We will do this entire process in multiple steps. First, write the function randomInt, which generates a random value between low and high, inclusive. Be sure to include the relevant libraries! Use the lines to construct the code, then go back to complete the Activecode.
🔗
🔗
🔗
🔗

5.

Now we need a way to swap the values at two indices in a vector. Write the function swapValues, which takes a vector of ints and two indices as parameters.
🔗
Solution.
Below is one way to implement the program. We store the value at index1 in a temp variable, replace the value at index1 with the value at index2, and then finally replace the value at index2 with the value of temp. Make sure to pass vec by reference!
🔗
#include <iostream>
#include <vector>
using namespace std;

void swapValues (vector<int> &vec, int index1, int index2) {
    int temp = vec[index1];
    vec[index1] = vec[index2];
    vec[index2] = temp;
}
🔗
🔗

6.

Now that we have the functions randomInt and swapValues, we can write the function generateRandVec. generateRandVec creates a vector with values from 1 to 75, shuffles it using randomInt and swapValues, and returns the shuffled vector. Check the hint below for help with the construction of the code.
🔗
Hint.

Activity 13.14.3.

Now that we have the functions randomInt and swapValues, we can write the function generateRandVec. generateRandVec creates a vector with values from 1 to 75, shuffles it using randomInt and swapValues, and returns the shuffled vector. Use the lines to construct the code, then go back to complete the Activecode.
🔗
🔗
🔗
🔗

7.

We can now fill our BingoBoard with values! Write the BingoBoard member function makeBoard. Use the generateRandVec function and select the first 25 values to fill up the board. Make sure to create a free space in the middle of the board! Set the value of the free space to 0 and is_filled to true. All other spaces should have is_filled set to false.
🔗
Solution.
Below is one way to implement the program. First we need to initialize the board to the correct dimensions. Then, we use generateRandVec to create a vector of random values from 1 to 75. Afterwards, we set the values of the 25 Spaces to the first 25 values in the random vector. Lastly, we set the middle Space to 0 and set its is_filled to true.
🔗
#include <iostream>
#include <vector>
#include <cstdlib>
#include <numeric>
using namespace std;

struct Space {
    int value;
    bool is_filled;
};

struct BingoBoard {
    vector<vector<Space> > board;
    void makeBoard ();
};

int randomInt (int low, int high);
void swapValues (vector<int> &vec, int index1, int index2);
vector<int> generateRandVec ();

void BingoBoard::makeBoard() {
    // Initialize board
    Space s = {0, false};
    vector<Space> cols(5, s);
    for (size_t i = 0; i < 5; ++i) {
        board.push_back(cols);
    }

    // Fill board with random values
    vector<int> vec = generateRandVec();
    int count = 0;
    for (size_t row = 0; row < board.size(); ++row) {
        for (size_t col = 0; col < board[row].size(); ++col) {
        board[row][col].value = vec[count];
        ++count;
        }
    }

    // Create free space
    board[2][2].value = 0;
    board[2][2].is_filled = true;
}
🔗
🔗

8.

Let’s print out our BingoBoard! Write the BingoBoard member function printBoard. Insert tabs between each value in each row to make the board print out neater. Check the hint below for help with the construction of the code.
🔗
Hint.

Activity 13.14.4.

Let’s print out our BingoBoard! Write the BingoBoard member function printBoard. Insert tabs between each value in each row to make the board print out neater. Use the lines to construct the code, then go back to complete the Activecode.
🔗
🔗
🔗
🔗

9.

Bubble sort is a method of sorting that involves repeatedly swapping the adjacent elements if they are in the wrong order. For example, let’s say we have the vector with elements {3, 2, 4, 1}. On the first pass, we take a look at the first two elements, 3 and 2. Since 3 is bigger than 2, we swap them. Thus, the vector now looks like {2, 3, 4, 1}. Next, we look at the next two elements, 3 and 4. Since 3 is less than 4, we don’t swap. Lastly, we look at the last two elements, 4 and 1. Since 4 is greater than 1, we swap the. Thus the vector now looks like {2, 3, 1, 4}. Now we restart and look at the first two elements again and the process continues. This way, the biggest elements “bubble” to the back. Write the function bubbleSort, which takes a vector as a parameter and sorts it. Feel free to use the provided swapValues function.
🔗
Solution.
Below is one way to implement the program. We must loop through all elements in the vector. Since we know the last i elements are already in place, our inner loop only goes up to vec.size() - 1 - i. If the next element is greater than the current element, we swap the two elements.
🔗
#include <iostream>
#include <vector>
using namespace std;

void swapValues(vector<int> &vec, int index1, int index2) {
    int temp = vec[index1];
    vec[index1] = vec[index2];
    vec[index2] = temp;
}

void bubbleSort(vector<int> &vec) {
    for (size_t i = 0; i < vec.size() - 1; ++i) {
        for (size_t j = 0; j < vec.size() - 1 - i; ++j) {
            if (vec[j] > vec[j + 1]) {
                swapValues(vec, j, j + 1);
            }
        }
    }
}

int main() {
    vector<int> vec = { 5, 1, 4, 2, 8 };
    bubbleSort (vec);
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec[i] << " ";
    }
}
🔗
🔗

10.

You may have noticed that in some cases, our version of bubbleSort does an unnecessary amount of work. For example, if our vector was {1, 2, 3, 5, 4}, bubbleSort would swap 4 and 5, but then keep going even though our vector is already in order! We can save some work by including a bool called is_changed. If we swap values during a pass, we set is_changed to true. If nothing has been swapped, then is_changed stays false, and we know to break out of the loop since our vector is already sorted. Write the function fastBubbleSort, which is bubbleSort with this modification. Check the hint below for help with the construction of the code.
🔗
Hint.

Activity 13.14.5.

You may have noticed that in some cases, our version of bubbleSort does an unnecessary amount of work. For example, if our vector was {1, 2, 3, 5, 4}, bubbleSort would swap 4 and 5, but then keep going even though our vector is already in order! We can save some work by including a bool called is_changed. If we swap values during a pass, we set is_changed to true. If nothing has been swapped, then is_changed stays false, and we know to break out of the loop since our vector is already sorted. Write the function fastBubbleSort, which is bubbleSort with this modification. Use the lines to construct the code, then go back to complete the Activecode.
🔗
🔗
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext