This lab consists of two short programs. The key to solving each is to first discover a recursive solution. Once you have that, the implementation should require little effort. You might want to reread "Recursive Design Techniques" in Section 11.3 of the textbook, pp. 667-8.
Provide a solution to Programming Project #1 of chapter 11:
A savings account typically accrues savings using compound interest. If you deposit $1,000 with a 10% interest rate per year, then after one year you have a total of $ 1,100. If you leave this money in the account for another year at 10% interest, then after two years the total will be $ 1,210. After three years, you would have $1,331, and so on. Write a program that inputs the amount of money to deposit, an interest rate per year, and the number of years the money will accrue compound interest. Write a recursive function that calculates the amount of money that will be in the savings account using the input information.
The first step is to define a recursive function that expresses the accrued savings in terms of the number of years and interest. Let f(p, i, y) be the savings derived when the principle, p, has been in the bank for y years at an interest rate of i. So, for example, f(1000, .10, 5) is $1610.51--what you'd get for leaving $1000 in the bank for 5 years at 10% interest compounded annually [HAH! I wish!]. Can you think of a way to express f(p, i, y) in terms of f(p, i, y-1), assuming y > 0?
In the lab document, complete the recursive expression:
f(p,i,y) = .... [a mathematical expression involving f(p,i,y-1)]
Also in the lab document describe the base (the stopping) case. I.e., for what value of the parameters to f do you not need to invoke a recursive call? What should the value of f be in that case?
Once you have that, all you have to do is encode the function. Instead of calling it f, call it calcSavings.
Your driver (where the main() function is), CalcInterest.java, should prompt the user for the principle, interest and years, then print the result of invoking your recursive function with those values, as well as a "checksum"--the value of p times (1+i) raised to the yth power. You can use the Math.pow(a,b) function, which returns the value of a raised to the bth power. (The purpose of a "checksum" is to validate your result. If all goes well, your recursive solution should return the same (or very nearly the same) value as the checksum.)
Example output might be:
Please enter the principle, interest (e.g, .10 = 10%) and years: 1000, .10, 5 The accrued savings after 5 years at 10.0% is $1610.51, the checksum is $1610.51.
As the number of years increases, your output may start to look a bit gross, as you can get many digits after the decimal point (e.g., "$2357.947691000002"). Because the values we are calculating are dollars and cents, we want exactly two digits displayed after the decimal point. To do that, use Java's printf method to display a double:
System.out.printf("%.2f",yourVariableHere);
In the lab, demonstrate your program to the professor or to a TA. If you are taking this course online, provide a transcript of your program running on two different sets of input.
Provide a solution to programming project #4 of chapter 11 [There is a typo in the book's diagram: the value there should be "57", not "59"]:
The game of “ Jump It” consists of a board with n positive integers in a row except for the first column, which always contains zero. These numbers represent the cost to enter each column. Here is a sample game board where n is 6: [0 3 80 6 57 10] The object of the game is to move from the first column to the last column in the lowest total cost. The number in each column represents the cost to enter that column. Always start the game in the first column and have two types of moves. You can either move to the adjacent column or jump over the adjacent column to land two columns over. The cost of a game is the sum of the costs of the visited columns.
In the board shown above, there are several ways to get to the end. Starting in the first column, our cost so far is 0. We could jump to 80, then jump to 57, then move to 10 for a total cost of 80 + 57 + 10 = 147. However, a cheaper path would be to move to 3, jump to 6, then jump to 10, for a total cost of 3 + 6 + 10 = 19.
Write a recursive solution to this problem that computes the cheapest cost of the game and outputs this value for an arbitrarily large game board represented as an array. Your program does not have to output the actual sequence of jumps, only the cheapest cost of this sequence. After making sure that your solution works on small arrays, test your solution on boards of larger and larger values of n to get a feel for how efficient and scalable your solution is.
As usual, the trick to solving this recursively is to consider how you might solve the problem if you had a magic function that could solve any "smaller" problem of the same type. One of the key problems in deriving a recursive solution is figuring out how to define the "size" of a problem. Let's try a brute-force approach, first:
Suppose, such as in the text, you are asked to find the solution to a problem of size 6, i.e., a 6-element array. Suppose you had a function theMinCost(x), (where x is the size of the array) but it only worked for x < 6. In other words, it correctly returns the minimum cost of solving the problem for arrays of 5 and 4 elements, but not for 6. Can you see how you might calculate minCost(6), if you were given the values of theMinCost(5) and theMinCost(4)? Given that, can you generalize a solution for all positive values of x? Can you see how you might calculate minCost(x), for any x>0, in terms of minCost(x-1) and minCost(x-2)?
If you don't see the solution yet, it may be because from the way the problem is phrased above, it is not clear what the x in minCost(x) refers to. This is a common stumbling blocks in deriving recursive solutions--determing to what aspects of the problem the paraemters refer. It may help to think of x as a measure of the distance to the last element of the array. Thus, for a 6-element array, minCost(6) is the minimum cost of getting from the first to the last element of the array, minCost(5) is the minimum cost of getting from the secondto the last element, etc. More generally, let arr be the name of the array, and let arr have n elements. Then minCost(x) is the minimum path cost from arr[n-x] to arr[n-1].
In the lab document write the recursive expression: minCost(x) = ....
In the lab document write the base case expression(s): minCost(1) = ? minCost(0) = ?
Now, code up the solution. The driver should be called JumpIt. It should read the definition of the board from the file jumpIt.txt. The file will contain a series of integers (not more than 50), separated by whitespace. You should create an instance variable array, board[], setting board[0] to 0, and the remaining elements to the contents of jumpIt.txt. (Here is an example jumpIt.txt.) You'll want to set an instance variable to the number of integers in board. (This will be at least 1, because element 0 is always 0.) Your driver should then print the contents of the array and the minimum cost of traversing the board via the JumpIt rules. Example:
The board is: 0 3 80 6 57 10 The minimum JumpIt cost is 19.
In deciding what parameters should be passed to your recursive function, consider that--among other things--they somehow need to describe or delineate the "size" of the problem it is solving.
Extra Credit:
For 30% extra credit, also have the driver print the actual sequence of moves that obtains the minimum cost. You can do this by creating another recursive function, moveString, based on minCost. This should return a String, rather than an integer. Again, thinking recursively, consider how your moveString(x) might calculate the String it should return, assuming that you already have the values of moveString(x-1) and/or moveString(x-2) (as well as minCost(x-1) and minCost(x-2)).
The board is: 0 3 80 6 57 10 Cheapest path cost is 19 Cheapest path is: 0, 3, 6, 10
What to Submit:
Please submit your lab document, PDFs of your code, and a zip file containing your source code.