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.