Homework 03: structs and arrays

Due Thursday, September 24th, by 4pm

This is the initial repository for the third homework assignment for the Fall 2020 offering of Reed’s CSCI 221.

You should create a C++ source file (with suffix .cc) for each of the exercises below. Follow each specification carefully, test your code with several inputs to see whether your code works, and submit your repo using the add/commit/push Git commands.

Please work to mimic the coding style guidelines and formatting I’ve suggested so far. Include comments that describe the code, when appropriate. Include some comments at the top of your source code, including your name and other brief info describing the program. There should also be a brief comment that precedes each struct, function, and procedure definition you write. You also should only be using things I’ve described in class, or in my notes and assignments. The goal of these exercises is to give you puzzles based on what we’ve covered, not to see what you know about all of C++.

This repo has two .md files describing each of the above in detail.

You should work to complete each of these exercises so that they compile and run correctly. Should you face problems in solving an exercise, you can still submit broken code. In your top comment in that file PLEASE let us know in what way the code is broken (why it doesn’t compile, or what tests failed, etc.). In many cases, we are willing to give partial credit if you identify problems in the code.

Exercise 1: prime number sieve

Let’s look at prime numbers and divisors one more time. Here, I ask you to use an array to determine all the prime numbers less than a number that the user enters. We’ll use an array of that size to do this work, and we’ll rely on an array-based method called the prime number sieve of Eratosthenes.

Here’s the sieve strategy: build an array isPrime of booleans where, once we’ve done our work, isPrime[i] will be true if i is a prime number. We initialize this array with entries isPrime[0] and isPrime[1] set to false, the rest set to true. Our job is to “mark” all the other numbers that are not prime. We do this by setting their isPrime entry to false.

The way we do this is by walking through the array, from 2, upward. For each prime p we discover, we mark the entries at 2*p, 3*p, 4*p, 5*p, and so on because those numbers are not prime. They are each divisible by p. Once we stop marking all multiples of p we go back in isPrime and scan entries p+1, p+2, and so forth, looking for the next prime p'; that is guaranteed to be the next entry with isPrime set to true. Having found that, we mark its multiples 2*p', 3*p', 4*p', 5*p', and so forth,

Your program sieve.cc should ask for a number and then output in order the prime numbers less than that number. And it should use this sieve algorithm.

Exercise 2: a turtle

The language LOGO introduced beginners to programming by having them write code that moved a “turtle” to roam on a two-dimensional world. Here, we develop a program turtle.cc that controls a turtle object living on an integer grid. We represent a turtle with a struct.

Define a struct type named turtle that holds four pieces of information:

  • its name, as a string
  • an integer representing its x-coordinate on the grid
  • an integer representing its y-corrdinate on the grid
  • a char representing the direction it’s facing which will be one of N, S, E, or W.

When the turtle is facing east it’s looking in the positive x direction. When facing north it’s looking in the positive y direction.

Write a main program that asks the user for the turtle’s name, then puts the turtle at (0,0), facing east. The program should then loop accepting four commands: forward, left, right, and quit. The last command stops the loop and exits the program. The other three should call the appropriate one of these three functions, ones that you should also write:

  • turtle moveForward(turtle t): move the turtle one unit forward
  • turtle turnRight(turtle t): turn the turtle clockwise 90 degrees
  • turtle turnLeft(turtle t): turn the turtle counter-clockwise 90 degrees

These each should take a turtle struct and return a modified turtle struct. This means that your code that uses these functions will look something like:

t = moveForward(t);

to do the work, modifying the struct of turtle variable t.

Finally, before each command is entered, the current state of the turtle should be reported. Write a function

std::string toString(turtle t) { ... }

that gives back a string reporting the turtle’s state, something like

"Rory is located at (-1,4) facing east."

Your main should output this string to std::cout before receiving each command.

Exercise 3: merging

Create a new program merge.cc that asks for two sequence sizes and builds two C++ int arrays, say, named seq1 and seq2. It should ask the user for the values of those two integer sequences. It should expect the values of each sequence to be increasing.

