The Fibonacci Sequence (2 points)
One day in the 13th century, Leonardo Fibonacci decided to challenge the
brains of 1007 students. "I will destroy my arch-nemesis Painless
Computing Penelope once and for all!" he cackled. This is a true story,
and he's famous for this. He continued, "This recursive programming
problem will make your mind melt and your fingers tremble!"
In the Fibonacci sequence of integers, the first two terms are 0 and 1 (the
base case), and every additional term is the sum of the previous two terms
(the recursive case). Therefore, it looks like this:
0, 1, 1, 2, 3, 5, 8...
You are to write a recursive functions, fib, that takes one integer
parameter, n, and returns the n-th Fibonacci number. For
example, fib(0) should return 0, and fib(4) should return 3.
That's not too bad, says Penelope. She says the function to do this is
really quite short, and not too terrible to write. Just remember that in
the general case, the n-th Fibonacci number can be found by simply
adding together the (n-1)-th and the (n-2)-th Fibonacci
numbers, which are each found with a recursive call. Therefore, your
function should have two recursive calls in it. It must not use
the "for" or "while" statements -- no explicit loops.
"Ha ha ha ha ha ha!" retorts Leonardo. Prove him wrong by writing a loop
that repeatedly calls your function in order to output the first 12 terms
of the Fibonacci sequence.
High Tech Etch-a-Sketch(TM) (8 points)
We would like you to design a high-tech Etch-a-Sketch! Instead of
drawing pictures using a couple of silly knobs, we would like to
draw pictures using commands that you type in. Each command
starts with an action verb.
For example, we would like
to say things like:
Thus, we would like the following verbs to function:
- Draw a circle
- Draw a blue square
- Draw a green line up
- Make bigger
- Make smaller
- Move left
- Move to 2 3
- Draw a "unit-sized" (defined below) figure.
- We should be able to specify a color including red, blue, green,
and black. If no color is specified, you should draw the shape the
same color as the previous shape. Initially, the color should be
- We should have the option of drawing a square, circle, line, or one other shape of
your choice. The shapes should be centered on the current pen
- In the case of lines, we should be able to specify a direction
including up, down, left, and right. Note that drawing a line
has the effect of moving the pen, but drawing other shapes does not.
- Make the "unit" (defined below) smaller or large by a factor
of two. This command should not draw anything, but its effect
will be noticed the next time something is drawn!
- Move the pen (without drawing anything)...
- ...in a given direction: left, right, up or down by a "unit"
- ...to a specific location indicated by two single digit integers
in the format listed above. The first integer indicates the
x-coordinate of the point and the second integer indicates the
y-coordinate. Please check to make sure that the pen remains within the
window -- if not, do not move it.
- Quit the program: The user has finished drawing the
picture and would like to leave the program.
User errors: If the user types a command that does not
start with one of these verbs or does not provide the right sequence
of words after the verb, an error message should be printed informing
the user this was an illegal entry.
Unit of distance:
Initially, for your program the unit should be one inch. Thus, if you
give the command "Draw a red square" to the program, a one-inch red
square will appear on the graphics window at the location of the pen.
You can then modify the size of what you draw (and how far you move
the pen) using the "Make" command. "Make smaller" should halve the
size of the unit while "Make larger" should double it. Doing the
latter immediately after the former would leave the size unchanged.
Design with decomposition in mind.
In order to make your programming task easier, you must
write functions with the following prototypes, as well as a few other
IthWord returns word i from a
given string. Note that this function will probably also be useful for
a future homework assignment. Also note: although you may be aware
that strings are actually represented as arrays, at this stage we would
like to work with them more abstractly. Therefore, use the
functions, IthChar (p. 321) and SubString (p. 323).
- string IthWord(int i, string str)
- void DrawCircle(double size, double x-loc, double
- void DrawSquare(double size, double x-loc, double y-loc)
- void DrawFunkyShape(double size, double x-loc, double y-loc)
DrawCircle may not use DrawArc!
If you write these functions first and then test them
out to make sure that each works correctly, you will have a much easier
time assembling your program.
Make a separate function to handle each verb. For example, there must be
a Draw function, separate from DrawSquare, DrawCircle,
Note: There are several other functions that
we are expecting, but we will let you figure those out on your own!
To make it easier for you, you can make the following assumptions:
- The verb is always first.
- If the user does not follow the exact format, you should generate
an error message.
- The commands never consist of more than five words.
A couple of caveats and some advice:
As always, any embellishments or extensions will be greeted by with
great joy by the TAs, as well as potential extra credit. For example,
you might want to generate error messages in case the user wants to
draw something outside the graphics window.
- Start this assignment early!
- Most of your functions should not contain more than 8-10 commands
(not including variable declarations)! If a function contains many more
lines than this, you
have not decomposed the
- Modularity and reuse: If the same (or very similar) fragment of
code appears in multiple locations in your program, that is a strong
indication that you should think about making a function out of that
piece of code.
There are several places where you want to "branch" to one of
a few possible options,
e.g., when you branch according to the verb, when you pay attention
to the color (careful; the user types it in lowercase, but you
have to give SetPenColor(color) a string with the
color capitalized), and when you branch according to which
shape to draw. Other places, too. To do this,
you will want to use cascading if statements (page 115).
You will also want to use StringCompare (page 324) to
Note that you cannot
use the switch command for this, since you are comparing
- You'll probably want to use a function from Roberts' string
library to convert from strings to integers to handle "Move to".
- Talk among yourselves: You are encouraged to discuss the
structure and decomposition of the program. However,
writing the code together is
strictly prohibited; you must build up your own program from
- Since this is your first exercise with functions, we are not
placing a strong emphasis on decomposition and modularity with respect
to the grade for this homework. However, coming up
with reusable modules is a vital skill for programmers and as the
course goes on, we will be putting more and more value on these
skills. Make sure that you have sufficient practice with these skill
NOW so that you
will be proficient at them when a major portion of the grade will
depend on them.