Homework #3
(10 points)

Fibonacci and Etch-a-Sketch

Due Date

Reading: Chapter 5.

1. 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.

2. 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:
   • Draw a circle
   • Draw a blue square
   • Draw a green line up
   • Make bigger
   • Make smaller
   • Move left
   • Move to 2 3
   • Quit
   Thus, we would like the following verbs to function:
   1. 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 black.
      • 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 location.
      • 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.
   2. 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!
   3. Move the pen (without drawing anything)...
      • ...in a given direction: left, right, up or down by a "unit" (defined below).
      • ...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.
   4. 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 functions:

   • string IthWord(int i, string str)
   • void DrawCircle(double size, double x-loc, double y-loc)
   • void DrawSquare(double size, double x-loc, double y-loc)
   • void DrawFunkyShape(double size, double x-loc, double y-loc)
   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).

   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, etc.

   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:

   • 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 function sufficiently.
   • 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 compare strings. Note that you cannot use the switch command for this, since you are comparing strings.
   • 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 scratch.
   • 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.
   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.

Deliverables

Grading

• The Fibonacci sequence program is worth 2 points.
  1. (1 point) Does the program work and fulfill the requirement of the assignment?
  2. (0.5 points) Elegance and efficiency of your solution.
  3. (0.5 points) Formatting, commenting, and decomposition.
• Your version of the Etch-a-Sketch program is worth 8 points.
  1. (3 points) Does the program work and fulfill the requirement of the assignment?
  2. (2 points) Elegance and efficiency of your solution.
  3. (3 points) Formatting, commenting, and decomposition.