Enter the first sequence size: 4
Enter its values below. They must be increase.
2
3
5
9
Okay. Now enter the second sequence size: 5
Enter its values below. They must also increase.
1
2
5
6
10

Note that you should be allocating the arrays on the heap using new. That means that seq1 and seq2 should be variables of type int*.

Have the program then output:

Thanks. Those sorted sequences are:
[2,3,5,9]
[1,2,5,6,10]

Now write a function merge that has the following type signature:

int *merge(int* A, int n, int* B, int m) { ... }

It should return a pointer to the start of a C++ array, newly allocated on the heap, one that contains the combination of the values in A and in B, and in sorted order. Your main should call the merge function, passing it the pointers seq1 and seq2 and the two sizes. The call returns a pointer, which you can assign to the variable seq3, That should point to the new array of merged values. Report the result of the merge as follows:

Merging those sequences. The result is 
[1,2,2,3,5,5,6,9,10]
Bye!

Your merge procedure can loop by placing items, one at a time, into the third array by grabbing the smallest from the other two arrays.

You should also write a helper function output that does the work of outputting an integer sequence stored in a C++ array. It should be called three times in main, one for each of the sequences created. You’ll call output once for seq1, once for seq2, and then at the end for seq3.

When main is done, before the return 0; line, it should deallocate those three arrays from the heap using delete [].

Exercise 4: large numbers

Develop a program bignat.cc that works as described below. It will allow us to compute with integers of arbitrary size, rather than with the limited int type

Create a new struct type for holding a sequence of integer digits. Call it number. It should have two fields: an int* field named digits and also an int field named numDigits.

Now write a C++ procedure that has the signature:

number makeNumber(std::string value) { ... }

It works by assuming that the string value contains a bunch of decimal digits for a valid non-negative integer, like "12345" or "1213" or "10" or "9" or "0", or maybe even "76876876218700032230". It should examine the contents of that string, character by character, and place each digit, as an int, into the number’s digits.

To do this, you’ll need two operations on strings. The expression

value.length()

gives back the number of characters in that string’s sequence. And the expression

value[i]

will get the i-th character in the string. When you examine the string with value[i], C++ gives a value of type char. This type essentially is a one-byte integer type, and characters are coded as integers from 0 to 127. Each of these is the code for some character, called its “ASCII code” after an old standard. For example, upper case 'A' is character 65, lower case 'a' is 97, the space character ' ' is character 32, the “new line” character '\n' is 13.

These codes are all listed here at http://www.asciitable.com/. There you will see that the digit characters ‘0’, ‘1’, ‘2’, up to ‘9’ happen to have the codes 48, 49, 50, up to 57. That means that you’ll want to do something like

int digit = value[i] - 48;

to “convert” each character in the std::string value parameter to an integer digit value

The makeNumber function should allocate heap space for those digits in a number struct’s digits array. When makeNumber returns, it should have placed the ones digit of the string in digits[0], the tens digit in digits[1], the hundreds digit in digits[2], and so forth. And then numDigits should have the length of that number’s decimal representation. It returns that struct with that numDigits and that pointer to digits.

Now write a C++ function that has the signature:

number addNumbers(number N1, number N2) { ... }

It should give back a number struct, one whose digits were also allocated on the heap. So you’d have, within this function’s code, lines like

number N;
N.numDigits = some appropriate size;
N.digits = new int[N.digits];

and then the last line should be

return N;

write its code so that it performs a proper place-wise “long addition” of the two numbers, digit by digit, with carrying, storing the resulting digits into struct N.

Note: It’s okay if you allocate a digits array to be larger than ultimately needed, just so numDigits is set to the appropriate number of digits, with no leading 0s.

Now devise a main that tests out these new functions. At a minimum, it should ask the user for two strings, build two number structs using makeNumber, and then build a third using addNumbers. Then report the result.

You’d should write and use a function

std::string toString(number N) { ... }

that allows you to output your results to cout.

Finally, before main ends, it should deallocate the digits of those three number structs.