CSCI 221 Fall 2020

Homework 02:

procedures and functions and recursion oh my

Due 9/15/2020 by 9am

• from Git classroom link
• as ZIP file

Commit your four C++ files to this remote Git repo like we learned in lab.

PLEASE NOTE: I’ve made one major change to my ReedCS2-F20 Git set-up. Namely, the initial “branch” of my repos will be named main rather than master. So that means that, those of you who work from the initial branch (most of you do), you’ll want to instead type

git push origin main

when you want the remote repo to be updated with your locally committed changes.

And then also when you look at the repo online (on Git) above the file list you’ll see a main branch listed, not a master branch. I think this is a throughtful change on GitHub’s part, and it will become the new default for all of Git sometime within the next year, anytime a new repo is created.

Instructions

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.

Please also work to use readable coding “style” and formatting, for now using your best judgement. We’ll talk more about this practice throughout the semester, and I will work to publish a set of guidelines that are good to follow. We’ll also talk soon about strategies for debugging and testing your code. We will suggest schemes for generating test inputs, and ways of scripting your tests and capturing your tests’ output using Linux.

Exercises should only use basic integer operations, std::string operations, the std::cin and std::cout operations for input/output. You shouldn’t need to rely on anything that I haven’t showcased in class.

A final note: 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 some cases, we may be willing to give partial credit if you were diligent/good about identifying the problem.

The first exercise shows how one might carefully comment code components for functions and procedures. You should work on commenting the code you write for homework and other programs in this class in a similar way. You will be evaluated on the clarity of your coding and how carefully you communicate your work, including within the comments. The comments can be brief—don’t overdo it—but defnitely make some effort to document and package your work.

Exercise 1: six guesses, decomposed

In class I showed a slide for a C++ program that solves the “guess six” exercise from Homework 01 Exercise 1, and uses several functions and procedures to do it. It didn’t detail out the bodies of those functions/procedures though. Included in this repo is a copy of that source code. Finish the work of writing those code components.

The comments in the code hopefully will give you a sense of what is required for each. Here also is a sample transcript of my solution’s execution:

hw02 % ./guess6
I've chosen a number from 1 to 100. Try to guess what it is.
Enter a number: 65
That's too low. Try again.
What's your next guess? 78
That's too high. Try again.
What's your next guess? 71
That's too high. Try again.
What's your next guess? 68
That's too high. Try again.
What's your next guess? 66
Well done! 66 was the number I chose.
hw02 %

And here is another:

hw02 % ./guess6
I've chosen a number from 1 to 100. Try to guess what it is.
Enter a number: 50
That's too high. Try again.
What's your next guess? 25
That's too high. Try again.
What's your next guess? 12
That's too high. Try again.
What's your next guess? 8
That's too low. Try again.
What's your next guess? 9
That's too low. Try again.
This is your final guess. What's my number? 10
That's too low. Try again.
Sorry, you are out of guesses...
11 was the number I chose.
hw02 %

Notice the This is your final guess. prompt in the last few lines. Your code should do the same for the 6th guess.

Exercise 2: primes

A prime number is an integer larger than one that has exactly two positive integer divisors. Write a C++ program primes.cc that requests an integer value, and then lists all the prime numbers in order up to (and possibly including) that number.

You should work to decompose that program into several components. You should write a function isPrime that returns whether or not a number is prime. That function should try all divisors up to the integer square root of the number being checked. This means that you should write a helper function that calculates the “integer square root approximation” of a non-negative integer, defined as follows:

“The integer square root of an integer n is the largest integer i for which i*i <= n.

The function should be named intSqrt and should work for any non-negative integer. It can assume that it is never given a negative integer.

You should also write a helper function primesString that returns a string of the primes up to an integer value. The prime string should be the sequence of primes in order, starting with { and ending with }, and separated by commas. For example

"{2, 3, 5, 7, 11}"

would be the returned result of this code if given an 11 or 12, say. It should return "{2}" when given 2, and "{}" for anything less than 2.

Your main should ask for the integer value and output the string.

Exercise 3: the powers of two one-sum decomposition

Consider the following expressions made up of 1s, parentheses, and +.

1
(1+1)
((1+1)+(1+1))
(((1+1)+(1+1))+((1+1)+(1+1)))

Note that these sums are each a certain kind of decomposition of a power of 2. The first is just 2**0, the second sums to 2**1 or 2, the third sums to 2**2 or 4, and the fourth sums to 2**3 or 8. Note also that a sum is just the parenthesized sum of the prior expression, repeated.

Write a program oneSum.cc that, when given a positive integer n it outputs the first n such decompositions. I want you to write the code as follows:

• Write a recursive function oneSumOf that, when given an integer, returns the sum decomposition string for that integer. It can assume that the number it is given is positive.

• Write a procedure listOneSums that outputs all the decompositions of integers up to the given one. So it would output what we see above if the integer entered was 8 or 9, say.

Bonus exercise:
The decompositions above only work for powers of two. You could imagine, instead, decompositions for numbers that are not powers two. For example, the decompion of 6 could be something like:

   (((1+1)+1)+((1+1)+1))

And maybe it would be

   ((((1+1)+1)+((1+1)+1))+1)+((((1+1)+1)+((1+1)+1))+1)

for 14. I’ll let you devise the pattern, it need not be the same as what I have above for 6 and 14, but it should be some reasonable generalization of the strings described above for powers of two.

Write a program that instead enumerates all the decompositions from 1 up to n. Have your listOneSums list all these up to the given integer, then, so not just the ones that line up with powers of two.